論文の概要: Johnson Coverage Hypothesis: Inapproximability of k-means and k-median
in L_p metrics
- arxiv url: http://arxiv.org/abs/2111.10912v1
- Date: Sun, 21 Nov 2021 22:42:42 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-24 04:20:27.245434
- Title: Johnson Coverage Hypothesis: Inapproximability of k-means and k-median
in L_p metrics
- Title（参考訳）: Johnson Coverage hypothesis:L_p測定におけるk-meansとk-medianの近似性
- Authors: Vincent Cohen-Addad, Karthik C. S, and Euiwoong Lee
- Abstract要約: K-medianとk-meansはクラスタリングアルゴリズムの最も一般的な2つの目的である。
これらの目的のために文献で知られている近似係数の硬さを著しく改善する。
- 参考スコア（独自算出の注目度）: 16.953720670216093
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: K-median and k-means are the two most popular objectives for clustering
algorithms. Despite intensive effort, a good understanding of the
approximability of these objectives, particularly in $\ell_p$-metrics, remains
a major open problem. In this paper, we significantly improve upon the hardness
of approximation factors known in literature for these objectives in
$\ell_p$-metrics.
We introduce a new hypothesis called the Johnson Coverage Hypothesis (JCH),
which roughly asserts that the well-studied max k-coverage problem on set
systems is hard to approximate to a factor greater than 1-1/e, even when the
membership graph of the set system is a subgraph of the Johnson graph. We then
show that together with generalizations of the embedding techniques introduced
by Cohen-Addad and Karthik (FOCS '19), JCH implies hardness of approximation
results for k-median and k-means in $\ell_p$-metrics for factors which are
close to the ones obtained for general metrics. In particular, assuming JCH we
show that it is hard to approximate the k-means objective:
$\bullet$ Discrete case: To a factor of 3.94 in the $\ell_1$-metric and to a
factor of 1.73 in the $\ell_2$-metric; this improves upon the previous factor
of 1.56 and 1.17 respectively, obtained under UGC.
$\bullet$ Continuous case: To a factor of 2.10 in the $\ell_1$-metric and to
a factor of 1.36 in the $\ell_2$-metric; this improves upon the previous factor
of 1.07 in the $\ell_2$-metric obtained under UGC.
We also obtain similar improvements under JCH for the k-median objective.
Additionally, we prove a weak version of JCH using the work of Dinur et al.
(SICOMP '05) on Hypergraph Vertex Cover, and recover all the results stated
above of Cohen-Addad and Karthik (FOCS '19) to (nearly) the same
inapproximability factors but now under the standard NP$\neq$P assumption
(instead of UGC).
- Abstract（参考訳）: K-medianとk-meansはクラスタリングアルゴリズムの最も一般的な2つの目的である。
集中的な努力にもかかわらず、これらの目的、特に$\ell_p$-metrics における近似可能性の理解は依然として大きなオープンな問題である。
本稿では,これらの目的について文献で知られている近似因子の硬さを$\ell_p$-metrics で大幅に改善する。
ジョンソン被覆仮説 (Johnson Coverage hypothesis, JCH) と呼ばれる新しい仮説を導入し、ジョンソングラフの会員グラフがジョンソングラフの部分グラフである場合でも、集合系上のよく研究された最大 k 被覆問題は 1-1/e 以上の因子に近似することが難しいことを概説する。
次に, cohen-addad と karthik (focs '19) が導入した埋め込み手法の一般化と合わせて, jch は一般メトリクスで得られる値に近い因子に対して $\ell_p$-metrics で k-median と k-means の近似結果のハードネスを示唆することを示した。
特に、JCH を仮定すると、k-平均の目的を近似することは困難である: $\bullet$ Discrete case:$\ell_1$-metric の3.94 と $\ell_2$-metric の1.73 の係数に対して、UGC で得られる前の係数 1.56 と 1.17 がそれぞれ改善される。
$\bullet$ 連続ケース:$\ell_1$-metric の2.10倍、$\ell_2$-metric の1.36倍の係数。
また、k-median の目的に対して、JCH でも同様の改善が得られる。
さらに,超グラフ頂点被覆に関するdinur et al. (sicomp '05) の研究を用いて,jch の弱バージョンを証明し,上述した cohen-addad と karthik (focs '19) のすべての結果を (ほぼ) 同一の近似可能性因子に復元する。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - KPZ scaling from the Krylov space [83.88591755871734]
近年,Cardar-Parisi-Zhangスケーリングをリアルタイムの相関器や自動相関器に示す超拡散が報告されている。
これらの結果から着想を得て,Krylov演算子に基づく相関関数のKPZスケーリングについて検討する。
論文 参考訳（メタデータ） (2024-06-04T20:57:59Z) - Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。
適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
論文 参考訳（メタデータ） (2024-05-24T11:22:19Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Compressed and distributed least-squares regression: convergence rates
with applications to Federated Learning [9.31522898261934]
機械学習の勾配アルゴリズムに対する圧縮の影響について検討する。
いくつかの非バイアス圧縮演算子間の収束率の差を強調した。
我々はその結果を連合学習の事例にまで拡張する。
論文 参考訳（メタデータ） (2023-08-02T18:02:00Z) - Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates
and Model Misspecification [16.0817847880416]
ヒルベルト空間上の様々な線形予測問題を含む統一的なフレームワークを提供する。
誤特定レベル $epsilon$ に対して、これらの推定器は、文献で最もよく知られたレートと一致する、$O(maxleft|mathcalO|1/2n-1/2, |mathcalI|1/2n-1 right+epsilon)$ の誤差率を達成する。
論文 参考訳（メタデータ） (2022-01-06T08:51:08Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - On Approximability of Clustering Problems Without Candidate Centers [17.24716331811351]
k-平均の目的は、計量空間におけるクラスタリングタスクをモデル化するための最も広く使われるコスト関数である。
本稿では,これらの目的のために文献で知られている近似係数の硬さを大幅に改善する。
その結果、連続的な設定におけるクラスタリング問題と離散的な設定におけるクラスタリング問題の違いについて、新しい、おそらく反直感的な光を当てた。
論文 参考訳（メタデータ） (2020-09-30T20:05:46Z) - Towards Assessment of Randomized Smoothing Mechanisms for Certifying
Adversarial Robustness [50.96431444396752]
主な課題は、各ランダム化メカニズムの適切性を評価する方法である。
まず最初に、ガウスのメカニズムが$ell$-normを証明するための適切な選択肢であると結論付ける。
驚いたことに、ガウスのメカニズムは指数機構の代わりに$ell_infty$-normを証明するための適切な選択肢でもある。
論文 参考訳（メタデータ） (2020-05-15T03:54:53Z) - k-means++: few more steps yield constant approximation [3.7468898363447654]
Arthur and Vassilvitskii (SODA 2007) の k-means++ アルゴリズムは k-means クラスタリング問題を解くための最先端のアルゴリズムである。
最近、Lattanzi と Sohler (ICML) は k-means++ を O(k log k) 局所探索ステップで拡張し、k-means クラスタリング問題に一定の近似(期待)をもたらすことを提案した。
論文 参考訳（メタデータ） (2020-02-18T18:28:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。