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 deals with optimization in the non smooth and non convex setting. This work is mainly based on the definitions of [Gol77] and recent results of [ZLJ+20].

It allows to find an efficient algorithm (combination of Algorithms 1 and 2) which guarantees (Corollary 5 and Theorem 6) hold only assuming $L$-Lipschitz continuity and almost everywhere differentiability (in the sense of the Lebesgue measure).

Then, authors propose a cutting-plane method to solve the intermediate minNorm problem (previously solve by Algorithm 1).
The advantage of this is the improvement in complexity dependance to $\epsilon$.
The drawback is the dependence on $d$.
This is therefore useful in small dimension.
strengths_and_weaknesses: Strengths:
- Good guarantees with few assumptions.

Weakness:
- [ZLJ+20] already got similar results. Only the need of solution to (2) is assumed. And the claim made by this paper on this oracle seem strong (see first point of next section).

===================================================================================================
========================================= After rebuttal ==============================================
===================================================================================================

The oracle [ZLJ+20] uses is indeed not computationally easy to build, for instance not compatible with the chain rule.
questions: l.47: I think what the cited paper means is that if one has access to the solution of (2) for the functions that are composed together, then the chain rule provides the solution for the function of interest.

l.61: This is a strong affirmation based on the assumption that the previous claim is false.

l.110: « Famously, [ZLJ+20] showed ». I think authors here refer to « [Gol77] ».

l.113: minor: authors use the notation $x_0$ to refer to the first iterate. Then use the indices starting from 1 for $g$. I suggest uniforming the notations.

l.113: I also suggest removing the O notation in the last equation since it seems we have $T\leq\frac{\Delta}{\delta \epsilon}$.

l.123: « A short computation shows that this is sure to be the case for all small $\lambda > 0$ as long as $\left< u, g \right> \leq \|g\|^2$ ». As one can see in l.132, this argument relies on the first order expansion on the norm of interest. the second term is non negative, but for small $\lambda$, we expect the first term to be dominant. This is actually true if and only if the first term is not zero, hence the inequality $\left< u, g \right> \leq \|g\|^2$ must be replaced by the strict inequality: $\left< u, g \right> < \|g\|^2$. Reason why the $\delta / 2$ is used in equation (4) and Algorithm 1 even uses $\delta/4$.

limitations: No limitations.
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 work studies the problem of finding stationary points of a Lipschitz function. The paper is an improvement to [ZLJ+20], where in the latter the authors proposed an algorithm motivated by Goldstein's subgradient method. The main obstacle of [ZLJ+20] is that the proposed algorithm needs the solutions of a convex feasibility problem (outlined in eq. (2), page 2). Under the assumption that the objective function is Lipschitz and its gradient and function evaluations can be computed almost everywhere, this paper proposed an algorithm that overcomes the aforementioned limitation of [ZLJ+20] and can recover the main result of [ZLJ+20], outlined in Theorem 6, page 6.  Then, the authors claim that the paper can improve the efficiency of the algorithm in low dimensions. The results also provide a further improvement in the case that the objective function is weakly convex (defined in line 19). 
strengths_and_weaknesses: Strengths:

1. The main contribution of the paper which is an improvement to [ZLJ+20] is well motivated. 
2. The authors provide a sufficient literature review. 

Weaknesses: 

1. From a technical point of view, it is not clear what the main technical novelties of this paper compare to [ZLJ+20].
2. The paper suffers from a lack of a discussion section at the very end of the paper.
3. In section 3 it would be nice if the authors emphasize more the role of "low dimensions", how they characterize the notion of "low dimensions" and technically exactly at which part they are exploring the low dimension phenomena.
questions: 1. Lines 110 - 111: "Famously, [ZLJ+20] showed that one can significantly decrease the value of $f$...". I will appreciate that if the authors address this in [ZLJ+20] and point out where is exactly such a result. 

2. In the proof of Lemma 3, what are the definitions of $\mathbb{R}_{+}\{y\}$ and $Q$?

3. In Algorithm 3, line 4: Since $\Omega_k$ may be a complicated set, how one can compute the center of gravity of such a set?

4. In Theorems 11 and 12: What is the definition of the covariance matrix of a convex set?
limitations: The authors addressed the limitations of their work (lines 98 - 99). I will update this part after the discussion phase and author responses.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the problem of minimising a Lipschitz function that is potentially non-smooth. Such functions are widely used in machine learning such as neural networks based on the ReLU activation function.
They are known to be differentiable almost everywhere (in Lebesgue measure sense), and the so-called Clarke sub-differential can be used in place of the usual gradient.

The subgradient method is a classical algorithm for minimising such functions, and its behaviour has been well studied for weakly convex functions. Recently, the paper [ZLJ+20] proposed an algorithm for finding stationary points for arbitrary Lipshitz and directionally differentiable functions based on Goldstein's conceptual sub gradient method. Recently, this was also complemented with lower bounds.

