論文の概要: Order-Optimal Projection-Free Algorithm for Adversarially Constrained Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2502.16744v1
• Date: Sun, 23 Feb 2025 23:18:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:56:05.749738
• Title: Order-Optimal Projection-Free Algorithm for Adversarially Constrained Online Convex Optimization
• Title（参考訳）: 制約付きオンライン凸最適化のための順序最適投影自由アルゴリズム
• Authors: Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal,
• Abstract要約: 制約付きオンライン凸最適化(COCO)のための投影型アルゴリズムは、高次元設定においてスケーラビリティの課題に直面している。 本稿では,プロジェクションの必要性を排除しつつ,最先端の性能保証を実現するCOCOのプロジェクションフリーアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 29.705337940879705
• License:
• Abstract: Projection-based algorithms for constrained Online Convex Optimization (COCO) face scalability challenges in high-dimensional settings due to the computational complexity of projecting iterates onto constraint sets. This paper introduces a projection-free algorithm for COCO that achieves state-of-the-art performance guarantees while eliminating the need for projections. By integrating a separation oracle with adaptive Online Gradient Descent (OGD) and employing a Lyapunov-driven surrogate function, while dynamically adjusting step sizes using gradient norms, our method jointly optimizes the regret and cumulative constraint violation (CCV). We also use a blocked version of OGD that helps achieve tradeoffs betweeen the regret and CCV with the number of calls to the separation oracle. For convex cost functions, our algorithm attains an optimal regret of $\mathcal{O}(\sqrt{T})$ and a CCV of $\mathcal{O}(\sqrt{T} \log T)$, matching the best-known projection-based results, while only using $\tilde{\mathcal{O}}({T})$ calls to the separation oracle. The results also demonstrate a tradeoff where lower calls to the separation oracle increase the regret and the CCV. In the strongly convex setting, we further achieve a regret of $\mathcal{O}(\log T)$ and a CCV of $\mathcal{O}(\sqrt{T\log T} )$, while requiring ${\mathcal{O}}({T}^2)$ calls to the separation oracle. Further, tradeoff with the decreasing oracle calls is studied. These results close the gap between projection-free and projection-based approaches, demonstrating that projection-free methods can achieve performance comparable to projection-based counterparts.
• Abstract（参考訳）: 制約付きオンライン凸最適化(COCO)の投影に基づくアルゴリズムは、制約セットに繰り返し投影する計算の複雑さにより、高次元設定においてスケーラビリティの課題に直面している。 本稿では,プロジェクションの必要性を排除しつつ,最先端の性能保証を実現するCOCOのプロジェクションフリーアルゴリズムを提案する。 分離オラクルを適応的オンライングラディエントDescent(OGD)と統合し、リアプノフ駆動のサロゲート関数を用い、勾配ノルムを用いてステップサイズを動的に調整することにより、後悔と累積的制約違反(CCV)を共同で最適化する。 我々はまた、OGDのブロックされたバージョンを使用して、分離の神託への呼び出し数で、後悔とCCVに賭けるトレードオフを達成するのに役立ちます。 凸コスト関数に対して、我々のアルゴリズムは、$\mathcal{O}(\sqrt{T})$と$\mathcal{O}(\sqrt{T} \log T)$のCCVを最適後悔し、最もよく知られたプロジェクションベースの結果と一致し、$\tilde{\mathcal{O}}({T})$の分離オラクルへの呼び出しのみを使用する。 また,分離オラクルに対する低要求が後悔とCCVを増加させるトレードオフを示した。 強い凸設定では、$\mathcal{O}(\log T)$と$\mathcal{O}(\sqrt{T\log T} )$のCCVの後悔をさらに達成し、${\mathcal{O}}({T}^2)$の分離オラクルへの呼び出しを要求する。 さらに, オラクルコールの減少に伴うトレードオフについて検討した。 これらの結果はプロジェクションフリーアプローチとプロジェクションベースアプローチのギャップを埋め、プロジェクションフリー手法がプロジェクションベース手法に匹敵する性能を達成できることを示した。

関連論文リスト

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints [10.047668792033033]
  本稿では,オンライン凸最適化(OCO)フレームワークの時間的逆制約による一般化について検討する。 この問題では、凸判定セットから実行可能な動作を選択した後、各ラウンドのコスト関数とともに凸制約関数を$X,$とする。 我々は,一ラウンドに1回,線形プログラム(LP)ソルバに1回コールする*プロジェクションフリー*オンラインポリシーを提案する。
  論文  参考訳（メタデータ） (2025-01-28T13:04:32Z)
• Revisiting Projection-Free Online Learning with Time-Varying Constraints [35.573654458435854]
  我々は制約付きオンライン凸最適化について検討し、そこでは決定は固定的で典型的には複雑な領域に属する必要がある。 いくつかのプロジェクションフリーな手法が$mathcalO(T3/4 sqrtlog T)$ regret boundと$mathcalO(T3/4 sqrtlog T)$ cumulative constraint violation (CCV) bound for general convex lossで提案されている。 本稿では,損失関数が強凸である場合に,この結果を改善し,さらにテクスチノーベルの後悔とCCV境界を確立する。
  論文  参考訳（メタデータ） (2025-01-27T13:38:51Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Riemannian Projection-free Online Learning [5.918057694291832]
  プロジェクション操作は、オンライン勾配降下(OGD)のような最適化アルゴリズムにおける重要な要素である。 これは高次元の設定における計算上の制限や、不条件の制約セットを扱う際に悩まされる。 本稿では,曲面空間上でのオンライン測地線凸最適化において,線形後悔の保証を得る手法を提案する。
  論文  参考訳（メタデータ） (2023-05-30T18:22:09Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Functional Constrained Optimization for Risk Aversion and Sparsity Control [7.561780884831967]
  リスクとスパーシリティの要件は、ポートフォリオ最適化、アソート計画、放射線計画など、多くのアプリケーションで同時に実施する必要がある。 本稿では,これらの課題に対して凸あるいはスパース軌道を生成するレベル条件勾配(LCG)法を提案する。 提案手法は,極小勾配を解くための内部条件近似(CGO)を最適値のレベル1セット投影することを示す。
  論文  参考訳（メタデータ） (2022-10-11T02:51:51Z)
• Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning [8.461907111368628]
  我々はオンライン凸最適化(OCO)のための新しい効率的なプロジェクションフリーアルゴリズムを開発した。 我々は,LOOracleを1ラウンドに2回呼び出すOCOアルゴリズムを開発し,ほぼ最適の$widetildeO(sqrtT)を後悔する。 また, 一般凸集合に対して, 1ラウンド当たりのO(d)$ LO Oracleへのコール数を$widetilde O(d)$に設定するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T17:13:46Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。