論文の概要: A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs

• arxiv url: http://arxiv.org/abs/2502.02085v1
• Date: Tue, 04 Feb 2025 08:05:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 14:53:18.170618
• Title: A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs
• Title（参考訳）: トレードオフを改善した$k$-$\mathtt{means}$++に対する新しいリジェクションサンプリングアプローチ
• Authors: Poojan Shah, Shashwat Agrawal, Ragesh Jaiswal,
• Abstract要約: 単純かつ効果的なリジェクションサンプリングに基づくアプローチで,$k$-$mathttmeans$++ を高速化する。 最初のメソッドは $tildeO(mathttnnz (mathcalX) + beta k2d)$ で実行されます。 第2の手法は,計算コストと解品質の新たなトレードオフを示す。
• 参考スコア（独自算出の注目度）: 0.12289361708127876
• License:
• Abstract: The $k$-$\mathtt{means}$++ seeding algorithm (Arthur & Vassilvitskii, 2007) is widely used in practice for the $k$-means clustering problem where the goal is to cluster a dataset $\mathcal{X} \subset \mathbb{R} ^d$ into $k$ clusters. The popularity of this algorithm is due to its simplicity and provable guarantee of being $O(\log k)$ competitive with the optimal solution in expectation. However, its running time is $O(|\mathcal{X}|kd)$, making it expensive for large datasets. In this work, we present a simple and effective rejection sampling based approach for speeding up $k$-$\mathtt{means}$++. Our first method runs in time $\tilde{O}(\mathtt{nnz} (\mathcal{X}) + \beta k^2d)$ while still being $O(\log k )$ competitive in expectation. Here, $\beta$ is a parameter which is the ratio of the variance of the dataset to the optimal $k$-$\mathtt{means}$ cost in expectation and $\tilde{O}$ hides logarithmic factors in $k$ and $|\mathcal{X}|$. Our second method presents a new trade-off between computational cost and solution quality. It incurs an additional scale-invariant factor of $ k^{-\Omega( m/\beta)} \operatorname{Var} (\mathcal{X})$ in addition to the $O(\log k)$ guarantee of $k$-$\mathtt{means}$++ improving upon a result of (Bachem et al, 2016a) who get an additional factor of $m^{-1}\operatorname{Var}(\mathcal{X})$ while still running in time $\tilde{O}(\mathtt{nnz}(\mathcal{X}) + mk^2d)$. We perform extensive empirical evaluations to validate our theoretical results and to show the effectiveness of our approach on real datasets.
• Abstract（参考訳）: k$-$\matht{means}$++ シードアルゴリズム (Arthur & Vassilvitskii, 2007) は、データセット $\mathcal{X} \subset \mathbb{R} ^d$ を$k$クラスタにクラスタ化することを目標とする$k$-meansクラスタリング問題において、実際に広く使われている。 このアルゴリズムの人気は、期待する最適解と競合する$O(\log k)$の単純かつ証明可能な保証のためである。 しかし、実行時間は$O(|\mathcal{X}|kd)$であり、大規模なデータセットには高価である。 そこで本研究では,$k$-$\mathtt{means}$++を高速化するための,シンプルかつ効果的な拒絶サンプリングに基づくアプローチを提案する。 私たちの最初のメソッドは時間$\tilde{O}(\mathtt{nnz} (\mathcal{X}) + \beta k^2d)$ で実行されます。 ここで、$\beta$はデータセットの分散を最適な$k$-$\matht{means}$期待のコストと$\tilde{O}$が$k$と$|\mathcal{X}|$に隠すパラメータである。 第2の手法は,計算コストと解品質の新たなトレードオフを示す。 k^{-\Omega(m/\beta)} \operatorname{Var} (\mathcal{X})$に加え、$O(\log k)$ guarantee of $k$-$\matht{means}$++ improve on a result of (Bachem et al, 2016a) who get a additional factor of $m^{-1}\operatorname{Var}(\mathcal{X})$ while while still running in time $\tilde{O}(\matht{nnz}(\mathcal{X}) + mk^2d)$。 我々は、理論結果の検証と、実際のデータセットに対するアプローチの有効性を示すために、広範な経験的評価を行う。

関連論文リスト

• Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
  シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。 適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
  論文  参考訳（メタデータ） (2024-11-08T17:10:38Z)
• 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)
• 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)
• Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
  本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。 mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
  論文  参考訳（メタデータ） (2023-10-02T16:44:47Z)
• Improved Outlier Robust Seeding for k-means [3.9973713691377646]
  逆ノイズや外れ値では、D2$サンプリングは、より遠方の外れ値から中心を選別する傾向にある。 サンプル分布として$D2$の単純な変種を提案する。 我々のアルゴリズムは、$O(k)$クラスタの代わりに正確に$k$クラスタを出力するように修正することもできる。
  論文  参考訳（メタデータ） (2023-09-06T04:46:01Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Near-optimal Algorithms for Explainable k-Medians and k-Means [12.68470213641421]
  Dasgupta, Frost, Moshkovitz, Rashtchian (ICML 2020) が導入した$k$-medians と $k$-means の問題を考える。 私たちのゴールは、データを$kクラスタに分割し、$k-mediansや$k-meansの目的を最小化する、最適な決定ツリーを見つけることです。
  論文  参考訳（メタデータ） (2021-07-02T02:07:12Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。