論文の概要: Locally Private $k$-Means Clustering with Constant Multiplicative
Approximation and Near-Optimal Additive Error
- arxiv url: http://arxiv.org/abs/2105.15007v1
- Date: Mon, 31 May 2021 14:41:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-01 22:26:36.734277
- Title: Locally Private $k$-Means Clustering with Constant Multiplicative
Approximation and Near-Optimal Additive Error
- Title（参考訳）: 定乗法近似と準最適加算誤差を用いた局所プライベート$k$-Meansクラスタリング
- Authors: Anamay Chaturvedi, Matthew Jones, Huy L. Nguyen
- Abstract要約: 2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。
局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
- 参考スコア（独自算出の注目度）: 10.632986841188
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a data set of size $n$ in $d'$-dimensional Euclidean space, the
$k$-means problem asks for a set of $k$ points (called centers) so that the sum
of the $\ell_2^2$-distances between points of a given data set of size $n$ and
the set of $k$ centers is minimized. Recent work on this problem in the locally
private setting achieves constant multiplicative approximation with additive
error $\tilde{O} (n^{1/2 + a} \cdot k \cdot \max \{\sqrt{d}, \sqrt{k} \})$ and
proves a lower bound of $\Omega(\sqrt{n})$ on the additive error for any
solution with a constant number of rounds. In this work we bridge the gap
between the exponents of $n$ in the upper and lower bounds on the additive
error with two new algorithms. Given any $\alpha>0$, our first algorithm
achieves a multiplicative approximation guarantee which is at most a
$(1+\alpha)$ factor greater than that of any non-private $k$-means clustering
algorithm with $k^{\tilde{O}(1/\alpha^2)} \sqrt{d' n} \mbox{poly}\log n$
additive error. Given any $c>\sqrt{2}$, our second algorithm achieves $O(k^{1 +
\tilde{O}(1/(2c^2-1))} \sqrt{d' n} \mbox{poly} \log n)$ additive error with
constant multiplicative approximation. Both algorithms go beyond the
$\Omega(n^{1/2 + a})$ factor that occurs in the additive error for arbitrarily
small parameters $a$ in previous work, and the second algorithm in particular
shows for the first time that it is possible to solve the locally private
$k$-means problem in a constant number of rounds with constant factor
multiplicative approximation and polynomial dependence on $k$ in the additive
error arbitrarily close to linear.
- Abstract（参考訳）: 大きさ$n$ in $d'$-次元ユークリッド空間のデータセットが与えられたとき、$k$-平均問題は、与えられた大きさのデータセットの点間の$\ell_2^2$-距離の和が$n$と$k$中心の集合が最小となるように、$k$点(センターと呼ばれる)の集合を求める。
局所的プライベートな設定におけるこの問題に関する最近の研究は、加法誤差$\tilde{O} (n^{1/2 + a} \cdot k \cdot \max \{\sqrt{d}, \sqrt{k} \})$で定数乗法近似を達成し、一定の数のラウンドを持つ任意の解に対する$\Omega(\sqrt{n})$の低い境界を証明している。
この研究では、2つの新しいアルゴリズムで加算誤差の上界と下界に$n$の指数の間のギャップを橋渡しします。
任意の$\alpha>0$が与えられた場合、我々の最初のアルゴリズムは、少なくとも$(1+\alpha)$ファクタが$k^{\tilde{O}(1/\alpha^2)} \sqrt{d' n} \mbox{poly}\log n$加法誤差を持つ任意の非プライベートな$k$-meansクラスタリングアルゴリズムよりも大きい乗法近似を保証する。
任意の$c>\sqrt{2}$が与えられると、第2のアルゴリズムは、定数乗算近似を伴う加法誤差$o(k^{1 + \tilde{o}(1/(2c^2-1))} \sqrt{d' n} \mbox{poly} \log n)$ を達成する。
どちらのアルゴリズムも、前回の作業で任意に小さいパラメータの加法誤差で発生する$\omega(n^{1/2 + a})$ factorを超越しており、特に第2のアルゴリズムは、任意に線形に近い加法誤差の$k$に対する定数因子乗法近似と多項式依存性を持つ一定数のラウンドにおいて、局所的にプライベートな$k$-means問題を解くことができることを初めて示している。
関連論文リスト
- $\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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Parameterized Approximation for Robust Clustering in Discrete Geometric
Spaces [0.6732660670243813]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。
また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文 参考訳（メタデータ） (2023-05-12T08:43:28Z) - Bicriteria Approximation Algorithms for Priority Matroid Median [1.7188280334580193]
我々は、プライオリティを$k$-Median問題に一般化する、プライオリティ・マトロイド・メディア問題を考える。
目標は、mathcalF ff_iの$sum_iを最小化するために、サブセット$S subseteq MathcalF$を選択することである。
論文 参考訳（メタデータ） (2022-10-04T20:19:55Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - 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) - Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization
Domain [11.562923882714093]
Y f(x,y) における max_y の $min_x 形式の最適化問題における近似一階定常点の探索問題について検討する。
我々のアプローチは、関数 $f(x,cdot)$ を $k 次テイラー近似($y$ で)に置き換え、ほぼ定常点を $Y$ で見つけることに依存する。
論文 参考訳（メタデータ） (2021-10-08T07:46:18Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Subspace approximation with outliers [6.186553186139257]
本稿では, オフリヤを用いた部分空間近似問題に対するサンプリングに基づいて, 次元削減手法と双基準近似を拡張する方法を示す。
我々の結果は、0 delta leq 1 - α$ が満たされる条件が満たされる限り、alpha$ が大きければ成り立つ。
論文 参考訳（メタデータ） (2020-06-30T07:22: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。