論文の概要: Improved Coresets for Euclidean $k$-Means
- arxiv url: http://arxiv.org/abs/2211.08184v2
- Date: Wed, 16 Nov 2022 06:42:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 16:33:01.904723
- Title: Improved Coresets for Euclidean $k$-Means
- Title(参考訳): ユークリッド$k$-Meansのための改善されたCoreset
- Authors: Vincent Cohen-Addad and Kasper Green Larsen and David Saulpic and
Chris Schwiegelshohn and Omar Ali Sheikh-Omar
- Abstract要約: 1組の$d$次元の$n$ポイントが与えられたとき、ユークリッド$k$平均問題(ユークリッド$k$中間問題を参照)は、$k$センターを見つけることからなる。
本稿では,$tilde O(min(k2 cdot varepsilon-2,kcdot varepsilon-4)$ for $k$-means and $tilde O(min(k4/3 cdot varepsilon)を改善する。
- 参考スコア(独自算出の注目度): 24.850829728643923
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a set of $n$ points in $d$ dimensions, the Euclidean $k$-means problem
(resp. the Euclidean $k$-median problem) consists of finding $k$ centers such
that the sum of squared distances (resp. sum of distances) from every point to
its closest center is minimized. The arguably most popular way of dealing with
this problem in the big data setting is to first compress the data by computing
a weighted subset known as a coreset and then run any algorithm on this subset.
The guarantee of the coreset is that for any candidate solution, the ratio
between coreset cost and the cost of the original instance is less than a
$(1\pm \varepsilon)$ factor. The current state of the art coreset size is
$\tilde O(\min(k^{2} \cdot \varepsilon^{-2},k\cdot \varepsilon^{-4}))$ for
Euclidean $k$-means and $\tilde O(\min(k^{2} \cdot \varepsilon^{-2},k\cdot
\varepsilon^{-3}))$ for Euclidean $k$-median. The best known lower bound for
both problems is $\Omega(k \varepsilon^{-2})$. In this paper, we improve the
upper bounds $\tilde O(\min(k^{3/2} \cdot \varepsilon^{-2},k\cdot
\varepsilon^{-4}))$ for $k$-means and $\tilde O(\min(k^{4/3} \cdot
\varepsilon^{-2},k\cdot \varepsilon^{-3}))$ for $k$-median. In particular, ours
is the first provable bound that breaks through the $k^2$ barrier while
retaining an optimal dependency on $\varepsilon$.
- Abstract(参考訳): d$次元において n$ 個の点が与えられると、ユークリッドの $k$-means 問題(つまり、ユークリッドの $k$-median 問題)は、すべての点から最も近い中心までの距離(距離の和)の和が最小となるような $k$ 中心を見つけることで成り立っている。
ビッグデータ設定でこの問題に対処する最も一般的な方法は、まずcoresetとして知られる重み付きサブセットを演算し、次にこのサブセット上でアルゴリズムを実行することでデータを圧縮することである。
コアセットの保証は、任意の候補解に対して、コアセットコストと元のインスタンスのコストの比率が$(1\pm \varepsilon)$ factor未満であることである。
現在のアートコアセットサイズは$\tilde O(\min(k^{2} \cdot \varepsilon^{-2},k\cdot \varepsilon^{-4}))$ for Euclidean $k$-means and $\tilde O(\min(k^{2} \cdot \varepsilon^{-2},k\cdot \varepsilon^{-3})$ for Euclidean $k$-medianである。
両問題の最もよく知られた下限は$\omega(k \varepsilon^{-2})$である。
本稿では、上界を$\tilde O(\min(k^{3/2} \cdot \varepsilon^{-2},k\cdot \varepsilon^{-4})$ for $k$-means and $\tilde O(\min(k^{4/3} \cdot \varepsilon^{-2},k\cdot \varepsilon^{-3})$ for $k$-medianとする。
特に、最初の証明可能な境界は$k^2$障壁を破り、$\varepsilon$への最適な依存を維持している。
関連論文リスト
- $\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) - Towards Optimal Lower Bounds for k-median and k-means Coresets [25.713987341159918]
計量空間における点の集合が与えられたとき、$(k,z)$-クラスタリング問題は、センターと呼ばれる点の集合を見つけることからなる。
我々は、$(k,z)$クラスタリングの任意のコアセットが、少なくとも$Omega(k varepsilon-2 log n)$と$Omega(k varepsilon-2 D)$ポイントでなければならないことを示す。
論文 参考訳(メタデータ) (2022-02-25T16:13:28Z) - 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) - Approximate Maximum Halfspace Discrepancy [6.35821487778241]
範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。
数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
論文 参考訳(メタデータ) (2021-06-25T19:14:45Z) - Self-training Converts Weak Learners to Strong Learners in Mixture
Models [86.7137362125503]
擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。
さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
論文 参考訳(メタデータ) (2021-06-25T17:59:16Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳(メタデータ) (2020-11-24T22:39:21Z) - Mathematical comparison of classical and quantum mechanisms in
optimization under local differential privacy [0.0]
我々は、$mathrmEC_n(varepsilon)not=mathrmCQ_n(varepsilon)$ for every $nge3$を示し、$mathrmEC_n(varepsilon)$と$mathrmCQ_n(varepsilon)$の差をある方法で見積もる。
論文 参考訳(メタデータ) (2020-11-19T17:05:11Z) - Optimal Coreset for Gaussian Kernel Density Estimation [0.8376091455761259]
点集合 $Psubset mathbbRd$ が与えられたとき、$P$ の核密度推定は [ overlinemathcalG_P(x) = frac1left|Pright|sum_pin Pe-leftlVert x-p rightrVert2 ] for any $xinmathbbRd$ と定義される。
我々は、小さなサブセット$Q$ of $P を構築する方法を研究する。
論文 参考訳(メタデータ) (2020-07-15T22:58:50Z) - Sets Clustering [25.358415142404752]
我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。
このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。
オープンソースコードと文書分類および施設位置の実験結果も提供される。
論文 参考訳(メタデータ) (2020-03-09T13:30:30Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳(メタデータ) (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。