論文の概要: Revisiting Subgradient Method: Complexity and Convergence Beyond
Lipschitz Continuity
- arxiv url: http://arxiv.org/abs/2305.14161v1
- Date: Tue, 23 May 2023 15:26:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-24 15:11:54.845947
- Title: Revisiting Subgradient Method: Complexity and Convergence Beyond
Lipschitz Continuity
- Title（参考訳）: リプシッツ連続性を超えた複雑さと収束性
- Authors: Xiao Li, Lei Zhao, Daoli Zhu, Anthony Man-Cho So
- Abstract要約: 次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究ではまず, 次進法における典型的な複雑性を, 対物関数の凸度と弱凸度に拡張する。
ステップサイズの適切な減少規則を用いて,非Lipschitz凸および弱凸目的関数に対する収束結果を提供する。
- 参考スコア（独自算出の注目度）: 29.56022052936922
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The subgradient method is one of the most fundamental algorithmic schemes for
nonsmooth optimization. The existing complexity and convergence results for
this algorithm are mainly derived for Lipschitz continuous objective functions.
In this work, we first extend the typical complexity results for the
subgradient method to convex and weakly convex minimization without assuming
Lipschitz continuity. Specifically, we establish $\mathcal{O}(1/\sqrt{T})$
bound in terms of the suboptimality gap ``$f(x) - f^*$'' for convex case and
$\mathcal{O}(1/{T}^{1/4})$ bound in terms of the gradient of the Moreau
envelope function for weakly convex case. Furthermore, we provide convergence
results for non-Lipschitz convex and weakly convex objective functions using
proper diminishing rules on the step sizes. In particular, when $f$ is convex,
we show $\mathcal{O}(\log(k)/\sqrt{k})$ rate of convergence in terms of the
suboptimality gap. With an additional quadratic growth condition, the rate is
improved to $\mathcal{O}(1/k)$ in terms of the squared distance to the optimal
solution set. When $f$ is weakly convex, asymptotic convergence is derived. The
central idea is that the dynamics of properly chosen step sizes rule fully
controls the movement of the subgradient method, which leads to boundedness of
the iterates, and then a trajectory-based analysis can be conducted to
establish the desired results. To further illustrate the wide applicability of
our framework, we extend the complexity results to the truncated subgradient,
the stochastic subgradient, the incremental subgradient, and the proximal
subgradient methods for non-Lipschitz functions.
- Abstract（参考訳）: 勾配法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
このアルゴリズムの既存の複雑性と収束結果は、主にリプシッツ連続目的関数に導かれる。
本研究では、まず、リプシッツの連続性を仮定することなく、下次法の典型的な複雑性結果を凸と弱凸最小化に拡張する。
具体的には、凸の場合の準最適ギャップ ``$f(x) - f^*$'' と弱凸の場合のモロー包絡関数の勾配の項で $\mathcal{o}(1/{t}^{1/4})$ の項で $\mathcal{o}(1/\sqrt{t})$ を定める。
さらに、ステップサイズの適切な減少規則を用いて、非Lipschitz凸および弱凸目的関数に対する収束結果を提供する。
特に、$f$ が凸であるとき、準最適ギャップの観点から $\mathcal{O}(\log(k)/\sqrt{k})$収束率を示す。
追加の二次成長条件により、最適解集合への二乗距離の観点で、レートは$\mathcal{o}(1/k)$に改善される。
f$ が弱凸であるとき、漸近収束が導かれる。
中心的な考え方は、適切に選択されたステップサイズルールのダイナミクスが、反復の有界性をもたらす下位法の運動を完全に制御し、そこで軌道に基づく解析を行い、所望の結果を確立することである。
さらに,このフレームワークの幅広い適用性を説明するために,非リプシッツ関数の縮約部分次数,確率的部分次数,漸進的部分次数,近位部分次数への複雑性結果を拡張した。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - 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) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Accelerated first-order methods for convex optimization with locally
Lipschitz continuous gradient [0.0]
まず,Lipschitz連続勾配 (LLCG) を用いた非拘束凸最適化について検討し,それを解決するための加速近位勾配 (APG) 法を提案する。
提案手法は検証可能な終端基準を備えており、演算複雑性は$cal O(varepsilon-1/2log varepsilon-1)$である。
提案手法の性能を実証するために,予備的な数値計算結果を示す。
論文 参考訳（メタデータ） (2022-06-02T10:34:26Z) - Thinking Outside the Ball: Optimal Learning with Gradient Descent for
Generalized Linear Stochastic Convex Optimization [37.177329562964765]
我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。
この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。
しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
論文 参考訳（メタデータ） (2022-02-27T09:41:43Z) - Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
この楽観的な手法は凸凹点問題の解法として人気が高まっている。
我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
論文 参考訳（メタデータ） (2022-02-19T20:31:05Z) - 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) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z) - Randomized Bregman Coordinate Descent Methods for Non-Lipschitz
Optimization [31.474280642125734]
そこで本研究では,新しいテクステンラン化ブレグマン座標降下法(CD)を提案する。
提案手法は$O(epsilon-2n)$であり,$n$は座標のブロック数であることを示す。
論文 参考訳（メタデータ） (2020-01-15T09:57:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。