論文の概要: $\ell_p$-Regression in the Arbitrary Partition Model of Communication
- arxiv url: http://arxiv.org/abs/2307.05117v1
- Date: Tue, 11 Jul 2023 08:51:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-12 15:43:36.910755
- Title: $\ell_p$-Regression in the Arbitrary Partition Model of Communication
- Title（参考訳）: 任意分割通信モデルにおける$\ell_p$-regression
- Authors: Yi Li, Honghao Lin, David P. Woodruff
- Abstract要約: コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
- 参考スコア（独自算出の注目度）: 59.89387020011663
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the randomized communication complexity of the distributed
$\ell_p$-regression problem in the coordinator model, for $p\in (0,2]$. In this
problem, there is a coordinator and $s$ servers. The $i$-th server receives
$A^i\in\{-M, -M+1, \ldots, M\}^{n\times d}$ and $b^i\in\{-M, -M+1, \ldots,
M\}^n$ and the coordinator would like to find a $(1+\epsilon)$-approximate
solution to $\min_{x\in\mathbb{R}^n} \|(\sum_i A^i)x - (\sum_i b^i)\|_p$. Here
$M \leq \mathrm{poly}(nd)$ for convenience. This model, where the data is
additively shared across servers, is commonly referred to as the arbitrary
partition model.
We obtain significantly improved bounds for this problem. For $p = 2$, i.e.,
least squares regression, we give the first optimal bound of
$\tilde{\Theta}(sd^2 + sd/\epsilon)$ bits.
For $p \in (1,2)$,we obtain an $\tilde{O}(sd^2/\epsilon +
sd/\mathrm{poly}(\epsilon))$ upper bound. Notably, for $d$ sufficiently large,
our leading order term only depends linearly on $1/\epsilon$ rather than
quadratically. We also show communication lower bounds of $\Omega(sd^2 +
sd/\epsilon^2)$ for $p\in (0,1]$ and $\Omega(sd^2 + sd/\epsilon)$ for $p\in
(1,2]$. Our bounds considerably improve previous bounds due to (Woodruff et al.
COLT, 2013) and (Vempala et al., SODA, 2020).
- Abstract（参考訳）: コーディネータモデルにおける分散$\ell_p$-regression問題のランダム化通信複雑性を$p\in (0,2]$とみなす。
この問題では、コーディネータと$s$サーバーがあります。
$i$-thサーバは$A^i\in\{-M, -M+1, \ldots, M\}^{n\times d}$および$b^i\in\{-M, -M+1, \ldots, M\}^n$を受け取り、コーディネータは$(1+\epsilon)$-approximate Solution to $\min_{x\in\mathbb{R}^n} \|(\sum_i A^i)x - (\sum_i b^i)\|_p$を求める。
ここで、利便性のために$m \leq \mathrm{poly}(nd)$ である。
このモデルでは、データはサーバ間で付加的に共有され、一般に任意のパーティションモデルと呼ばれる。
この問題の限界は大幅に改善されている。
p = 2$、すなわち最小二乗回帰に対して、最初の最適境界は$\tilde{\Theta}(sd^2 + sd/\epsilon)$ bitsである。
p \in (1,2) に対して、$\tilde{O}(sd^2/\epsilon + sd/\mathrm{poly}(\epsilon))$上界を得る。
特に、$d$十分に大きい場合は、先頭の項は2次ではなく1/\epsilon$にのみ依存する。
また、$\Omega(sd^2 + sd/\epsilon^2)$ for $p\in (0,1]$と$\Omega(sd^2 + sd/\epsilon)$ for $p\in (1,2]$の通信下界を示す。
我々の限界は、Woodruff et al. COLT, 2013) と (Vempala et al., SODA, 2020) により、以前の限界を大幅に改善する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。
1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
論文 参考訳（メタデータ） (2024-06-04T15:50:42Z) - Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。
我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
論文 参考訳（メタデータ） (2024-05-25T08:34:49Z) - 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) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳（メタデータ） (2021-03-17T00:59:33Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。