論文の概要: 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の収束解析を行うことである。
分析フレームワークでは、主要なステップと中核的なアイデアをまとめています。
このフレームワークの直接的な応用として、シャッフル近位点法に対する同様の強い極限点収束結果を確立する。
関連論文リスト
- Nearly Optimal Sample Complexity of Offline KL-Regularized Contextual Bandits under Single-Policy Concentrability [49.96531901205305]
我々は,オフラインの文脈的包帯に対する単一政治中心性の下でのサンプル複雑性を$tildeO(epsilon-1)$とするemphfirstアルゴリズムを提案する。
我々の証明は、KL正則化の強い凸性と、真の報酬と悲観的推定子のギャップの条件的非負性を利用する。
我々は,このアルゴリズムを文脈的デュエル帯域に拡張し,ほぼ最適なサンプル複雑性を実現する。
論文 参考訳（メタデータ） (2025-02-09T22:14:45Z) - Shifted Composition III: Local Error Framework for KL Divergence [12.93725028754563]
引数の結合は、2つのプロセス間の偏差を境界付ける中心的なツールである。
カップリングの議論をKL(Kulback-Leibler)の発散に適用する。
論文 参考訳（メタデータ） (2024-12-23T21:40:01Z) - Enhancing Convergence of Decentralized Gradient Tracking under the KL Property [10.925931212031692]
我々は,分散勾配追跡に基づくアルゴリズムであるSONATAに対して,同じタイプの収束性を確立する。
これは、いつを除いて集中的な勾配アルゴリズムの収束挙動と一致する。
thetain (1/2,1)$, sub rate is confirmed; and
textbf(iii)$ if $thetain (1/2, 1)$, sub rate is certificate; and
textbf(iii)$ if $thetain (1/2,1)$, sub rate が認証される。
論文 参考訳（メタデータ） (2024-12-12T18:44:36Z) - 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) - On the Linear Convergence of Policy Gradient under Hadamard
Parameterization [4.182089296199263]
本研究では,アダマールパラメータ化に基づく決定論的政策勾配の収束性について検討する。
すべてのイテレーションに対して$O(frac1k)$レートでエラーが減少することを示す。
論文 参考訳（メタデータ） (2023-05-31T05:51:15Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。