Summary
This paper studies quantum algorithm for non-smooth non-convex stochastic optimization with zeroth-order oracle. It introduces an effective quantum estimator that reduces the variance compared to classical zeroth-order estimators. Upon substituting this estimator into known zeroth-order non-smooth optimizers, namely GFM and GDM+, the resulting quantum optimizer achieves improved rate $\tilde O(d^{3/2}\delta^{-1}\epsilon^{-3})$ and $\tilde O(d^{3/2}\delta^{-1}\epsilon^{-7/3})$ respectively for finding a $(\delta,\epsilon)$-Goldstein stationary point. Notably, quantum speedup improves upon the classical lower bound $\delta^{-1}\epsilon^{-3}$ by a factor of $\epsilon^{2/3}$. Moreover, a modified algorithm achieves $O(\sqrt{d}\epsilon^{-7/3})$ for smooth optimization, improving upon the best known rate.
Strengths
This paper proposes a new zeroth-order quantum estimator. This leads to new quantum algorithms that solves zeroth-order non-smooth non-convex optimization problem, which is not well studied in the literature. Moreover, the proposed algorithms show quantum speedup compared to their classical (non-quantum) counterparts. Notably, it improves over the classical lower bound of $\Omega(\delta^{-1}\epsilon^{-3})$ by a factor of $\epsilon^{2/3}$. Overall, these results represent a significant contribution to the understanding of optimization with quantum oracles. Given my expertise lies primarily in optimization and not in quantum computation, I am only able to assess the optimization-related aspects of this work.
Weaknesses
Although the dependence on $\delta,\epsilon$ is improved, the dimension dependence is suboptimal. In particular, since GFM and GFM+ are known to have suboptimal dimension dependence $d^{3/2}$, so do QGFM and QGFM+. On the other hand, as observed by Kornowsky and Shamir [1], optimizing the random smoothing $f_\delta$ with a non-smooth optimizer, such as online-to-non-convex (o2nc) [2], eliminates this $\sqrt{d}$ factor and achieves $O(d)$ in dimension. Hence, my intuition suggests that upon substituting the quantum estimator into o2nc and following a similar approach to Kornowsky and Shamir, the authors might be able to recover $O(d)$ (or even better) dimension dependence.
[1] Kornowski, G. and Shamir, O., “An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization”, 2023. doi:10.48550/arXiv.2307.04504.
[2] Cutkosky, A., Mehta, H., and Orabona, F., “Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion”, 2023. doi:10.48550/arXiv.2302.03775.
Questions
- As someone unfamiliar with quantum computation, I have a general question: Is the proposed quantum oracle practically feasible to implement, or is it purely theoretical?
- line 87: does state $|i\rangle$ denote the $i$-th orthonormal basis of $\mathcal{H}^m$?
- line 100: what does it mean by $|\mathbf{x}\rangle |q\rangle$? Is it a shorthand for tensor product?
- Thm 3.4 part 1: should it be $Var(\hat g) \le \hat\sigma_1^2$ instead of $\hat \sigma_1$? part 2: number of queries should be $\frac{d^{3/2}L\\|y-x\\|}{\delta \hat\sigma_2}$ (i.e., currently it's missing $1/\delta$)? Since this theorem is the main result of the quantum oracle, I encourage the authors to carefully check its correctness.
also in the proof (line 471): $\sigma_1^2$ => $\hat\sigma_1^2$?
Minor comments:
- line 98: $C_{f(x)} = f(x)$ => $C_f(x) = f(x)$?
- Proposition 2.1: the properties of smooth surrogate $f_\delta$ are known in [1] and [2], and Lin et. al. and Chen et. al. are restating these results in their papers. Hence, these should be more appropriate references.
[1] Yousefian, F., Nedić, A., and Shanbhag, U. V., “On Stochastic Gradient and Subgradient Methods with Adaptive Steplength Sequences”, 2011. doi:10.48550/arXiv.1105.4549.
[2] Duchi, J. C., Bartlett, P. L., and Wainwright, M. J., “Randomized Smoothing for Stochastic Optimization”, 2011. doi:10.48550/arXiv.1103.4296.