論文の概要: Random Reshuffling with Variance Reduction: New Analysis and Better
Rates
- arxiv url: http://arxiv.org/abs/2104.09342v1
- Date: Mon, 19 Apr 2021 14:30:10 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-20 14:23:16.635738
- Title: Random Reshuffling with Variance Reduction: New Analysis and Better
Rates
- Title（参考訳）: 分散低減によるランダムリシャッフル--新しい解析とより良いレート
- Authors: Grigory Malinovsky, Alibek Sailanbayev, Peter Richt\'arik
- Abstract要約: 一般問題に対するRRSVRG(Random Reshuffling)の最初の解析を提供します。
rrsvrgは、ほぼ広く使われている$mathcalo(kappa3/2)レートで$calo(kappa3/2)に改善できる。
これは以前の最高の$mathcalO(kappa3/2) RRSVRGメソッドを改善します。
- 参考スコア（独自算出の注目度）: 0.8594140167290099
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Virtually all state-of-the-art methods for training supervised machine
learning models are variants of SGD enhanced with a number of additional
tricks, such as minibatching, momentum, and adaptive stepsizes. One of the
tricks that works so well in practice that it is used as default in virtually
all widely used machine learning software is {\em random reshuffling (RR)}.
However, the practical benefits of RR have until very recently been eluding
attempts at being satisfactorily explained using theory. Motivated by recent
development due to Mishchenko, Khaled and Richt\'{a}rik (2020), in this work we
provide the first analysis of SVRG under Random Reshuffling (RR-SVRG) for
general finite-sum problems. First, we show that RR-SVRG converges linearly
with the rate $\mathcal{O}(\kappa^{3/2})$ in the strongly-convex case, and can
be improved further to $\mathcal{O}(\kappa)$ in the big data regime (when $n >
\mathcal{O}(\kappa)$), where $\kappa$ is the condition number. This improves
upon the previous best rate $\mathcal{O}(\kappa^2)$ known for a variance
reduced RR method in the strongly-convex case due to Ying, Yuan and Sayed
(2020). Second, we obtain the first sublinear rate for general convex problems.
Third, we establish similar fast rates for Cyclic-SVRG and Shuffle-Once-SVRG.
Finally, we develop and analyze a more general variance reduction scheme for
RR, which allows for less frequent updates of the control variate. We
corroborate our theoretical results with suitably chosen experiments on
synthetic and real datasets.
- Abstract（参考訳）: 教師付き機械学習モデルをトレーニングするための、事実上すべての最先端の手法は、ミニバッチ、運動量、適応ステップサイズなどの追加のトリックで強化されたSGDの変種である。
事実上広く使われている機械学習ソフトウェアでデフォルトとして使用されるような、実際にうまく機能するトリックの1つは、ランダムリシャッフル(RR)である。
しかし、RRの実践的な利点は、理論を用いて十分に説明される試みを非常に最近まで免れた。
Mishchenko, Khaled and Richt\'{a}rik (2020) による最近の発展によって動機づけられたこの研究において、一般有限サム問題に対するランダムリシャッフル(RR-SVRG)の下でのSVRGの最初の解析を提供する。
まず、RR-SVRG は強凸の場合で $\mathcal{O}(\kappa^{3/2})$ と線形収束し、さらにビッグデータレシスタンス($n > \mathcal{O}(\kappa)$ で $\mathcal{O}(\kappa)$ に改善可能であることを示す。
これにより、Ying, Yuan and Sayed (2020) による強凸の場合の分散還元RR法で知られている前の最高値 $\mathcal{O}(\kappa^2)$ が改善される。
第二に、一般凸問題に対する最初の部分線型率を求める。
第3に、Cyclic-SVRGとShuffle-Once-SVRGに対して同様の高速速度を確立する。
最後に,制御変動の頻繁な更新を可能にするrrのより一般的な分散低減方式を開発し,解析する。
我々は、合成および実データ集合に関する適切に選択された実験で理論結果と照合する。
関連論文リスト
- Asymptotics of Random Feature Regression Beyond the Linear Scaling
Regime [22.666759017118796]
機械学習の最近の進歩は、トレーニングデータの近くにトレーニングされた過度にパラメータ化されたモデルを使用することによって達成されている。
モデル複雑性と一般化はパラメータ数$p$にどのように依存するか?
特に、RFRRは近似と一般化パワーの直感的なトレードオフを示す。
論文 参考訳（メタデータ） (2024-03-13T00:59:25Z) - A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization [6.314057999212246]
ランダムリシャッフル技術は、ニューラルネットワークのような大規模アプリケーションで使用される。
本稿では,ノルムPRRが生成するランダムリシャッフル型反復が線形設定に収束することを示す。
最後に,提案手法に適用可能な最終収束率を導出する。
論文 参考訳（メタデータ） (2023-12-02T07:12:00Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Bounding the Width of Neural Networks via Coupled Initialization -- A
Worst Case Analysis [121.9821494461427]
2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。
また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
論文 参考訳（メタデータ） (2022-06-26T06:51:31Z) - DASHA: Distributed Nonconvex Optimization with Communication
Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。
MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
論文 参考訳（メタデータ） (2022-02-02T20:10:40Z) - Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。
ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。
本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
論文 参考訳（メタデータ） (2021-06-06T19:08:53Z) - Robust Kernel-based Distribution Regression [13.426195476348955]
2段階のサンプリングを含む分布回帰(DR)を研究し、ヒルベルト空間(RKHS)を再現するカーネル上での確率測度から実値応答への回帰を目指す。
2段階サンプリング問題に対するロバストロス関数$l_sigma$の導入により,新たなロバスト分布回帰(RDR)スキームを提案する。
論文 参考訳（メタデータ） (2021-04-21T17:03:46Z) - Proximal and Federated Random Reshuffling [11.83842808044211]
ランダムリシャッフルのための2つの新しいアルゴリズムを提案する。
ProxRR と FedRR は複合凸有限和最小化問題を解く。
ProxRRは、各イテレーションの近位演算子を評価するアルゴリズムよりも高速です。
論文 参考訳（メタデータ） (2021-02-12T18:59:24Z) - Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for
Strongly Convex Decentralized Optimization [69.49313819343992]
広範に使われているEXTRA法とDIG法を拡張し,VR-EXTRA法とVR-DIGing法という2つの手法を提案する。
提案されたVR-EXTRAは、$O(kappa_s+n)logfrac1epsilon)$グラデーション評価と$O(kappa_b+kappa_c)logfrac1epsilon)$通信ラウンドを必要とする。
提案されているVR-DIGingは、O(kappa_b+kappa)の通信コストが少し高い
論文 参考訳（メタデータ） (2020-09-09T15:48:44Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Random Reshuffling: Simple Analysis with Vast Improvements [9.169947558498535]
ランダムリシャッフル(Random Reshuffling, RR)は、データリシャッフルと共に反復降下ステップを利用する有限サム関数を最小化するアルゴリズムである。
論文 参考訳（メタデータ） (2020-06-10T17:57:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。