Fugu-MT 論文翻訳(概要): On Approximability of $\ell

論文の概要: On Approximability of $\ell_2^2$ Min-Sum Clustering

arxiv url: http://arxiv.org/abs/2412.03332v1
Date: Wed, 04 Dec 2024 14:03:27 GMT
ステータス: 翻訳完了
システム内更新日: 2024-12-05 15:06:27.612636
Title: On Approximability of $\ell_2^2$ Min-Sum Clustering
Title（参考訳）: $\ell_2^2$ Min-Sumクラスタリングの近似性について
Authors: Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, Samson Zhou,
Abstract要約: 本稿では、$ell2$ minsum $k$-clustering問題に対して、最初の強度近似結果を与える。さらに、ジョンソン被覆仮説の均衡を仮定すると、その目的を1.327よりも良い因子に近似することはNPハードであることが示される。
参考スコア（独自算出の注目度）: 17.403803548692498
License:
Abstract: The $\ell_2^2$ min-sum $k$-clustering problem is to partition an input set into clusters $C_1,\ldots,C_k$ to minimize $\sum_{i=1}^k\sum_{p,q\in C_i}\|p-q\|_2^2$. Although $\ell_2^2$ min-sum $k$-clustering is NP-hard, it is not known whether it is NP-hard to approximate $\ell_2^2$ min-sum $k$-clustering beyond a certain factor. In this paper, we give the first hardness-of-approximation result for the $\ell_2^2$ min-sum $k$-clustering problem. We show that it is NP-hard to approximate the objective to a factor better than $1.056$ and moreover, assuming a balanced variant of the Johnson Coverage Hypothesis, it is NP-hard to approximate the objective to a factor better than 1.327. We then complement our hardness result by giving the first $(1+\varepsilon)$-coreset construction for $\ell_2^2$ min-sum $k$-clustering. Our coreset uses $\mathcal{O}\left(k^{\varepsilon^{-4}}\right)$ space and can be leveraged to achieve a polynomial-time approximation scheme with runtime $nd\cdot f(k,\varepsilon^{-1})$, where $d$ is the underlying dimension of the input dataset and $f$ is a fixed function. Finally, we consider a learning-augmented setting, where the algorithm has access to an oracle that outputs a label $i\in[k]$ for input point, thereby implicitly partitioning the input dataset into $k$ clusters that induce an approximately optimal solution, up to some amount of adversarial error $\alpha\in\left[0,\frac{1}{2}\right)$. We give a polynomial-time algorithm that outputs a $\frac{1+\gamma\alpha}{(1-\alpha)^2}$-approximation to $\ell_2^2$ min-sum $k$-clustering, for a fixed constant $\gamma>0$.
Abstract（参考訳）: $\ell_2^2$ min-sum $k$-clustering 問題は、入力セットをクラスタ $C_1,\ldots,C_k$ に分割して $\sum_{i=1}^k\sum_{p,q\in C_i}\|p-q\|_2^2$ を最小化することである。 $\ell_2^2$ min-sum $k$-clustering は NP-hard であるが、ある因子を超えて $\ell_2^2$ min-sum $k$-clustering を近似する NP-hard かどうかは不明である。本稿では、$\ell_2^2$ min-sum $k$-clustering問題に対して、最初の強度近似結果を与える。さらに、ジョンソン被覆仮説のバランスの取れた変種を仮定すると、その目的を1.327よりも良い因子に近似することはNPハードであることが示される。次に、最初の$(1+\varepsilon)$-coreset construction for $\ell_2^2$ min-sum $k$-clustering を与えることで、ハードネスの結果を補完する。我々のコアセットは$\mathcal{O}\left(k^{\varepsilon^{-4}}\right)$ spaceを使用し、実行時$nd\cdot f(k,\varepsilon^{-1})$で多項式時間近似スキームを達成するために利用できる。最後に、アルゴリズムが入力ポイントに$i\in[k]$というラベルを出力するオラクルにアクセスでき、それによって暗黙的に入力データセットを$k$のクラスタに分割し、ほぼ最適な解を誘導し、ある量の逆誤差$\alpha\in\left[0,\frac{1}{2}\right)$まで含める学習拡張設定を考える。固定定数 $\gamma>0$ に対して$\frac{1+\gamma\alpha}{(1-\alpha)^2}$-approximation を $\ell_2^2$ min-sum $k$-clustering に出力する多項式時間アルゴリズムを与える。

関連論文リスト

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering [10.697784653113095]
すべてのクラスタ$C$とすべてのグループ$i in [ell]$に対して、$C$ from group $i$のポイント数は、他のグループ$j in [ell]$のポイントの数のt倍でなければならない。私たちは、$ell=2$が一般的な均一容量$k$-medianに匹敵する難易度である場合にも、その問題を示します。
論文参考訳（メタデータ） (2024-05-16T18:17:44Z)
Simple, Scalable and Effective Clustering via One-Dimensional Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文参考訳（メタデータ） (2023-10-25T16:37:45Z)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
$\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)
Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。我々はこの$d$への依存が対数的要因まで最適であることを示す。また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文参考訳（メタデータ） (2021-11-09T00:20:01Z)
Approximating Fair Clustering with Cascaded Norm Objectives [10.69111036810888]
ベクトルの $ell_q$-norm を $ell_p$-norms の $ell_p$-norm よりも小さくするクラスタリングが、中心から$P$ の点の重み付き距離の $ell_p$-norms より小さい。これはSocially Fair $k$-Medianや$k$-Meansなど、さまざまなクラスタリング問題を一般化する。
論文参考訳（メタデータ） (2021-11-08T20:18:10Z)
Nearly-Tight and Oblivious Algorithms for Explainable Clustering [8.071379672971542]
Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) によって初めて定式化された設定における説明可能なクラスタリングの問題について検討する。 k$クラスタリングは、各内部ノードデータが1次元(機能)で閾値をカットした点を示す決定木によって与えられる場合、説明可能であると言われる。我々は、$k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、少なくとも$O(log2 k)$の係数を失う説明可能なクラスタリングを出力するアルゴリズムを提供する。
論文参考訳（メタデータ） (2021-06-30T15:49:41Z)
Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
論文参考訳（メタデータ） (2021-05-31T14:41:40Z)
Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文参考訳（メタデータ） (2021-03-02T06:53:44Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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