論文の概要: ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full
Gradient Computation
- arxiv url: http://arxiv.org/abs/2103.01447v1
- Date: Tue, 2 Mar 2021 03:31:06 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-03 15:42:21.340899
- Title: ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full
Gradient Computation
- Title（参考訳）: ZeroSARAH:ゼロフルグラデーション計算による効率的な非凸有限数最適化
- Authors: Zhize Li, Peter Richt\'arik
- Abstract要約: 本稿では,SARnIDER法の新しい勾配計算法を提案する。
この新しい方法は最もよく知られた$n1/2勾配計算を必要としない。
また、新しい最新結果を得ることもできる。
- 参考スコア（独自算出の注目度）: 17.259824817932294
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose ZeroSARAH -- a novel variant of the variance-reduced method SARAH
(Nguyen et al., 2017) -- for minimizing the average of a large number of
nonconvex functions $\frac{1}{n}\sum_{i=1}^{n}f_i(x)$. To the best of our
knowledge, in this nonconvex finite-sum regime, all existing variance-reduced
methods, including SARAH, SVRG, SAGA and their variants, need to compute the
full gradient over all $n$ data samples at the initial point $x^0$, and then
periodically compute the full gradient once every few iterations (for SVRG,
SARAH and their variants). Moreover, SVRG, SAGA and their variants typically
achieve weaker convergence results than variants of SARAH: $n^{2/3}/\epsilon^2$
vs. $n^{1/2}/\epsilon^2$. ZeroSARAH is the first variance-reduced method which
does not require any full gradient computations, not even for the initial
point. Moreover, ZeroSARAH obtains new state-of-the-art convergence results,
which can improve the previous best-known result (given by e.g., SPIDER,
SpiderBoost, SARAH, SSRGD and PAGE) in certain regimes. Avoiding any full
gradient computations (which is a time-consuming step) is important in many
applications as the number of data samples $n$ usually is very large.
Especially in the distributed setting, periodic computation of full gradient
over all data samples needs to periodically synchronize all machines/devices,
which may be impossible or very hard to achieve. Thus, we expect that ZeroSARAH
will have a practical impact in distributed and federated learning where full
device participation is impractical.
- Abstract（参考訳）: 本稿では,多数の非凸関数 $\frac{1}{n}\sum_{i=1}^{n}f_i(x)$ の平均を最小化するために,分散還元法 SARAH (Nguyen et al., 2017) の新しい変種である ZeroSARAH を提案する。
我々の知る限り、この非凸有限サム法では、SARAH, SVRG, SAGA およびそれらの変種を含む既存の分散還元法は、初期点 $x^0$ ですべての$n$のデータサンプルの完全な勾配を計算し、数回の繰り返し(SVRG, SARAH およびそれらの変種)で周期的に全勾配を計算する必要がある。
さらに、SVRG、SAGAおよびそれらの変種は通常、SARAHの変種よりも弱い収束結果が得られる: $n^{2/3}/\epsilon^2$ vs. $n^{1/2}/\epsilon^2$。
ZeroSARAHは、初期点においても完全な勾配計算を必要としない最初の分散還元法である。
さらに、ZeroSARAHは新たな最先端コンバージェンス結果を得ることができ(例えば、SPIDER、SpiderBoost、SARAH、SSRGD、PAGEなど)、以前の最もよく知られた結果を改善することができる。
データサンプル$n$の数が通常非常に大きいので、すべてのグラデーション計算(これは時間のかかるステップです)を避けることは多くのアプリケーションで重要です。
特に分散設定では、すべてのデータサンプルに対するフルグラデーションの定期的な計算は、すべてのマシン/デバイスを定期的に同期させる必要があります。
したがって、ZeroSARAHは、完全なデバイス参加が現実的でない分散・フェデレーション学習において実践的な影響を期待する。
関連論文リスト
- Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。
本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
論文 参考訳（メタデータ） (2024-10-28T18:19:13Z) - MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。
最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。
一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
論文 参考訳（メタデータ） (2024-05-29T18:36:59Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Variance-reduced accelerated methods for decentralized stochastic
double-regularized nonconvex strongly-concave minimax problems [7.5573375809946395]
我々は、ピアツーピア通信により、$m$のコンピューティングエージェントのネットワークが協調すると考えている。
我々のアルゴリズムフレームワークは、二変数のコンセンサス制約を取り除くために、アグラジアン乗算器を導入している。
我々の知る限りでは、これはNCSCミニマックス問題に対する収束保証を、原始変数と双対変数の両方に適用する一般の非正規化器で提供する最初の研究である。
論文 参考訳（メタデータ） (2023-07-14T01:32:16Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Bounding the Width of Neural Networks via Coupled Initialization -- A
Worst Case Analysis [121.9821494461427]
2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。
また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
論文 参考訳（メタデータ） (2022-06-26T06:51:31Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - 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) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Fast decentralized non-convex finite-sum optimization with recursive
variance reduction [19.540926205375857]
本稿では,SARAH型分散低減技術を用いたGT-SARAHと呼ばれる一階勾配法について述べる。
特に、$n = O(Nfrac12(lambda)3)$のようなビッグデータでは、ネットワークの複雑さとは無関係に、この複雑さは$O(Nfrac12Lepsilon-2)$に減少する。
さらに、局所的なミニバッチサイズの適切な選択は、勾配複雑性と通信複雑性のトレードオフをバランスさせる。
論文 参考訳（メタデータ） (2020-08-17T15:51:32Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。