論文の概要: PAGE: A Simple and Optimal Probabilistic Gradient Estimator for
Nonconvex Optimization
- arxiv url: http://arxiv.org/abs/2008.10898v3
- Date: Fri, 11 Jun 2021 21:37:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-25 02:58:09.509696
- Title: PAGE: A Simple and Optimal Probabilistic Gradient Estimator for
Nonconvex Optimization
- Title（参考訳）: PAGE:非凸最適化のための簡易かつ最適確率勾配推定器
- Authors: Zhize Li, Hongyan Bao, Xiangliang Zhang, Peter Richt\'arik
- Abstract要約: 本報告では,NonpsOmegaのための新しい確率勾配エストリマト(フラスト)を提案する。
小さなPAGEからバニラSGDへと設計されているため、実装が容易である。
トレーニングにおいてSGDよりもはるかに早く収束するだけでなく、高い精度を達成する。
- 参考スコア（独自算出の注目度）: 33.346773349614715
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a novel stochastic gradient estimator --
ProbAbilistic Gradient Estimator (PAGE) -- for nonconvex optimization. PAGE is
easy to implement as it is designed via a small adjustment to vanilla SGD: in
each iteration, PAGE uses the vanilla minibatch SGD update with probability
$p_t$ or reuses the previous gradient with a small adjustment, at a much lower
computational cost, with probability $1-p_t$. We give a simple formula for the
optimal choice of $p_t$. Moreover, we prove the first tight lower bound
$\Omega(n+\frac{\sqrt{n}}{\epsilon^2})$ for nonconvex finite-sum problems,
which also leads to a tight lower bound $\Omega(b+\frac{\sqrt{b}}{\epsilon^2})$
for nonconvex online problems, where $b:= \min\{\frac{\sigma^2}{\epsilon^2},
n\}$. Then, we show that PAGE obtains the optimal convergence results
$O(n+\frac{\sqrt{n}}{\epsilon^2})$ (finite-sum) and
$O(b+\frac{\sqrt{b}}{\epsilon^2})$ (online) matching our lower bounds for both
nonconvex finite-sum and online problems. Besides, we also show that for
nonconvex functions satisfying the Polyak-\L{}ojasiewicz (PL) condition, PAGE
can automatically switch to a faster linear convergence rate $O(\cdot\log
\frac{1}{\epsilon})$. Finally, we conduct several deep learning experiments
(e.g., LeNet, VGG, ResNet) on real datasets in PyTorch showing that PAGE not
only converges much faster than SGD in training but also achieves the higher
test accuracy, validating the optimal theoretical results and confirming the
practical superiority of PAGE.
- Abstract（参考訳）: 本稿では,非凸最適化のための確率勾配推定器-確率勾配推定器(PAGE)を提案する。
PAGE はバニラ SGD への小さな調整によって設計されているため実装が容易であり、各イテレーションでバニラ minibatch SGD 更新を確率 $p_t$ で使用するか、より少ない計算コストで、確率 $1-p_t$ で以前の勾配を再利用する。
p_t$ を最適に選択するための簡単な公式を与える。
さらに、最初の厳密な下界$\Omega(n+\frac{\sqrt{n}}{\epsilon^2})$を非凸有限サム問題に対して証明し、非凸オンライン問題に対して$\Omega(b+\frac{\sqrt{b}}{\epsilon^2})$(b:= \min\{\frac{\sigma^2}{\epsilon^2},n\}$)とする。
次に、PAGE が最適収束結果 $O(n+\frac{\sqrt{n}}{\epsilon^2})$ (finite-sum) および $O(b+\frac{\sqrt{b}}{\epsilon^2})$ (online) を非凸有限サムおよびオンライン問題の両方に対する下界に一致することを示す。
さらに、Polyak-\L{}ojasiewicz (PL)条件を満たす非凸関数に対して、PAGEは自動的により高速な線型収束率$O(\cdot\log \frac{1}{\epsilon})$に切り替えることができる。
最後に、PyTorchの実際のデータセット上でいくつかのディープラーニング実験(LeNet、VGG、ResNetなど)を行い、PAGEはトレーニングにおいてSGDよりもはるかに早く収束するだけでなく、高いテスト精度を実現し、最適理論的結果の検証とPAGEの実用上の優位性を確認する。
関連論文リスト
- Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - (Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentum [7.095058159492494]
ヘビーボール運動量(SHB)は、機械学習モデルのトレーニングに一般的に用いられ、勾配降下の反復よりも経験的な改善を提供することが多い。
SHB は小サイズが $kappa の閾値 $b* よりも大きい場合に加速できることを示す。
論文 参考訳（メタデータ） (2024-01-12T18:17:28Z) - Breaking the Lower Bound with (Little) Structure: Acceleration in
Non-Convex Stochastic Optimization with Heavy-Tailed Noise [28.780192812703948]
重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。
簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。
また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
論文 参考訳（メタデータ） (2023-02-14T00:23:42Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳（メタデータ） (2022-10-25T11:37:11Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Minimax Optimal Regression over Sobolev Spaces via Laplacian
Regularization on Neighborhood Graphs [25.597646488273558]
非パラメトリック回帰に対するグラフに基づくアプローチであるラプラシア平滑化の統計的性質について検討する。
ラプラシアン滑らか化が多様体適応であることを証明する。
論文 参考訳（メタデータ） (2021-06-03T01:20:41Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。