論文の概要: Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers

• arxiv url: http://arxiv.org/abs/2510.24621v1
• Date: Tue, 28 Oct 2025 16:49:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-29 15:35:37.287511
• Title: Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers
• Title（参考訳）: ロバストな幾何学メディアのためのコアセット:外乱のサイズの依存性を除去する
• Authors: Ziyi Fang, Lingxiao Huang, Runkai Yang,
• Abstract要約: サイズ $tildeO(varepsilon-2 cdot minvarepsilon-2, d)$ if $n geq 4m$。 d = 1$ の特別な場合、最適コアセットサイズは $tildeTheta(varepsilon-1/2 + fracmn varepsilon-1)$ となる。 我々の結果は、ロバスト$(k,z)$-clusteringにまで拡張されます。
• 参考スコア（独自算出の注目度）: 9.19267739465056
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the robust geometric median problem in Euclidean space $\mathbb{R}^d$, with a focus on coreset construction.A coreset is a compact summary of a dataset $P$ of size $n$ that approximates the robust cost for all centers $c$ within a multiplicative error $\varepsilon$. Given an outlier count $m$, we construct a coreset of size $\tilde{O}(\varepsilon^{-2} \cdot \min\{\varepsilon^{-2}, d\})$ when $n \geq 4m$, eliminating the $O(m)$ dependency present in prior work [Huang et al., 2022 & 2023]. For the special case of $d = 1$, we achieve an optimal coreset size of $\tilde{\Theta}(\varepsilon^{-1/2} + \frac{m}{n} \varepsilon^{-1})$, revealing a clear separation from the vanilla case studied in [Huang et al., 2023; Afshani and Chris, 2024]. Our results further extend to robust $(k,z)$-clustering in various metric spaces, eliminating the $m$-dependence under mild data assumptions. The key technical contribution is a novel non-component-wise error analysis, enabling substantial reduction of outlier influence, unlike prior methods that retain them.Empirically, our algorithms consistently outperform existing baselines in terms of size-accuracy tradeoffs and runtime, even when data assumptions are violated across a wide range of datasets.
• Abstract（参考訳）: ユークリッド空間 $\mathbb{R}^d$ におけるロバストな幾何学的中央値問題について、コアセットの構成に焦点をあてて検討する。コアセットはデータセット $P$ of size $n$ のコンパクトなサマリであり、乗法誤差 $\varepsilon$ 内のすべてのセンター $c$ のロバストなコストを近似する。 アウトリー数 $m$ が与えられたとき、サイズ $\tilde{O}(\varepsilon^{-2} \cdot \min\{\varepsilon^{-2}, d\})$ のとき、$n \geq 4m$ が成立し、先行の作業 [Huang et al , 2022 & 2023] に存在する $O(m)$依存を排除した。 d = 1$ の特別の場合、最適コアセットサイズは $\tilde{\Theta}(\varepsilon^{-1/2} + \frac{m}{n} \varepsilon^{-1})$ となり、[Huang et al , 2023; Afshani and Chris, 2024] で研究されたバニラ事件から明確な分離が明らかとなる。 我々の結果は、様々な距離空間におけるロバストな$(k,z)$-clusteringにまで拡張され、穏やかなデータ仮定の下での$m$-dependenceを排除します。 実験的な方法では、データ仮定が広範囲のデータセットで違反された場合でも、我々のアルゴリズムは、サイズと精度のトレードオフと実行時間の観点から、既存のベースラインを一貫して上回ります。

関連論文リスト

• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  制約付き部分空間近似のための一般的なフレームワークを導入する。 分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
  論文  参考訳（メタデータ） (2025-04-29T15:56:48Z)
• Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation [47.790126028106734]
  NPハードネスに対処するための一般的なアプローチは、強力なコアセットを計算することである。 我々は$ell_p$サブスペース近似を$tilde O(kepsilon-4/p)$ for $p2$と$tilde O(kp/2epsilon-p)$ for $p>2$に対して強コアセットを構築するアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-07-03T16:49:28Z)
• Data Structures for Density Estimation [66.36971978162461]
  p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。 また、Acharyaなどのアルゴリズムの改良版も提供します。
  論文  参考訳（メタデータ） (2023-06-20T06:13:56Z)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• Towards Optimal Lower Bounds for k-median and k-means Coresets [25.713987341159918]
  計量空間における点の集合が与えられたとき、$(k,z)$-クラスタリング問題は、センターと呼ばれる点の集合を見つけることからなる。 我々は、$(k,z)$クラスタリングの任意のコアセットが、少なくとも$Omega(k varepsilon-2 log n)$と$Omega(k varepsilon-2 D)$ポイントでなければならないことを示す。
  論文  参考訳（メタデータ） (2022-02-25T16:13:28Z)

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

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