Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the computational cost of forward and backward automatic differentiation (AD° for *nonsmooth* programs, based on the notion of conservative gradient introduced by Bolte and Pauwels (2020a, b).
The relative cost of backward mode AD/backpropagation (compared to the original program/function) is proved to be independent of the dimension for path-differentiable functions (that encompass semialgebraic and definable locally Lipschitz functions). Theorem 2 is a nice result that extends results that were known in the smooth case under the name of "cheap gradient principle" (Baur and Strassen, 1983).
Lastly, the authors show that such results on conservative gradients do not hold for other nonsmooth alternatives: the cost ratio for computing $p$ directional derivatives depends on the dimension $p$ unless the matrix exponent is equal to 2 (Theorem 3), and finding two distinct Clarke subgradients in the Clarke subdifferential is NP hard (Theorem 4, by reduction to 3-SAT).
strength_and_weaknesses: Strengths:
- Nonsmooth operations/layers are ubiquitous in model neural networks (ReLU activation, sorting operations, max pooling, etc), and backpropagation is the default algorithm to train these networks. Having a rigorous theory of what backpropagation actually computes, and at which cost, is of paramount importance.
- The concept of conservative gradients fills this need, and thus studying it in more detail is important for our understanding of theory and practice. 
- The paper is well-written, with a wealth of examples, a motivated impact.

Weaknesses:
- no important ones (see minor clarifications below)

### Minor remarks and question
- In Theorem 2, ii, an upper bound on the ratio is derived where $\omega_f$ depends on the dimension $p$. For completeness, one may add that this upper bound is reached, for example in the case where $|pr(i)|$, and the costs of $g_i$ and $gd_i$ are independent of $i$. Otherwise it could just be a bad upper bound.
- In the first paragraph of Section 5.1: is it known than the matrix multiplication exponent $\omega$ is $> 2$? If $\omega$ were to be equal to $2$, then the overhead ratio of order $p^{\omega - 2 + o(1)}$ could in fact be dimensionless. This is later discussed in the "Consequences" part (and at the end of Section A.2.2) but it could be mentioned earlier: in all rigor, there is currently no result that says $\omega > 2$, and so the derived ratio could be dimensionless (though all practical evidences are against this so far), which contradicts "in contrast with the smooth case with essentially dimensionless overhead.".
- The ReLU requires only 2 bits of encoding > is it not a single bit (a binary value encoding the sign of the input)?


### Very minor cosmetic:
- the authors may consider configuring hyperref through \hypersetup in order to avoid the flashy green and red boxes (see 2nd answer here: https://tex.stackexchange.com/questions/823/remove-ugly-borders-around-clickable-cross-references-and-hyperlinks)
- when the citation is part of the sentence, it should not use parentheses: "see Griewank et al (1989)". When it is not part of the citation, it should use parentheses: "It is at the core of modern learning architectures (Rumelhart et al., 1986).". Use \citet and \citep respectively.
- , little is known about the nonsmooth case. > "but" little is known about the nonsmooth case?
- Standard computational practice of AD consists of: "consists of" means "is composed of". You mean "consists in"
- in an ML > in a ML
- In particular,they > missing space after comma
- To conculde
- Let $F, G$ be locally Lipschitz continuous mapping > mappings
- Lipchitz
- Path differentiable functions are ubiquituous > ubiquitous
- consist of combinations outputs of > consists of combinations *of* outputs of
- is an optimization algorithms > algorithm
- The function F may describe, for instance, a ReLU feedforward neural network empirical loss, parameterized by $p$ real weights, with $q$ inputs: isn't $p$ the number of inputs and $q$ the number of parameters in the previous sentence?
- then evaluate $p$ scalar product > products
- for example $F$ is feedforward neural network > $F$ is a feedforward
- Case 13: This can be done by sorting the n numbers and output the value value > and outputting + "value" duplicated
- Therefore, the each affine part has zero derivative > remove "the"
- fintiely
clarity,_quality,_novelty_and_reproducibility: The work is clear, novel and original.
summary_of_the_review: Well-written and theoretical sound paper on important recent development in automatic differentiation for non smooth functions, in particular neural networks.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper:   In this paper, the authors consider the problem of computing subgradients of non-smooth non-convex functions that are given as programs that are based on the small set of elementary functions. Their main contributions are the following:
  1. They analyze the computational complexity of the algorithm suggested by Bolte and Pauwels 2020a for forward and backward evaluations of a relaxation of subgradients called conservative gradients. An important corollary of their analysis is that when we apply backward evaluation, the cost of evaluating the gradient is only a dimension-independent constant time larger than the cost of evaluating the function value. The authors also show that this is not the case for the forward evaluation of the gradient.
  2. They show that given a program P that computes a function $f$ using only the operations $\{ +, -, \mathrm{ReLu} \}$, and a point $x$, deciding whether $f$ is differentiable at $x$ is NP-hard. In contrast deciding whether $f$ is path-differentiable at $x$, which means that there is a unique conservative gradient, is possible in polynomial time.
strength_and_weaknesses: Strengths
======================
  - The problem of theoretically understanding the complexity of computing subgradients of non-smooth functions is very important and interesting.

Weaknesses - Comments
========================

  1. The main problem with the paper is that most of the material is a restatement of results provided by Bolte and Pauwels 2020a. In particular, the algorithms for forward and backward computation of conservative gradients are provided in exactly the same form in Bolte and Pauwels 2020a, at least in their arxiv version. Given that, the novelty of this part of the paper is the proof of Theorem 2, which can be found in page 15 and mostly follows a very simple induction argument similar to the existing proofs for the smoothed case.

  2. I am not sure I understand the motivation of Theorem 3. Why would we need to compute the directional derivatives since we can compute the whole subgradient?

  3. Related to Theorem 4: The problem of given a function $f$, a vector $v$, and a point $x$ verify whether $v$ is a subgradient of $f$ at $x$ is solvable in polynomial time or not?

  4. If the answer to question 3 is positive then I am puzzled with Theorem 4 (b). The authors state that deciding the differentiability of a non-smooth function at a point $x$ is NP-hard. But I believe that the correct statement is that deciding the non-differentiability of $f$ is NP-hard. In fact, if the answer to 3 is positive, deciding the non-differentiability should be NP-complete, since the existence of two subgradients is a witness of the non-differentiability of $f$ at $x$. This means that deciding the differentiability is coNP-complete and we do not expect it to either be in NP or being NP-hard.

  5. There is a small issue with Theorem 4 that usually is swept under the rug, but when proving computational hardness results it needs attention. What is the representation of the numbers that you assume in Theorem 4?  
  **(a)** If you use binary representation, then the hardness result of Theorem 4 implies that there is no algorithm with complexity polynomial in $p$ (the dimension) and $\log(1/\epsilon)$, where $\epsilon$ is the accuracy that we choose to represent the numbers.  
  **(b)** If you can show the hardness result even when you use unary representation, then the Theorem 4 implies that there is no algorithm with complexity polynomial in $p$ and $1/\epsilon$.  
  If the case is (a) then this would be a less interesting result because the ML community focuses on algorithms with running time $\mathrm{poly}(1/\epsilon)$. In any case, a discussion about this is missing and is important.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written, the proof are clean and the previous works are well-cited.

summary_of_the_review:   The contribution of this paper is interesting but I am not sure if it is enough to guarantee acceptance at ICLR. For this reason I am slightly leaning towards rejection.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper utilizes the concept of a conservative gradient to bound the complexity of non-smooth derivatives, and shows that the computational complexity for backprop with conservative gradients has a computational overhead ratio independent of dimension (Theorem 2), and hence generalizes Baur-Strassen to non-smooth programs. 

The authors show that in general for other differentiation oracles (like directional derivatives, etc) for the forward mode the overhead depends upon the dimension p (for example is O(p^\omega) for directional derivatives), and therefore can be limited.
strength_and_weaknesses: The paper points out the different complexity for computing derivatives for non-smooth functions, and shows a variety of results regarding the complexity ratio of different derivative methods. 

- the paper provides and rigorously prove bounds for the computational hardness non-smooth AD as well as for different generalized gradient methods.
- The authors show that calculating distinct elements in a clarke differential of a given point is NP-hard.
- The proofs (as much as i could follow them) seem correct.

However, i think the proof sketches could be made more clearer in the main text, since it was a bit hard to follow.
clarity,_quality,_novelty_and_reproducibility: The extension to the nonsmooth functions using conservative gradients seems novel. 
summary_of_the_review: The authors extend the cheap gradient principle and show that it is independent of the dimension. They further show that bound the forward auto-diff complexity will have an overhead due to matrix multiplication.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper extends the emerging theory of automatic differentiation in the presence of nonsmooth functions.  Given the plethora of nonsmooth operations (Relu, top k, max) in modern ML models, this is a valuable endeavour.

One reviewer expresses concern about the magnitude of the contribution over previous work by Bolte and Pauwels, which the rebuttal does not answer directly, speaking instead to extensions over Griewank and Walther 2008.  On inspection, the arguments show sufficient novelty in the new work.


justification_for_why_not_higher_score: Although this is an interesting area, and as argued above, nonsmooth functions abound in modern ML, it remains the case that the implications are largely theoretical.
justification_for_why_not_lower_score: A spotlight feels appropriate because although the practical implications are probably sufficiently small that most ML practitioners do not "need" to know this work, it is also the case that many ought to be interested in its existence.
Decision: Accept: notable-top-25%