@inproceedings{
liu2024quantum,
title={Quantum Algorithms for Non-smooth Non-convex Optimization},
author={Chengchang Liu and Chaowen Guan and Jianhao He and John C.S. Lui},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=wsGzvhnoaX}
}
This paper considers the problem for finding the  $(\delta,\epsilon)$-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 $\tilde{\mathcal{O}}(d^{3/2}\delta^{-1}\epsilon^{-3})$ on the stochastic function value oracle, where $d$ is the dimension of the problem. 
We also enhance the query complexity to $\tilde{\mathcal{O}}(d^{3/2}\delta^{-1}\epsilon^{-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 $\epsilon$ by a factor of $\epsilon^{-2/3}$.
Quantum Algorithms for Non-smooth Non-convex Optimization
Chengchang Liu Chaowen Guan Jianhao He John C.S. Lui