論文の概要: 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に対する準ニュートン型法の証明可能な利得を示す最初のものである。
このような結果を得るために,我々はモンテイロ・スヴェイター加速フレームワークの最近の変種に基づく手法を構築し,ヘッセン近似行列を更新するためのオンライン学習視点を適用し,この手法の収束率と行列空間における特定のオンライン凸最適化問題の動的後悔を関連づける。
関連論文リスト
- Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence [20.766358513158206]
双対性ギャップの観点から、大域収束率を$O(min1/k,sqrtd/k1.25)$とする。
これらの結果は、外勾配法よりも準ニュートン法の証明可能な利点を示す最初の大域収束結果である。
論文 参考訳（メタデータ） (2024-10-03T16:08:16Z) - Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Stochastic Newton Proximal Extragradient Method [18.47705532817026]
そこで本稿では,これらの境界を改良するNewton Extragradient法を提案する。
我々はHybrid Proximal Extragradient(HPE)フレームワークを拡張してこれを実現する。
論文 参考訳（メタデータ） (2024-06-03T16:06:23Z) - 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 [53.044526424637866]
本稿では、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) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Nesterov Accelerated Shuffling Gradient Method for Convex Optimization [15.908060383231371]
このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。
我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。
数値シミュレーションはアルゴリズムの効率を実証する。
論文 参考訳（メタデータ） (2022-02-07T21:23:17Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。