論文の概要: Robust $k$-means Clustering for Distributions with Two Moments
- arxiv url: http://arxiv.org/abs/2002.02339v2
- Date: Tue, 3 Nov 2020 15:59:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-03 13:34:30.206384
- Title: Robust $k$-means Clustering for Distributions with Two Moments
- Title（参考訳）: 2モーメント分布に対するロバストな$k$-meansクラスタリング
- Authors: Yegor Klochkov, Alexey Kroshnin, and Nikita Zhivotovskiy
- Abstract要約: 我々は、$N$独立観測に基づいて量子化器を構成する$k$-meansクラスタリング問題に対するロバストアルゴリズムについて考察する。
我々の主な結果は、一般分離ヒルベルト空間における2つの有界モーメント仮定の下で成り立つ平均に基づく非漸近的過剰歪み境界の中央値である。
- 参考スコア（独自算出の注目度）: 4.21934751979057
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the robust algorithms for the $k$-means clustering problem where
a quantizer is constructed based on $N$ independent observations. Our main
results are median of means based non-asymptotic excess distortion bounds that
hold under the two bounded moments assumption in a general separable Hilbert
space. In particular, our results extend the renowned asymptotic result of
Pollard, 1981 who showed that the existence of two moments is sufficient for
strong consistency of an empirically optimal quantizer in $\mathbb{R}^d$. In a
special case of clustering in $\mathbb{R}^d$, under two bounded moments, we
prove matching (up to constant factors) non-asymptotic upper and lower bounds
on the excess distortion, which depend on the probability mass of the lightest
cluster of an optimal quantizer. Our bounds have the sub-Gaussian form, and the
proofs are based on the versions of uniform bounds for robust mean estimators.
- Abstract（参考訳）: 我々は,$n$独立観測に基づいて量子化器が構築される$k$-meansクラスタリング問題に対するロバストアルゴリズムを考える。
我々の主な結果は、一般分離ヒルベルト空間における2つの有界モーメント仮定の下で成り立つ平均に基づく非漸近的過剰歪み境界の中央値である。
特に、1981年のPollardの有名な漸近的結果を拡張し、2つのモーメントの存在は、$\mathbb{R}^d$における経験的最適量化器の強い一貫性に十分であることを示した。
2つの有界なモーメントの下で、$\mathbb{r}^d$ でのクラスタリングの特別なケースでは、最適量子化器の最も軽いクラスターの確率質量に依存する過剰な歪みに対して(定数因子まで)非漸近的な上限が一致することが証明される。
我々の境界は準ガウス形式を持ち、証明はロバスト平均推定子に対する一様境界のバージョンに基づいている。
関連論文リスト
- Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Uncertainty quantification in the Bradley-Terry-Luce model [14.994932962403935]
本稿では,MLEとスペクトル推定という,近年注目されている2つの推定器に焦点を当てた。
統一的な証明戦略を用いることで,両推定器の急激かつ均一な非漸近的拡張を導出する。
我々の証明は、二階ベクトルの自己整合方程式と、新しい二階解法に基づくものである。
論文 参考訳（メタデータ） (2021-10-08T03:06:30Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。
アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
論文 参考訳（メタデータ） (2021-06-04T16:37:19Z) - Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。
精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
論文 参考訳（メタデータ） (2021-05-11T03:39:08Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Convergence Rates of Stochastic Gradient Descent under Infinite Noise
Variance [14.06947898164194]
ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。
SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。
その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
論文 参考訳（メタデータ） (2021-02-20T13:45:11Z) - Nonparametric approximation of conditional expectation operators [0.3655021726150368]
最小の仮定の下で、$[Pf](x) := mathbbE[f(Y) mid X = x ]$ で定義される$L2$-operatorの近似について検討する。
我々は、再生されたカーネル空間上で作用するヒルベルト・シュミット作用素により、作用素ノルムにおいて$P$が任意に適切に近似できることを証明した。
論文 参考訳（メタデータ） (2020-12-23T19:06:12Z) - Optimal Bounds between $f$-Divergences and Integral Probability Metrics [8.401473551081748]
確率分布の類似性を定量化するために、$f$-divergencesとIntegral Probability Metricsが広く使われている。
両家系の関係を凸双対性の観点から体系的に研究する。
我々は、Hoeffdingの補題のような統一的な方法でよく知られた結果を回復しながら、新しい境界を得る。
論文 参考訳（メタデータ） (2020-06-10T17:39:11Z) - The role of regularization in classification of high-dimensional noisy
Gaussian mixture [36.279288150100875]
雑音状態における2つのガウスの高次元混合を考える。
正規化凸分類器の一般化誤差を厳密に解析する。
ベイズ最適性能に到達できるような正規化の驚くべき効果について論じる。
論文 参考訳（メタデータ） (2020-02-26T14:54:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。