Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper surveys and summarizes the theoretical support for performing implicit differentiation in the broader, not-necessarily smooth settings. The derived formulas and theories, importantly, are compatible with AD. The authors have established the generalization of their conservative-Jacobian-based approach to multiple scenarios, including equilibrium networks, optimization layer, etc.
main_review: Overall, I believe this paper rigorously explored a gap that prior works on implicit deep learning have missed, which is the non-smooth structures. To that end, I think this paper is appropriate for the NeurIPS community, and offers a solid & sound theoretical support for the recent progress in implicit networks (which is obviously needed, and is why I recommend acceptance). However, I'm also simultaneously concerned about 1) the novelty of the conclusion; and 2) the practicality of theoretical results.

Pros:
- Rigorous math and well-stated assumptions, conditions and results.
- Tackles a missing gap by the prior works in this direction (i.e., IFT applied in non-smooth settings)
- The theory captures a relatively wide variety of scenarios, including equilibrium networks, hyperparameter optimization (bi-level optimization), and optimization layer.

Cons:
- The technique used for the non-smooth analysis is not new (conservative Jacobians), and there have been (as the authors acknowledged) plenty of prior explorations of non-smooth implicit differentiation in the literature (e.g., "An implicit function theorem for nonsmooth function" by Robinson; "Implicit functions and sensitivity of stationary points" by Jongen et al. (the authors didn't cite this?); the monotone DEQ paper also briefly discussed Clarke generalized Jacobian).
- The results derived completed the theoretical picture of various implicit ML methods but has limited practical implications (unless the function is extremely ill-posed). For instance, the result for monotone DEQ (proposition 3) is not different from theorem 2 of [Winston & Kolter 2020] (but better characterizes the condition and assumption for a more general applicability). As another example, the hyperparameter optimization discussion has been centered around the LASSO type problem.
- The experiment has a limited scope and is on low dimension.

I'm also particularly curious about the case where an equilibrium network does not have a unique fixed point. In particular, most likely we can guarantee uniqueness locally (e.g., by making the layer locally contractive, and then making sure we initialize the fixed point estimate well) but not globally in the entire R^n space. How will the theory change in this case (and broadly, when the layer is not monotone)?

---------
---------

### Post-rebuttal

I've read the authors' responses and would like to thank the authors for the clarification. I don't have any major issue with accepting this paper, but at the same time (as the authors acknowledge) there is still limited practicality to the analysis presented here. I urge the authors to include the references I pointed out in the review.
limitations_and_societal_impact: As this is a theory paper, the authors have discussed the limitations by clearly stating the assumptions.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Conservative Jacobians provide a formalism that justifies the application of standard AD techniques even when the computational graph contains nonsmooth Lipschitz elemental functions such as relu. An element of the conservative Jacobian can be computed by picking any element of the Clarke Jacobian for the elemental functions and applying the chain rule. In that sense the formalism of conservative Jacobians has a significant practical benefit compared to previously proposed approaches for nonsmooth AD, such as e.g. [1] and [2], because no directional information needs to be propagated (there is no qualification).

In this paper the authors present the natural application of the conservative Jacobian formalism to implicit differentiation and highlight the necessity of invertibility as analogous to the classical implicit function theorem.

The authors highlight some applications of implicit differentiation in the area of machine learning:
 - Monotone implicit layers
 - Embedded optimization problems such as optimization layers and hyperparam optimization for L1 regularized optimization problems

If the optimality condition for an embedded optimization problem can be formulated as a nonsmooth implicit function with the assumed Lipschitz composed structure then the authors' implicit function theorem applies.

In some cases it can be possible to prove that the invertibility condition is guaranteed.

The authors give a theorem showing that gradient descent with a sufficient step size decay converges to Clarke stationary points when conservative gradients are used. This theorem is not related to the implicit function theorem and also holds for non-implicit conservative differentiation.

The authors show that conservative gradient dynamics for nonsmooth functions can be cycling and even chaotic in the case the invertibility assumption is not satisfied and demonstrate the resulting discrete gradient dynamics in numerical experiments to highlight the relevance of the invertibility assumption of their implicit function theorem in practical examples.

[1] Branch-locking AD techniques for nonsmooth composite functions and nonsmooth implicit functions
[2] Provably Correct Automatic Subdifferentiationfor Qualified Programs
main_review: Strong points:

- The paper gives theoretic justification to methods that are already used in practice.
- The paper provides examples for use cases that show that the theory is somewhat relevant to practical applications (in machine learning)
- The authors formally extend on a theory that has been picked up by different authors for analyzing nonsmooth functions (in machine learning applications)
- The theory and derivations are clean and of high quality and seems relevant

Weak points:

- The paper itself does not provide a good motivation and intuition of how the conservative Jacobian works. As a reader that is not familiar with the conservative Jacobian formalism it is probably necessary to go to the cited literature to gain clarity.
- The paper does not cite other approaches for nonsmooth differentiation in the context of AD, explain how they apply in the context of implicit differentiation, and what the benefits of the conservative Jacobian formalism are over these other approaches (see e.g. [1], [2] cited in the summary).
- From the toy numerical examples provided to show that invertibility can be an issue it is not immediately clear whether these problems occur in any practical machine learning applications.

Originality: Although the application of the conservative Jacobian formalism to implicit differentiation follows naturally the associated analysis of the implications and applications to e.g. bilevel optimization is original work.

Quality: The presented theory is high quality. The numerical experiments are only toy examples.

Clarity: Clarity can be improved in the motivation and introduction of the formalism. The presentation of the implicit function theorem result itself, example use cases and convergence theory for gradient descent are clear.

Significance: The paper is probably not immediately significant to machine learning practitioners but the ideas in the paper advance the state of formal understanding of practices that work in machine learning in practice and is, therefore, significant.

I recommend to accept the paper because the authors present and analyze the consequences of an implicit function theorem that follows naturally from a theory for nonsmooth AD that seems highly relevant to what is used in the practical machine learning world.

Recommendations:
- Improve the initial explanation of the conservative differentiation formalism as it applies to AD as used in ML frameworks
- Contrast your results to other nonsmooth AD approach to highlight the pros / cons

An example of implicit differentiation via elements of the conservative derivative for an implicit function that does not satisfy the invertibility condition is the following:

Let

0 = x - (relu(y) - relu(-y)) = g(x, y(x))

where since relu(y) - relu(-y) = y we have y(x) = x and hence y'(x) = 1 everywhere.

But since at x = 0, y = 0 a valid element of the Clarke Jacobian of relu(y) is relu'(y) = 0 by AD and implicit function theorem at x = 0 we can have

y'(x) = -dg/dy^{-1} * dg/dx = -0^{-1} * 1

i.e. in such a case the invertibility condition is not satisfied.

With a "limiting Jacobian" approach as e.g. suggested by [2] we can associate the direction dir_y = 1 and which would lock the derivatives to

relu'(y; dir_y) = 1
relu'(-y; dir_y) = 0

or alternatively for dir_y = -1 we have

relu'(y; dir_y) = 0
relu'(-y; dir_y) = -1

and so in both cases we have

dg/dy(.; dir_y) = (relu'(y; dir_y) - relu(-y; dir_y)) = 1

which avoids the non-invertibility.

- I'm not sure whether the convergence result for gradient descent should be in the paper as it is already dense and the result is not specific to the implicit function theorem.

Nits:
- Right of Figure 1 looks very similar to Figure 3 (b), is it necessary to have both?
- For the first example you have
x = tanh(z) + relu(-z) + z - relu(z)
= tanh(z) + z + max(0, -z) - max(0, z)
= tanh(z) + z - z
= tanh(z)
which seems to imply that z = tanh^{-1}(x) instead of z = tanh(x) like you write.
The legend of figure one (invtanh) suggests that's what you had in mind anyways.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces a nonsmooth implicit differentiation theorem via conservative Jacobians, which is compatible with algorithmic differentiation. The authors then apply this theorem to optimize over implicit differentiation problems with gradient descent and proves a convergence result of the algorithm.
main_review: **Quality**: I did not check the theorem statements/proofs, though the logical progression of the theorems makes sense to me.

**Clarity**: The paper is very clear and well-motivated. I especially like the way that the authors use explicit (counter)examples to motivate their discussions throughout the text. 

**Originality and Significance**: Even though I have not worked on nonsmooth implicit problems in the past, I do expect that such problems can have very different behavior from smooth ones, and the framework proposed in the paper is a good step going forward in this direction. From a practical perspective, I would say that the experiments performed in the paper are rather of small scale, and I would be curious if the authors can implement any one of the three deep learning examples presented in the paper to see how the time complexity of such methods grow with large-scale problems. Since my field of research is only marginally related to this, I do not have much to comment on the originality/impact of the paper.
limitations_and_societal_impact: I do not see any limitations or potential negative societal impact of the work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work provides theoretical foundations for nonsmooth implicit differentiation based on conservative Jacobians. Specifically, it provides conditions under which implicit differentiation is compatible with backpropagation and first-order optimization algorithms. The authors then study the applications of the implicit differentiation algorithm, including deep equilibrium problems, conic optimization layers, and hyperparameter optimization problems for Lasso. The specific conditions and the forms of the Jacobians are also provided. After that, the authors obtain the convergence guarantees for first-order optimization algorithms. Finally, two examples -- a cyclic gradient dynamic via optimization layer and a Lorenz-like attractor via implicit differentiation – are used to demonstrated that the optimization may fail when the conditions are not satisfied.
main_review: The paper is well-written and is written in a very rigorous way. The related concepts are well-defined and the failure cases are clearly demonstrated. 

The precise conditions for applicability of backpropagation and first-order optimization can be useful for many machine learning applications, which is a solid contribution to the community.

As a small suggestion for improvement: If I was writing this paper, I would put the current section 5, i.e., numerical experiments, in the introduction or section 2, as part of the motivation for this work. The current section 2, i.e., the main results, is rigorous but abstract. Describing it with some examples can make it more concrete for the readers. Besides, the current numerical experiments are more like two examples than real ML experiments.

limitations_and_societal_impact: This work is purely theoretical and does not involve any applications that may lead to negative social impact.
review_title: null

Meta-review: This paper provided the justification of the implicit differentiation in the non-smooth settings with conservative Jacobians. The proposed method is also compatible with the standard AD. The authors also established the connection of the conservative Jacobians with the Clarke Jacobian. The authors finally apply the results to multiple machine learning problems, e.g., deep equilibrium networks, optimization layers, and bi-level optimization. The paper is well-written and easy-to-follow. I believe this paper will be of interest to the wide range of NeurIPS community. 

There are still several minor issues need to be address, especially the discussion to the related work in literature (Reviewer gMrk, 2ovw) and more comprehensive empirical experiments (Reviewer eaLv). 
Decision: Accept (Poster)