Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity

Summary

The paper consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. Authors provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds. They propose an algorithm that features a combination of a bootstrapping stage and a mirror-descent stage.

Strengths

The authors consider a problem formulation where the gradient of the function or higher order derivatives are not available. This problem formulation is of extreme interest in the field of Machine Learning. However, the work has many weaknesses (see below).

Weaknesses

1. Almost no mention is made of work motivation. This is an important part that **cannot be missed**... 2. Also, this paper gives the impression that **it was produced clearly not in this year**, since the main references are **from 2021** and earlier. But since 2021, the research, in particular in the area of zero-order optimization has a lot of interest in the community and is highly advanced compared to what the authors cited as related works. For example, in addition to a number of cited papers studying the zero-order optimization problem with the assumption of increased smoothness of the function, there is already a more recent paper that has been missed: _Akhavan et al. (2023)_ [1], which proposes an improved analysis of gradient approximation bias estimation as well as second moment estimation. Similarly, there is a weakly described section presenting different gradient approximations, where the main focus fell on the smoothing vector (Gaussian vector or Randomized vector). But, there are already a number of papers, such as _Gasnikov et al. (2024)_ [2], which have shown that the randomized approximation clearly performs better on practical experiments than the Gaussian approximation. It seems better to give an overview of different gradient approximations, including $l_1$ randomization, in this section 3. Since I have already mentioned the topic of practical experiments, it is important to note that despite the fact that the authors provide mainly theoretical work, a paper that is intended for presentation at the NeurIPS conference should **show the effectiveness of the proposed results** in real life. This paper lacks any experiments, which is a major weakness of the paper. 4. The structure of the article is poorly chosen... It seems that the sections "Main contribution", "Discussion" and "Conclusion" would **have improved the presentation** of the article's results. 5. Regarding the results themselves, essentially **only one result is presented**, which is a minor contribution. It would be interesting to consider when the function is not only twice differentiable but also has a higher order of smoothness, as well as other settings of the problem: convex, non-convex, maybe the Polyak–Lojasiewicz condition, etc. [1] Akhavan A. et al. (2023). Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm //arXiv preprint arXiv:2306.02159. [2] Gasnikov, A. et al. (2024). Highly smooth zeroth-order methods for solving optimization problems under the PL condition. Computational Mathematics and Mathematical Physics.

Questions

I have a few questions and suggestions: - It seems that Theorem 3.1 can be improved in terms of dependence on the problem dimension $d$ using tricks from the work of _Akhavan et al. (2023)_ [1] - Can the authors explain what the final result would look like if $w_t$ does not necessarily have zero mean, but is independent of vector $e$ (randomization on the sphere)? Also, if we consider deterministic noise $|\delta(x)| \leq \Delta$ as noise. [1] Akhavan A. et al. (2023). Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm //arXiv preprint arXiv:2306.02159.

Rating

5

Confidence

3

Soundness

2

Presentation

1

Contribution

2

Limitations

N/A

Summary

The paper studies zero order stochastic optimization (the learner has access to noisy function evaluation only) assuming the objective is $M$-strongly convex and has a $\rho$-Lipschitz (in forbenius norm) Hessian. Matching upper and lower bounds are presented, which establish a tight result of suboptimality $\Theta(d T^{-2/3}M^{-1})$ (w.h.p.) after $T$ function evaluations.

Strengths

* A tight result is achieved for the setting studied. * On the technical side, the gradient evaluation procedure in the final stage of the algorithm uses samples from the ellipsoid induced by the Hessian approximation rather than opting for isotropic sampling. Further, a novel approach for analyzing the bias and variance of this estimation procedure is presented that yields sharp bounds. This technique has not been used by prior works, and seems crucial for the minimax optimal result. * This result improves over the most closely related prior state-of-the-art Novitskii & Gasnikov (2021) by a factor of $d^{1/3}$, who require an additional Lipschitz gradient assumption (see discussion in Appendix A).

Weaknesses

Nothing in particular.

Questions

- Lines 125-126: 1-subgaussianity already implies variance $\leq 1$. - Akhavan et al. (2020) consider the Lipschitz gradient setting and do not require a Lipschitz Hessian. Hence it seems their results and yours are incomparable (correct?). Given this I did not understand lines 315-317: "On the other hand ... well." Do you include Akhavan et al in this statement? It doesn't seem true that a direct application of your algorithm order wise improves the result of Akhavan et al because your result does not apply in their setting. - Since we consider a twice differentiable objective over a bounded domain, it follows the gradient is in fact Lipschitz. With this in mind, are the assumptions of Novitskii & Gasnikov (2021) indeed stronger than those made in this work?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

Summary

This work studies the convergence of zeroth order stochastic optimization for a class of strongly convex, second-order smooth objective functions. The authors assume that the noisy one-point feedback oracle is available, and the additive noise is subgaussian. Both the asymptotic upper bound and the matching lower bound for the minimax simple regret are provided.

Strengths

The authors propose a novel algorithm that combines gradient estimation, bootstrapping procedures, and a mirror descent procedure. This combination enables accurate estimation of gradients and Hessians under second-order smoothness, thereby achieving the optimal rate.

