Sublinear Time Quantum Sensitivity Sampling

원문 초록

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\geq\mathrm{poly}(k/\epsilon)$ and, for regression, $n\geq\mathrm{poly}(d)$: - $k$-median/$k$-means: For $n$ points in $\mathbb{R}^d$, we build an $\epsilon$-coreset of input points of size $\tilde O(k^{4/3}\epsilon^{-2})$ (resp. $\tilde O(k^{3/2}\epsilon^{-2})$) in time $\tilde O(\epsilon^{-1}n^{0.5}dk^{1.67})$ (resp. $\tilde O(\epsilon^{-1}n^{0.5}dk^{1.75})$). Our better $d$- and linear $1/\epsilon$-dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for $d\geq\Omega(k^{7/3})$ (resp. $\Omega(k^{2.5})$). - $\ell_p$ regression: For $\min_x\|Ax-b\|_p$, $A\in\mathbb{R}^{n\times d}$, we build an $\epsilon$-coreset of size $\tilde O_p(d^{\max\{1,p/2\}}\epsilon^{-2})$ in time $\tilde O_p(n^{0.5}d^{1.5}\epsilon^{-1})$ for $p\leq 2$ and $\tilde O_p(n^{0.5}d^{p/4+1}(\epsilon^{-1}+d^{0.5}))$ for $p>2$, matching [Liu and Ji, ICML'26] for $p\leq 2$ and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all $p>2$. - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank-$k$ approximation of $A\in\mathbb{R}^{d\times n}$ free of data-dependent parameters, running in $\tilde O(n^{0.5}dk^{0.5}\epsilon^{-0.5})$ time with factored output (plus $\tilde O(nk^2\epsilon^{-2})$ to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity $S$, any quantum algorithm outputting an $\epsilon$-coreset of size $o(\sqrt{nS})$ needs $\Omega(\sqrt{nS})$ queries, so our query complexity is optimal up to $\mathrm{poly}(\epsilon^{-1},\log n)$ and VC-dimension factors.