論文の概要: 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})$で収束させます。
シミュレーションおよび実世界の問題に関する実験を通じて理論的知見をバックアップし、ランダムにリシャッフルされた手話法が既存のベースラインに一致するか、あるいは超えるかを検証する。
関連論文リスト
- Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。
我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
論文 参考訳(メタデータ) (2024-03-05T12:28:00Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - 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) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳(メタデータ) (2022-06-16T17:10:57Z) - A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning [3.655021726150368]
マルチエージェント強化学習(MARL: Multi-Agent Reinforcement Learning)では、複数のエージェントが共通の環境と相互作用し、シーケンシャルな意思決定において共有問題を解く。
我々は、MARLで有用な分散非線形近似スキームの族を反復する新しい法則を導出する。
論文 参考訳(メタデータ) (2021-10-27T08:01:17Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳(メタデータ) (2021-07-22T14:25:16Z) - Complexity of zigzag sampling algorithm for strongly log-concave
distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。
ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文 参考訳(メタデータ) (2020-12-21T03:10:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。