論文の概要: 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$ が弱凸であるとき、漸近収束が導かれる。
中心的な考え方は、適切に選択されたステップサイズルールのダイナミクスが、反復の有界性をもたらす下位法の運動を完全に制御し、そこで軌道に基づく解析を行い、所望の結果を確立することである。
さらに,このフレームワークの幅広い適用性を説明するために,非リプシッツ関数の縮約部分次数,確率的部分次数,漸進的部分次数,近位部分次数への複雑性結果を拡張した。
関連論文リスト
- A Unified Analysis for the Subgradient Methods Minimizing Composite
Nonconvex, Nonsmooth and Non-Lipschitz Functions [8.960341489080609]
非Lipschitzおよび非滑らかな最適化問題の文脈における新しい収束解析を提案する。
論文で導入すべき下次上界条件のいずれかの下では、$O (1/stqrT)$がエンベロープ関数の平方勾配で成り立つことを示し、さらに1/2$指数を持つ一様KL条件が成り立つ場合、$O (1/T)$に改善される。
論文 参考訳(メタデータ) (2023-08-30T23:34:11Z) - 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) - Convergence rate of the (1+1)-evolution strategy on locally strongly
convex functions with lipschitz continuous gradient and their monotonic
transformations [20.666734673282498]
進化戦略(ES)は、ブラックボックス連続最適化のための有望なアルゴリズムの1つである。
本研究では,局所$L$-強凸関数上の (1+1)-ES の線型収束率の上界と下界を$U$-Lipschitz連続勾配で導出した。
論文 参考訳(メタデータ) (2022-09-26T07:16:50Z) - 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) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳(メタデータ) (2022-05-30T14:28:02Z) - Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
この楽観的な手法は凸凹点問題の解法として人気が高まっている。
我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
論文 参考訳(メタデータ) (2022-02-19T20:31:05Z) - Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave
Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
線形凸凹サドル点問題 $min_xmax_y f(x) ytopmathbfA x - g(y) について検討する。
論文 参考訳(メタデータ) (2021-12-30T20:31:46Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。