Quantum Speedups for Minimax Optimization and Beyond
Chengchang Liu, Zongqi Wan, Institute of Computing Jialin Zhang, Institute of Computing Xiaoming Sun, John C. S. Lui
This paper investigates convex-concave minimax optimization problems where only the function value access is allowed.We introduce a class of Hessian-aware quantum zeroth-order methods that can find the $\epsilon$-saddle point within $\tilde{\mathcal{O}}(d^{2/3}\epsilon^{-2/3})$ function value oracle calls.This represents an improvement of $d^{1/3}\epsilon^{-1/3}$ over the $\mathcal{O}(d\epsilon^{-1})$ upper bound of classical zeroth-order methods, where $d$ denotes the problem dimension.We also extend these results to $\mu$-strongly-convex $\mu$-strongly-concave minimax problems using a restart strategy, and show a speedup of $d^{1/3}\mu^{-1/3}$ compared to classical zeroth-order methods.The acceleration achieved by our methods stems from the construction of efficient quantum estimators for the Hessian, requiring only $\tilde{\mathcal{O}}(d)$ queries to function value oracle, and the subsequent design of efficient Hessian-aware algorithms.Furthermore, we show that such quantum estimators can also be applied to non-convex problems, leading to a reduction in the query complexity compared to classical methods.