Weaknesses

The idea of this work is interesting, but the presentation needs improvement. Some main results should be explicitly and rigorously stated as theorems, for example, eq (6). Additionally, it is unclear why the two stages in Algorithm 4 are necessary. Providing intuition and explanation for the two stages and the choice of parameters in Algorithm 4 would be beneficial. Furthermore, the proof of the upper bounds contains gaps. The result obtained in line 601 is $\lim_{T\to\infty} T^{2/3}E[\|\nabla f(x_N^B)\|^3]=0$. It is unclear how $M$ and $\rho$ enter the final result and match eq(6) with the specific choice of $\epsilon$ in line 170. More detailed steps in the proof would help clarify this connection.

Questions

1. Remark 4.2: I cannot understand the first sentence. Are there any established results for the case of the cubic polynomial function $f$? 2. Algorithm 4: Is the $\hat H$ returned by HessianEst invertible? 3. Proof of Theorem 3.1: 1) In line 200, "First, recall our construction ensures that," could the author provide the proof of this statement? 2) In lines 203-204, the two displays omit the dimension dependence. Will this omission impact the final dimension dependence? 4. Line 358: I cannot see how to apply Lemma B.2, also known as Proposition 7 in [Yu et. al. 2023]. What is the $Var_{f\sim p}[f(x)]$?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The paper proposes a new algorithm but does not provide any numerical results to validate it. There are many interesting questions that could be investigated numerically regarding this method, such as its dependence on the length of the first and second stages.

Summary

The paper studies the problem of zero-order optimization of a strongly convex function whose Hessian is Lipschitz continuous. The proposed algorithm exploits zero-order information from the oracle to estimate the Hessian and gradient of the function at each iteration. Using these estimates, the authors employ a second-order method to achieve convergence for the optimization error. The results are asymptotic and valid for a sufficiently large number of function evaluations. The main contribution of the paper is improving the dependency of the achieved optimization error with respect to the dimension. The derived upper bound is minimax optimal with respect to the number of function evaluations, dimension, and the strong convexity parameter.

Strengths

The result of the paper regarding the upper bound is a significant and surprising contribution. In the literature, there was an optimality gap with respect to the dimension: the existing lower bound was of the order $d$, while the upper bound was of the order $d^{4/3}$. The main anticipation was that the lower bound was not tight enough. However, the result of this paper shows that $d$ is minimax optimal, which I find to be a very valuable observation.

Weaknesses

The main issue I encountered while reading the paper is that the authors should provide more motivation for their algorithm. For instance, they use two different gradient estimators, GradientEst and BootstrappingEst, but it is unclear why both are necessary and why one is not sufficient. The assumption on the noise is also more restrictive compared to previous work in the literature, see e.g. [1]. The authors assume that the noise is sub-Gaussian, whereas other papers have only assumed a finite second moment. The authors did not explain why this stronger restriction on the noise is needed. The main algorithm of the paper, Algorithm 4, consists of two stages. While the first stage of the algorithm seems natural, the second stage is not well motivated. [1] Arya Akhavan, Massimiliano Pontil, and Alexandre Tsybakov. Exploiting higher order smoothness in derivative-free optimization and continuous bandits. Advances in Neural Information Processing Systems, 2020.

Questions

1. As I mentioned earlier, could the authors explain why there is a need for two different gradient estimators? 2. Why does the noise need to be sub-Gaussian? Specifically, the results of Theorem 4.1 also hold for any noise with a finite second moment. 3. Could the authors motivate the second stage of the algorithm? The authors mentioned, "The role of the final stage is to ensure that $f(x_B) - f(x^*)$ is sufficiently small with high probability," but why you need such a guarantee with high probability, and not just in expectation? 4. Could the authors explain why they need a high probability bound in Theorem 4.3 and why expectation bounds are not sufficient? 5. I am a bit confused about where the authors used Assumption A (3). The parameter $R$ does not appear anywhere in the algorithms or in the final bound. 6. It would be helpful if the authors provided a discussion on the number of function evaluations used overall in the main algorithm. 7. A version of Theorem 3.2 has already appeared in [1] without the dependency on $\rho$. So, the novel aspect of this lower bound is its dependency on $\rho$, which I found interesting. Please correct me if I'm wrong, but unfortunately, I cannot see the proof of this theorem in the paper. 8. I would like to know the authors' thoughts on higher-order smoothness: if we assume that the higher derivatives are uniformly bounded, do the authors believe it is possible to achieve the dependency of $d$ with respect to the dimension by estimating higher-order derivatives? 9. Could the authors specify the lower bound for $T$ for all the results in the paper to hold? [1] Arya Akhavan, Massimiliano Pontil, and Alexandre Tsybakov. Exploiting higher order smoothness in derivative-free optimization and continuous bandits. Advances in Neural Information Processing Systems, 2020.

Rating

6

Confidence

3

Soundness

2

Presentation

2

Contribution

3

Limitations

The authors adequately addressed the limitations.

Rebuttal acknowledgment

I would like to thank the authors for the rebuttal. For now, I will maintain my current score. I plan to discuss the paper with the other reviewers and look forward to the author's discussions with them as well. I will update my score accordingly.