論文の概要: Differentially private $k$-means clustering via exponential mechanism
and max cover
- arxiv url: http://arxiv.org/abs/2009.01220v1
- Date: Wed, 2 Sep 2020 17:52:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-22 20:03:48.559155
- Title: Differentially private $k$-means clustering via exponential mechanism
and max cover
- Title（参考訳）: 指数的メカニズムと最大被覆による差分プライベート$k$-meansクラスタリング
- Authors: Anamay Chaturvedi, Huy Nguyen, Eric Xu
- Abstract要約: 我々は、$k$-meansクラスタリング問題に対して、新しい$(epsilon_p, delta_p)$-differentially privateアルゴリズムを導入する。
- 参考スコア（独自算出の注目度）: 6.736814259597673
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce a new $(\epsilon_p, \delta_p)$-differentially private algorithm
for the $k$-means clustering problem. Given a dataset in Euclidean space, the
$k$-means clustering problem requires one to find $k$ points in that space such
that the sum of squares of Euclidean distances between each data point and its
closest respective point among the $k$ returned is minimised. Although there
exist privacy-preserving methods with good theoretical guarantees to solve this
problem [Balcan et al., 2017; Kaplan and Stemmer, 2018], in practice it is seen
that it is the additive error which dictates the practical performance of these
methods. By reducing the problem to a sequence of instances of maximum coverage
on a grid, we are able to derive a new method that achieves lower additive
error then previous works. For input datasets with cardinality $n$ and diameter
$\Delta$, our algorithm has an $O(\Delta^2 (k \log^2 n
\log(1/\delta_p)/\epsilon_p + k\sqrt{d \log(1/\delta_p)}/\epsilon_p))$ additive
error whilst maintaining constant multiplicative error. We conclude with some
experiments and find an improvement over previously implemented work for this
problem.
- Abstract（参考訳）: 我々は、k$-meansクラスタリング問題に対して、新しい$(\epsilon_p, \delta_p)$-differentially privateアルゴリズムを導入する。
ユークリッド空間のデータセットが与えられたとき、$k$-meansクラスタリング問題は、各データポイントと返される$k$内の最も近い各ポイントの間のユークリッド距離の合計が最小化されるような、その空間内の$k$ポイントを見つける必要がある。
Balcan et al., 2017; Kaplan and Stemmer, 2018) は、この問題を解決するための優れた理論的保証を持つプライバシー保護方法が存在するが、実際には、これらの手法の実用的な性能を規定する追加エラーである。
グリッド上の最大カバレッジのインスタンス数に問題を縮小することで、以前の処理よりも少ない加算誤差を達成する新しいメソッドを導出することができる。
n$ と直径 $\delta$ の入力データセットに対して、このアルゴリズムは、一定の乗算誤差を維持しながら$o(\delta^2 (k \log^2 n \log(1/\delta_p)/\epsilon_p + k\sqrt{d \log(1/\delta_p)}/\epsilon_p))$加算誤差を持つ。
我々は、いくつかの実験で結論付け、この問題に対する以前実装された作業よりも改善を見出した。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile
Streaming [48.18845814885398]
本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。
高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。
ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
論文 参考訳（メタデータ） (2023-10-29T16:46:26Z) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - Differential Privacy for Clustering Under Continual Observation [5.220940151628734]
我々は、点の挿入と削除の両方を行う$mathbbRd$のデータセットをプライベートにクラスタリングする問題を考える。
連続観測において、$k$-meansの目的に対して、$varepsilon$-differentially private clustering 機構を提供する。
論文 参考訳（メタデータ） (2023-07-07T07:23:56Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Improved Learning-augmented Algorithms for k-means and k-medians
Clustering [8.04779839951237]
学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。
本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。
我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
論文 参考訳（メタデータ） (2022-10-31T03:00:11Z) - 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) - Locally Private $k$-Means Clustering with Constant Multiplicative
Approximation and Near-Optimal Additive Error [10.632986841188]
2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。
局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
論文 参考訳（メタデータ） (2021-05-31T14:41:40Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。