An expected approximation guarantee of an expected approximation guarantee of $8(\ln k+2)\left(\frac{1+\varepsilon}{1-\varepsilon}{1-\varepsilon}\right)^4 = (1+O(\varepsilon))\,8(\ln k+2)$.
Abstract
The celebrated $k$-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) achieves an $O(\log k)$ expected approximation for the classical $k$-means problem using $D^2$-sampling, a technique now ubiquitous in clustering algorithm design. Bhattacharya et al. (ESA 2020) introduced $\varepsilon$-noisy $k$-means++, where sampling probabilities may incur an adversarial multiplicative error of $(1\pm\varepsilon)$, but obtained only an $O(\log^2 k)$ guarantee. Grunau et al. (ESA 2023) recovered the asymptotic $O(\log k)$ guarantee, but their analysis loses a constant factor of roughly $147{,}638$ even as $\varepsilon\to0$, leaving open whether $k$-means++ is highly sensitive to even a small amount of noise. They asked whether a bound within $1+O(\varepsilon)$ of the classical guarantee is possible. We resolve this affirmatively, proving an expected approximation guarantee of $8(\ln k+2)\left(\frac{1+\varepsilon}{1-\varepsilon}\right)^4 = (1+O(\varepsilon))\,8(\ln k+2)$. We complement the upper bound with two separations. First, a noisy version of the Arthur and Vassilvitskii lower-bound instance incurs a $1+\Omega(\varepsilon)$ loss over exact $k$-means++, so linear dependence on the noise is necessary. Second, pointwise multiplicative control is qualitatively essential: replacing it with per-round total variation closeness admits no finite approximation guarantee, even for $k=2$.
The proofs combine a persistent randomized Balog-Szemer\'edi-Gowers procedure producing a fixed implicit small-doubling subset on the $\sqrt{\alpha}$ retained-mass scale, conditionally exact finite product sampling, size-oblivious algorithmic PFR, and deterministic lifting.
Setting $m=1$ proves that the $\log K$ for ordinary $K$-armed bandits against adaptive non-anticipating adversaries is unavoidable, closing the remaining $\sqrt{\log K}$ gap between confidence-tuned upper and lower bounds left by Gerchinovitz and Lattimore.
F. Bacchiocchi, Tommaso Cesari, Roberto Colomboni· 0 citations
The $k$-means++ algorithm is a standard and widely used seeding method for $k$-means clustering, but for a fixed number $k$ of centers its worst-case expected approximation ratio is $\Theta(\log k)$. We consider the same algorithm when an adversary first fixes the dataset and some $K$; the number of centers $k$ is then chosen uniformly from $\{K,\ldots,2K-1\}$. We prove that $k$-means++ is an $O(1)$-approximation with constant probability in this budget-smoothed setup.
A classical problem in sparse Fourier transforms, which dates back to the work by Prony in 1795 at least, is to learn a $k$-Fourier-sparse signal $x(t):=\sum_{j=1}^k \alpha_j e^{2 \pi \mathbf{i} f_j t}$ with arbitrary frequencies $f_1,\ldots,f_k$. We study this problem of learning $x(t)$ in a fixed time window $[-T,T]$ under adversarial noise with bounded $\ell_2$ norm, where the frequencies $f_1,\ldots,f_k$ may be"off-grid"-- arbitrarily located in a given bandlimit $[-F,F]$. In particular, our goal is to output a sparse interpolation $\tilde{x}$ such that $\tilde{x}(t) \approx x(t)$ in the time window $[-T,T]$. 1. Our first result shows that the sample complexity of interpolation is $k^2 \cdot O(\log \frac{k FT}{\epsilon})^2$. While its running time is $(\frac{k FT}{\epsilon})^{O(k)}$, this improves the previous upper bound $k^{4} \cdot (\log FT)^{O(1)}$ on the sample complexity substantially and leaves a gap of about $k$ to the lower bound $\Omega(k \log FT)$. 2. Our second result provides efficient algorithms to interpolate $x(t)$. The first algorithm takes $m=k^{3.75} \cdot (\log FT)^{O(1)}$ samples and $m^{\omega+o(1)}$ time ($\omega$ is the matrix multiplication exponent). Assuming that the growth of any $k$-Fourier-sparse signal cannot be significantly larger than the growth of the degree-$(k-1)$ Chebyshev polynomial -- specifically, $x(t) \le e^{k \cdot O\big( \sqrt{\frac{|t|}{T}-1} \big)} \cdot \underset{s \in [-1,1]}{\max} |x(s)|$ for any $t \notin [-T,T]$, the second algorithm further improves the sample complexity to $m'=k^{3} \cdot (\log FT)^{O(1)}$ and the time complexity to $(m')^{\omega+o(1)}$.
Dongrun Cai, Xue Chen, Xiaowei Shao et al.· 0 citations
We give a new dual fitting algorithm which gives improved approximation ratios of $3+\ln 2 + \epsilon\ (\approx 3.694)$ and $4.9+\epsilon$ for $k$-Means in (high-dimensional) Euclidean and general metrics respectively, improving upon the previously known ratios of $4+\epsilon$ [Charikar, Cohen-Addad, Gao, Grandoni, Lee, and van Wijland STOC'26] and $5+\epsilon$ [Byrka, Guo, Hu, Li, Wan, Wang FOCS'26], resp. In particular, our result for Euclidean $k$-Means breaks the hardness barrier of $1+8/e\approx 3.94$ for Metric $k$-Means. Prior to our work, no such separation between general and Euclidean metrics was known for $k$-Median, $k$-Means, or Facility Location in terms of their approximability. Unlike prior dual fitting approaches for $k$-Means, our new dual fitting algorithm tightly accounts for dual payments while still facilitating an effective dual feasibility analysis. We introduce a new framework that uses spectral analysis for determining the approximation factor of our algorithm.
Aditya Anand, Moses Charikar, Vincent Cohen-Addad et al.· 0 citations
In $k$-clustering problems, we are given a metric space $(\mathcal{C}, d)$, and must choose a set $S$ of $k$ centers to open. Each client $j \in \mathcal{C}$ incurs an assignment cost, which is the distance between $j$ and center in $S$ that it has been assigned to. In this work, we study the \emph{minimum-norm $k$-clustering problem}, where we are given an arbitrary monotone symmetric norm $f$, and wish to open $k$ centers so as to minimize $f$(assignment-cost vector). This is a powerful generalization, encompassing many classical $k$-clustering problems including the $k$-median, $k$-means, and $k$-center problems. A simple and efficient algorithmic idea is that of \emph{adaptive sampling}, wherein we randomly choose the location of the next center to open with probability proportional to its ``cost"under the currently chosen set. While this has yielded fast algorithms for some $k$-clustering problem, little is known for settings \emph{without} ``min-sum"objectives. We devise the first adaptive-sampling-based bicriteria constant-factor approximation algorithm for general minimum-norm $k$-clustering, vastly expanding the scope of problems handled by adaptive sampling. For the special case of $\text{Top}_\ell$ norms, which form a building block of monotone symmetric norms, we show that adaptive sampling yields an $O(\log k)$-approximation algorithm.