論文の概要: Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization
- arxiv url: http://arxiv.org/abs/2306.02212v1
- Date: Sat, 3 Jun 2023 23:31:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-06 19:27:51.922626
- Title: Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization
- Title(参考訳): 加速準ニュートン近位指数:平滑凸最適化の高速化
- Authors: Ruichen Jiang and Aryan Mokhtari
- Abstract要約: 我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
- 参考スコア(独自算出の注目度): 26.328847475942894
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose an accelerated quasi-Newton proximal extragradient
(A-QPNE) method for solving unconstrained smooth convex optimization problems.
With access only to the gradients of the objective, we prove that our method
can achieve a convergence rate of ${O}\bigl(\min\{\frac{1}{k^2},
\frac{\sqrt{d\log k}}{k^{2.5}}\}\bigr)$, where $d$ is the problem dimension and
$k$ is the number of iterations. In particular, in the regime where $k =
{O}(d)$, our method matches the optimal rate of ${O}(\frac{1}{k^2})$ by
Nesterov's accelerated gradient (NAG). Moreover, in the the regime where $k =
\Omega(d \log d)$, it outperforms NAG and converges at a faster rate of
${O}\bigl(\frac{\sqrt{d\log k}}{k^{2.5}}\bigr)$. To the best of our knowledge,
this result is the first to demonstrate a provable gain of a quasi-Newton-type
method over NAG in the convex setting. To achieve such results, we build our
method on a recent variant of the Monteiro-Svaiter acceleration framework and
adopt an online learning perspective to update the Hessian approximation
matrices, in which we relate the convergence rate of our method to the dynamic
regret of a specific online convex optimization problem in the space of
matrices.
- Abstract(参考訳): 本稿では,制約のない滑らかな凸最適化問題の解法として,準ニュートン近位勾配(A-QPNE)法を提案する。
目的の勾配にのみアクセスすることにより、我々の手法が${O}\bigl(\min\{\frac{1}{k^2}, \frac{\sqrt{d\log k}}{k^{2.5}}\}\bigr)$の収束率を達成できることが証明される。
特に、$k = {O}(d)$の場合、我々の方法は、ネステロフの加速勾配 (NAG) による${O}(\frac{1}{k^2})$の最適速度と一致する。
さらに、$k = \Omega(d \log d)$ が NAG を上回り、${O}\bigl(\frac{\sqrt{d\log k}}{k^{2.5}}\bigr)$ の速度で収束する状態である。
我々の知る限り、この結果は凸設定におけるNAGに対する準ニュートン型法の証明可能な利得を示す最初のものである。
このような結果を得るために,我々はモンテイロ・スヴェイター加速フレームワークの最近の変種に基づく手法を構築し,ヘッセン近似行列を更新するためのオンライン学習視点を適用し,この手法の収束率と行列空間における特定のオンライン凸最適化問題の動的後悔を関連づける。
関連論文リスト
- Enhancing Stochastic Gradient Descent: A Unified Framework and Novel
Acceleration Methods for Faster Convergence [9.668078830796999]
2つのプラググルー収束条件下での収束に対処する統一的な枠組みを提案する。
これらの2つの手法が理論的にAインレートに導かれることを示す。
論文 参考訳(メタデータ) (2024-02-02T15:55:25Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳(メタデータ) (2023-07-04T16:55:41Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳(メタデータ) (2022-11-03T14:12:51Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳(メタデータ) (2022-03-30T11:39:00Z) - Nesterov Accelerated Shuffling Gradient Method for Convex Optimization [15.908060383231371]
このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。
我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。
数値シミュレーションはアルゴリズムの効率を実証する。
論文 参考訳(メタデータ) (2022-02-07T21:23:17Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳(メタデータ) (2021-10-28T14:19:30Z) - Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる
新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
論文 参考訳(メタデータ) (2021-05-13T04:23:07Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳(メタデータ) (2021-02-05T14:02:20Z) - Stochastic Subspace Cubic Newton Method [14.624340432672172]
本稿では,高次元凸関数$f$を最小化するランダム化二階最適化アルゴリズムを提案する。
ミニバッチサイズが変化するにつれて、SSCNのグローバル収束速度は座標降下速度(CD)と立方正規化ニュートン速度とを補間することを示した。
注目すべきことに、SSCN の局所収束速度は、次数関数 $frac12 (x-x*)top nabla2f(x*)(x-x*)$ の最小化問題に適用される部分空間降下率と一致する。
論文 参考訳(メタデータ) (2020-02-21T19:42:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。