論文の概要: Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling
- arxiv url: http://arxiv.org/abs/2609.06394v1
- Date: Sun, 06 Sep 2026 05:08:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-10 19:44:08.245809
- Title: Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling
- Title（参考訳）: 決定サンプリングによる$k$-Clusteringのための最悪のコアセット境界を超えて
- Abstract要約: 本稿では,指数点法を応用した新しい相関サンプリングフレームワーク「textitdeterminantal sample」を提案する。
効率よく構成可能な$varepsilon$-coreset for $(k,z)$-clustering in $mathbb Rd$ を得る。
これは、これらの下界を極端に超越した仮定によって証明できる最初の結果である。
- 参考スコア（独自算出の注目度）: 2.0357579455195007
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Massive datasets in modern machine learning have made data reduction a central challenge, particularly for clustering tasks where memory and computational constraints demand compact yet faithful summaries. A standard approach is to construct an \textit{$ε$-coreset}: a small weighted subset that approximately preserves the clustering cost for every plausible choice of centers. For the \textit{$(k,z)$-clustering problem}, existing worst-case bounds on coreset size are essentially tight, ruling out substantially smaller coresets in general. However, such worst-case instances are often unrepresentative of real-world data. In this work, we show that significantly smaller coresets are possible under mild and natural assumptions on the underlying data distribution. We introduce a new correlated sampling framework, called \textit{determinantal sampling}, based on a novel application of determinantal point processes. Using this framework, we obtain an efficiently constructible $\varepsilon$-coreset for $(k,z)$-clustering in $\mathbb R^d$ whose dependence on $1/\varepsilon$ has exponent strictly smaller than $2$ when $d$ is fixed. This improves over the worst-case $\varepsilon^{-2}$ barrier under our beyond-worst-case assumptions. To the best of our knowledge, this is the first result that provably surpasses these lower bounds through beyond-worst-case assumptions. Finally, we validate our approach on synthetic and real-world benchmark datasets, where it consistently achieves smaller coresets than existing state-of-the-art methods, even without explicitly enforcing the assumptions used in the analysis.
- Abstract（参考訳）: 現代の機械学習における膨大なデータセットは、特にメモリと計算の制約がコンパクトで忠実な要約を必要とするクラスタリングタスクにおいて、データ削減を中心的な課題にしている。
標準的なアプローチは、すべての可算な中心の選択に対するクラスタリングコストを概ね保存する小さな重み付き部分集合である \textit{$ε$-coreset} を構築することである。
textit{$(k,z)$-clustering problem} の場合、コアセットサイズ上の既存の最悪のケース境界は本質的に厳密であり、概してより小さなコアセットを除外する。
しかし、このような最悪のケースは実世界のデータでは表現できないことが多い。
本研究では,基礎となるデータ分布について,軽度で自然な仮定の下で,より小さなコアセットが実現可能であることを示す。
本稿では,決定点プロセスの新たな応用に基づいて,新しい相関サンプリングフレームワーク「textit{determinantal sample}」を導入する。
このフレームワークを用いて、$/\varepsilon$に依存する$(k,z)$-clustering in $\mathbb R^d$に対して効率的に構成可能な$\varepsilon$-coresetを得る。
これは、最悪のケースである$\varepsilon^{-2}$バリアよりも改善します。
私たちの知識を最大限に活用するために、これは明らかにこれらの下界を超越した最初の結果である。
最後に、我々は、既存の最先端手法よりも小さなコアセットを一貫して達成し、分析で使われる仮定を明示的に強制することなく、合成および実世界のベンチマークデータセットに対するアプローチを検証する。
関連論文リスト
- Active Learning with Low-Rank Structure for Data Selection [85.43185363043362]
低ランク近似と残差に基づくサンプリングに基づく新しいデータ選択フレームワークを提案する。
平均損失がデータセット全体の平均損失を近似した$tildeOleft(k + frac1varepsilon2right)$データポイントの重み付きサブセットを選択することができることを示す。
論文 参考訳（メタデータ） (2026-06-14T22:29:59Z) - SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。
我々は悲観的な収束分析を避ける分析を提供する。
我々の成果は、既存の最先端の体制を改善した。
論文 参考訳（メタデータ） (2026-06-14T14:11:07Z) - Simple KNN-Based Outlier Detection Achieves Robust Clustering [0.8250700096210891]
外れ値の存在に堅牢であることは、実際にクラスタリングアルゴリズムを適用する上で極めて重要です。
我々は,K$-Nearest-Neighbor 距離の大きい点を除去することで,近似保証の点から先行処理に匹敵する性能が得られることを示す。
論文 参考訳（メタデータ） (2026-05-08T02:08:50Z) - Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers [9.19267739465056]
サイズ $tildeO(varepsilon-2 cdot minvarepsilon-2, d)$ if $n geq 4m$。
d = 1$ の特別な場合、最適コアセットサイズは $tildeTheta(varepsilon-1/2 + fracmn varepsilon-1)$ となる。
我々の結果は、ロバスト$(k,z)$-clusteringにまで拡張されます。
論文 参考訳（メタデータ） (2025-10-28T16:49:03Z) - Coresets for Clustering Under Stochastic Noise [33.12252505929148]
本稿では,入力データセットがノイズによって破損した場合に,$(k, z)$-clusteringに対してコアセットを構築するという問題について検討する。
私たちは、真のクラスタリングコストと確実に関連付けられた、トラクタブルなサロゲートエラーメトリクスを使用します。
コアセットのサイズは最大$mathrmpoly(k)$で改善できるが、$n$はデータセットのサイズである。
論文 参考訳（メタデータ） (2025-10-27T15:41:27Z) - Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。
我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。
次に,新しい2段階クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-02T05:10:40Z) - Universal Weak Coreset [3.1509756165776635]
弱コアセットは点の部分集合の対$(J,S)$であり、そこでは点集合の要約として$S$が作用し、ポテンシャル中心の集合として$J$が作用する。
我々は、制約付きクラスタリング設定のために、ユニバーサル弱コアセットと呼ばれるこのフレームワークを開発した。
論文 参考訳（メタデータ） (2023-05-26T12:51:16Z) - Nystr\"om Kernel Mean Embeddings [92.10208929236826]
Nystr"om法に基づく効率的な近似手法を提案する。
サブサンプルサイズの条件は標準の$n-1/2$レートを得るのに十分である。
本稿では,この結果の最大誤差と二次規則の近似への応用について論じる。
論文 参考訳（メタデータ） (2022-01-31T08:26:06Z) - Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。
アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
論文 参考訳（メタデータ） (2021-06-04T16:37:19Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。