論文の概要: Projection-Free Online Convex Optimization with Time-Varying Constraints

• arxiv url: http://arxiv.org/abs/2402.08799v1
• Date: Tue, 13 Feb 2024 21:13:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-15 17:29:10.419683
• Title: Projection-Free Online Convex Optimization with Time-Varying Constraints
• Title（参考訳）: 時間変化制約を用いた投影自由なオンライン凸最適化
• Authors: Dan Garber, Ben Kretzu
• Abstract要約: 逆時間制約によるオンライン凸最適化の設定について検討する。 固定可能な集合を投影することが難しいシナリオによって動機付けられ、線形最適化オラクル(LOO)を通してのみこの集合にアクセスするプロジェクションフリーアルゴリズムを考える。 我々は、長さ$T$のシーケンスで、全体$T$をLOOに呼び出し、$tildeO(T3/4)$ regret w.r.t.の損失と$O(T7/8)$制約違反を保証します。
• 参考スコア（独自算出の注目度）: 19.993839085310643
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the setting of online convex optimization with adversarial time-varying constraints in which actions must be feasible w.r.t. a fixed constraint set, and are also required on average to approximately satisfy additional time-varying constraints. Motivated by scenarios in which the fixed feasible set (hard constraint) is difficult to project on, we consider projection-free algorithms that access this set only through a linear optimization oracle (LOO). We present an algorithm that, on a sequence of length $T$ and using overall $T$ calls to the LOO, guarantees $\tilde{O}(T^{3/4})$ regret w.r.t. the losses and $O(T^{7/8})$ constraints violation (ignoring all quantities except for $T$) . In particular, these bounds hold w.r.t. any interval of the sequence. We also present a more efficient algorithm that requires only first-order oracle access to the soft constraints and achieves similar bounds w.r.t. the entire sequence. We extend the latter to the setting of bandit feedback and obtain similar bounds (as a function of $T$) in expectation.
• Abstract（参考訳）: 本稿では,オンライン凸最適化を,動作を固定制約集合として実行可能とし,さらに時間変動制約を概ね満たすために平均的に要求する,敵対的時間変動制約と組み合わせることを考える。 固定可能な集合(ハード制約)が投影し難いシナリオによって動機付けられ、線形最適化オラクル(LOO)を通してのみこの集合にアクセスするプロジェクションフリーアルゴリズムを考える。 我々は、長さ$t$ のシーケンス上で、loo への$t$ コールを使用して、$\tilde{o}(t^{3/4})$ regret w.r.t の損失と$o(t^{7/8})$制約違反($t$を除くすべての量を無視している)を保証するアルゴリズムを提案する。 特に、これらの境界は列の任意の間隔を保持する。 また、ソフト制約への1次オラクルアクセスのみを必要とするより効率的なアルゴリズムを提案し、シーケンス全体と類似のバウンダリを実現する。 我々は、後者をバンディットフィードバックの設定に拡張し、期待値の同様の境界($t$の関数として)を得る。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Analyzing and Improving Greedy 2-Coordinate Updates for Equality-Constrained Optimization via Steepest Descent in the 1-Norm [12.579063422860072]
  我々は,この問題に対する2座標更新と,1ノルムにおける等式制約付き急降下との接続を利用する。 次に、サポートベクトルマシン双対問題において生じるような、和制約と有界制約の両方で最小化を検討する。
  論文  参考訳（メタデータ） (2023-07-03T17:27:18Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback [0.0]
  本稿では,O(sqrtT)$期待後悔とゼロ制約違反を保証できるドリフト・プラス・ペナルティアルゴリズムの変種を提案する。 我々のアルゴリズムは、バニラドリフト・プラス・ペナルティ法とは対照的に、時間地平線の長さが$T$である。
  論文  参考訳（メタデータ） (2023-01-26T18:04:26Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees [21.30065439295409]
  オンライン凸最適化(OCO)のための効率的なテキストプロジェクションフリーアルゴリズムを提案する。 提案アルゴリズムは,テキストインファシブルプロジェクション(textitinfeasible projections)と呼ばれる新しい,効率的なアプローチによるテクスタイトライン勾配降下アルゴリズムに基づいている。 我々は、全体として$O(T)$コールを使用して分離オラクルを呼び出し、$O(sqrtT)$アダプティブな後悔と$O(T3/4)$アダプティブな期待された後悔を保証します。
  論文  参考訳（メタデータ） (2022-02-09T20:56:16Z)
• Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints [24.97580261894342]
  本稿では,長期的制約を伴うオンライン凸最適化について考察する。 新たなアルゴリズムが最初に提案され、静的後悔のために$mathcalO(Tmaxc,1-c)$bound、累積制約違反のために$mathcalO(T(1-c)/2)$boundを達成する。
  論文  参考訳（メタデータ） (2021-06-09T15:18:06Z)
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method [54.93433440034386]
  実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。 提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
  論文  参考訳（メタデータ） (2020-10-05T08:16:56Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• Gradient-Variation Bound for Online Convex Optimization with Constraints [25.002868073267464]
  複数の機能的制約とユークリッド球のような比較的単純な制約セットからなる制約を持つオンライン凸最適化について検討する。 一階法は、$mathcalO(sqrtT)$ regret と $mathcalO(1)$ 制約違反を達成するが、問題の構造的情報を考慮してはならない。 本稿では,新しいオンライン原始双対ミラー-プロキシアルゴリズムによって得られる複雑な制約を伴って,オンライン凸最適化のインセンタンス依存バウンダリを提供する。
  論文  参考訳（メタデータ） (2020-06-22T17:38:14Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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