論文の概要: Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex
Optimization
- arxiv url: http://arxiv.org/abs/2310.15976v1
- Date: Tue, 24 Oct 2023 16:25:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-25 17:48:47.446857
- Title: Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex
Optimization
- Title（参考訳）: 非凸最適化のための符号ベースランダムリシャッフルアルゴリズムの収束
- Authors: Zhen Qin, Zhishuai Liu, Pan Xu
- Abstract要約: SignSGDは通信効率のために非最適化で人気がある。
Sign は$O(log(nT)/stnT + |sigma2$, ここで (log(nT)/stnT)$ はデータセットサイズである。
シミュレーションおよび実世界の問題に関する実験を通じて理論的知見をバックアップし、ランダムにリシャッフルされた手話法が既存のベースラインに一致するか、あるいは超えるかを検証する。
- 参考スコア（独自算出の注目度）: 14.69450310695133
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: signSGD is popular in nonconvex optimization due to its communication
efficiency. Yet, existing analyses of signSGD rely on assuming that data are
sampled with replacement in each iteration, contradicting the practical
implementation where data are randomly reshuffled and sequentially fed into the
algorithm. We bridge this gap by proving the first convergence result of
signSGD with random reshuffling (SignRR) for nonconvex optimization. Given the
dataset size $n$, the number of epochs of data passes $T$, and the variance
bound of a stochastic gradient $\sigma^2$, we show that SignRR has the same
convergence rate $O(\log(nT)/\sqrt{nT} + \|\sigma\|_1)$ as signSGD
\citep{bernstein2018signsgd}. We then present SignRVR and SignRVM, which
leverage variance-reduced gradients and momentum updates respectively, both
converging at $O(\log(nT)/\sqrt{nT})$. In contrast with the analysis of
signSGD, our results do not require an extremely large batch size in each
iteration to be of the same order as the total number of iterations
\citep{bernstein2018signsgd} or the signs of stochastic and true gradients
match element-wise with a minimum probability of 1/2
\citep{safaryan2021stochastic}. We also extend our algorithms to cases where
data are distributed across different machines, yielding dist-SignRVR and
dist-SignRVM, both converging at $O(\log(n_0T)/\sqrt{n_0T})$, where $n_0$ is
the dataset size of a single machine. We back up our theoretical findings
through experiments on simulated and real-world problems, verifying that
randomly reshuffled sign methods match or surpass existing baselines.
- Abstract（参考訳）: signSGDは通信効率のために非凸最適化で人気がある。
しかし、既存のSignSGDの分析では、データが各反復でサンプル化され、ランダムにリシャッフルされ、アルゴリズムにシーケンシャルに供給される実践的な実装と矛盾する、と仮定している。
非凸最適化のためのランダムリシャッフル(SignRR)を用いたSignSGDの最初の収束結果を証明することにより、このギャップを埋める。
データセットのサイズが$n$、データのエポック数が$t$、確率勾配 $\sigma^2$ の分散境界が与えられると、signgd \citep{bernstein2018signsgd} と同じ収束率 $o(\log(nt)/\sqrt{nt} + \|\sigma\|_1$ が signgd と同じであることが分かる。
次に,分散勾配と運動量更新をそれぞれ利用する signrvr と signrvm を示し,それぞれ$o(\log(nt)/\sqrt{nt})$ で収束させる。
signgdの分析とは対照的に、各イテレーションで非常に大きなバッチサイズが必要はなく、イテレーションの総数である \citep{bernstein2018signsgd} や、確率的かつ真の勾配の符号は、要素ごとに最小確率1/2 \citep{safaryan2021stochastic} で一致している。
また、異なるマシンに分散している場合にもアルゴリズムを拡張し、dist-signrvrとdist-signrvmを生成し、どちらも$o(\log(n_0t)/\sqrt{n_0t})$で収束させます。
シミュレーションおよび実世界の問題に関する実験を通じて理論的知見をバックアップし、ランダムにリシャッフルされた手話法が既存のベースラインに一致するか、あるいは超えるかを検証する。
関連論文リスト
- Variable Selection in Convex Piecewise Linear Regression [5.366354612549172]
本稿では,凸片方向線形回帰における変数選択の解としてスパース勾配を提案する。
亜ガウス雑音下でのSpGDには非漸近局所収束解析が提供される。
論文 参考訳（メタデータ） (2024-11-04T16:19:09Z) - Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - On the Convergence of a Federated Expectation-Maximization Algorithm [0.0]
本稿では,Federated Mixture of $K$ Linear Regressionsモデルに対する期待最大化(EM)アルゴリズムの収束率について検討する。
驚くべきことに、結果はボトルネックではなく、データの異質性によってフェデレート学習アルゴリズムの収束が加速することを示している。
論文 参考訳（メタデータ） (2024-08-11T16:46:42Z) - 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) - 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) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - 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) - On the Minimax Optimality of the EM Algorithm for Learning Two-Component
Mixed Linear Regression [30.09238179576628]
信号-雑音比(SNR)の全ての条件下での2成分混合線形回帰学習のためのEMアルゴリズムの収束率について検討する。
EMアルゴリズムは,すべてのSNR条件下で,最小限のサンプル複雑性を実現する。
論文 参考訳（メタデータ） (2020-06-04T00:56:07Z) - Non-asymptotic Convergence of Adam-type Reinforcement Learning
Algorithms under Markovian Sampling [56.394284787780364]
本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。
一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。
線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
論文 参考訳（メタデータ） (2020-02-15T00:26:49Z) - Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。
Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
論文 参考訳（メタデータ） (2020-01-25T14:44:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。