論文の概要: Closing the convergence gap of SGD without replacement
- arxiv url: http://arxiv.org/abs/2002.10400v6
- Date: Thu, 9 Jul 2020 14:18:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-29 03:39:31.927768
- Title: Closing the convergence gap of SGD without replacement
- Title（参考訳）: 置換なしでSGDの収束ギャップを閉鎖する
- Authors: Shashank Rajput, Anant Gupta and Dimitris Papailiopoulos
- Abstract要約: モデルトレーニングでは,置換サンプリングを伴わない勾配降下が広く用いられている。
置換のない SGD は、関数の和が二次であるときに $mathcalOleft(frac1T2+fracn2T3right)$ を達成することを示す。
- 参考スコア（独自算出の注目度）: 9.109788577327503
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic gradient descent without replacement sampling is widely used in
practice for model training. However, the vast majority of SGD analyses assumes
data is sampled with replacement, and when the function minimized is strongly
convex, an $\mathcal{O}\left(\frac{1}{T}\right)$ rate can be established when
SGD is run for $T$ iterations. A recent line of breakthrough works on SGD
without replacement (SGDo) established an
$\mathcal{O}\left(\frac{n}{T^2}\right)$ convergence rate when the function
minimized is strongly convex and is a sum of $n$ smooth functions, and an
$\mathcal{O}\left(\frac{1}{T^2}+\frac{n^3}{T^3}\right)$ rate for sums of
quadratics. On the other hand, the tightest known lower bound postulates an
$\Omega\left(\frac{1}{T^2}+\frac{n^2}{T^3}\right)$ rate, leaving open the
possibility of better SGDo convergence rates in the general case. In this
paper, we close this gap and show that SGD without replacement achieves a rate
of $\mathcal{O}\left(\frac{1}{T^2}+\frac{n^2}{T^3}\right)$ when the sum of the
functions is a quadratic, and offer a new lower bound of
$\Omega\left(\frac{n}{T^2}\right)$ for strongly convex functions that are sums
of smooth functions.
- Abstract（参考訳）: 置換サンプリングのない確率勾配降下は、モデルトレーニングの実践に広く用いられている。
しかし、SGD分析の大多数は、データが置換でサンプリングされることを前提としており、関数の最小化が強い凸であれば、$\mathcal{O}\left(\frac{1}{T}\right)$ rateは、SGDが$T$反復で実行されるときに確立される。
最近のsgdoにおける画期的な研究は、最小化された関数が強凸であり、n$の滑らかな関数の和である場合の$\mathcal{o}\left(\frac{n}{t^2}\right)$収束率と、二次和に対する$\mathcal{o}\left(\frac{1}{t^2}+\frac{n^3}{t^3}\right)$率を確立した。
一方、最も厳密な既知の下界は$\Omega\left(\frac{1}{T^2}+\frac{n^2}{T^3}\right)$ rateを仮定し、一般の場合においてより良いSGDo収束率の可能性を開放する。
本稿では,このギャップを閉じて,関数の和が二次的であるときに,置換のないsgd が $\mathcal{o}\left(\frac{1}{t^2}+\frac{n^2}{t^3}\right)$ の率を達成し,滑らかな関数の和である強凸函数に対して $\omega\left(\frac{n}{t^2}\right)$ の新たな下限を与えることを示す。
関連論文リスト
- Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction [16.82220229840038]
それぞれ$mathcalO(d1/2T-1/2 + dn-1/2)$と$mathcalO(d1/4T-1/4)$の収束率を改善する2つの新しいアルゴリズムを導入する。
提案手法の有効性を検証した数値実験を行った。
論文 参考訳（メタデータ） (2024-06-01T16:38:43Z) - Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳（メタデータ） (2023-05-10T01:12:11Z) - Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。
我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
論文 参考訳（メタデータ） (2023-02-13T18:13:36Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - The Convergence Rate of SGD's Final Iterate: Analysis on Dimension
Dependence [2.512827436728378]
Gradient Descent (SGD) は最適化において最も単純で一般的な手法の一つである。
定次元設定におけるSGDの最終点収束を特徴付ける方法を示す。
論文 参考訳（メタデータ） (2021-06-28T11:51:04Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。