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

CardsList
  1. Sensitivity Sampling with Predictions for k-Means Clustering

    Jul 6, 2026Cristian Boldrin, Fabio VandinClusteringImportance Sampling

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

    Sep 6, 2026Diptarka Chakraborty, Satyaki Mukherjee, Gaurav Vallabhdas Revankar +1Coreset SelectionClustering

  3. Active Learning with Low-Rank Structure for Data Selection

    Jun 14, 2026Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni +3Active LearningData Selection