Improved Approximations for Euclidean $k$-means and $k$-median, via Nested Quasi-Independent Sets

• URL: http://arxiv.org/abs/2204.04828v2
• Date: Tue, 12 Apr 2022 03:16:11 GMT
• Title: Improved Approximations for Euclidean $k$-means and $k$-median, via Nested Quasi-Independent Sets
• Abstract summary: We propose a primal-dual algorithm for high-dimensional Euclidean $k$-median and $k$-means problems. Our algorithm achieves an approximation ratio of $2.406$ and $5.912$ for Euclidean $k$-median and $k$-means, respectively. In turn, this technique may be of interest for other optimization problems in Euclidean and $ell_p$ metric spaces.
• Score: 34.92651216338062
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by data analysis and machine learning applications, we consider the popular high-dimensional Euclidean $k$-median and $k$-means problems. We propose a new primal-dual algorithm, inspired by the classic algorithm of Jain and Vazirani and the recent algorithm of Ahmadian, Norouzi-Fard, Svensson, and Ward. Our algorithm achieves an approximation ratio of $2.406$ and $5.912$ for Euclidean $k$-median and $k$-means, respectively, improving upon the 2.633 approximation ratio of Ahmadian et al. and the 6.1291 approximation ratio of Grandoni, Ostrovsky, Rabani, Schulman, and Venkat. Our techniques involve a much stronger exploitation of the Euclidean metric than previous work on Euclidean clustering. In addition, we introduce a new method of removing excess centers using a variant of independent sets over graphs that we dub a "nested quasi-independent set". In turn, this technique may be of interest for other optimization problems in Euclidean and $\ell_p$ metric spaces.

Related papers

• A Sub-4 Approximation for Fair $k$-Means [18.61347737579578]
  We study fair $k$-means clustering in Euclidean space, where the proportion of each protected group in every cluster must lie within specified lower and upper bounds.<n>We propose an approximation algorithm that combines a linear programming relaxation with geometric transformations of the input to construct candidate center sets.
  arXiv  Detail & Related papers  (2026-09-07T20:54:36Z)
• Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering [7.186850020419764]
  We develop an approximation algorithm for fair $k$-center clustering using Euclidean spaces.<n>Our methods significantly outperform state-of-the-art approaches in terms of clustering accuracy.
  arXiv  Detail & Related papers  (2026-09-06T04:49:44Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems.<n>Our framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation.
  arXiv  Detail & Related papers  (2025-09-20T20:18:49Z)
• Stacey: Promoting Stochastic Steepest Descent via Accelerated $\ell_p$-Smooth Nonconvex Optimization [15.179519413549086]
  We introduce a new accelerated $ell_p$ steepest descent algorithm, called Stacey, to handle non-Euclidean smooth optimization tasks.<n>In addition to providing theoretical guarantees for the foundations of our algorithm, we empirically compare our approach against popular methods.
  arXiv  Detail & Related papers  (2025-06-07T00:47:07Z)
• Dynamic Consistent $k$-Center Clustering with Optimal Recourse [0.6077284832583713]
  We prove that the $k$-center clustering problem admits optimal recourse bounds by developing a deterministic constant-factor approximation with worst-case recourse of $1$ per update. Our incremental algorithm improves over the $8$-approximation algorithm by Charikar, Chekuri, Feder, and Motwani.
  arXiv  Detail & Related papers  (2024-12-04T11:39:03Z)
• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
  Given a dataset comprising several groups, the fairness constraint requires that each cluster should contain a proportion of points from each group. We propose a novel Relax and Merge'' framework, where $rho$ is the approximate ratio of an off-the-shelf vanilla $k$-means algorithm. If equipped with a PTAS of $k$-means, our solution can achieve an approximation ratio of $(5+O(epsilon))$ with only a slight violation of the fairness constraints.
  arXiv  Detail & Related papers  (2024-11-02T02:50:12Z)
• Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means [6.160566143252452]
  Clustering problems such as $k$-means and $k$-median staples are of unsupervised learning.<n>We focus on the class of greedy approximation algorithm, that attracted less attention than local-search or primal-dual counterparts.
  arXiv  Detail & Related papers  (2024-07-15T20:04:06Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Parameterized Approximation Schemes for Clustering with General Norm Objectives [0.6956677722498498]
  This paper considers the well-studied regime of designing a $(k,epsilon)$-approximation algorithm for a $k$-clustering problem. Our main contribution is a clean and simple EPAS that settles more than ten clustering problems.
  arXiv  Detail & Related papers  (2023-04-06T15:31:37Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Byzantine-Robust Federated Linear Bandits [27.77095339417368]
  We study a linear bandit optimization problem in a federated setting where a large collection of distributed agents collaboratively learn a common linear bandit model. Standard federated learning algorithms are vulnerable to Byzantine attacks on even a small fraction of agents. We show that our proposed algorithm is robust to Byzantine attacks on fewer than half of agents and achieves a sublinear $tildemathcalO(T3/4)$ regret with $mathcalO(sqrtT)$ steps of communication.
  arXiv  Detail & Related papers  (2022-04-03T20:22:26Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• Hardness of Approximation of Euclidean $k$-Median [0.25782420501870296]
  The Euclidean $k$-median problem is defined in the following manner: given a set $mathcalX$ of $n$ points in $mathbbRd$, find a set $C subset mathbbRd$ of $k$ points (called centers) In this work, we provide the first hardness of approximation result for the Euclidean $k$-median problem.
  arXiv  Detail & Related papers  (2020-11-09T06:50:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.