Poster
Quantum Algorithms for Non-smooth Non-convex Optimization
Chengchang Liu · Chaowen Guan · Jianhao He · John C. S. Lui
West Ballroom A-D #7204
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 on the stochastic function value oracle, where is the dimension of the problem. We also enhance the query complexity to 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 .
Chat is not available.