# Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent

arXiv: https://arxiv.org/abs/2411.03925 · HTML: https://mlsanity.com/paper/2411.03925/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 113 references that are in the map.
- First posted on arXiv 6 Nov 2024.

## Builds on (most cited first, 30 of 30)

- [Online Learning: A Comprehensive Survey](https://mlsanity.com/paper/1802.02871/) (2018)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Improved Dynamic Regret for Non-degenerate Functions](https://mlsanity.com/paper/1608.03933/) (2016)
- [Online Learning of Quantum States](https://mlsanity.com/paper/1802.09025/) (2018)
- [Online Learning for Time Series Prediction](https://mlsanity.com/paper/1302.6927/) (2013)
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://mlsanity.com/paper/1804.01973/) (2018)
- [Quantum SDP-Solvers: Better upper and lower bounds](https://mlsanity.com/paper/1705.01843/) (2017)
- [Online Sparse Reinforcement Learning](https://mlsanity.com/paper/2011.04018/) (2020)
- [The complexity of quantum support vector machines](https://mlsanity.com/paper/2203.00031/) (2022)
- [Adaptive Proximal Gradient Method for Convex Optimization](https://mlsanity.com/paper/2308.02261/) (2023)
- [Provably Faster Gradient Descent via Long Steps](https://mlsanity.com/paper/2307.06324/) (2023)
- [Forward-Backward Selection with Early Dropping](https://mlsanity.com/paper/1705.10770/) (2017)
- [Bounded-Regret MPC via Perturbation Analysis: Prediction Error, Constraints, and Nonlinearity](https://mlsanity.com/paper/2210.12312/) (2022)
- [Adaptive Online Learning of Quantum States](https://mlsanity.com/paper/2206.00220/) (2022)
- [Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling](https://mlsanity.com/paper/2301.03763/) (2023)
- [Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters](https://mlsanity.com/paper/2311.14823/) (2023)
- [Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games](https://mlsanity.com/paper/2304.14197/) (2023)
- [A Sublinear-Time Quantum Algorithm for Approximating Partition Functions](https://mlsanity.com/paper/2207.08643/) (2022)
- [Sublinear classical and quantum algorithms for general matrix games](https://mlsanity.com/paper/2012.06519/) (2020)
- [How to Design Robust Algorithms using Noisy Comparison Oracle](https://mlsanity.com/paper/2105.05782/) (2021)
- [Quantum Sparse Support Vector Machines](https://mlsanity.com/paper/1902.01879/) (2019)
- [A Framework of Sparse Online Learning and Its Applications](https://mlsanity.com/paper/1507.07146/) (2015)
- [Stabilized Sparse Online Learning for Sparse Data](https://mlsanity.com/paper/1604.06498/) (2016)
- [Quantum Circuit Designs of Integer Division Optimizing T-count and T-depth](https://mlsanity.com/paper/1809.09732/) (2018)
- [Quantum and Classical Algorithms for Approximate Submodular Function Minimization](https://mlsanity.com/paper/1907.05378/) (2019)
- [Quantum-enhanced least-square support vector machine: simplified quantum algorithm and sparse solutions](https://mlsanity.com/paper/1908.01462/) (2019)
- [Quantum Algorithms for the Pathwise Lasso](https://mlsanity.com/paper/2312.14141/) (2023)
- [Large-Scale Learning with Less RAM via Randomization](https://mlsanity.com/paper/1303.4664/) (2013)

## Abstract (arXiv)

Logistic regression, the Support Vector Machine (SVM), and least squares are well-studied methods in the statistical and computer science community, with various practical applications. High-dimensional data arriving on a real-time basis makes the design of online learning algorithms that produce sparse solutions essential. The seminal work of hyperlinkcite.langford2009sparseLangford, Li, and Zhang (2009) developed a method to obtain sparsity via truncated gradient descent, showing a near-optimal online regret bound. Based on this method, we develop a quantum sparse online learning algorithm for logistic regression, the SVM, and least squares. Given efficient quantum access to the inputs, we show that a quadratic speedup in the time complexity with respect to the dimension of the problem is achievable, while maintaining a regret of O(1/√T), where T is the number of iterations.