Skip to yearly menu bar Skip to main content


Poster

Quantum Algorithms for Non-smooth Non-convex Optimization

Chengchang Liu · Chaowen Guan · Jianhao He · John C. S. Lui

West Ballroom A-D #7204
[ ]
Fri 13 Dec 11 a.m. PST — 2 p.m. PST

Abstract: This paper considers the problem for finding the (δ,ϵ)-Goldstein stationary point of Lipschitz continuous objective, which is a rich function class to cover a great number of important applications. We construct a novel zeroth-order quantum estimator for the gradient of the smoothed surrogate. Based on such estimator, we propose a novel quantum algorithm that achieves a query complexity of O~(d3/2δ1ϵ3) on the stochastic function value oracle, where d is the dimension of the problem. We also enhance the query complexity to O~(d3/2δ1ϵ7/3) by introducing a variance reduction variant. Our findings demonstrate the clear advantages of utilizing quantum techniques for non-convex non-smooth optimization, as they outperform the optimal classical methods on the dependency of ϵ by a factor of ϵ2/3.

Chat is not available.