論文の概要: Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization
- arxiv url: http://arxiv.org/abs/2206.14981v3
- Date: Wed, 23 Aug 2023 13:25:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-24 19:20:20.925314
- Title: Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization
- Title（参考訳）: 非運動複合最適化のためのランダム座標部分勾配法
- Authors: Lei Zhao and Ding Chen and Daoli Zhu and Xiao Li
- Abstract要約: 非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
- 参考スコア（独自算出の注目度）: 11.017632675093628
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Coordinate-type subgradient methods for addressing nonsmooth optimization
problems are relatively underexplored due to the set-valued nature of the
subdifferential. In this work, our study focuses on nonsmooth composite
optimization problems, encompassing a wide class of convex and weakly convex
(nonconvex nonsmooth) problems. By utilizing the chain rule of the composite
structure properly, we introduce the Randomized Coordinate Subgradient method
(RCS) for tackling this problem class. To the best of our knowledge, this is
the first coordinate subgradient method for solving general nonsmooth composite
optimization problems. In theory, we consider the linearly bounded subgradients
assumption for the objective function, which is more general than the
traditional Lipschitz continuity assumption, to account for practical
scenarios. We then conduct convergence analysis for RCS in both convex and
weakly convex cases based on this generalized Lipschitz-type assumption.
Specifically, we establish the $\widetilde{\mathcal{O}}$$(1/\sqrt{k})$
convergence rate in expectation and the $\tilde o(1/\sqrt{k})$ almost sure
asymptotic convergence rate in terms of the suboptimality gap when $f$ is
convex. For the case when $f$ is weakly convex and its subdifferential
satisfies the global metric subregularity property, we derive the
$\mathcal{O}(\varepsilon^{-4})$ iteration complexity in expectation. We also
establish an asymptotic convergence result. To justify the global metric
subregularity property utilized in the analysis, we establish this error bound
condition for the concrete (real-valued) robust phase retrieval problem. We
also provide a convergence lemma and the relationship between the global metric
subregularity properties of a weakly convex function and its Moreau envelope.
Finally, we conduct several experiments to demonstrate the possible superiority
of RCS over the subgradient method.
- Abstract（参考訳）: 非滑らかな最適化問題に対処するための座標型部分勾配法は、部分微分のセット値の性質のため、比較的未熟である。
本研究は, 広範囲の凸および弱凸(非凸非滑らか)問題を包含する非滑らかな合成最適化問題に焦点を当てた。
複合構造の連鎖則を適切に利用することにより、この問題クラスに取り組むためのランダム化座標サブグレードエント法(rcs)を導入する。
我々の知る限り、これは一般的な非滑らかな複合最適化問題を解くための最初の座標次法である。
理論的には、従来のリプシッツ連続性仮定よりも一般の目的関数に対する線形有界な部分次数の仮定を考える。
次に,この一般化リプシッツ型仮定に基づき,凸および弱凸のいずれの場合においてもrcsの収束解析を行う。
具体的には、$\widetilde{\mathcal{O}}$$(1/\sqrt{k})$収束率と$\tilde o(1/\sqrt{k})$ほぼ確実に漸近収束率を、$f$が凸であるときの漸近収束率に設定する。
f$ が弱凸であり、その部分微分が大域的距離準正則性を満たす場合、期待値において $\mathcal{o}(\varepsilon^{-4})$ の反復複雑性を導出する。
また,漸近収束結果も確立する。
解析に用いた大域的計量サブレギュラリティ特性を正当化するために,具体的(実数値)ロバストな位相検索問題に対して,この誤差境界条件を定式化する。
また,弱凸関数の大域的計量準正則性とそのモロー包絡との関係について,収束補題を提案する。
最後に, 下位勾配法よりもrcsが優れていることを示す実験を複数実施した。
関連論文リスト
- Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - 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) - Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
論文 参考訳（メタデータ） (2023-05-23T15:26:36Z) - Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。
また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
論文 参考訳（メタデータ） (2023-04-27T06:27:37Z) - Decentralized Weakly Convex Optimization Over the Stiefel Manifold [28.427697270742947]
我々は分散環境でスティーフェル多様体に焦点をあて、$nMn log-1)$のエージェントの連結ネットワークをテストする。
そこで本研究では,nMn log-1 以下の自然ステーションを強制的に強制する分散下位段階法 (DRSM)$ という手法を提案する。
論文 参考訳（メタデータ） (2023-03-31T02:56:23Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - 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) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Generalization in Supervised Learning Through Riemannian Contraction [4.3604518673788135]
教師付き学習環境では、計量 0 がアセシアンレート $lambda で収縮している場合、それは一様に$math であることを示す。
結果は、連続および安定な $-time において、勾配と決定論的損失曲面を保っている。
それらは、Descent$凸面や強い凸損失面など、ある種の線形な設定で最適であることを示すことができる。
論文 参考訳（メタデータ） (2022-01-17T23:08:47Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳（メタデータ） (2020-02-09T09:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。