論文の概要: Projection-Free Online Convex Optimization via Efficient Newton
Iterations
- arxiv url: http://arxiv.org/abs/2306.11121v1
- Date: Mon, 19 Jun 2023 18:48:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-21 16:40:58.599543
- Title: Projection-Free Online Convex Optimization via Efficient Newton
Iterations
- Title（参考訳）: 効率的なニュートン反復によるオンライン凸最適化
- Authors: Khashayar Gatmiry and Zakaria Mhammedi
- Abstract要約: 本稿では、凸領域$mathcalKサブセットmathbbRd$に対するオンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 10.492474737007722
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents new projection-free algorithms for Online Convex
Optimization (OCO) over a convex domain $\mathcal{K} \subset \mathbb{R}^d$.
Classical OCO algorithms (such as Online Gradient Descent) typically need to
perform Euclidean projections onto the convex set $\cK$ to ensure feasibility
of their iterates. Alternative algorithms, such as those based on the
Frank-Wolfe method, swap potentially-expensive Euclidean projections onto
$\mathcal{K}$ for linear optimization over $\mathcal{K}$. However, such
algorithms have a sub-optimal regret in OCO compared to projection-based
algorithms. In this paper, we look at a third type of algorithms that output
approximate Newton iterates using a self-concordant barrier for the set of
interest. The use of a self-concordant barrier automatically ensures
feasibility without the need for projections. However, the computation of the
Newton iterates requires a matrix inverse, which can still be expensive. As our
main contribution, we show how the stability of the Newton iterates can be
leveraged to compute the inverse Hessian only a vanishing fraction of the
rounds, leading to a new efficient projection-free OCO algorithm with a
state-of-the-art regret bound.
- Abstract（参考訳）: 本稿では、凸領域 $\mathcal{K} \subset \mathbb{R}^d$ 上のオンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
古典的なOCOアルゴリズム(例えば Online Gradient Descent)は典型的には、イテレートの実現性を確保するために、凸集合の$\cK$にユークリッド投影を実行する必要がある。
フランク=ウルフ法のような別のアルゴリズムは、潜在的に拡張可能なユークリッド射影を$\mathcal{K}$に置き換え、$\mathcal{K}$を線形最適化する。
しかし、このようなアルゴリズムはプロジェクションベースのアルゴリズムに比べてOCOに準最適の後悔を持っている。
本稿では,利子集合に対する自己一致バリアを用いて近似ニュートンイテレートを出力する3種類のアルゴリズムについて検討する。
自己一致障壁の使用は、投影を必要とせずに自動的に実現可能である。
しかし、ニュートンイテレートの計算には行列逆行列が必要であり、それでも高価である。
我々の主な貢献として、ニュートンイテレートの安定性がどのように活用され、逆ヘッセン数のみを計算し、最先端の後悔境界を持つ新しい効率的なプロジェクションフリーなOCOアルゴリズムを実現するかを示す。
関連論文リスト
- Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。
提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。
決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
論文 参考訳（メタデータ） (2023-11-18T23:06:33Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。
GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。
我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
論文 参考訳（メタデータ） (2022-11-22T23:53:06Z) - 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) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Efficient Projection-Free Online Convex Optimization with Membership
Oracle [11.745866777357566]
ユークリッド球上で定義された任意のアルゴリズムAを、球に含まれる制約付き集合 C 上のアルゴリズムに変換する新しい還元法を提案する。
我々の削減には、O(T log T) を T ラウンド後に C 上で Oracle に呼び出しる必要があり、C 上の線形最適化は不要である。
論文 参考訳（メタデータ） (2021-11-10T17:22:29Z) - Newton-LESS: Sparsification without Trade-offs for the Sketched Newton
Update [88.73437209862891]
2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。
本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。
ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
論文 参考訳（メタデータ） (2021-07-15T17:33:05Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Efficient Projection-Free Algorithms for Saddle Point Problems [39.88460595129901]
複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。
条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$tildeO (1/sqrtepsilon)$評価と$tildeO (1/epsilon2)$線形最適化しか必要としないことを示す。
論文 参考訳（メタデータ） (2020-10-21T15:05:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。