mlsanityData to 14 Oct 2026

Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent

arXiv 2411.03925 ↗First posted 6 Nov 2024cs.LG quant-phcited by 0

Not on the map. Why?

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.

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

30 of 113 references.

References · 30

  1. 2018Online Learning: A Comprehensive Surveycited by 205
  2. 2013Non-stationary Stochastic Optimizationcited by 175
  3. 2015Online Optimization : Competing with Dynamic Comparatorscited by 99
  4. 2016Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradientcited by 66
  5. 2016Improved Dynamic Regret for Non-degenerate Functionscited by 46
  6. 2018Online Learning of Quantum Statescited by 37
  7. 2013Online Learning for Time Series Predictioncited by 33
  8. 2018The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulationcited by 30
  9. 2017Quantum SDP-Solvers: Better upper and lower boundscited by 27
  10. 2020Online Sparse Reinforcement Learningcited by 25
  11. 2022The complexity of quantum support vector machinescited by 23
  12. 2023Adaptive Proximal Gradient Method for Convex Optimizationcited by 21
18 more
  1. 2023Provably Faster Gradient Descent via Long Stepscited by 20
  2. 2017Forward-Backward Selection with Early Droppingcited by 18
  3. 2022Bounded-Regret MPC via Perturbation Analysis: Prediction Error, Constraints, and Nonlinearitycited by 16
  4. 2022Adaptive Online Learning of Quantum Statescited by 12
  5. 2023Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Samplingcited by 7
  6. 2023Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameterscited by 7
  7. 2023Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Gamescited by 6
  8. 2022A Sublinear-Time Quantum Algorithm for Approximating Partition Functionscited by 5
  9. 2020Sublinear classical and quantum algorithms for general matrix gamescited by 4
  10. 2021How to Design Robust Algorithms using Noisy Comparison Oraclecited by 4
  11. 2019Quantum Sparse Support Vector Machinescited by 3
  12. 2015A Framework of Sparse Online Learning and Its Applicationscited by 2
  13. 2016Stabilized Sparse Online Learning for Sparse Datacited by 2
  14. 2018Quantum Circuit Designs of Integer Division Optimizing T-count and T-depthcited by 2
  15. 2019Quantum and Classical Algorithms for Approximate Submodular Function Minimizationcited by 2
  16. 2019Quantum-enhanced least-square support vector machine: simplified quantum algorithm and sparse solutionscited by 2
  17. 2023Quantum Algorithms for the Pathwise Lassocited by 2
  18. 2013Large-Scale Learning with Less RAM via Randomizationcited by 1

Built on by

Not cited yet.