Despite its strengths, the algorithm of [ZLJ+20] requires the solution of a so-called auxiliary convex feasibility problem, which may be very difficult when the subgradient of the function is complicated. Hence the algorithm is not easy to implement in practice. 

The paper proposes two algorithms that address these concerns by replacing the non-standard auxiliary problem (oracle) of [ZLJ+20] with a standard first-order oracle. This is implementable for any Lipschitz function where the gradients can be computed almost everywhere in terms of Lipschitz measure. The algorithms output an approximate stationary point. The number of gradient/function evaluations for the first algorithm has no dimension dependence, and $O(1/(\epsilon^3 \delta))$ dependence in the approximation accuracy parameters $\epsilon$ and $\delta$. The second algorithm has a better behaviour in low dimensions, with $O(d/(\epsilon^2 \delta))$ dependence, and even better rates for weakly convex functions.
strengths_and_weaknesses: In our opinion, this is a very nice paper that studies a highly practically relevant question on finding stationary points for non-smooth Lipschitz functions.  The contributions of the paper are novel algorithms together with rigorous convergence analysis that obtain state-of-the-art accuracy guarantees for this problem. These algorithms cleverly use randomisation ideas to get around the issues of non-differentiability on a set of Lebesgue measure zero. The paper is very well written and it is a pleasure to read. In our opinion, this is an important contribution to the literature.

This is an important theoretical contribution with a significant amount of effort devoted to the proofs. It is understandable that there is no space in the current NeurIPS format for experimental evaluation, this is something that could be looked at in the future.
questions: Do the authors think that this new algorithm could be used for training ReLU-based neural networks?
There have been many efforts recently on coming up with sharp bounds on the Lipschitz constants, but perhaps the computation time for such algorithms could be a limiting factor.
limitations: The authors have adequately addressed the limitations of their work.
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: In this paper the authors propose a new algorithm to minimize a Lipschitz function.  The general machinery is based on the [ZLJ 20] algorithm and the main contribution of this paper is to propose a novel implementable oracle for it.

strengths_and_weaknesses: In contrast to [ZLJ 20], the proposed algorithm is easy to implement. This was done without sacrificing a good complexity, which in our case  matches lower bounds. In lower dimensions using the cutting plane algorithm instead of the subgradient method, the authors were able to improve complexity upon [ZLJ 20].

I think it is a nice paper with a clear and well-executed idea and with good explanations that show the motivation for each statement or its proof. However, the last section on low dimensions can be improved: first to make the reading more or less uniform and second to familiarize readers with those concept given there without definitions and intuition. I presume it was the page limit that prevented the authors from doing it in the first place.
questions: line 53: extra space between reference and a word. 

paragraph after eq (4): either not larger instead of smaller or it should be a strict inequality later. Otherwise, $u=g$ is a counterexample.

Lemma 2: I think the constant can be improved from 16 to 4. It is clear that the given proof is not optimal: we estimate $\|u - g\|$ in a crude way. Instead, we should use $\|u\|^2, \|g\|^2$ separately because for the inner product we have a much nicer bound.  Not important of course, but a few consecutive constants will become smaller.

Lemma 3: We integrate here over $S^{d-1}\times \mathbb{R}_+$ and Fubini's theorem allows us to switch integrals. Why does it give us the existence of the set $Q$? I feel it should be correct but perhaps some argument is missing.

Proof of Lemma 3: different fonts for $Q$.

line 194: Don't we need boundedness of $Q$ for min?

line 204: It is correct, but I spent like 5 min to understand why it is so. Just adding "first-order optimality condition" would save me them.

Section 3.1: I think it would be nicer to add more details. Right now it is written by someone and for someone who already knows all the ingredients: cutting plane algorithms, ellipsoid algorithms, center of gravity, etc. Perhaps with an extra page it would be possible to make that part more readable.

Proof of Th. 4: In the display equation we use Lipschitzness of $f$ twice, why not to mention it?
My simple geometry suggests that the bound for $\| \hat g_k - \hat \zeta\|^2$ contains an extra factor $2$. 

limitations: --
review_title: null

Meta-review: metareview: The main contribution of this work is to extend and improve previous results regarding optimization complexity of Lipschitz functions.

In particular, it addresses issues in previously proposed algorithms that did not make it implementable. The newly proposed algorithm does not use the strong oracle that was required in previous work, and only uses first-order information, as is common in large-scale optimization problems in ML. There is also improved analysis of the complexity of the algorithms.

The reviewers had many questions for the authors, and there was a fruitful and constructive discussion between all parties. Their remarks have been adressed, and all reviewers recommend to accept this work, and so do I.

The comments that I would personally have is that 1) For an implementable algorithm, an implementation would have been nice 2) Since the motivation is to train models in an ML setting, some discussion about the "quality" of these stationary points from the point of view of generalization abilities would also complete nicely this work. 
confidence: Certain
Decision: Accept