論文の概要: Randomized Coordinate Subgradient Method for Nonsmooth Optimization
- arxiv url: http://arxiv.org/abs/2206.14981v2
- Date: Mon, 17 Apr 2023 03:53:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-19 00:33:43.403524
- Title: Randomized Coordinate Subgradient Method for Nonsmooth Optimization
- Title（参考訳）: 非平滑最適化のためのランダム化座標次法
- Authors: Lei Zhao and Ding Chen and Daoli Zhu and Xiao Li
- Abstract要約: 非平滑凸および非平滑非(非平滑弱凸)問題に対するRandomized Coordinate Subgradient Method (RCS)を提案する。
RCSは、1つのブロック座標をランダムに選択し、繰り返しごとに更新する。
本研究では, 過渡法よりもRCSの方が優れていることを示すために, いくつかの実験を行った。
- 参考スコア（独自算出の注目度）: 10.366968510541952
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we propose the {Randomized Coordinate Subgradient method} (RCS)
for solving nonsmooth convex and nonsmooth nonconvex (nonsmooth weakly convex)
optimization problems. RCS randomly selects one block coordinate to update at
each iteration, making it more practical than updating all coordinates. 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 thorough
convergence analysis for RCS in both convex and nonconvex 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
suboptimality gap when $f$ is nonsmooth convex. If $f$ further satisfies the
global quadratic growth condition, the improved $\mathcal{O}(1/k)$ rate is
shown in terms of the squared distance to the optimal solution set. For the
case when $f$ is nonsmooth weakly convex and its subdifferential satisfies the
global metric subregularity property, we derive the $\mathcal{O}(1/T^{1/4})$
iteration complexity in expectation, where $T$ is the total number of
iterations. 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, which is of independent interest. We provide a convergence
lemma and the relationship between the global metric subregularity properties
of a weakly convex function and its Moreau envelope, which are also of
independent interest. Finally, we conduct several experiments to demonstrate
the possible superiority of RCS over the subgradient method.
- Abstract（参考訳）: 本研究では,非平滑凸および非平滑凸(非平滑凸)最適化問題の解法として {Randomized Coordinate Subgradient Method} (RCS) を提案する。
RCSは、1つのブロック座標をランダムに選択し、繰り返しごとに更新する。
我々は,従来のリプシッツ連続性仮定よりも一般の目的関数に対する線形有界部分次数の仮定を考える。
次に,この一般化リプシッツ型仮定に基づき,凸および非凸のいずれの場合においてもrcsの完全収束解析を行う。
具体的には、期待における$\widetilde{\mathcal{O}}(1/\sqrt{k})$収束率と$\tilde o(1/\sqrt{k})$ほぼ確実に漸近収束率を、f$が非滑らか凸であるときの準最適差の点で確立する。
さらに$f$が大域二次成長条件を満たすならば、改善された$\mathcal{O}(1/k)$レートは最適解集合への平方距離で示される。
f$ が非滑らかな弱凸であり、その部分微分が大域的計量準正則性を満たす場合、期待値において$\mathcal{o}(1/t^{1/4})$ の反復複雑性が導出され、ここで$t$ は反復の総数である。
また,漸近収束結果も確立する。
解析に用いた大域的計量サブレギュラリティ特性を正当化するために, 独立に利害関係を有する具体的な(実価値)ロバストな位相検索問題に対して, この誤差境界条件を定式化する。
収束補題と弱凸函数の大域的計量部分正則性とモローエンベロープの関係は独立な関心を持つ。
最後に, 下位勾配法よりもrcsが優れていることを示す実験を複数実施した。
関連論文リスト
- Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。