論文の概要: Mini-batch $k$-means terminates within $O(d/\epsilon)$ iterations

• arxiv url: http://arxiv.org/abs/2304.00419v1
• Date: Sun, 2 Apr 2023 00:58:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-04 18:17:35.583344
• Title: Mini-batch $k$-means terminates within $O(d/\epsilon)$ iterations
• Title（参考訳）: Mini-batch $k$-meansが$O(d/\epsilon)$ iterations内で終了する
• Authors: Gregory Schwartzman
• Abstract要約: サンプルバッチにおけるクラスタリングの品質改善がしきい値以下である場合にのみ終了するミニバッチ$k$-meansについて検討する。 一見すると、このアルゴリズムは永遠に実行可能であるように見えるが、上記の疑問に肯定的に答える。 我々は,Scikit-learn (sklearn) pythonライブラリに実装されたミニバッチ$k$-meansアルゴリズムの適用性を示す。
• 参考スコア（独自算出の注目度）: 0.07614628596146598
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We answer the question: "Does local progress (on batches) imply global progress (on the entire dataset) for mini-batch $k$-means?". Specifically, we consider mini-batch $k$-means which terminates only when the improvement in the quality of the clustering on the sampled batch is below some threshold. Although at first glance it appears that this algorithm might execute forever, we answer the above question in the affirmative and show that if the batch is of size $\tilde{\Omega}((d/\epsilon)^2)$, it must terminate within $O(d/\epsilon)$ iterations with high probability, where $d$ is the dimension of the input, and $\epsilon$ is a threshold parameter for termination. This is true regardless of how the centers are initialized. When the algorithm is initialized with the $k$-means++ initialization scheme, it achieves an approximation ratio of $O(\log k)$ (the same as the full-batch version). Finally, we show the applicability of our results to the mini-batch $k$-means algorithm implemented in the scikit-learn (sklearn) python library.
• Abstract（参考訳）: ローカルな進捗(バッチ)は、ミニバッチの$k$-meansのグローバルな進捗(データセット全体)を意味するのでしょうか? 具体的には、サンプルバッチにおけるクラスタリングの品質改善がしきい値以下である場合にのみ終了するミニバッチ$k$-meansを検討する。 一見すると、このアルゴリズムは永久に実行されるように見えるが、肯定的に上記の質問に答えると、バッチのサイズが$\tilde{\omega}((d/\epsilon)^2)$であれば、$d$が入力の次元であり、$\epsilon$が終了のしきい値パラメータであるような高い確率で$o(d/\epsilon)$イテレーションを終了しなければならない。 これはセンタの初期化方法に関わらず当てはまります。 アルゴリズムが$k$-means++の初期化スキームで初期化されると、その近似比は$O(\log k)$(フルバッチ版と同じ)となる。 最後に、scikit-learn (sklearn) pythonライブラリに実装されたmini-batch $k$-meansアルゴリズムに対する結果の適用性を示す。

関連論文リスト

• Mini-Batch Kernel $k$-means [4.604003661048267]
  私たちのアルゴリズムの1つのイテレーションは$widetildeO(kb2)$時間であり、フルバッチカーネルの$k$-meansに必要な$O(n2)$時間よりもはるかに高速です。 実験により,本アルゴリズムは品質の低下を最小限に抑えた10-100倍の高速化を実現していることがわかった。
  論文  参考訳（メタデータ） (2024-10-08T10:59:14Z)
• Multiple-policy Evaluation via Density Estimation [30.914344538340412]
  本稿では,この問題に対して$mathrmCAESAR$というアルゴリズムを提案する。 低次かつ対数的な$mathrmCAESAR$は、$tildeOleft(fracH4epsilon2sum_h=1Hmax_kin[K]sum_s,afrac(d_hpik(s,a))2mu*_h(s,a)right)$である。
  論文  参考訳（メタデータ） (2024-03-29T23:55:25Z)
• 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)
• Data Structures for Density Estimation [66.36971978162461]
  p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。 また、Acharyaなどのアルゴリズムの改良版も提供します。
  論文  参考訳（メタデータ） (2023-06-20T06:13:56Z)
• A Nearly Tight Analysis of Greedy k-means++ [1.452875650827562]
  k$-means++アルゴリズムは期待して$Theta(log k)$近似解を返すことが知られている。 我々は、greedy $k$-means++アルゴリズムに対して、ほぼ一致する下界と上界を示す。
  論文  参考訳（メタデータ） (2022-07-16T13:49:07Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• 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)

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

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