論文の概要: A Unified Analysis for the Subgradient Methods Minimizing Composite
Nonconvex, Nonsmooth and Non-Lipschitz Functions
- arxiv url: http://arxiv.org/abs/2308.16362v1
- Date: Wed, 30 Aug 2023 23:34:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-01 18:20:39.333151
- Title: A Unified Analysis for the Subgradient Methods Minimizing Composite
Nonconvex, Nonsmooth and Non-Lipschitz Functions
- Title(参考訳): 複合非凸・非平滑・非リプシッツ関数を最小化する下位手法の統一解析
- Authors: Daoli Zhu and Lei Zhao and Shuzhong Zhang
- Abstract要約: 非Lipschitzおよび非滑らかな最適化問題の文脈における新しい収束解析を提案する。
論文で導入すべき下次上界条件のいずれかの下では、$O (1/stqrT)$がエンベロープ関数の平方勾配で成り立つことを示し、さらに1/2$指数を持つ一様KL条件が成り立つ場合、$O (1/T)$に改善される。
- 参考スコア(独自算出の注目度): 8.960341489080609
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we propose a proximal subgradient method (Prox-SubGrad) for
solving nonconvex and nonsmooth optimization problems without assuming
Lipschitz continuity conditions. A number of subgradient upper bounds and their
relationships are presented. By means of these upper bounding conditions, we
establish some uniform recursive relations for the Moreau envelopes for weakly
convex optimization. This uniform scheme simplifies and unifies the proof
schemes to establish rate of convergence for Prox-SubGrad without assuming
Lipschitz continuity. We present a novel convergence analysis in this context.
Furthermore, we propose some new stochastic subgradient upper bounding
conditions and establish convergence and iteration complexity rates for the
stochastic subgradient method (Sto-SubGrad) to solve non-Lipschitz and
nonsmooth stochastic optimization problems. In particular, for both
deterministic and stochastic subgradient methods on weakly convex optimization
problems without Lipschitz continuity, under any of the subgradient upper
bounding conditions to be introduced in the paper, we show that $O(1/\sqrt{T})$
convergence rate holds in terms of the square of gradient of the Moreau
envelope function, which further improves to be $O(1/{T})$ if, in addition, the
uniform KL condition with exponent $1/2$ holds.
- Abstract(参考訳): 本稿では,リプシッツ連続性条件を仮定せずに非凸および非滑らかな最適化問題を解くための近位部分勾配法(prox-subgrad)を提案する。
多くの下位の上限とその関係が提示される。
これらの上界条件を用いて、弱い凸最適化のためのモロー包絡に関する一様再帰関係を定式化する。
この一様スキームは、証明スキームを単純化し、リプシッツ連続性を仮定せずに、プロックス・サブグラードの収束率を確立するために統一する。
この文脈における新しい収束解析を提案する。
さらに,非リプシッツおよび非滑らかな確率的最適化問題を解くために,確率的下次法(Sto-SubGrad)に対する収束と反復の複雑性の確立を新たに提案する。
特に、リプシッツの連続性を持たない弱凸最適化問題に対する決定論的および確率的半次法は、この論文で導入すべき下次上界条件のいずれかの下で、$O(1/\sqrt{T})$収束率はモローエンベロープ関数の勾配の平方部で成り立ち、さらに$O(1/{T})$に改善される。
関連論文リスト
- Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳(メタデータ) (2023-06-02T04:21:59Z) - Revisiting Subgradient Method: Complexity and Convergence Beyond
Lipschitz Continuity [29.56022052936922]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究ではまず, 次進法における典型的な複雑性を, 対物関数の凸度と弱凸度に拡張する。
ステップサイズの適切な減少規則を用いて,非Lipschitz凸および弱凸目的関数に対する収束結果を提供する。
論文 参考訳(メタデータ) (2023-05-23T15:26:36Z) - Projective Proximal Gradient Descent for A Class of Nonconvex Nonsmooth
Optimization Problems: Fast Convergence Without Kurdyka-Lojasiewicz (KL)
Property [22.232788341658924]
非滑らかな最適化問題は、学習にとって重要かつ困難である。
本稿では,PSGDの高速収束を示す新しい解析法について述べる。
論文 参考訳(メタデータ) (2023-04-20T17:39:24Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳(メタデータ) (2023-02-02T10:37:23Z) - Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳(メタデータ) (2022-09-12T06:53:24Z) - 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) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳(メタデータ) (2021-10-20T02:57:21Z) - Cyclic Coordinate Dual Averaging with Extrapolation [22.234715500748074]
単調作用素を用いた変分不等式(VI)問題の一般クラスに適用可能な新しいブロック座標法を提案する。
得られた収束境界は、全勾配法の最適収束境界と一致する。
座標ブロックが$m$の場合、我々の境界における勾配リプシッツ定数は、従来のユークリッドのリプシッツ定数と比較して$sqrtm$よりも大きくなることはない。
論文 参考訳(メタデータ) (2021-02-26T00:28:58Z) - ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm [77.71051081132912]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
emphRecursive One-Over-T Root (ROOTSGD) と呼ばれる小説を考案する。
有限サンプル勾配, 漸近感覚, 感覚を同時に達成することを証明する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。