Research map / Bandits and online learning / Online convex optimization and games
Quantum Algorithm for Online Exp-concave Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a quantum online quasi-Newton method (QONS) that estimates gradients with O(1) quantum queries per round to a zeroth-order oracle, achieving O(n log T) regret for bandit exp-concave optimization with multi-point feedback.
Problem
Online exp-concave optimization with zeroth-order (bandit, multi-query) feedback, where classical methods only achieve O(nT^{2/3} log T) regret.
Approach
Uses a quantum gradient estimation circuit (Jordan-style, with an improved analysis giving O(1) queries) to produce an inexact gradient with l1-norm error control, plugged into an online Newton step update; extends the inexact-gradient analysis to exp-concave losses and proposes quantum adaptive gradient and Hessian-update variants.
Key results
- Quantum online quasi-Newton method achieves O((DG+1/alpha) n log(T+log T)) regret with O(1) oracle queries per round, versus O(nT^{2/3} log T) for the best classical zeroth-order method.
- Gradient estimation error is bounded in l1 norm with probability 1-rho using O(1) queries, removing the O(log n) repetitions of prior quantum gradient estimators.
- Online Newton method with Hessian update achieves O(DLn/alpha log(T+1)) regret under its assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use quantum zeroth-order gradient estimation with QONS instead of the classical estimated-gradient online Newton step | Online exp-concave optimization · Zeroth-order feedback | regret bound: $O\left(DGn T^{2/3} \log T\right)$ -> $O\left(DGn \log (T+\log T)\right)$ | Helped |
| Use quantum zeroth-order feedback instead of full-information feedback | Online exp-concave optimization · Online exp-concave optimization | regret bound: $O\left(DGn \log T\right)$ -> $O\left(DGn \log (T+\log T)\right)$ | No clear effect |
Surprising findings
- The analysis implies a classical finite-difference method with O(n) queries per round also attains logarithmic regret.
Limitations
- Assumes loss functions are beta-smooth in the main analysis; non-smooth case requires extra randomized smoothing and different parameter choices.
- Quantum Hessian estimation with first-order oracle needs O(n) queries, so O(1)-query Hessian estimation remains open.
- Requires quantum-enabled player and adversary with quantum zeroth-order oracle access; no hardware experiments.
Experimental setup
Metrics: regret
Baselines: Online Newton step with estimated gradient (Liu et al. 2018) Full-information online Newton step (Hazan et al. 2007) Finite difference ONS
Builds on: online Newton step Jordan quantum gradient estimation AdaGrad quantum online subgradient descent
Closest papers by meaning
- Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes (ICML 2025 · similarity 0.86)
- Quantum Algorithms for Non-smooth Non-convex Optimization (NeurIPS 2024 · similarity 0.86)
- Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss (ICLR 2024 · similarity 0.85)
- Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret (ICML 2024 · similarity 0.85)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.85)
- Quantum Algorithms and Lower Bounds for Finite-Sum Optimization (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.