論文の概要: The Computational Complexity of Almost Stable Clustering with Penalties
- arxiv url: http://arxiv.org/abs/2510.03143v1
- Date: Fri, 03 Oct 2025 16:15:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-06 16:35:52.477715
- Title: The Computational Complexity of Almost Stable Clustering with Penalties
- Title（参考訳）: 罰則をもつ準安定クラスタリングの計算複雑性
- Authors: Kamyar Khodamoradi, Farnam Mansouri, Sandra Zilles,
- Abstract要約: 両次元の小さい測度において,$mathrmk-M SmallEANS$と$mathrmk-M SmallEDIAN$の安定(あるいは摂動耐性)インスタンスの複雑性について検討する。
ほぼ安定な$mathrmk-MsmallEANS$/$mathrmk-MsmallEDIAN$(罰則付き)の特別なケースは、時間内に解決可能であることを示す。
- 参考スコア（独自算出の注目度）: 2.689067085628911
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate the complexity of stable (or perturbation-resilient) instances of $\mathrm{k-M\small{EANS}}$ and $\mathrm{k-M\small{EDIAN}}$ clustering problems in metrics with small doubling dimension. While these problems have been extensively studied under multiplicative perturbation resilience in low-dimensional Euclidean spaces (e.g., (Friggstad et al., 2019; Cohen-Addad and Schwiegelshohn, 2017)), we adopt a more general notion of stability, termed ``almost stable'', which is closer to the notion of $(\alpha, \varepsilon)$-perturbation resilience introduced by Balcan and Liang (2016). Additionally, we extend our results to $\mathrm{k-M\small{EANS}}$/$\mathrm{k-M\small{EDIAN}}$ with penalties, where each data point is either assigned to a cluster centre or incurs a penalty. We show that certain special cases of almost stable $\mathrm{k-M\small{EANS}}$/$\mathrm{k-M\small{EDIAN}}$ (with penalties) are solvable in polynomial time. To complement this, we also examine the hardness of almost stable instances and $(1 + \frac{1}{poly(n)})$-stable instances of $\mathrm{k-M\small{EANS}}$/$\mathrm{k-M\small{EDIAN}}$ (with penalties), proving super-polynomial lower bounds on the runtime of any exact algorithm under the widely believed Exponential Time Hypothesis (ETH).
- Abstract（参考訳）: 安定な(あるいは摂動耐性の)インスタンスの複雑さを$\mathrm{k-M\small{EANS}}$と$\mathrm{k-M\small{EDIAN}}$の2倍次元のメトリクスにおけるクラスタリング問題について検討する。
これらの問題は、低次元ユークリッド空間(例えば、Friggstad et al , 2019; Cohen-Addad and Schwiegelshohn, 2017)における乗法的摂動レジリエンスの下で広く研究されているが、より一般的な安定性の概念である 'almost stable' を採用しており、これはバルカンとリアンによって導入された$(\alpha, \varepsilon)$-摂動レジリエンスに近い。
さらに、結果を$\mathrm{k-M\small{EANS}}$/$\mathrm{k-M\small{EDIAN}}$に拡張します。
ほぼ安定な $\mathrm{k-M\small{EANS}}$/$\mathrm{k-M\small{EDIAN}}$ の特殊ケースは多項式時間で解けることを示す。
これを補完するために、ほぼ安定なインスタンスの硬さと$(1 + \frac{1}{poly(n)})$-stable instance of $\mathrm{k-M\small{EANS}}$/$\mathrm{k-M\small{EDIAN}}$(ペナルティ付き)を検証し、広く信じられている指数時間仮説(ETH)の下での任意のアルゴリズムの実行時の超多項式下限を証明した。
関連論文リスト
- Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
我々は、$rho$が$mtext-d$集合の近くに集中しているとき、これをノイズのあるデータを持つ多様体学習問題と解釈できることを示した。
Monge-Kantorovich $p$-cost $mathbbW_pp(rho, nu)$を介して$rho$を近似する際の$nu$のパフォーマンスを定量化し、$mathrmsupp nu$を$f : mathbbRmでカバーできるようにすることで複雑さを制限します。
論文 参考訳（メタデータ） (2024-09-25T01:30:16Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Randomised Composition and Small-Bias Minimax [0.9252523881586053]
クエリ複雑性に関する2つの結果が、$mathrmR(f)$であることを示す。
まず、「線形化」複雑性測度$mathrmLR$を導入し、内部衝突合成定理を満たすことを示す: $mathrmR(f) geq Omega(mathrmR(f) mathrmLR(g))$ for all partial $f$と$g$。
論文 参考訳（メタデータ） (2022-08-26T23:32:19Z) - Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates
of Linear Stochastic Approximation [22.51165277694864]
本稿では,線形近似 (LSA) アルゴリズムの有限時間解析を行う。
LSAは$d$次元線形系の近似解を計算するために用いられる。
論文 参考訳（メタデータ） (2022-07-10T14:36:04Z) - Monogamy of entanglement between cones [68.8204255655161]
モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。
我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
論文 参考訳（メタデータ） (2022-06-23T16:23:59Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - The Complexity of Dynamic Least-Squares Regression [11.815510373329337]
動的最小二乗回帰の複雑さ。
ゴールは、$min_mathbfx(t)| mathbfA(t) mathbfb(t) |$ for all $tin に対する $epsilon-approximate ソリューションを維持することである。
論文 参考訳（メタデータ） (2022-01-01T18:36:17Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。