論文の概要: Random Reshuffling: Simple Analysis with Vast Improvements
- arxiv url: http://arxiv.org/abs/2006.05988v3
- Date: Mon, 5 Apr 2021 11:40:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-23 05:16:11.802492
- Title: Random Reshuffling: Simple Analysis with Vast Improvements
- Title（参考訳）: ランダムリシャッフル: 最悪の改善を伴う簡易解析
- Authors: Konstantin Mishchenko and Ahmed Khaled and Peter Richt\'arik
- Abstract要約: ランダムリシャッフル(Random Reshuffling, RR)は、データリシャッフルと共に反復降下ステップを利用する有限サム関数を最小化するアルゴリズムである。
- 参考スコア（独自算出の注目度）: 9.169947558498535
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Random Reshuffling (RR) is an algorithm for minimizing finite-sum functions
that utilizes iterative gradient descent steps in conjunction with data
reshuffling. Often contrasted with its sibling Stochastic Gradient Descent
(SGD), RR is usually faster in practice and enjoys significant popularity in
convex and non-convex optimization. The convergence rate of RR has attracted
substantial attention recently and, for strongly convex and smooth functions,
it was shown to converge faster than SGD if 1) the stepsize is small, 2) the
gradients are bounded, and 3) the number of epochs is large. We remove these 3
assumptions, improve the dependence on the condition number from $\kappa^2$ to
$\kappa$ (resp. from $\kappa$ to $\sqrt{\kappa}$) and, in addition, show that
RR has a different type of variance. We argue through theory and experiments
that the new variance type gives an additional justification of the superior
performance of RR. To go beyond strong convexity, we present several results
for non-strongly convex and non-convex objectives. We show that in all cases,
our theory improves upon existing literature. Finally, we prove fast
convergence of the Shuffle-Once (SO) algorithm, which shuffles the data only
once, at the beginning of the optimization process. Our theory for
strongly-convex objectives tightly matches the known lower bounds for both RR
and SO and substantiates the common practical heuristic of shuffling once or
only a few times. As a byproduct of our analysis, we also get new results for
the Incremental Gradient algorithm (IG), which does not shuffle the data at
all.
- Abstract（参考訳）: ランダムリシャッフル(Random Reshuffling、RR)は、データリシャッフルと共に反復勾配降下ステップを利用する有限サム関数を最小化するアルゴリズムである。
SGD (Stochastic Gradient Descent) とは対照的に、RRは通常より高速で、凸最適化や非凸最適化でかなりの人気がある。
近年, rr の収束速度は注目され, 強凸および滑らかな関数の場合, sgd よりも高速に収束することが示されている。
1)ステップが小さい。
2)勾配は境界であり
3)エポックの数は多い。
これらの3つの仮定を取り除き、条件番号への依存度を$\kappa^2$から$\kappa$ (resp。
$\kappa$ から $\sqrt{\kappa}$) へ、さらに、RR が異なる種類の分散を持つことを示す。
我々は理論と実験を通じて、新しい分散型はRRの優れた性能のさらなる正当化を与えると論じる。
強い凸性を超えて、非強凸および非凸目的に対するいくつかの結果を示す。
いずれにせよ、我々の理論は既存の文献によって改善されている。
最後に、最適化プロセスの開始時に1回だけデータをシャッフルするShuffle-Once(SO)アルゴリズムの高速収束を証明した。
強凸目的に関する我々の理論は、RRとSOの双方の既知の下界と密に一致し、シャッフルの一般的な実践的ヒューリスティックを1回または数回しか証明しない。
分析の副産物として、データシャッフルを行わないインクリメンタル勾配アルゴリズム(ig)の新たな結果も得られました。
関連論文リスト
- On the Last-Iterate Convergence of Shuffling Gradient Methods [21.865728815935665]
対象値に関して勾配法をシャッフルする際の最終点収束率を初めて証明する。
我々の結果は、(ほぼ)既存のラストイテレートの下限と一致するか、あるいは、平均的なイテレートの前の最高の上限と同速である。
論文 参考訳（メタデータ） (2024-03-12T15:01:17Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization [6.314057999212246]
ランダムリシャッフル技術は、ニューラルネットワークのような大規模アプリケーションで使用される。
本稿では,ノルムPRRが生成するランダムリシャッフル型反復が線形設定に収束することを示す。
最後に,提案手法に適用可能な最終収束率を導出する。
論文 参考訳（メタデータ） (2023-12-02T07:12:00Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳（メタデータ） (2022-04-20T07:14:21Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Distributed Random Reshuffling over Networks [7.013052033764372]
凸関数と滑らかな対象関数の問題を解くために分散resh-upr (D-RR) アルゴリズムを提案する。
特に、滑らかな凸対象関数に対して、D-RRはD-T収束率(T がエポック数を数える)を大域ドライブ間の距離で達成する。
論文 参考訳（メタデータ） (2021-12-31T03:59:37Z) - Random Reshuffling with Variance Reduction: New Analysis and Better
Rates [0.8594140167290099]
一般問題に対するRRSVRG(Random Reshuffling)の最初の解析を提供します。
rrsvrgは、ほぼ広く使われている$mathcalo(kappa3/2)レートで$calo(kappa3/2)に改善できる。
これは以前の最高の$mathcalO(kappa3/2) RRSVRGメソッドを改善します。
論文 参考訳（メタデータ） (2021-04-19T14:30:10Z) - Proximal and Federated Random Reshuffling [11.83842808044211]
ランダムリシャッフルのための2つの新しいアルゴリズムを提案する。
ProxRR と FedRR は複合凸有限和最小化問題を解く。
ProxRRは、各イテレーションの近位演算子を評価するアルゴリズムよりも高速です。
論文 参考訳（メタデータ） (2021-02-12T18:59:24Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。