論文の概要: Adversarially robust clustering with optimality guarantees
- arxiv url: http://arxiv.org/abs/2306.09977v2
- Date: Wed, 14 Aug 2024 06:53:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-15 18:46:43.203965
- Title: Adversarially robust clustering with optimality guarantees
- Title(参考訳): 最適性保証付き逆ロバストクラスタリング
- Authors: Soham Jana, Kun Yang, Sanjeev Kulkarni,
- Abstract要約: 我々はガウス以下の混合系から得られるデータポイントをクラスタリングする問題を考察する。
ロイドアルゴリズムのような最適ラベル誤りを確実に達成する既存の手法は、通常、外れ値に対して脆弱である。
本稿では, 対数外乱が存在する場合でも, 座標中央値に基づく単純なロバストアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 7.0830450321883935
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of clustering data points coming from sub-Gaussian mixtures. Existing methods that provably achieve the optimal mislabeling error, such as the Lloyd algorithm, are usually vulnerable to outliers. In contrast, clustering methods seemingly robust to adversarial perturbations are not known to satisfy the optimal statistical guarantees. We propose a simple robust algorithm based on the coordinatewise median that obtains the optimal mislabeling rate even when we allow adversarial outliers to be present. Our algorithm achieves the optimal error rate in constant iterations when a weak initialization condition is satisfied. In the absence of outliers, in fixed dimensions, our theoretical guarantees are similar to that of the Lloyd algorithm. Extensive experiments on various simulated and public datasets are conducted to support the theoretical guarantees of our method.
- Abstract(参考訳): 我々はガウス以下の混合系から得られるデータポイントをクラスタリングする問題を考察する。
ロイドアルゴリズムのような最適ラベル誤りを確実に達成する既存の手法は、通常、外れ値に対して脆弱である。
対照的に、対向摂動に頑健であるように見えるクラスタリング法は、最適な統計的保証を満たすことは分かっていない。
本稿では, 対数外乱が存在する場合でも, 座標中央値に基づく単純なロバストアルゴリズムを提案する。
本アルゴリズムは, 弱い初期化条件が満たされた場合, 一定繰り返しにおける最適誤差率を達成する。
外れ値がない場合、固定次元では、我々の理論的保証はロイドアルゴリズムと類似している。
提案手法の理論的保証を支援するために, 様々なシミュレーションおよび公開データセットに関する大規模な実験を行った。
関連論文リスト
- A general theory for robust clustering via trimmed mean [7.650319416775203]
提案手法は,新しいトリミング平均型セントロイド推定器を用いたハイブリッドクラスタリング手法を導入し,誤ラベル保証を実現する。
その結果, 誤差がガウス以下の分布に従えば, ガウス以下のケースに還元されることがわかった。
これらの初期セントロイド推定値は,その後のクラスタリングアルゴリズムにおいて,最適な誤ラベル率を達成するのに十分であることを示す。
論文 参考訳(メタデータ) (2024-01-10T22:56:44Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic
Algorithm [77.53604156112144]
我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。
非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
論文 参考訳(メタデータ) (2023-10-19T13:57:38Z) - Scalable Clustering: Large Scale Unsupervised Learning of Gaussian
Mixture Models with Outliers [5.478764356647437]
本稿では,損失最小化に基づくロバストなクラスタリングアルゴリズムを提案する。
これはアルゴリズムが高い確率で高い精度を得るという理論的保証を提供する。
実世界の大規模データセットの実験では、アルゴリズムの有効性が示されている。
論文 参考訳(メタデータ) (2023-02-28T14:39:18Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - Learning-Augmented $k$-means Clustering [44.06375788674942]
予測器を付加した$k$-means問題を考えると、任意の点で、そのクラスタラベルを、何らかの、おそらくは逆のエラーまで、ほぼ最適なクラスタリングで返します。
精度の高い予測器に従えば、高いクラスタリングコストがもたらされるが、予測器の精度とともに性能が向上するアルゴリズムを提案する。
我々は、実際のデータセット上でアルゴリズムを評価し、クラスタリングの品質を大幅に改善したことを示す。
論文 参考訳(メタデータ) (2021-10-27T00:11:49Z) - Learning to Hash Robustly, with Guarantees [79.68057056103014]
本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。
理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。
我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
論文 参考訳(メタデータ) (2021-08-11T20:21:30Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Sparse PCA: Algorithms, Adversarial Perturbations and Certificates [9.348107805982604]
標準統計モデルにおけるスパースPCAの効率的なアルゴリズムについて検討する。
私たちのゴールは、小さな摂動に耐性を持ちながら、最適な回復保証を達成することです。
論文 参考訳(メタデータ) (2020-11-12T18:58:51Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳(メタデータ) (2020-10-12T17:41:44Z) - Consistency of Anchor-based Spectral Clustering [0.0]
アンカーベースの手法は、スペクトルクラスタリングアルゴリズムの計算複雑性を低減する。
厳密な分析が可能であり,実践に有効であることを示す。
我々はChenとCaiの最先端のLCC法と競合することが判明した。
論文 参考訳(メタデータ) (2020-06-24T18:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。