Fugu-MT 論文翻訳(概要): Revisiting Distributed Sign-Based Variance Reduction

論文の概要: Revisiting Distributed Sign-Based Variance Reduction

arxiv url: http://arxiv.org/abs/2609.18656v1
Date: Wed, 16 Sep 2026 13:35:52 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-20 08:55:53.822186
Title: Revisiting Distributed Sign-Based Variance Reduction
Title（参考訳）: 分散署名に基づく可変化の再検討
Abstract要約: 署名ベースの圧縮されたコンポーネントリフレッシュは、データが不均一である場合にバイアスを発生させることができる。本稿では,符号に基づく手法が,非和点と正確な局所点の両方に対して最適収束率を得ることができないことを示す。結果として得られるサンプルの総和は$M+dsa-2$と$O(M+O)$ for $M+$と$ell$$ grade norms at most $$$と$O(M+O)$ for $M+O$である。
参考スコア（独自算出の注目度）: 41.0127093986946
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Sign-based methods reduce communication costs in distributed environments, but aggregating local signs can introduce bias when data are heterogeneous. As a result, existing sign-based variance reduction methods fail to obtain the optimal convergence rates. In this paper, we solve this problem and obtain optimal rates for both nonconvex stochastic and finite-sum optimization. We first give a counterexample showing that majority voting can fail to approach stationary points even with exact local gradients. Motivated by this limitation, we propose tracking the global gradient at the server through unbiased compression of recursive gradient increments. As a result, we can obtain the convergence rates of $O(\sqrt{d/K}+\sqrt d (a/(nK))^{1/3})$ for the $\ell_1$-norm and $O(\sqrt{a/K}+\sqrt a/(nK)^{1/3})$ for the $\ell_2$-norm. Here, $K$ is the iteration number, $n$ is the number of workers, $d$ is the dimension, and $a=1+ω$, with $ω$ denoting the compressor's relative variance. For finite-sum problems with $M$ components, we combine periodic exact gradient refreshes with compressed component-gradient differences. The resulting total sample complexities are $O(M+d\sqrt{aM}ε^{-2})$ and $O(M+a\sqrt M\ epsilon^{-2})$ for $\ell_1$ and $\ell_2$ gradient norms at most $ε$, matching the corresponding bounds in centralized settings.
Abstract（参考訳）: 信号ベースの手法は分散環境における通信コストを低減させるが、局所的な信号の集約は、データが不均一である場合にバイアスをもたらす可能性がある。その結果、既存の符号ベースの分散還元法は最適収束率を得ることができない。本稿では,この問題を解き,非凸確率および有限サム最適化の最適値を求める。まず、局所勾配が正確になくても多数決が定常点に近づくことができないことを示す。この制限により,再帰的勾配増加の非バイアス圧縮によるサーバのグローバル勾配の追跡を提案する。その結果、$O(\sqrt{d/K}+\sqrt d (a/(nK))^{1/3})$ for the $\ell_1$-norm and $O(\sqrt{a/K}+\sqrt a/(nK)^{1/3})$ for the $\ell_2$-norm。ここで、$K$は反復数、$n$は労働者数、$d$は次元、$a=1+ω$は圧縮機の相対的分散を表す$ω$である。 M$成分を持つ有限サム問題に対して、周期的正確な勾配修正と圧縮された成分勾配差を組合せる。結果として得られるサンプルの総和は$O(M+d\sqrt{aM}ε^{-2})$と$O(M+a\sqrt M\epsilon^{-2})$ for $\ell_1$と$\ell_2$の勾配ノルムで、対応する境界を集中的に設定する。

論文の概要: Revisiting Distributed Sign-Based Variance Reduction

関連論文リスト