論文の概要: A Tight VC-Dimension Analysis of Clustering Coresets with Applications

• arxiv url: http://arxiv.org/abs/2501.06588v1
• Date: Sat, 11 Jan 2025 17:00:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-14 14:20:33.611542
• Title: A Tight VC-Dimension Analysis of Clustering Coresets with Applications
• Title（参考訳）: クラスタリングコアセットのVC次元解析とその応用
• Authors: Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, Chris Schwiegelshohn,
• Abstract要約: ここでは,距離の最小化を行う中心に点を割り当てることが目的とする,$k$-clustering問題に対するコアセットを検討する。 点集合 $P$ が与えられたとき、コアセット $Omega$ はすべての候補解に対して$P$ のコストを近似する小さな重み付き部分集合である。 以下の指標に対して、改良された$k$-medianコアセット境界を得る。
• 参考スコア（独自算出の注目度）: 19.213536807823836
• License:
• Abstract: We consider coresets for $k$-clustering problems, where the goal is to assign points to centers minimizing powers of distances. A popular example is the $k$-median objective $\sum_{p}\min_{c\in C}dist(p,C)$. Given a point set $P$, a coreset $\Omega$ is a small weighted subset that approximates the cost of $P$ for all candidate solutions $C$ up to a $(1\pm\varepsilon )$ multiplicative factor. In this paper, we give a sharp VC-dimension based analysis for coreset construction. As a consequence, we obtain improved $k$-median coreset bounds for the following metrics: Coresets of size $\tilde{O}\left(k\varepsilon^{-2}\right)$ for shortest path metrics in planar graphs, improving over the bounds $\tilde{O}\left(k\varepsilon^{-6}\right)$ by [Cohen-Addad, Saulpic, Schwiegelshohn, STOC'21] and $\tilde{O}\left(k^2\varepsilon^{-4}\right)$ by [Braverman, Jiang, Krauthgamer, Wu, SODA'21]. Coresets of size $\tilde{O}\left(kd\ell\varepsilon^{-2}\log m\right)$ for clustering $d$-dimensional polygonal curves of length at most $m$ with curves of length at most $\ell$ with respect to Frechet metrics, improving over the bounds $\tilde{O}\left(k^3d\ell\varepsilon^{-3}\log m\right)$ by [Braverman, Cohen-Addad, Jiang, Krauthgamer, Schwiegelshohn, Toftrup, and Wu, FOCS'22] and $\tilde{O}\left(k^2d\ell\varepsilon^{-2}\log m \log |P|\right)$ by [Conradi, Kolbe, Psarros, Rohde, SoCG'24].
• Abstract（参考訳）: ここでは,距離の最小化を行う中心に点を割り当てることが目的とする,$k$-clustering問題に対するコアセットを検討する。 一般的な例として、$k$-median objective $\sum_{p}\min_{c\in C}dist(p,C)$がある。 点集合 $P$ が与えられたとき、コアセット $\Omega$ は小さな重み付き部分集合であり、すべての候補解に対して $C$ のコストを 1 から 1 までの乗法係数に近似する。 本稿では、コアセット構築のための鋭いVC次元に基づく分析を行う。 その結果、$k$-median coreset bounds for the size $\tilde{O}\left(k\varepsilon^{-2}\right)$ for shortest path metrics in Planar graphs, improve over the bounds $\tilde{O}\left(k\varepsilon^{-6}\right)$ by [Cohen-Addad, Saulpic, Schwiegelshohn, STOC'21] and $\tilde{O}\left(k^2\varepsilon^{-4}\right)$ by [Braverman, Jiang, Krauthgamer, Wu, SODA'21] 大きさのコアセット $\tilde{O}\left(kd\ell\varepsilon^{-2}\log m\right)$ for clustering $d$-dimensional polygonal curves at most $m$ at most $$\ell$ at most $\ell $ for lengths at Frechet metrics, improve over the bounds $\tilde{O}\left(k^3d\ell\varepsilon^{-3}\log m\right)$ by [Braverman, Cohen-Addad, Jiang, Krauthgamer, Schwiegelshohn, Toftrup, and Wu, FOCS'22] and $\tilde{O}\left(k^2d\ell\varepsilon^{-2}\log m\right) and $\tilde{O}\left(k^3d\ell\psilon^{-3}\log m\right)$ by [Braverman, Cohen-Addad, Jiang, Krauthgamer, Schwiegelshohn, Wu, FOCS'22]

関連論文リスト

• Nearly Linear Sparsification of $\ell_p$ Subspace Approximation [47.790126028106734]
  $ell_p$ 部分空間近似問題のNP硬度に対処する一般的なアプローチは、強いコアセットを計算することである。 我々は、$ell_p$部分空間近似に対して、ランクパラメータ$k$にほぼ最適に依存する強いコアセットを構築するための最初のアルゴリズムを得る。 我々の手法は、オフライン設定と同様のバウンダリを持つ$ell_p$サブスペース近似のための、ほぼ最適に近いオンライン強力なコアセットにも繋がる。
  論文  参考訳（メタデータ） (2024-07-03T16:49:28Z)
• Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
  サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。 1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
  論文  参考訳（メタデータ） (2024-06-04T15:50:42Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Improved Coresets for Euclidean $k$-Means [24.850829728643923]
  1組の$d$次元の$n$ポイントが与えられたとき、ユークリッド$k$平均問題(ユークリッド$k$中間問題を参照)は、$k$センターを見つけることからなる。 本稿では,$tilde O(min(k2 cdot varepsilon-2,kcdot varepsilon-4)$ for $k$-means and $tilde O(min(k4/3 cdot varepsilon)を改善する。
  論文  参考訳（メタデータ） (2022-11-15T14:47:24Z)
• 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)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• Optimal Coreset for Gaussian Kernel Density Estimation [0.8376091455761259]
  点集合 $Psubset mathbbRd$ が与えられたとき、$P$ の核密度推定は [ overlinemathcalG_P(x) = frac1left|Pright|sum_pin Pe-leftlVert x-p rightrVert2 ] for any $xinmathbbRd$ と定義される。 我々は、小さなサブセット$Q$ of $P を構築する方法を研究する。
  論文  参考訳（メタデータ） (2020-07-15T22:58:50Z)
• Sets Clustering [25.358415142404752]
  我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。 このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。 オープンソースコードと文書分類および施設位置の実験結果も提供される。
  論文  参考訳（メタデータ） (2020-03-09T13:30:30Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。 我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
  論文  参考訳（メタデータ） (2020-02-12T03:40:52Z)

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

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