Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper analyses the uniform stability of zero-order optimisation algorithms. Using the Gaussian randomisation for the gradient estimator that was put forward and extensively analysed by Nesterov and Spokoiniy, the authors establish the stability result in the spirit of Hardt et al [1] (who were only dealing with the pure SGD). This work focuses only on the generalisation bounds and ignores the optimisation error, referring to the work of Duchi et al [13].
strengths_and_weaknesses: Overall the paper is relatively well written and easy to follow. My main concern is in the relevance and the novelty of the analysis. Nesterov and Spokoiniy [14] (see Theorem 1) show that the gradient estimator deployed by the authors of this submission is an *unbiased estimator* of a smoothed version of $f(\cdot, z)$. As long as the original function is Lipschitz (which is the case here), the smoothed version is a good approximation of the original one and the quality of this approximation is controlled by the parameter $\mu$. Thus, the algorithm analyzed by the authors of this submission is an SGD performed on a slightly different objective, which has identical regularity properties. Consequently, using the result of Hardt et al [1] in the context of SGD + the triangle inequality coupled with Theorem 1 from Nesterov and Spokoiniy [14], we immediately get the stability result for the zero-order variant considered in this submission (and it allows us to pick $\mu$ properly). Thus, I wonder if the authors could actually compact all their analysis into a couple of lines outsourcing most of the analysis from [1] and [14]?

What is actually pretty interesting is that if the original functions are NOT $\beta$-smooth, then the smoothed function has a Lipschitz gradient with the constant that depends on $\mu$. Hence, an interesting direction could be the exploration of the case of non-$\beta$-smooth loss functions. Unfortunately, this case is not considered by the authors.
questions: I addressed my main concerns in the previous part. I will update this part after the discussion phase and the authors' responses.
limitations: The authors addressed the limitations of their work. I will update this part after the discussion phase and the authors' responses.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: 
In this paper, the authors provide generalization error bounds for derivative-free updates under $L$-Lipschitz and $\beta$-smooth assumption of the loss fucntion.  The main technique extends  (Hardt et al.  2016) by bounding an additional gradient approximation error term ($\epsilon_{est}$).
strengths_and_weaknesses: 
Pros.
1.  The generalization bounds for zeroth-order gradient update are new, and it may be potential for black-box learning tasks.

2.  The bounds are independent of the dimension $d$ and the number of function evaluations per step $K$.

Cons.

1.  In the proof of Lemma 2 (Line 194), it seems that $P(\mathcal{E}_t) = \frac{1}{n}$ instead of $P(\mathcal{E}_t) = 1- \frac{1}{n}$.  
    If so, how does this influence the following proof and main theorem?

2. The $\beta$-smooth assumption of the loss function is a little bit strong. It requires the second-order derivative to be bounded.  It narrows down the potential loss functions because many practical loss functions may not have second-order derivatives, which makes the bounds less appealing.


===============================

Thanks for the authors' detailed response.  My main concern has been clarified. 
questions: 

 Could the authors explain more about the proof of Lemma 2 to clarify my above concern? if $P(\mathcal{E}_t) = \frac{1}{n}$ instead of $P(\mathcal{E}_t) = 1- \frac{1}{n}$, how does this influence the generalization bounds?
  
limitations: NA
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper establishes generalization error bounds of the gradient-free analogue of the SGD---zero-order stochastic search (ZoSS)---in which the gradient of the loss function at a point is approximated by $K + 1$ values ​​of the function in the vicinity of this point. The cases of nonconvex and bounded, convex and unbounded, nonconvex and unbounded loss functions are considered. However, in all cases, the authors require that the loss function be Lipschitz and smooth.
strengths_and_weaknesses: **Strengths**

- The bounds are a natural generalization of the bounds by Hardt et al. (2016) to the case of ZoSS. It is noteworthy that the order of the convergence rate of the ZoSS is the same as that of the SGD.

- The proofs of the theorems are quite accessible: the reader only needs a college-level knowledge of Calculus, Linear Algebra, and Probability.

**Weaknesses**

- The requirement that the loss function be smooth calls into question the motivation for this work. After all, if we have smoothness and we know the loss function, then we can use the SGD. If we don't know the loss function, then how can we check its smoothness?

- The work lacks empirical validation of the theory on real data. It would also be great if the authors show a specific natural example where the ZoSS (under the paper's assumptions) is applicable and the SGD is not.
questions: How one shall choose the values of $K$ and $\mu$ in practice?
limitations: I think that the requirement of Lipschitz and smoothness is the main limitation of this work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper provides generalization bounds for the ZoSS algorithm, based on the analysis of algorithmic stability. The bounds match the previous work of HRS16 on SGD. The main technical ingredient is a recursion lemma which controls how fast the expected distance between two ZoSS instances grow, when they differ on only one example. This result is then extended to a few different scenarios.
strengths_and_weaknesses: The method is similar to the analysis of SGD (HRS16) in spirit, and the achieved bound is not very surprising. Still, it's good to see similar generalization bounds can be obtained for zeroth-order optimization (though it shares the same drawbacks of HRS16 as well, such as the linear dependence on $T$).

The recursion lemma is interesting.

The writing is good and the paper is easy-to-follow in general.

The title seems a bit unclear and misleading to me. I suggest change it to be more specific to avoid confusion (like 'generalization bounds for zeroth-order optimization via algorithmic stability'?). The analysis also applies only to ZoSS algorithms and doesn't seem to be able to cover all zeroth-order algorithms.

To conclude, the results of this paper are solid and meaningful in that it provides the first generalization analysis for zeroth-order optimization. But it's felt that there isn't enough technical depth (incremental over HRS16) and the paper is a bit over-selling.
questions: What's 'high-probability analysis' (line 43)? Is it a typo?

Is it possible to achieve similar results for one-point zeroth-order algorithms? For example, the 'gradient descent without a gradient' method of FKM04.
limitations: The authors addressed some limitations
review_title: null

Meta-review: metareview: The paper provides generalization bounds for zeroth order stochastic search (ZoSS) based on algorithmic stability. The paper appears to follow from a fairly modest modification of Hardt, Recht and Singer `16, but the consensus among reviewers is that this modification is not trivial, and the bounds are novel and interesting. Consequently, I recommend acceptance.
confidence: Less certain
Decision: Accept