Fugu-MT 論文翻訳(概要): Mini-Batch Kernel $k$-means

論文の概要: Mini-Batch Kernel $k$-means

arxiv url: http://arxiv.org/abs/2410.05902v1
Date: Tue, 8 Oct 2024 10:59:14 GMT
ステータス: 処理完了
システム内更新日: 2024-11-01 12:10:29.848392
Title: Mini-Batch Kernel $k$-means
Title（参考訳）: Mini-Batch Kernel $k$-means
Authors: Ben Jourdan, Gregory Schwartzman,
Abstract要約: 私たちのアルゴリズムの1つのイテレーションは$widetildeO(kb2)$時間であり、フルバッチカーネルの$k$-meansに必要な$O(n2)$時間よりもはるかに高速です。実験により,本アルゴリズムは品質の低下を最小限に抑えた10-100倍の高速化を実現していることがわかった。
参考スコア（独自算出の注目度）: 4.604003661048267
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We present the first mini-batch kernel $k$-means algorithm, offering an order of magnitude improvement in running time compared to the full batch algorithm. A single iteration of our algorithm takes $\widetilde{O}(kb^2)$ time, significantly faster than the $O(n^2)$ time required by the full batch kernel $k$-means, where $n$ is the dataset size and $b$ is the batch size. Extensive experiments demonstrate that our algorithm consistently achieves a 10-100x speedup with minimal loss in quality, addressing the slow runtime that has limited kernel $k$-means adoption in practice. We further complement these results with a theoretical analysis under an early stopping condition, proving that with a batch size of $\widetilde{\Omega}(\max \{\gamma^{4}, \gamma^{2}\} \cdot \epsilon^{-2})$, the algorithm terminates in $O(\gamma^2/\epsilon)$ iterations with high probability, where $\gamma$ bounds the norm of points in feature space and $\epsilon$ is a termination threshold. Our analysis holds for any reasonable center initialization, and when using $k$-means++ initialization, the algorithm achieves an approximation ratio of $O(\log k)$ in expectation. For normalized kernels, such as Gaussian or Laplacian it holds that $\gamma=1$. Taking $\epsilon = O(1)$ and $b=\Theta(\log n)$, the algorithm terminates in $O(1)$ iterations, with each iteration running in $\widetilde{O}(k)$ time.
Abstract（参考訳）: 本稿では,最初のミニバッチカーネル$k$-meansアルゴリズムを提案する。我々のアルゴリズムの1つのイテレーションは、$\widetilde{O}(kb^2)$時間であり、フルバッチカーネルの$k$-meansで必要となる$O(n^2)$時間よりもはるかに高速である。大規模な実験により、我々のアルゴリズムは最小品質の損失を最小限に抑えた10-100倍のスピードアップを一貫して達成し、実際にカーネルが$k$-meansに制限された遅いランタイムに対処することを示した。さらに、これらの結果を早期停止条件下で理論解析し、バッチサイズが$\widetilde{\Omega}(\max \{\gamma^{4}, \gamma^{2}\} \cdot \epsilon^{-2})$で、アルゴリズムは高い確率で$O(\gamma^2/\epsilon)$イテレーションを終了し、$\gamma$は特徴空間における点のノルムを束縛し、$\epsilon$は終端しきい値であることを示す。我々の解析は任意の合理的な中心初期化を保ち、$k$-means++初期化を使用する場合、アルゴリズムは予想で$O(\log k)$の近似比を達成できる。ガウスやラプラシアンのような正規化された核に対しては、$\gamma=1$である。 $\epsilon = O(1)$ と $b=\Theta(\log n)$ とすると、アルゴリズムは$O(1)$イテレーションで終了し、各イテレーションは $\widetilde{O}(k)$タイムで実行される。

関連論文リスト

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)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文参考訳（メタデータ） (2023-08-16T06:46:37Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Mini-batch $k$-means terminates within $O(d/\epsilon)$ iterations [0.07614628596146598]
サンプルバッチにおけるクラスタリングの品質改善がしきい値以下である場合にのみ終了するミニバッチ$k$-meansについて検討する。一見すると、このアルゴリズムは永遠に実行可能であるように見えるが、上記の疑問に肯定的に答える。我々は,Scikit-learn (sklearn) pythonライブラリに実装されたミニバッチ$k$-meansアルゴリズムの適用性を示す。
論文参考訳（メタデータ） (2023-04-02T00:58:29Z)
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文参考訳（メタデータ） (2022-12-03T02:45:23Z)
A Faster $k$-means++ Algorithm [11.428775569173638]
ほぼ最適な実行時間で$k$-means++問題を解決するアルゴリズムを提案する。我々は、$widetildeO(nd + nk2)$時間しかかからない新しいアルゴリズムtextscFastKmeans++を提案する。
論文参考訳（メタデータ） (2022-11-28T08:17:12Z)
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文参考訳（メタデータ） (2021-06-16T03:34:14Z)
On Robust Optimal Transport: Computational Complexity, Low-rank Approximation, and Barycenter Computation [14.80695185915604]
我々は、最適なトランスポートの2つの頑健なバージョン、$textitRobust Semi-constrained Optimal Transport$ (RSOT) と $textitRobust Unconstrained Optimal Transport$ (ROT) を考える。離散設定における両方の問題に対して、$widetildemathcalO(fracn2varepsilon)$timeでRSOTとROTの$varepsilon$-approximationsを生成するSinkhornベースのアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-02-13T03:55:52Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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