Venue: NeurIPS 2022 Conference

Reviews:

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: This paper introduced two zero-order algorithms to compute the Goldstein stationary points for nonconvex nonsmooth problem. In contrast to the first-order case, the dependence on dimension is unavoidable for algorithms that only use function values. The authors show the gradient of a randomized smoothed function with a delta-ball is belong to the Goldstein delta-subdifferential, which forms the basis for the new gradient-free algorithms. They show the new algorithms compute a Goldstein stationary point in expectation within polynomial oracle complexity and the dimension dependence is only sqrt(d) worse than the convex/smooth case. They also proved a high-probability bound with a two-phase scheme.

strengths_and_weaknesses: As nonconvex nonsmooth problems are everywhere especially in the DL setting, new practical algorithm with finite time oracle complexity is important and desirable nowadays. This paper studies the computation of Goldstein approximate stationary point, which has exhibited attractive algorithmic consequence in recent years. The main contributions are two zero-order finite-time methods which are further built upon an interesting observation that the randomized smoothed function with a delta-ball is belong to the Goldstein delta-subdifferential. The paper is well-written and easy to follow. My comments are as follows:

* Proposition 2.3 basically repeats [78, Lemma 8]. In the proof, it might miss a norm in L629 and L634.
* The step size of Algorithm 1,2,3 seems dependent on the \Delta, which is usually unknown in practice and is not necessary in the first-order setting for Lipschitz functions, e.g., in [79].
* The following reference computing Goldstein stationary points concurrent partly to [30] might be relevant:

[R] Lai Tian, Kaiwen Zhou, and Anthony Man-Cho So. On the finite-time complexity and practical computation of approximate stationarity concepts of Lipschitz functions. ICML, 2022.

* L45: "Clark" -> "Clarke"
questions: See main comments above.
limitations: Yes.
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 established a novel optimality criterion for non-smooth non-convex Lipschitz function called (δ,ε)-Goldstein stationary point and proposed a gradient-free algorithm with its stochastic version by deriving the Goldstein subdifferential and uniform smoothing technical. The last-iterate convergence analysis of the proposed methods was given, which guarantee the convergence to a (δ,ε)-Goldstein stationary point with high probability for both deterministic and stochastic version. State-of-art lower bounds of total oracle calls are given in terms of δ,ϵ and Λ for the proposed methods. Numerical experiments have shown the effectiveness of the proposed methods.
strengths_and_weaknesses: The theoretical result in this paper is interesting.  The authors established a novel optimality criterion for non-smooth non-convex Lipschitz function called (δ,ε)-Goldstein stationary point and proposed a gradient-free algorithm with its stochastic version by deriving the Goldstein subdifferential and uniform smoothing technical. 
questions: Though the paper is theoretically sound, there are still some questions need to be discussed in this paper:

1.	The authors proposed a class of subdifferential-based gradient-free algorithms. What is the advantage of the proposed algorithms compared to the gradient-based methods and zeroth-order methods?

2.	The authors compared the performance of the proposed algorithms with different choice on MNIST, which is literally a small-scale and simple dataset. Why not use more larger datasets to verify the excellent performance of the proposed algorithm? In addition, the author's comparison algorithms are too few, which can be compared with some more advanced zeroth-order and gradient-free optimization algorithms like INGD[R1].
[R1] J. Zhang, H. Lin, S. Jegelka, S. Sra, and A. Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In ICML, pages 11173–11182. PMLR, 2020.

3.	It seems that the authors trained a quite simple convolutional neural network model on image classification task rather than some more modern and efficient models like [R2] and [R3] according to the experiment results, which is insufficient for validating the effectiveness of the proposed methods. 
[R2] He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016

[R3] G. Huang, Z. Liu, L. Van Der Maaten and K. Q. Weinberger, "Densely Connected Convolutional Networks," 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017

4.	Grammar mistakes. Line 342, “We have proposed and analyzed a class of…” “have proposed and analyzed” should be replaced by “propose and analyze”.

limitations: The authors proposed a class of subdifferential-based gradient-free algorithms. What is the advantage of the proposed algorithms compared to the gradient-based methods and zeroth-order methods? The authors compared the performance of the proposed algorithms with different choice on MNIST, which is literally a small-scale and simple dataset. Why not use more larger datasets to verify the excellent performance of the proposed algorithm?



----------after feedback---------------

The authors address my comments well, so I increased my score.
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: This paper studied the gradient-free (zeroth-order) methods for the nonsmooth nonconvex optimization problems, and provided the solid theoretical analysis for the proposed gradient-free methods. Notably, it established a useful relationship between the Goldstein subdifferential and uniform smoothing via appeal to the hyperplane separation theorem. Some experimental results demonstrate the effectiveness of the proposed methods. 
strengths_and_weaknesses: Novelty of this paper: Overall, it provides some solid theoretical results on gradient-free methods for the nonsmooth nonconvex optimization.

Weakness of this paper: The Lipschitz continuous condition used in the paper may be not mild. 

questions: Some comments:

1)	Could we further relax the Lipschitz continuous condition in the gradient-free methods for nonsmooth nonconvex optimization ?

2)	In the convergence analysis (Theorem 3.2,3.4-3.6), do we need to choose some small parameter $\delta$ that relies on $d$ and $ \epsilon$, as in the existing zeroth-order methods for smooth optimzation? 

limitations: Yes
review_title: null

Meta-review: metareview: The authors introduce two derivative-free algorithms for computing the Goldstein stationary points in the context of nonconvex nonsmooth optimization, and show that they enjoy polynomial complexity (in expectation), while the dimension dependence (which is unavoidable in the derivative-free setting) is worse by only an sqrt(d) factor compared to the convex/smooth case. A high-probability bound with a two-phase scheme was established as well.

The reviewers described the strengths of the paper in the following way:
- The paper is well-written and easy to follow. 
- The theoretical result in this paper is interesting. 
- The authors established a novel optimality criterion for non-smooth non-convex Lipschitz function called (δ,ε)-Goldstein stationary point and proposed a gradient-free algorithm with its stochastic version by deriving the Goldstein subdifferential and uniform smoothing technical.
- Overall, it provides some solid theoretical results on gradient-free methods for the nonsmooth nonconvex optimization.

Some criticism was raised, but the authors managed to address it in their rebuttal. I agree with the collective judgment of the reviewers that this paper clearly passes the bar of acceptance. Please make sure that all criticism is properly addressed in the camera-ready version of the paper as well.

Congratulations on a nice paper!

AC
confidence: Certain
Decision: Accept