論文の概要: New Bounds For Distributed Mean Estimation and Variance Reduction
- arxiv url: http://arxiv.org/abs/2002.09268v4
- Date: Wed, 7 Apr 2021 15:50:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 00:59:55.829963
- Title: New Bounds For Distributed Mean Estimation and Variance Reduction
- Title（参考訳）: 分散平均推定と分散低減のための新しい境界
- Authors: Peter Davies, Vijaykrishna Gurunathan, Niusha Moshrefi, Saleh
Ashkboos, Dan Alistarh
- Abstract要約: 本稿では,ローカルな$d$-dimensional vector $x_v を mathbbRd$ で与えられた$n$マシンが分散平均推定(DME)問題を考える。
提案手法は, 従来の手法と比較して, 応用の実践的改善をもたらすことを示す。
- 参考スコア（独自算出の注目度）: 25.815612182815702
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of distributed mean estimation (DME), in which $n$
machines are each given a local $d$-dimensional vector $x_v \in \mathbb{R}^d$,
and must cooperate to estimate the mean of their inputs $\mu = \frac 1n\sum_{v
= 1}^n x_v$, while minimizing total communication cost.
DME is a fundamental construct in distributed machine learning, and there has
been considerable work on variants of this problem, especially in the context
of distributed variance reduction for stochastic gradients in parallel SGD.
Previous work typically assumes an upper bound on the norm of the input
vectors, and achieves an error bound in terms of this norm. However, in many
real applications, the input vectors are concentrated around the correct output
$\mu$, but $\mu$ itself has large norm. In such cases, previous output error
bounds perform poorly.
In this paper, we show that output error bounds need not depend on input
norm. We provide a method of quantization which allows distributed mean
estimation to be performed with solution quality dependent only on the distance
between inputs, not on input norm, and show an analogous result for distributed
variance reduction. The technique is based on a new connection with lattice
theory. We also provide lower bounds showing that the communication to error
trade-off of our algorithms is asymptotically optimal.
As the lattices achieving optimal bounds under $\ell_2$-norm can be
computationally impractical, we also present an extension which leverages
easy-to-use cubic lattices, and is loose only up to a logarithmic factor in
$d$. We show experimentally that our method yields practical improvements for
common applications, relative to prior approaches.
- Abstract（参考訳）: 分散平均推定(DME)の問題を考えると、$n$マシンは局所的な$d$次元ベクトルである$x_v \in \mathbb{R}^d$をそれぞれ与え、合計通信コストを最小化しながら、それらの入力の平均を$\mu = \frac 1n\sum_{v = 1} x_v$と見積もる必要がある。
DMEは分散機械学習の基本的な構成であり、特に並列SGDにおける確率勾配の分散分散分散分散分散化の文脈において、この問題の変種についてかなりの研究がなされている。
以前の仕事は、通常、入力ベクトルのノルムの上界を仮定し、このノルムの項で境界付けられた誤差を達成する。
しかし、多くの実アプリケーションでは、入力ベクトルは正しい出力である\mu$の周りに集中するが、$\mu$自体は大きなノルムを持つ。
このような場合、前の出力エラー境界は不十分である。
本稿では,出力誤差境界が入力規範に依存しないことを示す。
本稿では,入力ノルムではなく入力間の距離にのみ依存して,分散平均推定を解品質で行うことができ,分散分散分散の低減に類似した結果を示す量子化法を提案する。
この手法は格子理論との新しい関係に基づいている。
また,アルゴリズムの誤りトレードオフに対する通信が漸近的に最適であることを示す下位境界も提供する。
また、$\ell_2$-norm の下で最適境界を成す格子は計算上非実用的であるため、使い易い立方格子を活用できる拡張も提示し、d$ の対数係数まで緩やかである。
提案手法は, 従来の手法と比較して, 応用の実践的改善をもたらすことを示す。
関連論文リスト
- Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias [13.642712817536072]
問題の次元が$d$になるにつれて、所望の誤差内で収束を保証するのに必要なイテレーションの数が増加することを示す。
私たちが取り組んだ重要な技術的課題は、収束を測定するための$W_2,ellinfty$メートル法に一段階の縮約性がないことである。
論文 参考訳（メタデータ） (2024-08-20T01:24:54Z) - Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond $1+\alpha$ Moments [10.889739958035536]
本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。
平均値の中央値は近傍最適であり, 一定の要因が得られている。
定数係数のずれのない近傍分離推定器を見つけることは自由である。
論文 参考訳（メタデータ） (2023-11-21T18:50:38Z) - Estimation of entropy-regularized optimal transport maps between
non-compactly supported measures [15.857723276537248]
本稿では,ガウシアン以下の音源と目標測度の間の2乗ユークリッドコストでエントロピー規則化された最適輸送マップを推定する問題に対処する。
論文 参考訳（メタデータ） (2023-11-20T17:18:21Z) - Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳（メタデータ） (2023-01-31T18:47:42Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳（メタデータ） (2022-01-05T15:17:35Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。
我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。
我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
論文 参考訳（メタデータ） (2020-10-16T08:10:02Z) - Log-Likelihood Ratio Minimizing Flows: Towards Robust and Quantifiable
Neural Distribution Alignment [52.02794488304448]
そこで本研究では,対数様比統計量と正規化フローに基づく新しい分布アライメント手法を提案する。
入力領域の局所構造を保存する領域アライメントにおいて,結果の最小化を実験的に検証する。
論文 参考訳（メタデータ） (2020-03-26T22:10:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。