cs.DSSep 20, 2025

Sublinear Time Quantum Sensitivity Sampling

Authors: Zhao Song, David P. Woodruff, Lichen Zhang

Organizations: University of California, Berkeley. · Carnegie Mellon University. · Massachusetts Institute of Technology.

Abstract

We present a unified quantum sensitivity sampling framework that streamlines coreset construction for many classical approximation problems, significantly speeding up clustering, regression, and low-rank approximation. We assume n,d≥poly(k/ε)n,d\geq\mathrm{poly}(k/ε) and, for regression, n≥poly(d)n\geq\mathrm{poly}(d): - kk-median/kk-means: For nn points in Rd\mathbb{R}^d, we build an εε-coreset of input points of size O~(k4/3ε−2)\tilde O(k^{4/3}ε^{-2}) (resp. O~(k3/2ε−2)\tilde O(k^{3/2}ε^{-2})) in time O~(ε−1n0.5dk1.67)\tilde O(ε^{-1}n^{0.5}dk^{1.67}) (resp. O~(ε−1n0.5dk1.75)\tilde O(ε^{-1}n^{0.5}dk^{1.75})). Our better dd- and linear 1/ε1/ε-dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for d≥Ω(k7/3)d\geqΩ(k^{7/3}) (resp. Ω(k2.5)Ω(k^{2.5})). - ℓp\ell_p regression: For min⁡x∥Ax−b∥p\min_x\|Ax-b\|_p, A∈Rn×dA\in\mathbb{R}^{n\times d}, we build an εε-coreset of size O~p(dmax⁡{1,p/2}ε−2)\tilde O_p(d^{\max\{1,p/2\}}ε^{-2}) in time O~p(n0.5d1.5ε−1)\tilde O_p(n^{0.5}d^{1.5}ε^{-1}) for p≤2p\leq 2 and O~p(n0.5dp/4+1(ε−1+d0.5))\tilde O_p(n^{0.5}d^{p/4+1}(ε^{-1}+d^{0.5})) for p>2p>2, matching [Liu and Ji, ICML'26] for p≤2p\leq 2 and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all p>2p>2. - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank-kk approximation of A∈Rd×nA\in\mathbb{R}^{d\times n} free of data-dependent parameters, running in O~(n0.5dk0.5ε−0.5)\tilde O(n^{0.5}dk^{0.5}ε^{-0.5}) time with factored output (plus O~(nk2ε−2)\tilde O(nk^2ε^{-2}) to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity SS, any quantum algorithm outputting an εε-coreset of size o(nS)o(\sqrt{nS}) needs Ω(nS)Ω(\sqrt{nS}) queries, so our query complexity is optimal up to poly(ε−1,log⁡n)\mathrm{poly}(ε^{-1},\log n) and VC-dimension factors.

Figures & tables

Explore similar work

Jul 6, 2026

Sensitivity Sampling with Predictions for k-Means Clustering

We study the problem of k-means clustering on large datasets. The state-of-the-art for the problem is given by coresets-based approaches, which build small weighted summaries of the input and derive approximate solutions with rigorous quality guarantees from them. One of the most popular and advanced approaches to derive coresets for k-means is sensitivity sampling. However, sensitivity sampling requires to compute the importance of each input point with respect to the whole dataset over all possible choices of centers. Since the exact computation of such quantities is unfeasible, current approaches work by approximating the sensitivity values. Nevertheless, the runtime of such approaches is still impractical for large datasets. In this work, we propose to reduce the runtime of sensitivity-based approaches for k-means by leveraging predictions to approximate the importance of input points. We first formally prove that current theoretical results on coresets construction via sensitivity sampling hold for coarser approximations of sensitivities compared to the one required by existing approaches. This implies that even fairly noisy predictors can be leveraged for sensitivity-sampling approaches. We then propose a natural predictor, which applies to the common scenario where clustering is performed (over time) on a sequence of datasets from the same problem. We prove that when the datasets in the sequence come from the same (unknown) distribution, centers resulting in a low error on one dataset can be used as predictions for sensitivity sampling in subsequent datasets, with guarantees on their quality. We perform an extensive experimental evaluation showing that our approach significantly improves, in terms of clustering cost vs runtime, over uniform sampling and state-of-the-art sensitivity sampling approaches when applied to sequences of datasets.
Sep 6, 2026

Beyond Worst-Case Coreset Bounds for kk-Clustering via Determinantal Sampling

Massive datasets in modern machine learning have made data reduction a central challenge, particularly for clustering tasks where memory and computational constraints demand compact yet faithful summaries. A standard approach is to construct an \textit{εε-coreset}: a small weighted subset that approximately preserves the clustering cost for every plausible choice of centers. For the \textit{(k,z)(k,z)-clustering problem}, existing worst-case bounds on coreset size are essentially tight, ruling out substantially smaller coresets in general. However, such worst-case instances are often unrepresentative of real-world data. In this work, we show that significantly smaller coresets are possible under mild and natural assumptions on the underlying data distribution. We introduce a new correlated sampling framework, called determinantal sampling, based on a novel application of determinantal point processes. Using this framework, we obtain an efficiently constructible ε\varepsilon-coreset for (k,z)(k,z)-clustering in Rd\mathbb R^d whose dependence on 1/ε1/\varepsilon has exponent strictly smaller than 22 when dd is fixed. This improves over the worst-case ε−2\varepsilon^{-2} barrier under our beyond-worst-case assumptions. To the best of our knowledge, this is the first result that provably surpasses these lower bounds through beyond-worst-case assumptions. Finally, we validate our approach on synthetic and real-world benchmark datasets, where it consistently achieves smaller coresets than existing state-of-the-art methods, even without explicitly enforcing the assumptions used in the analysis.
Jun 14, 2026

Active Learning with Low-Rank Structure for Data Selection

In the data selection problem, the objective is to choose a small, representative subset of data that can be used to efficiently train a machine learning model. Sener and Savarese [ICLR 2018] showed that, given an embedding representation of the data and suitable geometric assumptions, heuristics based on kk-center clustering can be used to perform data selection. This perspective was further explored by Axiotis et. al. [ICML 2024], who proposed a data selection approach based on kk-means clustering and sensitivity sampling. However, these methods rely on the assumption that the dataset exhibits intrinsic geometric structure that can be effectively captured by clustering, whereas many modern datasets instead possess global algebraic structure that is better exploited by low-rank approximation or principal component analysis. In this paper, we introduce a new data selection framework based on low-rank approximation and residual-based sampling, formulated through the lens of row subset selection and loss-preserving coreset construction. Given an embedding representation of the data satisfying mild regularity conditions, which can be interpreted as algebraic or angular notions of Lipschitz continuity, we show that it is possible to select a weighted subset of O~(k+1ε2)\tilde{O}\left(k + \frac{1}{\varepsilon^2}\right) data points whose average loss approximates the average loss over the full dataset within a (1+ε)(1+\varepsilon) relative error, up to an additive εΦk\varepsilon Φ_k term, where ΦkΦ_k denotes the optimal rank-kk approximation cost of the embedding matrix. We complement these theoretical guarantees with empirical evaluations, demonstrating that on a range of real-world datasets, our data selection approach achieves improved performance over prior strategies based on uniform sampling or clustering-based sensitivity sampling.