論文の概要: Convergence of Random Reshuffling Under The Kurdyka-{\L}ojasiewicz
Inequality
- arxiv url: http://arxiv.org/abs/2110.04926v1
- Date: Sun, 10 Oct 2021 23:20:04 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-13 10:39:03.500956
- Title: Convergence of Random Reshuffling Under The Kurdyka-{\L}ojasiewicz
Inequality
- Title（参考訳）: kurdyka-{\l}ojasiewicz不等式におけるランダム再帰の収束
- Authors: Xiao Li, Andre Milzarek, and Junwen Qiu
- Abstract要約: 我々はクルディカ・ロジャシエヴィチ(KL)の不等式に基づくステップサイズを小さくした非輝化RRの収束解析を行う。
我々は、KL指数と好適に選択された減少ステップサイズに応じて、対応する収束率を導出する。
また、近位点法に対して同様の強い極限点収束結果を確立する。
- 参考スコア（独自算出の注目度）: 3.960041987749073
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the random reshuffling (RR) method for smooth nonconvex optimization
problems with a finite-sum structure. Though this method is widely utilized in
practice such as the training of neural networks, its convergence behavior is
only understood in several limited settings. In this paper, under the
well-known Kurdyka-Lojasiewicz (KL) inequality, we establish strong limit-point
convergence results for RR with appropriate diminishing step sizes, namely, the
whole sequence of iterates generated by RR is convergent and converges to a
single stationary point in an almost sure sense. In addition, we derive the
corresponding rate of convergence, depending on the KL exponent and the
suitably selected diminishing step sizes. When the KL exponent lies in
$[0,\frac12]$, the convergence is at a rate of $\mathcal{O}(t^{-1})$ with $t$
counting the iteration number. When the KL exponent belongs to $(\frac12,1)$,
our derived convergence rate is of the form $\mathcal{O}(t^{-q})$ with $q\in
(0,1)$ depending on the KL exponent. The standard KL inequality-based
convergence analysis framework only applies to algorithms with a certain
descent property. Remarkably, we conduct convergence analysis for the
non-descent RR with diminishing step sizes based on the KL inequality, which
generalizes the standard KL analysis framework. We summarize our main steps and
core ideas in an analysis framework, which is of independent interest. As a
direct application of this framework, we also establish similar strong
limit-point convergence results for the shuffled proximal point method.
- Abstract（参考訳）: 有限サム構造をもつ滑らかな非凸最適化問題に対するランダムリシャッフル法(RR)について検討した。
この方法は、ニューラルネットワークのトレーニングなど、実際に広く利用されているが、収束挙動はいくつかの限られた設定でのみ理解されている。
本稿では、よく知られたクルディカ・ロジャシエヴィチの不等式の下で、RR が生成するイテレート全体の列が収束し、ほぼ確実な意味で単一の定常点に収束する、適切なステップサイズが減少する RR に対する強い極限点収束結果を確立する。
さらに,KL指数と適度に選択された縮小ステップサイズに依存して,対応する収束率を導出する。
KL指数が$[0,\frac12]$にあるとき、収束率は$\mathcal{O}(t^{-1})$で、反復数を数える$t$である。
KL指数が$(\frac12,1)$に属するとき、我々の導出した収束率は、KL指数に依存する$q\in (0,1)$の形で$\mathcal{O}(t^{-q})$である。
標準KL不等式に基づく収束解析フレームワークは、特定の降下特性を持つアルゴリズムにのみ適用される。
注目すべきは,標準kl分析フレームワークを一般化したkl不等式に基づくステップサイズを小さくした非希薄rrの収束解析を行うことである。
分析フレームワークでは、主要なステップと中核的なアイデアをまとめています。
このフレームワークの直接的な応用として、シャッフル近位点法に対する同様の強い極限点収束結果を確立する。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications [2.0584253077707477]
目的関数 $J(cdot)$ の定常点を求めるグラディエント・Descent (SGD) 法の収束特性について検討した。
この結果は、すべての定常点が大域最小値である性質を持つ invex' 関数のクラスに適用できる。
論文 参考訳（メタデータ） (2023-12-05T15:22:39Z) - A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization [6.314057999212246]
ランダムリシャッフル技術は、ニューラルネットワークのような大規模アプリケーションで使用される。
本稿では,ノルムPRRが生成するランダムリシャッフル型反復が線形設定に収束することを示す。
最後に,提案手法に適用可能な最終収束率を導出する。
論文 参考訳（メタデータ） (2023-12-02T07:12:00Z) - Compressed and distributed least-squares regression: convergence rates
with applications to Federated Learning [9.31522898261934]
機械学習の勾配アルゴリズムに対する圧縮の影響について検討する。
いくつかの非バイアス圧縮演算子間の収束率の差を強調した。
我々はその結果を連合学習の事例にまで拡張する。
論文 参考訳（メタデータ） (2023-08-02T18:02:00Z) - On the Linear Convergence of Policy Gradient under Hadamard
Parameterization [4.182089296199263]
本研究では,アダマールパラメータ化に基づく決定論的政策勾配の収束性について検討する。
すべてのイテレーションに対して$O(frac1k)$レートでエラーが減少することを示す。
論文 参考訳（メタデータ） (2023-05-31T05:51:15Z) - A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning [3.655021726150368]
マルチエージェント強化学習(MARL: Multi-Agent Reinforcement Learning)では、複数のエージェントが共通の環境と相互作用し、シーケンシャルな意思決定において共有問題を解く。
我々は、MARLで有用な分散非線形近似スキームの族を反復する新しい法則を導出する。
論文 参考訳（メタデータ） (2021-10-27T08:01:17Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Proximal Gradient Descent-Ascent: Variable Convergence under K{\L}
Geometry [49.65455534654459]
有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。
本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
論文 参考訳（メタデータ） (2021-02-09T05:35:53Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - The Convergence Indicator: Improved and completely characterized
parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
我々は、粒子が最終的に単一点に収束するか、分岐するかを計算するのに使用できる新しい収束指標を導入する。
この収束指標を用いて、収束群につながるパラメータ領域を完全に特徴づける実際の境界を提供する。
論文 参考訳（メタデータ） (2020-06-06T19:08:05Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。