論文の概要: Constrained Online Convex Optimization with Polyak Feasibility Steps

• arxiv url: http://arxiv.org/abs/2502.13112v1
• Date: Tue, 18 Feb 2025 18:26:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-19 14:05:36.846627
• Title: Constrained Online Convex Optimization with Polyak Feasibility Steps
• Title（参考訳）: Polyak Feasibility Stepsを用いた制約付きオンライン凸最適化
• Authors: Spencer Hutchinson, Mahnoosh Alizadeh,
• Abstract要約: 固定制約関数 $g : mathbbRd rightarrow mathbbR$ を用いてオンライン凸最適化について検討する。 制約満足度$g(x_t) leq 0 forall in [T]$, and matching $O(sqrtT)$ regret guarantees。
• 参考スコア（独自算出の注目度）: 3.928749790761187
• License:
• Abstract: In this work, we study online convex optimization with a fixed constraint function $g : \mathbb{R}^d \rightarrow \mathbb{R}$. Prior work on this problem has shown $O(\sqrt{T})$ regret and cumulative constraint satisfaction $\sum_{t=1}^{T} g(x_t) \leq 0$, while only accessing the constraint value and subgradient at the played actions $g(x_t), \partial g(x_t)$. Using the same constraint information, we show a stronger guarantee of anytime constraint satisfaction $g(x_t) \leq 0 \ \forall t \in [T]$, and matching $O(\sqrt{T})$ regret guarantees. These contributions are thanks to our approach of using Polyak feasibility steps to ensure constraint satisfaction, without sacrificing regret. Specifically, after each step of online gradient descent, our algorithm applies a subgradient descent step on the constraint function where the step-size is chosen according to the celebrated Polyak step-size. We further validate this approach with numerical experiments.
• Abstract（参考訳）: 本研究では,固定制約関数 $g : \mathbb{R}^d \rightarrow \mathbb{R}$ を用いたオンライン凸最適化について検討する。 この問題の以前の研究は、$O(\sqrt{T})$ regret と cumulative 制約満足度 $\sum_{t=1}^{T} g(x_t) \leq 0$ を示し、プレイアクション $g(x_t), \partial g(x_t)$ の制約値と下位値のみにアクセスする。 同じ制約情報を用いて、任意の時間制約満足度$g(x_t) \leq 0 \ \forall t \in [T]$, and matching $O(\sqrt{T})$ regret guaranteesを示す。 これらのコントリビューションは、Polyakの実現可能性ステップを使用して、後悔を犠牲にすることなく、制約満足度を確保するというアプローチのおかげです。 具体的には、オンライン勾配降下の各ステップの後に、このアルゴリズムは、有名なPolyakのステップサイズに応じてステップサイズが選択される制約関数に、段階的な降下ステップを適用する。 さらに数値実験により,本手法の有効性を検証した。

関連論文リスト

• Anytime Acceleration of Gradient Descent [92.02082223856479]
  エム収束保証による勾配勾配勾配の段階的加速度について検討する。 滑らかな(強くない)凸最適化のために、任意の停止時間に対して、勾配降下が$O(T-1.119)$の収束保証を達成できる段階的なスケジュールを提案する。
  論文  参考訳（メタデータ） (2024-11-26T18:29:44Z)
• Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints [31.526232903811533]
  我々はOCO(Optimistically Safe OCO)と呼ぶアルゴリズムを導入し、そのアルゴリズムが$tildeO(sqrtT)$ regretと制約違反がないことを示す。 静的線形制約の場合、これは同じ仮定の下で、以前の最もよく知られた $tildeO(T2/3)$ regret よりも改善される。 時間的制約の場合、当社の作業は、$O(sqrtT)$ regretと$O(sqrtT)$ cumulative violationを示す既存の結果を補完します。
  論文  参考訳（メタデータ） (2024-03-09T04:01:39Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraints [4.879346089164413]
  ブラックボックスの報酬関数 $f(x)$ を、連続空間上のブラックボックス制約関数 $g(x)leq 0$ に最適化する。 本稿では,楽観的かつ悲観的なGPバンディット学習を取り入れたペナルティベース手法であるRectified Pessimistic-Optimistic Learning framework (RPOL)を提案する。
  論文  参考訳（メタデータ） (2022-11-27T04:28: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)
• Safe Learning under Uncertain Objectives and Constraints [66.05180398174286]
  我々は、テキスト不明で安全クリティカルな制約の下で、非テクスト無知かつ安全クリティカルな最適化問題を考察する。 このような問題は、ロボティクス、製造、医療などの様々な領域で自然に発生する。 我々の分析の重要な要素は、安全な最適化の文脈で収縮と呼ばれる手法を導入し、適用することである。
  論文  参考訳（メタデータ） (2020-06-23T20:51:00Z)
• Gradient-Variation Bound for Online Convex Optimization with Constraints [25.002868073267464]
  複数の機能的制約とユークリッド球のような比較的単純な制約セットからなる制約を持つオンライン凸最適化について検討する。 一階法は、$mathcalO(sqrtT)$ regret と $mathcalO(1)$ 制約違反を達成するが、問題の構造的情報を考慮してはならない。 本稿では,新しいオンライン原始双対ミラー-プロキシアルゴリズムによって得られる複雑な制約を伴って,オンライン凸最適化のインセンタンス依存バウンダリを提供する。
  論文  参考訳（メタデータ） (2020-06-22T17:38:14Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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