Quantum Algorithms for Non-smooth Non-convex Optimization
Authors: Chengchang Liu, Chaowen Guan, Jianhao He, John C. S. Lui
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper considers the problem of finding the (δ,ǫ)-Goldstein stationary point of the Lipschitz continuous objective, which is a rich function class to cover a large 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 improve the query complexity to O(d3/2δ 1ǫ 7/3) by introducing a variance reduction variant. We present these results in Section 3 and Appendix A. The Proof of Lemma 3.2. |
| Researcher Affiliation | Academia | Chengchang Liu* 1 Chaowen Guan* 2 Jianhao He# 1 John C.S. Lui 1 1 The Chinese University of Hong Kong 2 University of Cincinnati |
| Pseudocode | Yes | Algorithm 1 Quantum Gradient-Free Method (QGFM) and Algorithm 2 Fast Quantum Gradient-Free Method (QGFM+) |
| Open Source Code | No | The paper is theoretical and does not mention releasing any source code for its proposed methods. |
| Open Datasets | No | The paper is theoretical and does not involve empirical training or evaluation on datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation on datasets. |
| Hardware Specification | No | The paper is theoretical and does not specify any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not list any software dependencies with specific version numbers for experimental replication. |
| Experiment Setup | No | The paper is theoretical and does not include details on experimental setup such as hyperparameters or training configurations. |