論文の概要: 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})$よりもずっと良くなる。
関連論文リスト
- Complexity of Minimizing Projected-Gradient-Dominated Functions with Stochastic First-order Oracles [38.45952947660789]
本稿では,$(alpha,tau,mathcal)$-projected-dominanceプロパティの下で関数を最小化する一階法の性能限界について検討する。
論文 参考訳（メタデータ） (2024-08-03T18:34:23Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Transformer In-Context Learning for Categorical Data [51.23121284812406]
我々は、分類結果、非線形基礎モデル、非線形注意を考慮し、文脈内学習のレンズを通してトランスフォーマーを理解する研究を機能データで拡張する。
我々は、ImageNetデータセットを用いて、この数発の学習方法論の最初の実世界の実演であると考えられるものを提示する。
論文 参考訳（メタデータ） (2024-05-27T15:03:21Z) - On the Complexity of Finite-Sum Smooth Optimization under the
Polyak-{\L}ojasiewicz Condition [14.781921087738967]
本稿では、$min_bf xinmathbb Rd f(bf x)triangleq frac1nsum_i=1n f_i(bf x)$, ここで、$f(cdot)$はパラメータ$mu$と$f_i(cdot)_i=1n$は$L$-mean-squared smoothである。
論文 参考訳（メタデータ） (2024-02-04T17:14:53Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - 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) - 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) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。