論文の概要: Towards Tight Communication Lower Bounds for Distributed Optimisation
- arxiv url: http://arxiv.org/abs/2010.08222v3
- Date: Tue, 7 Dec 2021 13:49:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-06 22:16:21.049944
- Title: Towards Tight Communication Lower Bounds for Distributed Optimisation
- Title（参考訳）: 分散最適化のためのタイト通信低境界に向けて
- Authors: Dan Alistarh and Janne H. Korhonen
- Abstract要約: N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。
我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。
我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
- 参考スコア（独自算出の注目度）: 30.134447658488057
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a standard distributed optimisation setting where $N$ machines,
each holding a $d$-dimensional function $f_i$, aim to jointly minimise the sum
of the functions $\sum_{i = 1}^N f_i (x)$. This problem arises naturally in
large-scale distributed optimisation, where a standard solution is to apply
variants of (stochastic) gradient descent. We focus on the communication
complexity of this problem: our main result provides the first fully
unconditional bounds on total number of bits which need to be sent and received
by the $N$ machines to solve this problem under point-to-point communication,
within a given error-tolerance. Specifically, we show that $\Omega( Nd \log d /
N\varepsilon)$ total bits need to be communicated between the machines to find
an additive $\epsilon$-approximation to the minimum of $\sum_{i = 1}^N f_i
(x)$. The result holds for both deterministic and randomised algorithms, and,
importantly, requires no assumptions on the algorithm structure. The lower
bound is tight under certain restrictions on parameter values, and is matched
within constant factors for quadratic objectives by a new variant of quantised
gradient descent, which we describe and analyse. Our results bring over tools
from communication complexity to distributed optimisation, which has potential
for further applications.
- Abstract（参考訳）: N$ マシンが$d$次元関数 $f_i$ を持ち、関数 $\sum_{i = 1}^N f_i (x)$ の和を最小化することを目的とする標準的な分散最適化設定を考える。
この問題は、(確率的な)勾配勾配の変種を標準解で適用する大規模分散最適化において自然に発生する。
私たちの主な結果は、与えられたエラー許容範囲内で、ポイントツーポイント通信の下でこの問題を解決するために、n$マシンによって送信され、受信する必要があるビットの総数について、最初の完全な無条件境界を提供します。
具体的には、$\omega( nd \log d / n\varepsilon)$ 合計ビットをマシン間で通信し、最小$\sum_{i = 1}^n f_i (x)$ に対して$\epsilon$近似を求める必要がある。
その結果、決定論的アルゴリズムとランダム化アルゴリズムの両方が成り立ち、重要なことは、アルゴリズム構造に仮定を必要としないことである。
下限はパラメータ値に対する一定の制限の下で厳密であり、我々が記述し分析する量子化勾配降下の新しい変種によって二次目的の定数因子内で一致している。
私たちの結果は、通信の複雑さから分散最適化に至るまでのツールをもたらします。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample
Complexity [25.775517797956237]
本稿では,Douubly Compressed Momentum-assisted tracking algorithm $ttDoCoM$ for communicationを提案する。
我々のアルゴリズムは、実際にいくつかの最先端のアルゴリズムより優れていることを示す。
論文 参考訳（メタデータ） (2022-02-01T07:27:34Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。