Skip to content

Sublinear Time Quantum Sensitivity Sampling

Sep 2025 · arXiv.org · Vol abs/2509.16801 · 0 citations
Computer Science Physics

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\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.

View source

Similar papers

#artificial intelligence Preprint Jul 2024

The Llama 3 Herd of Models

It is found that Llama 3 delivers comparable quality to leading language models such as GPT-4 on a plethora of tasks, and performs competitively with the state-of-the-art on image, video, and speech recognition tasks.

Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri et al. · 21,082 citations · ⚡3,832
#artificial intelligence Conference Open access Jun 2018

Gibson Env: Real-World Perception for Embodied Agents

This paper investigates developing real-world perception for active agents, proposes Gibson Environment for this purpose, and showcases a set of perceptual tasks learned therein.

F. Xia, Amir Zamir, Zhi-Yang He et al. · 1,069 citations · ⚡112
#computer vision Review Sep 2017

Agile Software Development Methods: Review and Analysis

This publication proposes a definition and a classification of agile software development approaches and analyses ten software development methods that can be characterized as being "agile" against the defined criterion.

P. Abrahamsson, O. Salo, Jussi Ronkainen et al. · 727 citations · ⚡54
#computer vision Jun 2008

The impact of agile practices on communication in software development

The study shows that agile practices improve both informal and formal communication, but indicates that, in larger development situations involving multiple external stakeholders, a mismatch of adequate communication mechanisms can sometimes even hinder the communication.

M. Pikkarainen, Jukka Haikara, O. Salo et al. · 401 citations · ⚡48
#machine learning Review Open access Oct 2014

Software development in startup companies: A systematic mapping study

The results indicate that software engineering work practices are chosen opportunistically, adapted and configured to provide value under the constrains imposed by the startup context.

Nicolò Paternoster, Carmine Giardino, M. Unterkalmsteiner et al. · 394 citations · ⚡54

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

MIT News · Artificial Intelligence Oct 28, 2026

Making machines that can listen

Professor Paris Smaragdis develops computers with superhuman hearing for applications like speech recognition, music understanding, and environmental monitoring.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.