論文の概要: A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization
- arxiv url: http://arxiv.org/abs/2312.01047v2
- Date: Tue, 30 Apr 2024 07:20:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-01 19:37:57.182879
- Title: A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization
- Title（参考訳）: 非滑らかな非凸有限サム最適化のための新しいランダムリシャッフル法
- Authors: Junwen Qiu, Xiao Li, Andre Milzarek,
- Abstract要約: ランダムリシャッフル技術は、ニューラルネットワークのような大規模アプリケーションで使用される。
本稿では,ノルムPRRが生成するランダムリシャッフル型反復が線形設定に収束することを示す。
最後に,提案手法に適用可能な最終収束率を導出する。
- 参考スコア（独自算出の注目度）: 6.314057999212246
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Random reshuffling techniques are prevalent in large-scale applications, such as training neural networks. While the convergence and acceleration effects of random reshuffling-type methods are fairly well understood in the smooth setting, much less studies seem available in the nonsmooth case. In this work, we design a new normal map-based proximal random reshuffling (norm-PRR) method for nonsmooth nonconvex finite-sum problems. We show that norm-PRR achieves the iteration complexity $O(n^{-1/3}T^{-2/3})$ where $n$ denotes the number of component functions $f(\cdot,i)$ and $T$ counts the total number of iterations. This improves the currently known complexity bounds for this class of problems by a factor of $n^{-1/3}$. In addition, we prove that norm-PRR converges linearly under the (global) Polyak-Lojasiewicz condition and in the interpolation setting. We further complement these non-asymptotic results and provide an in-depth analysis of the asymptotic properties of norm-PRR. Specifically, under the (local) Kurdyka-Lojasiewicz inequality, the whole sequence of iterates generated by norm-PRR is shown to converge to a single stationary point. Moreover, we derive last iterate convergence rates that can match those in the smooth, strongly convex setting. Finally, numerical experiments are performed on nonconvex classification tasks to illustrate the efficiency of the proposed approach.
- Abstract（参考訳）: ランダムリシャッフル技術は、ニューラルネットワークのトレーニングなど、大規模アプリケーションで広く使われている。
ランダムリシャッフル型手法の収束と加速効果はスムーズな環境ではかなりよく理解されているが、非滑らかなケースではより少ない研究が利用できるように思われる。
本研究では,非滑らかな非凸有限サム問題に対する正規写像に基づく近位ランダムリシャッフル法 (norm-PRR) を設計する。
ノルムPRRは反復複雑性を$O(n^{-1/3}T^{-2/3})$で表し、$n$は成分関数の数を$f(\cdot,i)$で表し、$T$は反復の総数を数える。
これにより、このクラスの問題の現在知られている複雑性境界を$n^{-1/3}$の係数で改善する。
さらに、ノルムPRRは(球状)ポリアック・ロジャシエヴィチ条件と補間条件の下で線型収束することが証明される。
我々は、これらの非漸近的結果をさらに補完し、ノルムPRRの漸近的特性を詳細に分析する。
具体的には、(局所的な)クルディカ・ロジャシエヴィチの不等式の下で、ノルムPRRによって生成されるイテレート全体の列は、単一の定常点に収束することが示されている。
さらに、スムーズで強い凸条件で一致できる最後の反復収束率を導出する。
最後に,非凸分類タスクにおける数値実験を行い,提案手法の効率性を示す。
関連論文リスト
- Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文 参考訳（メタデータ） (2023-11-18T04:41:07Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Distributed Random Reshuffling Methods with Improved Convergence [8.112170817124444]
本稿では,GT-RR(Gdient Tracking with Random Reshuffling)とED-RR(Exact Diffusion with Random Reshuffling)の2つの分散ランダムリシャッフル手法を提案する。
論文 参考訳（メタデータ） (2023-06-21T06:05:34Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Proximal and Federated Random Reshuffling [11.83842808044211]
ランダムリシャッフルのための2つの新しいアルゴリズムを提案する。
ProxRR と FedRR は複合凸有限和最小化問題を解く。
ProxRRは、各イテレーションの近位演算子を評価するアルゴリズムよりも高速です。
論文 参考訳（メタデータ） (2021-02-12T18:59:24Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - Random Reshuffling: Simple Analysis with Vast Improvements [9.169947558498535]
ランダムリシャッフル(Random Reshuffling, RR)は、データリシャッフルと共に反復降下ステップを利用する有限サム関数を最小化するアルゴリズムである。
論文 参考訳（メタデータ） (2020-06-10T17:57:21Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。