論文の概要: Error Feedback Shines when Features are Rare
- arxiv url: http://arxiv.org/abs/2305.15264v1
- Date: Wed, 24 May 2023 15:52:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-25 14:40:59.942535
- Title: Error Feedback Shines when Features are Rare
- Title（参考訳）: 特徴が希少なときにエラーフィードバックが輝く
- Authors: Peter Richt\'arik, Elnur Gasanov, Konstantin Burlachenko
- Abstract要約: 例えば、$left(colorgreensf GDright)$ with greedy sparsilonleft(colorgreensf TopKright)$ can solve $colorgreensf GD when distributed_xin math_xin bbRd f(x)=frac1nsum_i=1n f_i(x)$。
- 参考スコア（独自算出の注目度）: 3.2872586139884623
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide the first proof that gradient descent $\left({\color{green}\sf
GD}\right)$ with greedy sparsification $\left({\color{green}\sf TopK}\right)$
and error feedback $\left({\color{green}\sf EF}\right)$ can obtain better
communication complexity than vanilla ${\color{green}\sf GD}$ when solving the
distributed optimization problem $\min_{x\in \mathbb{R}^d}
{f(x)=\frac{1}{n}\sum_{i=1}^n f_i(x)}$, where $n$ = # of clients, $d$ = # of
features, and $f_1,\dots,f_n$ are smooth nonconvex functions. Despite intensive
research since 2014 when ${\color{green}\sf EF}$ was first proposed by Seide et
al., this problem remained open until now. We show that ${\color{green}\sf EF}$
shines in the regime when features are rare, i.e., when each feature is present
in the data owned by a small number of clients only. To illustrate our main
result, we show that in order to find a random vector $\hat{x}$ such that
$\lVert {\nabla f(\hat{x})} \rVert^2 \leq \varepsilon$ in expectation,
${\color{green}\sf GD}$ with the ${\color{green}\sf Top1}$ sparsifier and
${\color{green}\sf EF}$ requires ${\cal O} \left(\left( L+{\color{blue}r}
\sqrt{ \frac{{\color{red}c}}{n} \min \left( \frac{{\color{red}c}}{n} \max_i
L_i^2, \frac{1}{n}\sum_{i=1}^n L_i^2 \right) }\right) \frac{1}{\varepsilon}
\right)$ bits to be communicated by each worker to the server only, where $L$
is the smoothness constant of $f$, $L_i$ is the smoothness constant of $f_i$,
${\color{red}c}$ is the maximal number of clients owning any feature ($1\leq
{\color{red}c} \leq n$), and ${\color{blue}r}$ is the maximal number of
features owned by any client ($1\leq {\color{blue}r} \leq d$). Clearly, the
communication complexity improves as ${\color{red}c}$ decreases (i.e., as
features become more rare), and can be much better than the ${\cal
O}({\color{blue}r} L \frac{1}{\varepsilon})$ communication complexity of
${\color{green}\sf GD}$ in the same regime.
- Abstract（参考訳）: We provide the first proof that gradient descent $\left({\color{green}\sf GD}\right)$ with greedy sparsification $\left({\color{green}\sf TopK}\right)$ and error feedback $\left({\color{green}\sf EF}\right)$ can obtain better communication complexity than vanilla ${\color{green}\sf GD}$ when solving the distributed optimization problem $\min_{x\in \mathbb{R}^d} {f(x)=\frac{1}{n}\sum_{i=1}^n f_i(x)}$, where $n$ = # of clients, $d$ = # of features, and $f_1,\dots,f_n$ are smooth nonconvex functions.
2014年に${\color{green}\sf EF}$がSeideらによって最初に提案されて以来、集中的な研究が続けられたが、この問題は現在まで未解決のままである。
例えば、少数のクライアントが所有するデータに各機能が存在している場合に、その機能が希少である場合に、${\color{green}\sf EF}$が政権に輝くことを示す。
To illustrate our main result, we show that in order to find a random vector $\hat{x}$ such that $\lVert {\nabla f(\hat{x})} \rVert^2 \leq \varepsilon$ in expectation, ${\color{green}\sf GD}$ with the ${\color{green}\sf Top1}$ sparsifier and ${\color{green}\sf EF}$ requires ${\cal O} \left(\left( L+{\color{blue}r} \sqrt{ \frac{{\color{red}c}}{n} \min \left( \frac{{\color{red}c}}{n} \max_i L_i^2, \frac{1}{n}\sum_{i=1}^n L_i^2 \right) }\right) \frac{1}{\varepsilon} \right)$ bits to be communicated by each worker to the server only, where $L$ is the smoothness constant of $f$, $L_i$ is the smoothness constant of $f_i$, ${\color{red}c}$ is the maximal number of clients owning any feature ($1\leq {\color{red}c} \leq n$), and ${\color{blue}r}$ is the maximal number of features owned by any client ($1\leq {\color{blue}r} \leq d$).
明らかに、通信複雑性は、${\color{red}c}$が減少するにつれて改善され(つまり、機能がより稀になるにつれて)、同じ状態にある${\color{green}\sf GD}$の通信複雑性は${\cal O}({\color{blue}r} L \frac{1}{\varepsilon})$よりもずっと良くなる。
関連論文リスト
- Matching upper bounds on symmetric predicates in quantum communication
complexity [0.0]
共役共役が許されるとき、f circ G = f(G)mathrmQCC_mathrmE(G)) という形の関数の量子通信複雑性に焦点を当てる。
我々は,同じ文が共用絡み合いを持たないことを示し,その結果を一般化する。
論文 参考訳（メタデータ） (2023-01-01T08:30:35Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple,
and Practical [1.2183405753834562]
有限集合系 $(X,mathcal S)$ が与えられたとき、2色の $chi:Xto-1,1$ は数学的な S|chi(S)|$ において $max_S として定義される。
我々は、任意の$d>0$と$(X,mathcal S)$に対して、二重シャッター関数 $pi*(k)=O(kd)$ のランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-02T15:59:09Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Complexity and Avoidance [0.0]
適切な$f$と$p$に対して$q$と$g$があり、$mathrmLUA(q) leq_mathrms mathrmCOMPLEX(f)$と$q$と$g$の成長率があることを示す。
シフト複雑性に関して、$$$q$が$rmLUA(q)$の任意のメンバに対して、$delta$-shift複素列を計算するためにどれだけ遅くなるかという明示的な境界が与えられる。
論文 参考訳（メタデータ） (2022-04-24T14:36:38Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - DIPPA: An improved Method for Bilinear Saddle Point Problems [18.65143269806133]
本稿では,min_bfx max_bfy g(fracx) + bfxtop bfbftop fracbfa kappa_x kappa_x (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y)について述べる。
論文 参考訳（メタデータ） (2021-03-15T10:55:30Z) - Deep Neural Networks with ReLU-Sine-Exponential Activations Break Curse
of Dimensionality on H\"older Class [6.476766717110237]
活性化関数としてReLU,sine,2x$のニューラルネットワークを構築した。
スーパー表現力に加えて、ReLU-sine-$2x$ネットワークで実装された関数は(一般化)微分可能である。
論文 参考訳（メタデータ） (2021-02-28T15:57:42Z) - Revisiting EXTRA for Smooth Distributed Optimization [70.65867695317633]
改良された$Oleft(left(fracLmu+frac11-sigma_2(W)right)logfrac1epsilon (1-sigma_2(W))right)$。
高速化されたEXTRAの通信複雑性は、$left(logfracLmu (1-sigma_2(W))right)$と$left(logfrac1epsilon (1。
論文 参考訳（メタデータ） (2020-02-24T08:07:08Z) - Few-Shot Learning via Learning the Representation, Provably [115.7367053639605]
本稿では,表現学習による少数ショット学習について検討する。
1つのタスクは、ターゲットタスクのサンプルの複雑さを減らすために、$T$ソースタスクと$n_1$データを使用して表現を学習する。
論文 参考訳（メタデータ） (2020-02-21T17:30:00Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。