論文の概要: 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$への最適な依存を維持している。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Nearly Linear Sparsification of $\ell_p$ Subspace Approximation [47.790126028106734]
$ell_p$ 部分空間近似問題のNP硬度に対処する一般的なアプローチは、強いコアセットを計算することである。
我々は、$ell_p$部分空間近似に対して、ランクパラメータ$k$にほぼ最適に依存する強いコアセットを構築するための最初のアルゴリズムを得る。
我々の手法は、オフライン設定と同様のバウンダリを持つ$ell_p$サブスペース近似のための、ほぼ最適に近いオンライン強力なコアセットにも繋がる。
論文 参考訳（メタデータ） (2024-07-03T16:49:28Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - 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) - $\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) - 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) - Sets Clustering [25.358415142404752]
我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。
このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。
オープンソースコードと文書分類および施設位置の実験結果も提供される。
論文 参考訳（メタデータ） (2020-03-09T13:30:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。