Nonsmooth Implicit Differentiation for Machine-Learning and Optimization
Authors: Jerome Bolte
Tam Le
Edouard Pauwels
Antonio Silveti-Falls
Venue: NeurIPS 2021 Poster (2021)
Keywords: Implicit differentiation
algorithmic differentiation
nonsmooth optimization
deep learning
conservative fields.

Abstract: In view of training increasingly complex learning architectures, we establish a nonsmooth implicit function theorem with an operational calculus. Our result applies to most practical problems (i.e., definable problems) provided that a nonsmooth form of the classical invertibility condition is fulfilled. This approach allows for formal subdifferentiation: for instance, replacing derivatives by Clarke Jacobians in the usual differentiation formulas is fully justified for a wide class of nonsmooth problems. Moreover this calculus is entirely compatible with algorithmic differentiation (e.g., backpropagation). We provide several applications such as training deep equilibrium networks, training neural nets with conic optimization layers, or hyperparameter-tuning for nonsmooth Lasso-type models. To show the sharpness of our assumptions, we present numerical experiments showcasing the extremely pathological gradient dynamics one can encounter when applying implicit algorithmic differentiation without any hypothesis.

Nonsmooth Implicit Differentiation for Machine Learning and Optimization
Jéröme Bolte Toulouse School of Economics Univ. Toulouse Toulouse, France
Tam Le Toulouse School of Economies Univ. Toulouse Toulouse, France
Edouard Pauwels IRIT, CNRS Univ. Toulouse
Antonio Silveti-Falls
Toulouse School of Economics Univ. Toulouse Toulouse, France
Toulouse, France
Abstract
In view of training increasingly complex learning architectures, we establish a non- smooth implicit function thcorem with an operational calculus. Our result applies to most practical problems (i.e., definable problems) provided that a nonsmooth form of the classical invertibility condition is fulfilled. This approach allows for formal subdifferentiation: for instance, replacing derivatives by Clarke Jacobians in the usual differentiation formulas fully justified for wide class of nons- mooth problems. Moreover this calculus is entirely compatible with algorithmic differentiation (e.g., backpropagation). We provide several applications such training deep equilibrium networks, training neural nets with conic optimization layers, or hyperparameter-tunigg for nonsmooth Lasso-type models. To show the sharpness of our assumptions, we present numerical experiments showcasing the extremely pathological gradient dynamics one can encounter when applying implicit algorithmic differentiation without any hypothesis.
Introduction
Differentiable programming. The recent introduction of deep equilibrium networks [7], the in- creasing importance of bilevel programming (e.g., hyperparameter optimization) [48] and the ubiquity of differentiable programming (e.g.. TensorFlow [1] Py PoTcch [47), JAX (16) in modern optimization call for the development of versatile theory of nonsmooth differentiation. Our focus is on nonsmooth practices lying the crossroads of mathematics
implicit differentiation. There are currently and computer science: on the one hand the use of the standard smooth implicit function theorem "almost everywhere" [31 30 and the other hand the development of algorithmic differentiation tools 2 3 59 The empirical use of the latter in the nonsmooth world has shown surprisingly efficient results [59], but the current theories cannot explain this success. We bridge this gap by providing nonsmooth implicit differentiation results and illustrating their impact on the training of neural networks and hyperparameter optimization.
Backpropagation: a formal differentiation approach. Let us consider 2 implicitly defined through F(2(x)) = h(x) where F and h have full domain and adequate dimensions. How does autograd apply to evaluating the "derivative" of the implicitly defined function 2? Regardless of differentiability or nonsmoothness, and provided that inversion is possible, commonly uses (or dynamically approximates) this derivative by
(tac)) backprop,,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

where backprop outputs the result of formal backpropagation, see e.g., [50]. This identity is used to provide efficient training despite the fact that the rules of classical nonsmooth calculus are transgressed 7 [59] Note that spurious outputs may be created by this approach, but on a negligible
set. Consider for example the simple implicit problem x f(((=)) where f(() == tanh(=) +
relu(-2) - rel, whose solution is =(x)) tanh z. Yet applying the implicit differentiation
framework of 7 using JAX library, as presented in [59), provides inconsistency of the derivative at the origin, see Figure [ As mentioned above, despite these unpredictable outputs, propagating derivatives leads to an undeniable efficiency. But can we parallel these propagation ideas with a simple mathematical counterpart? Is there rigorous theory backing up formal (sub jdifferentiation or formal propagation? The answer is positive and was initiated in [4 13
through conservative
Jacobians (see also 41 24
mathematical model for propagating derivatives. Conservative calculus models nonsmooth algorithmic differentiation faithfully and allows for sharp study of training methods in Deep
Learning 14 15]. It involves a new class of derivatives, generalizing Clarke Jacobians [20]. A distinctive feature of conservative calculus is that it is preserved by Jacobian multiplication. Consider for example a feed forward network combining analytic or relu activations and max pooling. A conservative Jacobian for this network can be obtained by using Clarke Jacobians formally as classical Jacobians, regardless of qualification conditions, compared to other approaches, e.g. (37 for which stricter qualification conditions are imposed to ensure that element of the Clarke Jacobian itself can be computed using algorithmic differentiation. For instance, Figure [ depicts a selection in a conservative Jacobian. This approach is general enough handle spurious points such as in Figure [ while keeping the essence of the properties one expects from derivative. It was proved in [14] that backprop, applied to any reasonable program of function, is conservative Jacobian for this function; in contrast, backprop cannot be modelled by some subdifferential operator. For instance for the fixed point problem above, given conservative Jacobians JF and Jj, (e.g.. Clarke Jacobians) for F and h one obtains a new conservative Jacobian J. implicitly defined through
JF Jz(z(z))J5(z) = (x)
This property exactly parallels the idea of "propagating derivatives" in practice. It gives a strong meaning to the formal use of Jacobians proposed in [7]. and many empirical approaches 332 2 31 30
Main contributions:
We establish nonsmooth conservative implicit function theorem that comes with an implicit calculus which is the central focus of this paper. Our calculus amounts somehow to formal subdiffer- entiation with Clarke Jacobians. This approach cannot rely on classical tools like the inverse of Clarke Jacobian or a composition of Clarke Jacobians, which are not in general Clarke Jacobians. Indeed, a surprising example (Example [} shows that an "inverse function theorem with Clarke calculus" is not possible.
We study wide range of applications of our implicit differentiation theorem, covering deep equilibrium problems [7], conic optimization layers (2), and hyperparameter optimization for the Lasso [9]. Each case is detailed and its specificities are discussed.
As a consequence, we obtain convergence guarantees for maniedatched stochastic algorithms with vanishing step size for training wide classes of Neural Nets, or for Lasso hyperparameter selection. The assumptions needed for our results are mild and fulfilled by most losses occurring in ML. in the spirit of [15] 40]: elementary log-exp functions [15), semialgebraic functions [12], all being
subclasses of definable functions 23 55). The use of such structural classes has become standard in
nonsmooth optimization and is more and more common in ML (see, e.g., [18 15 40 35)).
As in the smooth implicit function theorem, the invertibility condition not avoidable in general. We provide various examples for which the assumption is not satisfied; this results in severe failures for the corresponding gradient methods. In Figure one sees how lack of invertibility on an otherwise ordinary problem may provide totally unpredictable behavior for smooth quadratic optimization.
Related work on implicit differentiation: The classical implicit function theorem has two parts: an existence and regularity part, and a calculus part, which is called implicit differentiation. Nons-
'The notation backprop, instead of backprop(2) is indicative of the fact that backprop is an operator that does not act functions themselves but rather on the program used to represent them, [15]

---

Invtanh Invtanh
1
0-
-1
100
200
-0.5
-200
0
100
200
200
Figure 1: Left: Inconsistencies due to combination of implicit differentiation and algorithmic differentiation. Right: gradient trajectory of an implicitly defined quadratic function.
mooth generalizations have mostly focused on the existence part. We focus on Lipschitz equations, for which existence of implicit functional relation is due to [4], based Clarke's inverse mapping theorem [9], all these elements being summarized in [20]. Various extensions of this result have been proposed. let mention result in approximation context in [3).. semismooth extension in
[52] and a tame extension differentiation in practice. There have been extensions of the nonsmooth implicit function theorem with a calculus limited to directional derivatives and lexicographic derivatives (a sort of directional derivative introduced in (45) in 49 Corollary 3.4] and [38] Theorem 2.3], respectively; the former requiring stronger assumptions than just the invertiblity condition. The limitation of the calculus of these extensions directional derivatives is furthermore incompatible with the most common numerical libraries used for algorithmic differentiation in practice, as opposed to the framework we present.
[29]: however, all these extensions lack a calculus amenable to implicit
Definitions and Notations. A function F R + R is locally Lipschitz if, for each x E R", there exists neighborhood U of x such that F is Lipschitz U. Given matrices A Raxm and B E RR [A B] [=x(ppp) denotes their concatenation; Id, denotes the x n identity matrix. For q E RR, diag (q) E Rax" denotes the diagonal matrix whose diagonal entries are given by the 9:: sign (q) E 1, denotes the componentwise sign function. The convex hull of U is denoted conv U. The projection onto a closed convex set E IR" is given, for each x E R", by
Pe (x) = a ||u x|| u C). Given a convex proper lower semicontinuous function E", prox, (x) argmin (u)+ ||u x| u E R"). Set-valued maps are denoted by =, for example the subgradient 0f: R" = Rn. Additional details and notations are provided in Appendix
f: R [U(+ we define its proximal operator through
2 Implicit Differentiation with Conservative Jacobians
Definitions and conservativity. Conservative Jacobians are generalized forms of Jacobians well suited for automatic differentiation, introduced (14). Given locally Lipschitz continuous function F Rn + 12m,, we say that JF 12 n = I is conservative mapping or conservative Jacobian for F' JF has closed graph, is locally bounded, and is nonempty with
d dt F((()) J=(7(())(() a.e.
whenever y an absolutely continuous curve in R When 1, the corresponding vectors are called conservative gradient fields. Note that when JF is conservative, so is its pointwise convexified extension conv JF.
locally Lipschitz function is called path differentiable it has conservative Jacobian. Recall that the Clarke Jacobian is defined as
Jac F(x)= = conv
lim 10-00000
Jac F(xx): E diff Th
1=++00
where difl is the full measure set of points where F is differentiable and Jac F is the standard Jacobian F. Path differentiability is equivalent to having a chain rule as in TT) for the Clarke subdifferential, see 25)

---

Examples of path differentiable functions and conservative Jacobians. (a) Convex functions and concave functions are path differentiable, see (14) This implies that their subdifferential in the
sense of convex analysis is conservative field.
As a result, the Clarke Jacobian of Lipschitz definable mapping is conservative Jacobian. Definable functions (see [5] I8 [14] for an optimization context and [23] for a foundational work) encompass semialge- braic functions [1], elementary log-exp selection [14. PAP 40) (restricted to analytic functions with full domain), and many others, see (55) and references therein. This includes networks with common nonlinearities: for example analytic with full domain (e.g., square, exponential, logistic loss, hyperbolic tangent, sigmoid), relu, max pooling, sort, (see Appendix A.2 for more detail). (c) The backpropagation can be seen an oracle (in the optimization sense) for conservative Jaco- bian. Let Pr be a numerical program for a function F, aggregating elementary functions, for instance, relu, max pooling, affine mappings. polynomials (in general, any definable function). Then the back- propagation algorithm applied to Pr. which we denote (abusively) by backprop Pr == backpropp outputs element of conservative Jacobian [4 Theorem 8] which depends PF and can be constructed by closure procedure [15] definition SJ. As described in [15]. due to spurious behaviors, backprop not in general an element of the Clarke Jacobian of F.
(b) The vast class of definable functions are path differentiable 25
The structure of conservative Jacobians. As established in 41 in semialgebraic context, the discrepancy between conservative gradients and Clarke subdifferentials is somehow negligible. Let us provide version of that result matching our concerns. We call conservative mappings of the null function residual or residual conservative. Such mapping R has the property that R(x + te)e = 0 for almost all t in R and all x. in R" x R". The following theorem and proposition (partially) extend results from [4] and [1], their proof is given in Appendix B
Theorem (The Clarke Jacobian is a minimal conservative Jacobian) Given a nonempty open R subset U Th and F : 2 Tke Th. locally Lipschitz, let Jr be convex-valued conservative Jacobian for F. Then for almost all x E U, Jr(z) = (Jac F} and, for all x E U, Jac e F(#) C (x)
Proposition 1 (Decomposition of conservative fields) Let Jr be a conservative Jacobian for F. then there is residual R such that
JF Jac + R.
Note that the above may not hold with equality. Consider F(x) |a|| and Jr(0) = u] (2, Jr (x) = sign (x) otherwise. One cannot write Jr = Jac F + R with a residual operator R.
Formal subdifferentiation in a nonsmooth setting. Propagating derivatives within a nonsmooth function finds its justification in the following:
Proposition 2 (Stability by composition, 14) Let F R Rm and G R + R² be two locally path differentiable functions having respective conservative Jacobians JF and Jg. Then F G is path differentiable and the point-to-set matrix-valued x = (((())) is conservative.
A conservative Implicit Function Theorem. There is already long tradition of nonsmooth
implicit function theorems, e.g., 120 6 (6). What makes the following theorem useful is that comes with -ralffccation-free calculus. The proofs are given in Appendix B
Theorem 2 (Implicit differentiation) Let F R" x Rm + R. be path differentiable on U x V C Ra R. an open set and U > V locally Lipsehitz,function such that, for each a E U.
F(x, G(x)) 0.
Furthermore, assume that for each x E U, for each [A B] E Jr(æ, G(x)), the matrix B is invertible where Je is a conservative Jacobian for F. Then, G : U + V path differentiable with conservative Jacobian given, for each x E U, by
Jo: x = = A: [A E JF(z,G(x))} G(x)))

---

Corollary (Path differentiable implicit function theorem) Let F R" X R + R be path differentiable with conservative Jacobian Jp. Let (t. () R R be such that F(ē. 9) = Assume that Jr D) is convex and that, for each [A B] Jr(r. 1). the matrix B is invertible. Then, there exists an open neighhorhood x V C Te The of (T,, () and a path differentiable function G: :: - V such that the conclusion of Theorem holds.
Corollary (Path differentiable inverse function theorem) Let U and V be open neighborhoods of in R and T U - V path differentiable with ((0) O. Assume that & has conservative Jaco- bian Jo such that Jø (0) contains only invertible matrices. Then, locally, o has a path differentiable inverse Wa with conservative Jacobian given by
Jo(y) - (A- AE Jo (V(())))
Remark 1 (a) (On the necessity of conservativity) Example I in Appendix B shows that one cannot hope for the formulas in Corollaries & to provide Clarke Jacobians in general, even if the input(s) are Clarke Jacobians themselves. This example is bivariate and piece-wise linear, illustrating that even in this simple situation, implicit differentiation fails and produces artifacts when formaly applied to Clarke Jacobians.
(b) (Lipschitz definable implicit and inverse function theorems) See Theorem and in the appendix
3 Nonsmooth implicit differentiation in Machine Learning
Detailed proof arguments for all considered models are given in Appendix C
Monotone deep equilibrium networks. Deep Equilibrium Networks (DEQs) 7 are specific neural network architectures including layers whose input-output relation is implicitly defined through a fixed point equation of the form
2 == f(z
(3)
where & E RP is given input and 2 E Ih the corresponding output. We may consider that the variable represents both the input layer and layer parameters. Assuming that, for each I E RP, there is unique = E I satisfying the relation (3), this defines an input-output relation 2: 12 + RT. Furthermore, if f is path differentiable with convex-valued conservative Jacobian Jy: RD x R = R (m++p) whose projection on the first m columns all invertible, then the function z itself admits a conservative Jacobian which can be computed from Theorem P
We now focus monotone operator implicit layers (58 for which assumptions are easily stated. Our method applies to other similar architectures, e-g., DEQs (7] or implicit graph neural networks (32]. Let _ + _ be the proximal operator of convex function and assume is path differentiable with conservative Jacobian J, RT = IR xm assumed to be convex-valued. This encompasses the majority of activation functions used in practice (II. Let W E m be matrix such that W + WT 2 29I with > 0. Under these assumptions the implicit equation
2 = oW + b)
(4)
has unique output 2(W, b) [58 Theorem 2]. The transformation (W, + 2(W,)) b) is a monotone implicil layer.
The set- valuvd mapping obtained from Theorem provides a conservative Jacobian for (W, 2) + z(W, z). A similar expression was described in [58 Theorem 2], without using conservativity and using the Clarke Jacobian formally classical Jacobian. The proposition below provides full justification of this heuristic and ensures convergence of algorithmic differentiation based training.
Proposition 3 (Path differentiation through monotone layers) Assume that Ja is convex-valued and that, for all Jo (WWW=(W =(W, b) + b), the matrix (Id,, JW) is invertible. Consider a loss-like function E: I - I with conservative gradient Dy: I8m = Rm" then g (W, + ((((W, b)) is path differentiable and has a conservative gradient D, defined through
Dg: (W,b) = [J"
-W)-Tuz" uz J (Idm - JW)-To) J E J, (W 2 b), VE Dr(z))
Remark 2 Convexity and invertibility assumptions satisfied when J, is the Clarke Jacobian [8]
5

---

Optimization layers: the conic program case. Optimization layers in deep learning may take many forms; we consider here those based on conic programming [17
We follow [3]. simplifying the analysis by ignoring infeasability certificates, which correspond to the absence of primal-dual solution [7], line with the implementation described in 2 Appendix BJ. Consider a
conic problem (P) and its dual (D):
(P) inf
c x
(D) inf subject
y A" y +c= (5) y VEK'
subject to
Ax = = 8 EC
with primal variable x R" dual variable y Rm and primal slack variable R The set K. C Ihm is nonempty closed convex cone and K.* C Ikm is its dual cone. The problem parameters are the matrix A R=*x and the vectors assumption that there is a unique primal-dual solution (z, s), we study the path differentiability of the solution mapping as function of its parameters:
I= and e E I"; the cone K. is fixed. Under the
(A, sol (A, b, (x,, y, 8).
For this, 1et us interpret the solution mapping as a composition mapping involving equation-like implicit formulations. Set N m, given b,b, RRmx x 1 x RR" define
A" 0
Q(A.b,c) -A
NNN
V(b.c)
b MERN.
T Th denote by IT the projection onto R K and define the residual map N RRN, T mxx x R R
Consider vector 2 (u, v)
+ R
W(z, A, b,c) (A -dd))) + v(b,c)+
The mapping N is synthetic form optimality measure for (P) and (D), capturing KKT conditions. To simplify the presentation, ignore the extreme cases of infeasibility and unboundedness which correspond to an absence of solution in 17].
Define the function á R- + RR x RT x RT through 6(u, v) (u, Pk- (v), Px- - uv. As
shown Appendix C.2 d(u, v) provides primal-dual KKT solution of problems (P) and (D) if and
only if (22 A, b, c) O. When we assume that, for fixed b, and c, there is unique E R such
that N(, A, = O, we have an implicitly defined a function 2 = v(A, b, c). such that
vol b, c) [Ø o vl (A..,c).
(6)
The following result extends the discussion in 17 3) limited to situations where IT is differentiable at the proposed solution 2, to a fully nonsmooth setting; its proof is postponed to Appendix C.2
Proposition 4 (Path differentiation through cone programming layers) Assume that Px-,, N path differentiable, denote respectively by JP Jx corresponding convex-valued conservative Jacobians. Assume that, for all A, b, E Rmxx x Rm x 12",, z v(A, b, c) E IR" x Rm the unique solution to (2, A, b, c) 0 and that all matrices formed from the N first columns of Jx A, b,b, are invertible. Then, 6, v, and sol are path functton
functions with conservative Jacobians:
b, (-U-'V (U V
A,b, A,bc))
Idn Jo(2) = 0
(v) (Jpe- (v) 1dm))
(p)
JA = b))
In practice, the path differentiability of conic projections is pervasive since they are generally semialgebraic (orthant, second-order cone, PSD cone). See 33
43 for the computations of corresponding Clarke Jacobians (which are conservative). Note that a conservative Jacobian for A' may be obtained from Jpc- using Proposition 2
43
39

---

Hyperparameter selection for Lasso type problems. Implicit differentiation can be used to tune hyperparameters via first-order methods optimizing some measure of task performance, see [TO] and references therein. In nonsmooth context, we recall the formulation in [9] of the general hyperparameter optimization problem as bi-level optimization problem:
min C(3(A) such that (()) E argmin (B, AeR
BERP
where C: IR R is continuously differentiable (e.g.. test loss) and sb R' X + R is possibly nonsmooth training loss, convex in 3, with hyperparameter E Rmm. We seek a subgradient type method for this problem with convergence guaranties; nonsmooth implicit differentiation results can be used for this purpose. We demonstrate this approach on the Lasso problem [53
(A) argmin {1 lly x3112 e² || B (2
R
where y E _ is the vector of observations, X ix....., Xpl RRXP is the design matrix with columns X, E j E {1....p} p), and À E R is the hyperparameter. Define F : R x R' - IR" to be
F (A, = 3 prox 111,, (B X" (XB - v))
and recall that, for each i E (I....,7 p}. [prox,>1HI, |H|,, (B)], = sign (3) max -e,, .}. The function F(A, () is thus nonsmooth but locally Lipschitz on x RR. An optimal ((A) for 7 must satisfy 0 [2 Prop. 3.1]. For given solution (()). we introduce the equicorrelation set by E = E (1. (L....p p} X (v- x x()( } which contains the support set supp 3 := {i
{L. 3 #3. In fact, & does not depend on the choice of the solution 3, see [54 Lemma 1]. The proof of the following result given Appendix C.3
Proposition 5 (Conservative Jacobian for the solution mapping) For all X R. assume X Xe is invertible where Xg is the submatrix of X formed by taking the columns indexed by E. Then B(A) is single-valued. path differentiable with conservatiee Jacobian, J3 (A), given for all X as
{[-c> (Id,- diag (q) (Idp xxxx)) diag (q) sign (B (8-x" x" (x--v)) w))] : :
where M(A) R is the set of vectors q such that qi if supp 3. q: if & & and %s E [0. if E supp.3. 3.
Taking, in Proposition 5 = 1 for all E E corresponds to the directional derivative given by LARS algorithm 28 see also 42 Alternatively, taking q: 0 for i supp 3 gives the weak derivative
described by 99. Both are particular selections in Jg. which is the underlying conservative field.
Optimizing implicit problems with gradient descent
We establish the convergence of gradient descent algorithms for compositional learning problems involving implicitly defined functions. The result follows from the previous section and the general convergence results of [15].
The minimization problem. mization problems of the type
The applications considered in the previous section all yield mini-
1 N
min (ww) WERY
((w) with = = o 99 .... 9:,1
(8)
where, for each E (1,..., NJ. 4 TRP - composition functions having appropriate input and output dimensions. The indices correspond in practice to learning samples while the loss f embodies an empirical expectation, as for instance in deep learning. We will enforce the following structural condition.
7

---

Assumption For i E NJ and j E (1....,L), the function Ii,j is locally Lipschitz with conservative Jacobian Ji, and one of the following holds
Jii and Ji,j are semialgebraic (or, more generally, definable).
9i. is defined as G in Theorem 2
with F and Jø semialgebraic (or, more generally, definable).
Actually, Assumption [ the second point implies the first point; we list both for clarity. More A..2 details on semialgebraiche and definability are given in Appendix A.2 Let us stress that virtually all elements entering the definition of neural networks are semialgebraic or, more generally, definable, see for example [15] for constructive model. In particular, beyond classical networks with usual nonlinearities (e.g., relu, sigmoid, max pooling... ...), this setting encompasses (through Corollary D
(a) Deep equilibrium networks: each Ji,j may correspond to usual explicit layers or an implicit layer involving a fixed point mapping and learning sample i in or
(b) Training with optimization layers: similarly, the inner maps Is.j may also be solution mapping to convex conic programs and related the sol function (6) of conic problems.
(c) One may assume that N 1, L and retrieve the hyperparameter tuning for Lasso in its implicit formulation.
SGD with backpropagation. Algorithmic differentiation (AD) is automated application of the chain rule of differential calculus. When applied to l, it amounts to computing one element of the product J; := 17 Jı.j by choosing one element in each Ji,j with appropriate inputs given by intermediate results kept in memory during forward computation of the composition.
In this context AD stochastic gradient descent requires an initial Wy R2 and sequence of i.i.d. random indices uniform in {1..... .....,,], N). (TE)ReN. It gives:
Wi++1 = wkk - 80
0g Jrp (wx).
(given by backprop),
(10)
where (aR))eN is a sequence of positive step sizes and s E (8mins 9max) is a scaling factor where Smax >> Smin >> A simpler choice could be Us E Ir (wx). however, the chain rule used within algorithmic differentiation routines does not produce subgradients (see, e.g., Figure [ In contrast, conservative Jacobians are faithful models of AD outputs. The asymptotic behavior of the above algorithm depends on the variational properties of the conservative Jacobian
== + N J.
Theorem 3 (Convergence result) Consider minimizing é given in ( using algorithm
10 under
Assumption 7 Assume furthermore the following
Step size: Σter ag = +oo and cg. =011/ log(k)).
* Bounddednes:: there exists M > O, and K C IR" open and bounded, such that, for all 8 (8mminn 8max) and wo E cl K, ||wa|l| Il S M almost surely.
For almost all We E K and s E (Smin, Smax). the objective value ((wk) converges and all accumula- tion points to of wi are Clarke-critical in the sense that d
This result shows that AD SGD may be applied successfully to all problems described in Section 3 combining algorithmic differentiation with implicit differentiation. Its proof may be adapted directly from 14 details are given in Appendix D
Numerical experiments
Using implicit differentiation when the invertibility condition in Theorem 2 does not hold can result in absurd training dynamics.
cyclic gradient dynamics via fixed-point/opptinzzzaii layer. Consider the bilevel problem:
min
f( ()x,8,8) = (xr - 31)2 + 4(y - 2
(11)
2,9.8
s.t. 8 SE sEs(z.)) == arg max {(a + b- + + 2): a [0.3]. e [0,5]].
8

---

Problem (11) has an equivalent fixed-poing formulation using projected gradient descent on the inner associates (z, the following:
problem (Appendix E.I.Ip. Backpropagation applied (TT)
V (o,,) y, (x)) + Jz, y, ((x))
y,
(12)
where J, piecewise derivative. We implement gradient descent for (T). evaluating (22 either using cvxpylayers [2] or the JAX tutorial [59] for fixed-point layers. In both cases, the invertibility condition in Theorem 2 fails when -3r + y + 2 = O, resulting in discontinuity dynamics globally: the gradient trajectory converges
8, affecting the limit cycle of non critical points (Figure 2a
see Appendix E.1 for details.
Persistence under small perturbations: For different initial points the gradient flow converges to the same limit cycle (Figure 2ap. The cycle persists even if perturb the coefficients the problem
see Appendix
E.1 for more details).
000
000
000
20.000
40.000
30
initial
5oo
gradiont flow
00.000
x
(a)
(b)
Figure 2: (a) Gradient flow for several initializations. (b) Gradient flow for 20 perturbed experiments with o² 0.4.
Lorenz-like dynamics via implicit differentiation. (ODE) writes:
The Lorenz Ordinary Differential Equation
2 z= x).
=x(p -) y. and ry Bz.
(13)
is well-known that taking (o, P, chaotic trajectory, displayed in Figure 3a Denoting F (z, 2, + (( 82) the vector field of the Lorenz system
(10, 28, 8/3), and (r(0), (0,1,, (1) gives
(33.. consider the optimization problem:
max
s.t.
z E arg min||s F(u)]I aER2
(14)
KERS
which is obviously equivalent to
max WER3
n F(u).
(15)
attractor
Implicit gradient ascent
Vanilla gradient
40C
1.0
40
30C
0.8
30
200
20
0.6
100
0.4
30
200
10
100
400
-20 -10
0
-200
0
100
100
200
200
20
200
-20
300
(a)
(b)
(c)
Figure 3: Implicit gradient ascent (b) outputs pathological curve with some qualitative aspects of the Lorenz dynamics (a) and really different from a classical gradient (c).

---

The function g: x² F(u) is a nondegenerate quadratic function whose expression can be found in Appendix E.2.1] The function g has for unique critical point (0, 0, 0) which is a strict saddle- point. We perform gradient ascent with implicit differentiation using cvxpylayers on (14). and the classical gradient ascent on the equívalent problem (15). The path obtained by implicit differentiation (Figure 3b resembles the Lorenz attractor (Figure Sap. in stark contrast to the conventional method (Figure 3c The chaotic dynamics are a consequence the lack of invertibility, due to the power 4 in (14). and various numerical approximations related to optimization and implicit differentiation.
Conclusion and future work
This article provides rigorous framework and calculus rules for nonsmooth implicit differentiation using the theory of conservative Jacobians. In particular, it describes precise conditions under which implicit differentiation can be used, in way that is compatible with backpropagation and first-order algorithms.
We show the applicability of results on practical machine learning problems including training of neural networks involving layers with implicitly defined outputs (deep equilibrium nets, networks with optimization layers) and nonsmooth hyperparameter optimization (Lasso-type models).
Finally, we demonstrate the necessity of a rigorous theory nonsmooth implicit differentiation through multiple numerical experiments. These illustrate the range of extremely pathological gradient dynamics that can occur when algorithmic differentiation combined with nonsmooth implicit differentiation outside the scope of our theorem, i.e., without satisfying the invertibility condition we specify.
Acknowledgments and Disclosure of Funding
The authors acknowledge the support of AI Interdisciplinary Institute ANITI funding, through the French "Investing for the Future PIA3" program under the Grant agreement ANR-19-PIA-- 0004, Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant numbers FA9550-19- 19-5000991--726- FA9550-18 1-500-1---- and ANR MaSDOL 19-CE23-0017-01. Bolte also acknowledges the support of ANR Chess, grant ANR-I7-EURE-0010 and TSE-P.
References
[1] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, M. Kudlur, J. Levenberg, R. Monga, S. Moore, D. G. Murray, B. Steiner, P. Tucker, V. Vasudevan, P. Warden, M. Wicke, Y. Yu, and X. Zheng. Tensorflow; A system for large- scale machine learning.
12th USENIX Symposium on Operating Systems Design and Implementattin (OSDI 16), pages 265-283, 2016.
[2] A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and Z. Kolter. Differentiable convex optimization layers. In Advances in Neural Information Processing Systems, volume 32, 2019.
[3] A. Agrawal, S. Barratt, S. Boyd, E. Busseti, and W. M. Moursi. Differentiating through a cone program. J. Appl. Numer. Optim, 1(2):107-115, 2019.
[4] B. Amos and J. Z. Kolter. Optnet: Differentiable optimization as layer in neural networks, In International Conference on Machine Learning, pages 136-145. PMLR, 2017.
[5] H. Attouch, J. Bolte, P. Redont, and A. Soubeyran. Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the -ajdykka-toassiewicz inequality. Mathematics of operations research, 35(2):438-45 2010.
[6] J.PP. Aubin and H. Frankowska. On inverse function theorems for set-valued maps. Journal de mathématiques pures el appliquées, 66(1):71-89, 1987.
[7] S. Bai, J. Z. Kolter, and V. Koltun. Deep equilibrium models. In Advances in Neural Information Processing Systems, volume 32, 2019.
[8] M. Benaïm, Hofbauer, and Sorin. Stochastic approximations and differential inclusions.
SIAM Journal on Control and Optimization, 44(1):328-344 2005.
10

---

[9] Q. Bertrand, Q. Klopfenstein, M. Blondel, S. Vaiter, A. Gramfort, and J. Salmon. Implicit dif- ferentiation of lasso-type models for hyperparameter optimization. In International Conference on Machine Learning, pages 810-821. PMLR, 2020.
[10] Q. Bertrand, Q. Klopfenstein, M. Massias, M. Blondel, S. Vaiter, A. Gramfort, and J. Salmon. Implicit differentiation for fast hyperparameter selection in non-smooth convex learning. arXiv preprint arXiv:2 2021.
[11] P. Bianchi, W. Hachem, and S. Schechtman. Convergence of constant step stochastic gradient descent for non-smooth non-convex functions. arXiv preprint arXiv:2005.085/4 2020.
[12] Bochnak, M. Coste, and M.-F. Roy. Real algebraic geometry, volume 36. Springer Science Business Media, 2013.
[13] J. Bolte, A. Daniilidis, A. Lewis, and M. Shiota. Clarke subgradients of stratifiable functions.
SIAM Journal on Optimization, 18(2)556-577, 2007.
[14] Bolte and E. Pauwels. Conservative set valued fields, automatic differentiation, stochastic
gradient methods and deep learning. Mathematical Programming, pages 1-33, 2020.
[15] J. Bolte and E. Pauwels. A mathematical model for automatic differentiation in machine learning. In Conference on Neural Information Processing Systems, 2020.
[16] Bradbbry, R. Frostig, P. Hawkins, M. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke,
J. VanderPlas, S. Wanderman-Milne, and Q Zhang. JAX: composable transformations of Python+NummP programs, 2018.
[17] E. Busseti, M. Moursi, and Boyd. Solution refinement at regular points of conic problems. Compulational Optimization and Applications, 74(3):627-643, 2019.
[18] C. Castera, J. Bolte, C. Févotte, and E. Pauwels. An inertial newton algorithm for deep learning. arXiv preprint arXiv; 19Ki: 1905. 12278, 2019.
[19] Clarke. On the inverse function theorem. Pacific Journal of Mathematics, 64(1):97-102, 1976.
[20] F. H. Clarke. Optimization and nonsmooth analysis. SIAM, 1983.
[21] P. I.. Combettes and J.-C. Pesquet. Deep neural network structures solving variational inequali- ties. Val-Valued and Variational Analysis, pages 1-28, 2020.
[22] L.. Combettes and V. R. Wajs. Signal recovery by proximal forward-backward splitting. Multiscale Modeling & Simulation, ((4):1168-120)) 2005.
[23] M. Coste. An introduction to o-minimal geometry. Istituti editoriali poligrafici internazionali
Pisa, 2000.
[24] D. Davis and D. Drusvyatskiy. Conservative and semismooth derivatives are equivalent for semialgebraic maps. arXiv preprint arXiv:2102.08 084444 2021.
[25] D. Davis, D. Drusvyatskiy, S. Kakade, and J. D. Lee. Stochastic subgradient method converges on tame functions. Foundations of computational mathematics, 20(1): 19-114,, 2020.
[26] A. L. Dontchev and R. T. Rockafellar. Implicit functionn and solution mappings, volume 543. Springer, 2009.
[27] L. Dries and C. Miller. On the real exponential field with restricted analytic functions. Israel Journal of Mathematics, 92:427, 1995.
[28] B. Efron, T. Hastie, Johnstone, R. Tibshirani, al. Least angle regression. Annals of statistics, 32(2):407-499, 2004.
[29] T. Fukui, K. Kurdyka, and L. Paunescu. Tame nonsmooth inverse mapping theorems. SIAM Journal on Optimization,
2010.
[30] L. E. Ghaoui, F. Gu, B. Travacca, and A. Askari. Implicit deep learning. CoRR, www/aabs.....00 05315, 2019.
[31] S. Gould, R. Hartley, and D. Campbell. Deep declarative networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[32] Gu, H. Chang, Zhu, Sojoudi, and I.. Ghaoui. Implicit graph neural networks. In Advances in Neural Information Processing Systems, volume 33, 2020.

---

[33] S. Hayashhi N. Yamashita, and M. Fukushima. A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM Journal on Optimization. (5(2):593-613) 2005.
[34] J.-B. Hiriart-Urruty. Tangent cones, generalized gradients and mathematical programming in banach spaces. Mathematics of operations research, 4(1):79-97, 1979.
[35] Z. Ji and M. Telgarsky. Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems, 33, 2020.
[36] H. Jongen, D. Klatte, and K. Tammer. Implicit functions and sensitivity of stationary points. Mathematical Programming, 49(1):123-138, 1990.
[37] S. M. Kakade and J. D. Lee. Provably correct automatic sub-differentiation for qualified pro- grams. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[38] K. A. Khan. Branch-locking ad techniques for nonsmooth composite functions and nonsmooth implicit functions. Optimization Methods and Software, 33(4-6): 127-1155, 2018.
[39] L. Kong, L. Tunçel, and N. Xiu. Clarke generalized jacobian of the projection onto symmetric cones. Ser- Ser- Valued and Variational Analysis, 17(2):135-1511 2009.
[40] W. Lee, H. Yu, X. Rival, and H. Yang. On correctness of automatic differentiation for non- differentiable functions. In NeurIPS 2020-34th Conference on Neural Information Processing Systems, 2020.
[41] A. Lewis and T. Tian. The structure of conservative gradient fields. arXiv:2101.000 00099, 2021.
arXiv preprint
[42] J. Mairal and B. Yu. Complexity analysis of the lasso regularization path. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1845-1842, 2012.
[43] J. Malick and H. S. Sendov. Clarke generalized jacobian of the projection onto the cone of positive semidefinite matrices. Set- Valued Analysis, 14(3):273-293: 2006.
[44] J. Moreau. Décomposition orthogonale d' un espace hilbertien selon deux cônes mutuellement polaires. Comptes rendus hebdomadaires des séances de I' l'Académie des sciences, 255:238-244 240, 1962.
[45] Y. Nesterov. Lexicographic differentiation of nonsmooth functions. Math. Program., 104:669- 700, 11 2005.
[46] M. R. Osborne, B. Presnell, and B. A. Turlach, On the lasso and its dual. Journal of Computa- tional and Graphical Statistics, 9(2):319-337, 2000.
[47] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang. Z. Vito,, M. Raison, A. Te- jani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, nigh-performance deep learning library. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024 8035. Curran Associates, Inc., 2019.
[48] F. Pedregosa. conference on machine learning, pages 737-746. PMLR, 2016.
Hyperparameter optimization with approximate gradient. In International
[49] M. Robinson. An implicit-function theorem for a class of nonsmooth functions. Mathematics of operations research, 16(2):292-309 1991.
[50] D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning Representations by Back- propagating Errors. Nature, 323(6088) 1986.
[51] M. Shiota. Geometry of subanalytic and semialgebraic sets. De Gruyter, 2011.
[52] D. Sun. A further result on an implicit function theorem for locally lipschitz functions. Opera- tions Research Letters, 28(4):193-1))
2001.
[53] R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Stotistical Society: Series (Methodological), 58(1 58(1):200 1:26772888, 1996.
[54] R. J. Tibshirani. The lasso problem and uniqueness. Electronic Journal of statistics, 7:1456-
1490, 2013.
12

---

[55] L. van den Dries and C. Miller. Geometric categories and o-minimal structures. Duke Math. J, 84(2):497-540, 1996.
[56] Warga. Fat homeomorphisms and unbounded derivate containers. Journal of Mathematical Analysis and Applications, :1:555560,, 1981.
[57] A. Wilkie. theorem of the complement and some new o-minimal structures. Selecta Mathematica, 5:397-421, 1999.
[58] E. Winston and J. Z. Kolter. Monotone operator equilibrium networks. In Advances in Neural Information Processing Systems, volume 33, 2020.
[59] M. Zico Kolter, David Duvenaud. Deep implicit layers neural odes, deep equilibirum models, and beyond, 2020. NeurlPS Tutorial.
13


Reviews:
[{"review_id": "eN2m19bDsn", "reviewer": "Reviewer_gMrk", "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).\n\nIn 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.\n\nThe authors highlight some applications of implicit differentiation in the area of machine learning:\n - Monotone implicit layers\n - Embedded optimization problems such as optimization layers and hyperparam optimization for L1 regularized optimization problems\n\nIf 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.\n\nIn some cases it can be possible to prove that the invertibility condition is guaranteed.\n\nThe 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.\n\nThe 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.\n\n[1] Branch-locking AD techniques for nonsmooth composite functions and nonsmooth implicit functions\n[2] Provably Correct Automatic Subdifferentiationfor Qualified Programs", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points:\n\n- The paper gives theoretic justification to methods that are already used in practice.\n- The paper provides examples for use cases that show that the theory is somewhat relevant to practical applications (in machine learning)\n- The authors formally extend on a theory that has been picked up by different authors for analyzing nonsmooth functions (in machine learning applications)\n- The theory and derivations are clean and of high quality and seems relevant\n\nWeak points:\n\n- 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.\n- 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).\n- 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.\n\nOriginality: 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.\n\nQuality: The presented theory is high quality. The numerical experiments are only toy examples.\n\nClarity: 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.\n\nSignificance: 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.\n\nI 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.\n\nRecommendations:\n- Improve the initial explanation of the conservative differentiation formalism as it applies to AD as used in ML frameworks\n- Contrast your results to other nonsmooth AD approach to highlight the pros / cons\n\nAn example of implicit differentiation via elements of the conservative derivative for an implicit function that does not satisfy the invertibility condition is the following:\n\nLet\n\n0 = x - (relu(y) - relu(-y)) = g(x, y(x))\n\nwhere since relu(y) - relu(-y) = y we have y(x) = x and hence y'(x) = 1 everywhere.\n\nBut 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\n\ny'(x) = -dg/dy^{-1} * dg/dx = -0^{-1} * 1\n\ni.e. in such a case the invertibility condition is not satisfied.\n\nWith 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\n\nrelu'(y; dir_y) = 1\nrelu'(-y; dir_y) = 0\n\nor alternatively for dir_y = -1 we have\n\nrelu'(y; dir_y) = 0\nrelu'(-y; dir_y) = -1\n\nand so in both cases we have\n\ndg/dy(.; dir_y) = (relu'(y; dir_y) - relu(-y; dir_y)) = 1\n\nwhich avoids the non-invertibility.\n\n- 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.\n\nNits:\n- Right of Figure 1 looks very similar to Figure 3 (b), is it necessary to have both?\n- For the first example you have\nx = tanh(z) + relu(-z) + z - relu(z)\n= tanh(z) + z + max(0, -z) - max(0, z)\n= tanh(z) + z - z\n= tanh(z)\nwhich seems to imply that z = tanh^{-1}(x) instead of z = tanh(x) like you write.\nThe legend of figure one (invtanh) suggests that's what you had in mind anyways.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "OqvGSi49rpS", "reviewer": "Reviewer_2ovw", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nPros:\n- Rigorous math and well-stated assumptions, conditions and results.\n- Tackles a missing gap by the prior works in this direction (i.e., IFT applied in non-smooth settings)\n- The theory captures a relatively wide variety of scenarios, including equilibrium networks, hyperparameter optimization (bi-level optimization), and optimization layer.\n\nCons:\n- 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).\n- 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.\n- The experiment has a limited scope and is on low dimension.\n\nI'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)?\n\n---------\n---------\n\n### Post-rebuttal\n\nI'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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As this is a theory paper, the authors have discussed the limitations by clearly stating the assumptions.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "FvVHQ6Cujky", "reviewer": "Reviewer_eaLv", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nThe 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.\n\nAs 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is purely theoretical and does not involve any applications that may lead to negative social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "C0uwrlTyoaG", "reviewer": "Reviewer_ZCf8", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Quality**: I did not check the theorem statements/proofs, though the logical progression of the theorems makes sense to me.\n\n**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. \n\n**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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any limitations or potential negative societal impact of the work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)