Research map / Learning theory and algorithms / Sample complexity
Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss
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.
Gives a quantum algorithm for minimizing the maximum of N convex Lipschitz functions with Õ(√N ε^{-5/3} + ε^{-8/3}) zeroth-order queries, plus a matching-in-N quantum lower bound Ω̃(√N ε^{-2/3}).
Problem
Minimizing the maximum of N convex, Lipschitz functions to ε-suboptimality, where classical methods need N-dependent subgradient/first-order queries; the quantum query complexity was open.
Approach
Implements the ball-regularized optimization oracle for the softmax surrogate by replacing classical sampling from the softmax distribution with quantum Gibbs-style state preparation plus quantum maximum finding and amplitude amplification, costing Õ(√N) quantum queries per sample batch; the lower bound adapts classical progress-control with a multi-round unstructured search problem.
Key results
- Quantum algorithm achieves Õ(√N ε^{-5/3} + ε^{-8/3}) queries to the quantum zeroth-order oracle, improving classical Õ(N ε^{-2/3} + ε^{-8/3}) in N by a quadratic factor.
- Quantum lower bound of Ω̃(√N ε^{-2/3}) queries for minimizing the maximum of N convex Lipschitz functions, matching the algorithm's N-dependence up to polylog factors.
- Quantum top-K maximum finding with O(√(KN) log(1/δ)) queries gives state preparation of K Gibbs samples in O(√(NK)) queries.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use quantum sampling instead of classical sampling in ball optimization acceleration | Ball optimization acceleration for minimizing the maximum of N convex, Lipschitz functions · Minimizing maximum of N convex, Lipschitz functions | oracle query complexity dependence on N: N -> \sqrt{N} | Helped |
| Use quantum sampling instead of classical sampling in ball optimization acceleration | Ball optimization acceleration for minimizing the maximum of N convex, Lipschitz functions · Minimizing maximum of N convex, Lipschitz functions | oracle query complexity dependence on \epsilon: \epsilon^{-2/3} -> \epsilon^{-5/3} | Mixed |
| Use quantum sampling in the proposed algorithm | Quantum algorithm for minimizing the maximum of N convex, Lipschitz functions · Minimizing maximum of N convex, Lipschitz functions | dependence on N relative to the quantum lower bound: \tilde{O}(\sqrt{N}\epsilon^{-5/3} + \epsilon^{-8/3}); \tilde{\Omega}(\sqrt{N}\epsilon^{-2/3}) | Helped |
Limitations
- Gap of order ε between the leading term of the upper bound (ε^{-5/3}) and the lower bound (ε^{-2/3}) remains open.
- Smoothness of the functions is not exploited; faster classical results with smooth functions are not matched quantumly.
Experimental setup
Metrics: query complexity
Baselines: subgradient method ball optimization acceleration with classical first-order oracle
Builds on: Monteiro-Svaiter acceleration ball optimization oracle acceleration Epoch-SGD-Proj quantum maximum finding quantum gradient estimation
Closest papers by meaning
- Quantum Algorithms and Lower Bounds for Finite-Sum Optimization (ICML 2024 · similarity 0.92)
- Quantum Algorithms for Non-smooth Non-convex Optimization (NeurIPS 2024 · similarity 0.90)
- Isotropic Noise in Stochastic and Quantum Convex Optimization (NeurIPS 2025 · similarity 0.88)
- Optimal algorithmic complexity of inference in quantum kernel methods (NeurIPS 2026 · similarity 0.86)
- Quantum Algorithms for Finite-horizon Markov Decision Processes (ICML 2025 · similarity 0.85)
- Quantum Algorithm for Online Exp-concave 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.