論文の概要: Quasi-Newton Steps for Efficient Online Exp-Concave Optimization
- arxiv url: http://arxiv.org/abs/2211.01357v1
- Date: Wed, 2 Nov 2022 17:57:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-03 14:50:51.990492
- Title: Quasi-Newton Steps for Efficient Online Exp-Concave Optimization
- Title（参考訳）: 効率的なオンラインExp-Concave最適化のための準ニュートンステップ
- Authors: Zakaria Mhammedi and Khashayar Gatmiry
- Abstract要約: Online Newton Step (ONS)は、$O(dln T)$を保証できる。
本稿では,自己協和性バリアを正規化器として使用することにより,一般化された投影をサイドステップで行う。
最終的なアルゴリズムはONSのより効率的なバージョンと見なすことができる。
- 参考スコア（独自算出の注目度）: 10.492474737007722
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The aim of this paper is to design computationally-efficient and optimal
algorithms for the online and stochastic exp-concave optimization settings.
Typical algorithms for these settings, such as the Online Newton Step (ONS),
can guarantee a $O(d\ln T)$ bound on their regret after $T$ rounds, where $d$
is the dimension of the feasible set. However, such algorithms perform
so-called generalized projections whenever their iterates step outside the
feasible set. Such generalized projections require $\Omega(d^3)$ arithmetic
operations even for simple sets such a Euclidean ball, making the total runtime
of ONS of order $d^3 T$ after $T$ rounds, in the worst-case. In this paper, we
side-step generalized projections by using a self-concordant barrier as a
regularizer to compute the Newton steps. This ensures that the iterates are
always within the feasible set without requiring projections. This approach
still requires the computation of the inverse of the Hessian of the barrier at
every step. However, using the stability properties of the Newton steps, we
show that the inverse of the Hessians can be efficiently approximated via
Taylor expansions for most rounds, resulting in a $O(d^2 T +d^\omega \sqrt{T})$
total computational complexity, where $\omega$ is the exponent of matrix
multiplication. In the stochastic setting, we show that this translates into a
$O(d^3/\epsilon)$ computational complexity for finding an $\epsilon$-suboptimal
point, answering an open question by Koren 2013. We first show these new
results for the simple case where the feasible set is a Euclidean ball. Then,
to move to general convex set, we use a reduction to Online Convex Optimization
over the Euclidean ball. Our final algorithm can be viewed as a more efficient
version of ONS.
- Abstract（参考訳）: 本稿では,オンラインおよび確率的exp-concave最適化設定のための計算効率と最適アルゴリズムを設計することを目的とする。
オンラインニュートンステップ(ONS)のようなこれらの設定のための典型的なアルゴリズムは、$O(d\ln T)$が、$T$ラウンド後の後悔に縛られ、$d$は実現可能な集合の次元である。
しかし、そのようなアルゴリズムは、イテレートが実現可能な集合の外に進むと、いわゆる一般化射影を行う。
このような一般化された射影は、ユークリッド球のような単純な集合であっても$\omega(d^3)$演算演算を必要とし、最悪の場合、$t$ ラウンドの後に$d^3 t$の順序のonの合計実行時間を作る。
本稿では,ニュートンステップを計算するために,自己一致バリアを正則化器として用いることにより,一般化された投影を行う。
これにより、イテレートは常に射影を必要とせずに実現可能集合内にあることが保証される。
このアプローチは、すべてのステップにおいて障壁のヘッセンの逆の計算を必要とする。
しかし、ニュートンステップの安定性特性を用いて、ほとんどのラウンドでテイラー展開によってヘッセンの逆は効率的に近似できることを示し、その結果、$O(d^2 T +d^\omega \sqrt{T})$トータル計算複雑性となり、$\omega$は行列乗算の指数となる。
確率的な設定では、これは o(d^3/\epsilon)$ の計算複雑性に変換され、\epsilon$-suboptimal point を見つけ、koren 2013 のオープン質問に答える。
まず、実現可能な集合がユークリッド球である簡単な場合のこれらの新しい結果を示す。
次に、一般凸集合に移行するために、ユークリッド球上のオンライン凸最適化の削減を用いる。
最終的なアルゴリズムはONSのより効率的なバージョンと見なすことができる。
関連論文リスト
- Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。
我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。
我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and
Minimizing the Maximum of Smooth Functions [44.655316553524855]
我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。
それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
論文 参考訳（メタデータ） (2023-11-17T22:07:18Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Projection-Free Online Convex Optimization via Efficient Newton
Iterations [10.492474737007722]
本稿では、凸領域$mathcalKサブセットmathbbRd$に対するオンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-19T18:48:53Z) - Projection-free Online Exp-concave Optimization [21.30065439295409]
LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。
我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
論文 参考訳（メタデータ） (2023-02-09T18:58:05Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Second-order optimization with lazy Hessians [55.51077907483634]
一般の非線形最適化問題を解くためにニュートンの遅延ヘッセン更新を解析する。
我々は、メソッドの各ステップで新しい勾配を計算しながら、これまで見られたヘッセン反復を再利用する。
論文 参考訳（メタデータ） (2022-12-01T18:58:26Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。