論文の概要: Gradient-Variation Bound for Online Convex Optimization with Constraints
- arxiv url: http://arxiv.org/abs/2006.12455v2
- Date: Tue, 23 Aug 2022 13:12:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-18 05:49:11.680262
- Title: Gradient-Variation Bound for Online Convex Optimization with Constraints
- Title（参考訳）: 制約付きオンライン凸最適化のための勾配変数境界
- Authors: Shuang Qiu, Xiaohan Wei, Mladen Kolar
- Abstract要約: 複数の機能的制約とユークリッド球のような比較的単純な制約セットからなる制約を持つオンライン凸最適化について検討する。
一階法は、$mathcalO(sqrtT)$ regret と $mathcalO(1)$ 制約違反を達成するが、問題の構造的情報を考慮してはならない。
本稿では,新しいオンライン原始双対ミラー-プロキシアルゴリズムによって得られる複雑な制約を伴って,オンライン凸最適化のインセンタンス依存バウンダリを提供する。
- 参考スコア（独自算出の注目度）: 25.002868073267464
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online convex optimization with constraints consisting of multiple
functional constraints and a relatively simple constraint set, such as a
Euclidean ball. As enforcing the constraints at each time step through
projections is computationally challenging in general, we allow decisions to
violate the functional constraints but aim to achieve a low regret and
cumulative violation of the constraints over a horizon of $T$ time steps.
First-order methods achieve an $\mathcal{O}(\sqrt{T})$ regret and an
$\mathcal{O}(1)$ constraint violation, which is the best-known bound, but do
not take into account the structural information of the problem. Furthermore,
the existing algorithms and analysis are limited to Euclidean space. In this
paper, we provide an \emph{instance-dependent} bound for online convex
optimization with complex constraints obtained by a novel online primal-dual
mirror-prox algorithm. Our instance-dependent regret is quantified by the total
gradient variation $V_*(T)$ in the sequence of loss functions. The proposed
algorithm works in \emph{general} non-Euclidean spaces and simultaneously
achieves an $\mathcal{O}(\sqrt{V_*(T)})$ regret and an $\mathcal{O}(1)$
constraint violation, which is never worse than the best-known $(
\mathcal{O}(\sqrt{T}), \mathcal{O}(1) )$ result and improves over previous
works that applied mirror-prox-type algorithms for this problem achieving
$\mathcal{O}(T^{2/3})$ regret and constraint violation. Finally, our algorithm
is computationally efficient, as it only performs mirror descent steps in each
iteration instead of solving a general Lagrangian minimization problem.
- Abstract（参考訳）: 複数の機能的制約とユークリッド球のような比較的単純な制約セットからなる制約を持つオンライン凸最適化について検討する。
プロジェクションによる各ステップの制約の実行は一般に計算的に困難であるので、我々は関数的制約に違反する決定を許すが、T$タイムステップの水平線上の制約の後悔と累積的違反を達成することを目指している。
一階法は、$\mathcal{O}(\sqrt{T})$ regret と $\mathcal{O}(1)$ constraint violation を達成する。
さらに、既存のアルゴリズムと解析はユークリッド空間に限定されている。
本稿では,オンライン凸最適化のために,新しいオンライン原始双対ミラー-プロックスアルゴリズムによって得られる複雑な制約を持つ,emph{instance-dependent}バウンドを提案する。
我々のインスタンス依存後悔は、損失関数の列における合計勾配変動$V_*(T)$によって定量化される。
提案したアルゴリズムは、非ユークリッド空間で機能し、$\mathcal{O}(\sqrt{V_*(T)})$ regret と $\mathcal{O}(1)$ constraint violation を同時に達成し、最もよく知られた $( \mathcal{O}(\sqrt{T}), \mathcal{O}(1) )$ result よりも悪くはならない。
最後に,本アルゴリズムは一般のラグランジアン最小化問題を解く代わりに,各イテレーションでミラー降下ステップのみを実行するため,計算効率がよい。
関連論文リスト
- Constrained Online Convex Optimization with Polyak Feasibility Steps [3.928749790761187]
固定制約関数 $g : mathbbRd rightarrow mathbbR$ を用いてオンライン凸最適化について検討する。
制約満足度$g(x_t) leq 0 forall in [T]$, and matching $O(sqrtT)$ regret guarantees。
論文 参考訳（メタデータ） (2025-02-18T18:26:20Z) - An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
逆制約を伴うオンライン凸最適化(OCO)について検討する。
本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。
以上の結果から,現在のO(sqrtT) $ regret と $ tildeO(sqrtT) $ cumulative constraint violation の改善が期待できることがわかった。
論文 参考訳（メタデータ） (2024-12-11T03:06:42Z) - 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) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。
まず、この方法はスティーフェル多様体に拡張される。
また、コスト関数が多くの関数の平均である場合の分散還元アルゴリズムについても検討する。
論文 参考訳（メタデータ） (2023-03-29T07:36:54Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - 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) - An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear
Bandits [16.103685478563072]
本稿では,一般制約付き線形帯域について考察する。
目的は、各ラウンドにおける一連の制約の対象となる水平線上の累積報酬を最大化することである。
本稿では,この問題に対する悲観的最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-10T07:30:37Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。