Automatic differentiation of nonsmooth iterative algorithms
Authors: Jerome Bolte
Edouard Pauwels
Samuel Vaiter
Venue: NeurIPS 2022 Accept (2022)
Keywords: Fixed point solvers
nonsmooth algorithms
automatic differentiation
unrolling
piggy back differentiation
conservative gradients.

Abstract: Differentiation along algorithms, i.e., piggyback propagation of derivatives, is now routinely used to differentiate iterative solvers in differentiable programming. Asymptotics is well understood for many smooth problems but the nondifferentiable case is hardly considered. Is there a limiting object for nonsmooth piggyback automatic differentiation (AD)? Does it have any variational meaning and can it be used effectively in machine learning? Is there a connection with classical derivative? All these questions are addressed under appropriate contractivity conditions in the framework of conservative derivatives which has proved useful in understanding nonsmooth AD. For nonsmooth piggyback iterations, we characterize the attractor set of nonsmooth piggyback iterations as a set-valued fixed point which remains in the conservative framework. This has various consequences and in particular almost everywhere convergence of classical derivatives. Our results are illustrated on parametric convex optimization problems with forward-backward, Douglas-Rachford and Alternating Direction of Multiplier algorithms as well as the Heavy-Ball method.

Automatic differentiation of nonsmooth iterative algorithms
Jérôme Bolte
Edouard Pauwels
Toulouse School of Economics, University of Toulouse Capitole. Toulouse, France.
IRIT, CNRS, Université de Toulouse. Institut Universitaire de France (IUF). Toulouse, France.
Samuel Vaiter
CNRS & Université Côte d' Azur, Laboratoire J. A. Dieudonné.
Nice, France.
Abstract
Differentiation along algorithms, i.e. piggyback propagation of derivatives, is now routinely used to differentiate iterative solvers in differentiable programming. Asymptoties is well understood for many smooth problems but the nondifferen- tiable case is hardly considered. Is there a limiting object for nonsmooth piggyback automatic differentiation (AD)? Does it have any variational meaning and it be used effectively in machine learning? Is there a connection with classical derivative? All these questions addressed under appropriate nonexpansivity conditions in the framework of conservative derivatives which has proved useful in understanding nonsmooth AD. We characterize the attractor set of nonsmooth piggyback iterations as a set-valued fixed point which remains in the conservative framework. Among various consequences gence of classical derivatives. Our results are illustrated on parametric convex optimization with serward-bacwwadd Douglas-Rachford Rachford and Alternating Direction of Multiplier algorithms as well as the Heavy-Ball method.
have almost everywhere conver-
Introduction
Differentiable programming. We consider Lipschitz function F: RP IR'" m RP, representing an iterative algorithm, param- eterized by 0 E RR, with Lipschitz initialization Zo 0 - (0) and
nonsmooth
Jz (0)
autodiff
limit?
(0) = ((rx(0), = (zx(())))
(1)
z(0)
w derivative?
Jeb
where Fg : F(, under the assumption that xy (0) converges to the unique fixed point of Fg: F(0)- fix(Fe). Such recursion represent for instance algorithms to solve an optimization problem min, h(x)) (e.g. empirical risk minimization), such gradient de- scent: F(z, 0) = x 0Vh(r). But (1) could also be a fixed-point equation such deep equilibrium network [5].
We study exis- tence and meaning of J as a derivative of ž, compatible with automatic differentiation of the iterates (zz()))
Figure 1:
In the last years, paradigm shift occurred: such algorithms are now implemented in algorithmic differentiation (AD)-friendly frameworks such Tensorflow [1]. PyTorch [42] or JAX [13]. For a differentiable F, is possible to compute iteratively the derivatives of
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Ridge (FB)
Lasso (FB)
Sparse Inv. Covar, (DR)
Trend Fibering (ADMM)
10
10-1_
10
10-1-
10-4
10"1
10-4
10-1-
500
1000
0
500
1000
500
1000
5000
1000
10
10.
10:11
10-1
10-1-
10
10-3
10
3010
1000
0
500
1000
500
1000
5000
1000
Ineration
itceation
iteration
iteration A:
Figure 2: Illustration of the linear convergence of proximal splitting methods. (First line) Distance of the iterates to the fixed point. (Second line) Distance of the piggyback Jacobians to the Jacobian of the fixed point. The acronyms are FB for Forward- Backwadd. DR for for Alternatigg Direction Method of Multipliers. In all cases, despite nonsmoothness, piggyback Jacobians converge, illustrating Corollary 2. Blue lines represent the median of 100 repetitions with random data, and the blue shaded area represents the first and last deciles.
Rachford and ADMM
F& with respect to 9 using the differential calculus rules resulting in so called "piggyback" recursion:
a 00 Tk+ + (0) og ((xx
à 02 F2 (zx
0 Tk (0)
where é Tg is the Jacobian of Ir with respect to 0. In practice, automatic differentiation frameworks do not compute the full Jacobian, but compute either vector-Jacobian products in reverse-mode (or backpropagation) [48] or Jacobian- vector products in forward mode [53]. We rather consider the full Jacobian, and therefore, our findings apply to both modes. We focus on two issues arising with nonsmooth recursions, illustrated in Figure 1. (i) what can be said about the chain rule (2) and its asymptotics when the function F is not smooth (for example a projected gradient step)? (ii) how to interpret its asymptotics answer to both questions, providing a solid theoretical ground to the idea of algorithmic differentiation of numerical solvers involving nonsmooth components in a differentiable programming context.
notion of derivative for the fixed point of F6? We propose a joint
Related works. Algorithmic use of the chain rule (2) to differentiate programs takes its root in [53]. with forward differentiation, and later in reverse mode [35]. Along with the development of AD, convergence of the iterative sequence (2) was investigated, notably in the optimization community as reviewed in [28]. This important survey paper gathers results in differentiable programming rediscovered/reusee later: implicit differentiation [43, 45] and its stability [8]. adjoint fixed point iteration [5] (a key aspect of the deep equilibrium network) and linear convergence of (2). Notably, linear convergence of Jacobians was investigated in [25, 27] for the forward mode and in [15, Theorem 2.3] for the reverse mode. This was more recently investigated for C2 functions in imaging for primal-dual algorithms [14, 9] and in machine learning for gradient descent [39, 36] and the Heavy-ball [39] method. In the specific context where F solves a min-min problem, the authors in [2] proved the linear convergence of the Jacobians. The use of AD for nonsmooth functions was justified with the notion of conservative Jacobians [12, 11] with a nonsmooth version of the chain rule for compositional models. Correctness of AD was also investigated in [34] for a large class of piecewise analytic functions, and in [33] where a qualification condition is used to compute a Clarke Jacobian. Along with AD, natural way to differentiate model (1) is by implicit differentiation, recently applied in several works [5, 3, 21]. In a nonsmooth context, an implicit function theorem [10] was proved for rath-differentiable functions. In terms of applications, nonsmooth piggyback derivatives are applied to hyperparameter tuning for inverse problems in [8] while the case of Lasso was investigated in [7]. Other relevant applications include plug-and-play denoising [32], parameter selection [19]. bilevel programming [41]
Contributions:
Under suitable nonexpansivity assumptions, our contributions are as follows.
. We address both questions illustrated in Figure for nonsmooth recursions. Set-valued extensions of the piggyback recursion (2) have well defined limit: the fixed point of subset map (Theorem 1), conservative for the fixed point map т. This is nonsmooth "infinite" chain rule for AD (Theorem 2).

---

* For almost all 8, despite nonsmoothness,, recursion (2) is well defined using the classical Jacobian and converges to the classical Jacobian of the fixed point (Corollary 2). This has implications for both forward and reverse modes of AD.
selection), it is possible to give quantitative rate estimate (Corollary 3), namely to prove linear convergence of the derivatives.
For a large class of functions (Lipschitz-gradien
We show that these results can be applied to proximal splitting algorithms in nonsmooth convex op- (Proposition 2), well Douglas- Rachhford (Proposition 3)
timization. We include bowward-backee
and ADMM, numerical illustration of the convergence of derivatives is given in Figure 2.
We also illustrate that, contrarily to the smooth case, nonsmooth piggy back derivatives of momen- tum methods such as Heavy-ball. may diverge even the iterates converge linearly (Proposition 4).
Notations. A function f T.P - R is locally Lipschtiz if, for each x E RR, there exists neighborhood of x on which f is Lipschitz. Denoting by R s R", the full measure set where f is differentiable, the Clarke Jacobian [16] at R is defined as
of (yx) M conv [ Br ,3(x)) s.t. lim yh 2, R. lim dy
Jac Jac"f(z) f(z)
(3)
The Clarke subdifferential, ʃ is defined similarly. Given two matrices A, B with compatible dimension, [A, B] is their concatenation. For a set X, conv is its convex hull. The symbol IB denotes unit ball, the corresponding norm should be clear from the context.
2 Nonsmooth piggyback differentiation
We first show how the use of the notion of conservative Jacobians allow us to justify rigorously the existence of nonsmooth equivalent of piggyback iterations in (2) that is compatible with AD.
Conservative Jacobians. Conservative Jacobians were introduced in [12] as generalization of derivatives to study automatic differentiation of nonsmooth functions. Given locally Lipschitz continuous function f: Rº - I"", the set-valued J : Rº = Rmxp is conservative Jacobian for the path differentiable f J has a closed graph, locally bounded and nowhere empty with
d dt f((()) J(x(t)))((t) a.e.
(4)
for any 7: [0, 1] IR. absolutely continuous with respect the Lebesgue measure. Conservative gradients are defined similarly. We refer to [12] for extensive examples and properties of this class of function, key ideas are recalled in Appendix A for completeness. Let us mention that the classes of convex functions, definable functions, or semialgebraic functions are contained in the set of path differentiable functions. Given Dy: IRP = IR, conservative gradient for f: IRP IR, we have:
(Clarke subgradient), for all x E R 0 (xx c conv(D,
(Gradient almost everywhere) (= = (V (z)) for almost all E IR.
* (Calculus) differential calculus rules preserve conservativity, e.g. sum and compositions of conser- vative Jacobians are conservative Jacobians.
Finally, Dy can be used as a first order optimization oracle for methods gradient type [11].
Piggyback differentiation of recursive algorithms. The following is standing throughout the text.
Assumption (The conservative Jacobian of the iteration mapping is contraction) F is lo- cally Lipschitz, path differentiable, jointly in (x. 0), and Jr is a conservative Jacobian for F. There exists 0 & p such that for any (x, 0) RP R and any pair [A, B] Jr(x, 0), with RPxP and e Rpxm, the operator norm of A is at most p. Jzo is conservative Jacobian for the initialization function + z0))).
Under Assumption 1, Fe is a striet contraction that (Ix(0)) keN converges linearly z(0) fix(Fe) the unique fixed point of the iteration mapping Fg. More precisely, for all k E N, we have
Io Fo(x))ll
I (0) - =(0) <
3

---

Furthermore, for every & E N, let us define the following set-valued piggyback recursion:
J JAN. (0) {AJ + B, [A, BJ E JF(zx(0),0)
Jr, (0))
(PB)
We will show in Section that (PB) plays the same role as (2) in the nonsmooth setting. Note that one can recursively evaluates sequence Ju Jay, k E N, through operations actually implemented in nonsmooth AD frameworks, as follows
Jk+1 = A + Bk where [A,, (f))x(0),0),
(5)
Remark (Local contractions) Assumption may be relaxed as follows: for all 8, the fixed point set fix( F6) is singleton žg such that Ię (f) - I(f) as k - and the operator norm condition on JF in Assumption 1 holds at the point (ā(0), 0). By graph closedness of JF. in a neighborhood of (z(0), 0), F6 is a strict contraction and the operator norm condition Jr holds, possibly with a larger contraction factor p. After finitely many steps, the iterates (Ix) keN remain on some neighborhood and all our convergence results hold, due to their asymptotic nature.
Remark 2 (Relation to existing work) For smooth F natural conservative Jacobian is the clas- sical one. The, hypotheses in [39, 36] for gradient descent (F is C)), are exactly the classical counterpart of Assumption
On the other hand [25, 27, 15] use a more general assumption on spectral radius, which allow to treat the Heavy-Ball method, e.g. in [39]. However this does not generalize to sets of matrices, as shown in Section 5. Hence Assumption 1 is on operator and not on spectral radius, which is sharp. contrary to the smooth case.
3
Asymptotics of nonsmooth piggyback differentiation
3.1 Fixed point of affine iterations
Gap and Haussdorf distance.
Being given two nonempty compact subsets X, ) of RR, set
(X)( max d(x,)) where d(z, }) min x yll. yey
xEX
and define the Hausdorff distance between X' and y by dist(XX))) = max X V), gap(). V.Y' X)). Note that gap(X,)) 0 if, and only if, X' = V, whereas dist 3)) 0 if, and only if, X y Moreover, X' = y + gap( X. V)B where IB is the unit ball. It means that gap(X, "measures" the default inclusion of X' V, see [46, Chapter 4] for more details.
Affine iterations by packets of matrices. Let J = (p-(x-m) be a compact subset of matrices such that any matrix of the form [A, B] E I with A e Rexp is such that A has operator norm at most - < 1. We let J act naturally on the matrices of size p x m as follows J: I 3 IRx the function from Ippxm to subsets of Rexm which is defined for each X I_ as follows: J(X) = (AX B, [A, B] J). This defines set-valued map through, for any RRxm
J(X) (AX B, [A, B] E J. X
Recursions of the form (PB) generate sequences (Ax) of subsets of Rpxm satisfying
X = J(X) V N.
The following is an instance of the Picard theorem (whose proof recalled Appendix B).
Theorem (Set-valued affine contractions) Let I RDx(p+m) be compact subset of matrices above with p < 1. Then there is unique nonempty compact set fix(T) c -ppxm satisfying fix(J) = J (fix(T)), where the action of J is given in (6).
Let (Me) be sequence of compact subsets of IRxxm, such that No # D. and satisfying the recursion (7). We have for all k
dist(Xy, fix(()) & tt dist List(Xoo,Co [(Xo))
where dist is the Hausdorff distance related to the Euclidean norm on p x matrices.

---

3.2 An infinite chain rule and its consequences
Define the following set-valued map based on the fix operator from Theorem
- 0 = fix [Jr(#(0),0])
where z(0) the unique fixed point of the algorithmic recursion. Since x(0) fix Fo))
we have equivalently that J is the fixed-point of the Jacobian at the fixed-point: JØ" = fix (f)())((F)))))))))))))) We have the following (proved in Appendix C) and consequence from Theo- rem 1.
Theorem (A conservative mapping for the fixed point map) Under Assumption 1, J well- defined, and is conservative Jacobian for the fixed point map x.
Corollary (Convergence of the piggy derivatives) Under Assumption f.ror all 8, the recur- sion (PB) satisfies
lim gap(Ja; (0), (0)) 0. k0
Unrolling the expression of Jzc, using (6) and (7), we can rewrite (8) with compositional product:
((Js(Cx(0)0)) (J (O), 0. (
K
lim gap K00
In plain words, this limit-derivative exchange result: Asymptotically, the gap between the automatic differentiation os and the derivative of the limit is zero. In particular the recursion (5) produces bounded sequences whose accumulation points are in f Since conservative Jacobians equal classical Jacobians almost everywhere [12], we have convergence of classical derivatives.
Corollary (Convergence a.e. of the classical piggybact derivatives) Under Assumption for almost all 6, the classical Jacobian è (0), is well defined for all i and converges towards the classical Jacobian of That is
à (+)
lim 1--20 08
20 z(0), for almost all
Remark 3 (Connection to implicit differentiation) The authors in [10] proved a qualification-Fii version of the implicit function theorem. Assuming that for every [A, B] [z(0),, 0), the matrix - A is invertible, we have that
jum = (U-))) JF(((0),))
conservative Jacobian for Under Assumption 1, one has J= c J (0) for all 8. Unfor- tunately, as soon F is not differentiable, the inclusion may be strict, see details in Appendix D.
3.3 Consequence for algorithmic differentiation
Given l: e N. θ Rm ūu RP, the following algorithms allow us to compute in J& using the forward mode of automatic differentation (Jacobian Vector Products, JVP), and 0% w/ Js using the backward mode of automatic differentiation (Vector Jacobian Products, VJP). In compositional model is the derivative of an inner functions controlling algorithm parameters 0, with another variable real variable e R. for example an hyper parameter. The goal is to combine 20()) and ax
(0) with the chain rule in forward pass to obtain the total derivative (zz On the other hand, in compositional model, Wx is typically the gradient of an outer loss functions evaluated at (0).).
In this case the goal is combine derivatives of iterates
(x) with Wi
a((az) in backward pass daz
00
to obtain (9))
20
5

---

Algorithm 1: Algorithmic differentiation of recursion (1), forward and reverse modes
Input: e N, 0 IR, 0 E I,, We E IP, initialization function (0))), recursion function
F(z, 0). conservative Jacobians (x 8) and Jzo (0). Initialize: To zo( e R".
Forward mode (JVP):
Reverse mode (VJP): 0s = 0.
in J0, J E (0). for i = =::=1.... 1...., do
for 1.... K do
= -(
I; F( 8)
for ....... do
I; = A + 1
0R 02 B 1-11 10
11
AT,
[A Bin1 Jr (1
[A. 1, B E (x
Return: i
02 0g J Wo. J Jzo (0)
Return: 0g
Proposition 1 (Convergence of VJP and JVP) Let k N, 0 R. wh IR, 23 R2, I RP, o R be in Agorithm I under Assumption 1. Then for almost all I Rm, Ib. 0.
Assume furthermore that, as k - CD, Wi v (for example, we v((ax) for C loss E), then for almost all 0 E R., 0 TT 0z
80
Remark 4 In addition to Proposition 1, in both cases, for all all accumulation points of both 4% and o% are elements of J á and w/ J respectively. This is a consequence of Corollary combined with algorithmic differentiation arguments which proof is given in Appendix D.
3.4 Linear convergence rate for semialgebraic piecewise smooth selection function
Semialgebraic functions are ubiquitous in machine learning (piecewise polynomials, f1, l norms, determinant matrix rank...). We refer the reader to [11] for a thorough discussion of their extensions, and use in machine learning. For more technical details, see [17, 18] for introductory material on semialgebraic and o-minimal geometry.
Lipschitz gradient selection functions. Let F: RD - R9 be semialgebraic and continuous. We say that F has a Lipschitz gradient selection (s, Fi...., Fm) if s: Rp (I....,m) m) is semialgebraic and there exists L > 0 such that for i = 1..., J...,,.. m. Fú: RD - RP is semial- gebraic with L-LLpsshitzz Jacobian, and for all E TR. F(z) (x) For any x R2, set [(x) fie [1.....m) m), F(z)
(z))). The set-valued map JØ: R. = R2xq given by Jj: r x= = conv (1 (o), i [xx) ). is a conservative Jacobian for F as shown in [11]. Here ar de denotes the classical Jacobian of F. Let us stress that such structure is ubiquitous in applications [11. 34].
Rate of convergence. We may now strengthen Corollary by proving the linear convergence of piggyback derivatives towards the fixed point. The following consequence of the fact that the proposed selection conservative Jacobians of Lipschitz gradient selection functions are Lipschitz-like -ike (Lemma 4 in Appendix E. Note that semialgebraicity only used as a sufficient condition to ensure conservativity of the selection Jacobian together with this Lipschitz like property. It could be relaxed if can be guaranteed by other means, in particular one could consider the broader class of definable functions in order to handle log- ligllikel data fitting terms.
Corollary 3 (Linear convergence of piggy back derivatives) In addition to Assumption 1, assume that has a Lipschitz gradient selection structure as above. Then, for any 0 and e 0, there exists C > such that the recursion (PB) with Jr = Jj. satisfies for all e N, gap(Ja, (f), Jhh (0)) & C(VP+ + e) Moreover, classical Jacobians in Corollary 2 converge at a linear rate for almost all
Application to proximal splitting methods in convex optimization
Consider the composite parametric convex optimization problem, where 0 e IRm represents parame- ters and E Rº is the decision variable
I(+)= = arg min f(x, + g(2, 0).

---

The purpose of this section is to construct examples of functions F used in recursion (1) based on known algorithms. The following assumption will be standing throughout the section.
Assumption 2 ʃ' semialgebraic, convex, its gradient with respect to for fixed 0, V.J., is locally Lipschitz jointly in (a, 0) and L-Lipschitz in æ for fixed A. Semialgcbraicity implies that =f path wath-differentiable jointly in (z, f), we denote by J7 its Clarke Jacobian. The function g is semialgebraic, convex in x for fixed A, and lower semicontinuous. For all a O. we assume that Ga(æ, 0) proxog((.9) (a) is locally Lipschitz jointly in (æ, 0). Semialgebraicity implies that is also path differentiable jointly in (2), 0). we denote by JG. its Clarke Jacobian.
This assumption covers very large diversity of problems in convex optimization most gradient and prox operations used in practice are semialgebraic (or definable). Under Assumption 2, we will provide sufficient conditions f and g for Assumption 1, for different algorithmic recursions. These will therefore imply convergence as stated in Corollary and 2, Proposition 1, as well Corollary 3 in the piecewise selection case. The proof' are postponed to Appendix F.
4.1 Splitting algorithms
In this section we provide sufficient condition for Assumption to hold. The underlying conservative Jacobian obtained by combining Clarke Jacobians of elementary algorithmic operations (gradient, proximal operator in Assumption 2), using the compositional rules of differential calculus [11] and implicit diffcrentiation [10]. Using [12], such Jacobians are conservative by semialgebraicity and their combination provide conservative Jacobians for the corresponding algorithmic recursion F. These objects are explicitly constructed in Appendix F.
Forward-backward algorithm.
The
iterations are given for a > 0 by
Tk+1 = prox (Ix- (xx
(10)
Under Assumption 2 with a 7, denote by Fa: Rexm TRP the forward- backward recursion in (10). For p. > 0, if either f is j-strrogly convex in for all 6 then Fa is a strict contraction and Assumption holds.
Proposition 2
is well known that if f y-strongly convex, choosing a 2/(L 14) provides contraction factor PFB = (T 1)/(1 T), where r = L/u 2 is the condition number of the problem.
Douglas-Rachfort algorithm.
Given a > 0, the algorithm goes as follows
yk+1 = 5 Raf(.,) Rag(- 0)
(11)
2
where Ras(-99 2prox
/ is the reflected proximal operator, which is 1-Lipschitz (and similarly for g). Following [6. Theorem 26.1 if the problem has minimizer, then (3% keN converges to a fixed point of (11), ÿ such that 5 = prox.g (f) a solution to the optimization problem. Following [26, Theorem 1], if f is strongly convex. then Raf(. is p-Lipschitz for some < 1 and our differentiation result applies to Douglas Rachhford splitting in this setting.
Proposition 3 Under Assumption with a > O, denote by Fa: RRxxM _ RP the recursion in (11). If is p-strongly convex in for all 0, then Fa is strict contraction and Assumption 1 holds.
Following [26, Proposition 3]. choosing a = 1/vLμ/ provides a contraction factor of order PDR(VT- 1)/(vT + 1) < PFB. where again 5 L/p is the condition number of the prob- lem. In this respect Rouglas-Rachfin 's iterations provide a faster asymptotic rate than those of which may also impact the convergence of derivatíves in the context of Corol-
lary 3.
Alternating Direction Method of Multipliers. Consider the separable convex problem
min do(u)) (u) + (0( subject to Agu Byv co.
(12)
7

---

The alternating direction method of multipliers (ADMM) algorithm combines two partial minimiza- tion of an augmented Lagrangian, and a dual update:
Us++1 = arg min (dl(w) + 2 Agu +
a
Aguu + BBvr - ce [
2
Ub+1 arg min (o(()) + 21 B& +
Aguu+1 + Boux - -col33
(13)
2
2b+1 z a( B8tR+1 cc))
As observed in [23]. the ADMM algorithm can be seen as the Douglas-Rachfon splitting method applied to the Fenchel dual of problem (12) (see Appendix F.3 for more details). More preciscly, ADMM updates are equivalent to Nouglas-Rachies iterations applied to the following problem
min Co + 06 (- A + Bg
(14)
f(x,0)
g(a.0)
Therefore, if Φe is strongly convex with Lipschitz gradient and A is injective, then ADMM converges linearly and one is able to combine derivatives of proximal operators to differentiate ADMM.
4.2 Numerical illustrations
We now detail how Figure 2 discussed in the introduction is obtained, and how it illustrates our theoretical results. We consider four scenarios (Ridge, Lasso, Sparse inverse covariance selection and Trend filtering) corresponding to the four columns. For each of them, the first line shows the empirical linear rate of the iterates T& and the second line shows the empirical linear rate of the 2 derivative 26 Tg All experiments are repeated 100 times and we report the median along with the first and last deciles.
Forward-Backward for the Ridge. The Ridge estimator is defined for
as x(0)
arg mitlgeR= 2 31 - 6112 + 0 01=:1 Among several possibilities to solve it, one can use the Forward- Backward algorithm applied to f: (z, 0) Ar b|2 and g 0| 2. Since g is strongly convex, the operator Fa is strongly convex, and thus Proposition may be applied.
Forward-Backward algorithm for the Lasso. to the Lasso problem [49], with parameter 0 0, i(f)= E arg minlyeRs &1 bl2 0||2]|
Consider the Forward Backwaard algorithm applied
arg min. 1 Aaz blß L |alla, where L is any upper bound on the operator norm of AA A. The gradient of the quadratic part is 1-Lipschitz, so we may consider the forward backward algorithm
21
(10), with unit step size and ʃ: (zr,0) - 2L Ax bl2 and g: (I, 0) - & ||1011-
A well known qualification condition involving generalized support optimality ensures uniqueness of the Lasso solution [20, 37J. It holds for generic problem data [50]. Following [10, Proposition 5], under this qualification condition, the implicit conservative Jacobian Jrr is such that, the solution x², the matrix set I Jr only contains invertible matrices. This means that there exists < 1, such that any M (x* has operator norm most p. Following Remark all convergence results apply qualitatively. Note that we recover the results of [7, Proposition 2] for the Lasso.
Dachlas-Rachford for the Sparse Inverse Covariance Selection. Selection [52, 22] reads z(f) arg min tr( tr(Cx) log det Ex, |azyle where C' is symmetric positive matrix and 0 0. It is possible to apply Rachlos-Rachford method to (a, 6) - tr(Cz) log det x and g (I, 0 - 0||z| 1.1 It is known that f is locally strongly convex, indeed x log det x is the standard self-concordant barrier in semidefinite programming [40]. Following Remark 1, all our convergence results apply qualitatively.
The Sparse Inverse Covariance
Rachford
ADMM for Trend Filtering. Introduced in [51] in statistics as a generalization of the Total Variation, the trend filtering estimator with observation 0 Rp reads =(()) arg mingers 1 I 01l + >| (4)) I, where ((k) a forward finite-differenn approximation of differential operator of order & (here ks = 2). Using the - A|u[[1 dh + ||u Oll (strongly convex), Ag -I (injective), Bo = (R), and cæ 0, we can apply the ADMM to solve trend filtering.

---

Failure of automatic differentiation for inertial methods
This section focuses on the Heavy-Ball method for strongly convex objectives, in its global linear convergence regime. For C2 objectives, piggyback derivatives converge to the derivative of the solution map [28, 39, 36]. However, we provide a C strongly convex parametric objective with path differentiable derivative, such that piggyback derivatives of the Heavy Ball algorithm contain diverging vectors for given parameter value. In this example, other conservative differentiation means (implicit differentiation, piggyback on gradient descent), avoid this divergent behaviors.
5.1 Heavy-ball algorithm and global convergence
Consider a function f: IR" x RT - IR, and 3 > O, for simplicity, when the second argument is fixed, we write fo: x f(x, 0). Set for all x, y. 0, F Fax, 0) (x fa((z) + B(x v), consider the Heavy-Ball algorithm (+++1,,++1) = F yk. 0) for & E
If fe is j-strongly convex with L-Lipschitz gradient, then, choosing a 1/L and B
2T. + V 47. + + the algorithm will converge globally at a linear rate to the unique solu- tion, z(0) [24, Theorem 4), local convergence is due Polyak [44]. Furthermore, if in addition is C forward propagation of derivatives converge to the derivative of the solution [28, 29, 39].
5.2 A diverging Jacobian accumulation
Details and proof of the following result are given in Section G.
Proposition 4 (Piggyback differentiation fails for the Heavy Ball method) Consider f: IR2 I. such that for all E I. f(x, 0) x²/2 if x 3 and f(x, 0) = z²/8 if x < 0. Assume that a 1 and 3 3/4. Then the heavy ball algorithm converges globally to 0 and V is path differ- entiable. The Clarke Jacobian of F with respect to (z. y) at (0,0, is ( (0,0,0) 0) = conv (M), where the product M1 MMM2MM has eigenvalue 99/8.
The presence of an eigenvalue with modulus greater than may produce divergence in (PB). Set
x² 1/2
if 1x20 0 fe: (z, -
x2/2 22/8
if x > 0 if $ 0.
f: (I,
2//8
if < 0.
Note that fi and fe are both equivalent xz() = y() = 0, we run a few iterations of the Heavy Ball algorithm for 0 = 0, and implement (PB) alternating between two steps on f1 and two steps on f2 and differentiate the resulting sequence (Ix Wer with respect to 0 using algorithmic differentiation. The divergence phenomenon predicted by Proposition 4 illustrated Figure 3, while the true derivative is (the sequence constant).
they implement the same function. With initializations
Conclusion
We have developed flexible theoretical framework describe convergence of piggyback differentia- tion applied to nonsmooth recursions providing, in particular, rigorous meaning to differentiation of nonsmooth solvers. The relevance of our approach is illustrated composite convex optimization
0.5
0.0
50
100
150
200
50
100
150
200
iteration
iteration
Figure 3: Behaviour of automatic differentiation for first-order methods on a quadratic function. (Left) Stability of the propagation of derivatives for the fixed step-size gradient descent. (Right) Instability of the propagation of Heavy-Bat initialized. Both methods are initialized at optimum.

---

through widely used methods as creward-bacwward Douglas- Douglas-Rachford or ADMM algorithms. Our framework allows however to consider many other abstract algorithmic recursions and provides thus theoretical ground for more general problems such as variational inequalities or saddle point problems as in [14, 9]. a matter for future work, we shall consider relaxing Assumption to study wider class of methods, e.g., when F is not strict contraction.
Acknowledgments
J. B. and E. P. acknowledge the financial support of the Al Interdisciplinary Institute ANITI funding under the grant agreement ANR- 19---0344,-0 Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant numbers 1A9550-11-1-7044
FA8655-22-1--0 1-722 and ANR MaSDOL 19-CEE2-0011-44 J. B. also acknowledges the support ANR Chess, grant ANR-17- EURE-0010, TSE-P and the Centre Lagrange. S. V. acknowledges the support ANR GraVa, grant ANR-18-CE540-0005.
References
[1] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp. Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large- scale machine learning on heterogeneous systems, 2015. Software available from tensorflow.org.
[2] Pierre Ablin, Gabriel Peyré, and Thomas Moreau. Super-efficiency of automatic differentiation for functions defined minimum. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 32 41. PMLR, 13-18 Jul 2020.
[3] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J. Zico Kolter. Differentiable convex optimization layers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. I'Alché-Buce E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[4] Charalambos D Aliprantis and Kim C Border. Infinite Dimensional Analysis: A Hitchhiker's Guide. Springer Science & Business Media, 2006.
[5] Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances in Neural Information Processing Systems, 32, 2019.
[6] Heinz H Bauschke, Patrick Combettes, et al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
[7] Quentin Bertrand, Quentin Klopfenstein, Mathieu Blondel, Samuel Vaiter, Alexandre Gram- fort, and Joseph Salmon. Implicit differentiation of lasso-type models for hyperparameter optimization. In International Conference on Machine Learning, pages 810-821. PMLR, 2020.
[8] Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Llinares- López, Fabian Pedregosa, and Jean-Philippe Vert. Efficient and modular implicit differentiation, 2021.
[9] Lea Bogensperger, Antonin Chambolle, and Thomas Pock. Convergence a Piggyback-style method for the differentiation of solutions of standard saddle-point problems. Technical report, 2022.
[10] Jérôme Bolte, Tam Le, Edouard Pauwels, and Antonio Silveti-Falls. Nonsmooth Implicit Differentiation for Machine Learning and Optimization. In Advances Neural Information Processing Systems, Online, 2021.
10

---

[11] Jerome Bolte and Edouard Pauwels. A mathematical model for automatic differentiation in machine learning. Conference on Neural Information Processing Systems, Vancouver, Canada, 2020.
[12] Jérôme Bolte and Edouard Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning. Mathematical Programming. 2020.
[13] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Londerrman-Milne and Qiao Zhang. JAX: composable transformations of Python+NummP programs, 2018.
[14] Antonin Chambolle and Thomas Pock. Learning consistent discretizations of the total variation.
SIAM Journal on Imaging Sciences, 14(2):77-811,, 2021.
[15] Bruce Christianson. Reverse accumulation and attractive fixed points. Optimization Methods and Software, 3(4):311-326, 1994.
[16] Frank H. Clarke. Optimization and nonsmooth analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. John Wiley & Sons, Inc., New York, 1983. A Wiley-Interscience Publication.
[17] Michel Coste. An introduction o-minimal geometry. Istituti editoriali poligrafici intermazion- ali Pisa, 2000.
[18] Michel Coste. introduction to semialgebraic geometry, 2000.
[19] Charles-Alban Deledalle, Samuel Vaiter, Jalal M. Fadili, and Gabriel Peyré. Stein Unbiased GrAdient estimator of the Risk (SUGAR) for multiple parameter selection. SIAM Journal on Imaging Sciences, 7(4):2448 2487, 2014.
[20] Bradley Efron, Trevor Hastie, lain Johnstone, Robert Tibshirani, et al. Least angle regression. Annals of statistics, 32(2):407-49, 2004.
[21] Laurent El Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, and Alicia Tsai. Implicit deep learning. SIAM Journal on Mahematics of Data Science, 3(3):930-958, 2021.
[22] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):432-441, 12 2007.
[23] Daniel Gabay. Applications of the method of multipliers to variational inequalities. In Studies in mathematics and its applications, volume 15, pages 299-331. Elsevier, 1983.
[24] Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy--bll method for convex optimization. 2015 European control conference (ECC), pages 310-315. IEEE, 2015.
[25] Jean Charles Gilbert. Automatic differentiation and iterative processes. Optimization Methods and Software, 1(1):13-21, 1992.
[26] Pontus Giselsson and Stephen Boyd. Linear convergence and metric selection for douglas- rachford splitting and admm. JEEÉ Transactions on Automatic Control, 62(2):532-544 2016.
[27] Andreas Griewank, Christian Bischof, George Corliss, Alan Carle, and Karen Williamson. Derivative convergence for iterative equation solvers. Optimization Methods and Software, 233-4):321-355 1993.
[28) Andreas Griewank and Christèle Faure. Piggyback differentiation and optimization. In Large- scale PDIE-constrained optimization, pages 148-164. Springer, 2003.
[29] Andreas Griewank and Andrea Walther. Evaluating derivatives: principles and techniques of algorithmic differentiation. SIAM, 2008.

---

[30] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Couraapaa,, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel Smith, Robert Kern. Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fer- nández del Río, Mark Wiehe, Pearu Peterson, Pierre Gtrard-Marchant Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585(7825):357-362, September 2020.
[31] D. Hunter. Matplotlib: A 2d graphics environment. Computing in Science & Engineering, 933)900-95, 2007.
[32] Samuel Hurault, Arthur Leclaire, and Nicolas Papadakis. Gradient step denoiser for convergent plug-and-play. International Conferencee on Learning Representations, 2021.
[33] Sham M Kakade and Jason D Lee. Provably correct automatic sub-differentiation for qual- ified programs. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[34] Wonyeol Lee, Hangyeol Yu, Xavier Rival, and Hongscok Yang. On correctness of automatic differentiation for non-differenniiall functions. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1719-6730 Curran Associates, Inc., 2020.
[35] Seppo Linnainmaa. The representation of the cumulative rounding error of algorithm Taylor expansion of the local rounding errors. Master's 's thesis, Univ. Helsinki, 1970.
[36] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1540-1552. PMLR, 26-28 Aug 2020.
[37] Julien Mairal and Bin Yu. Complexity analysis of the lasso regularization path. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1842, 2012.
[38] Swann Marx and Edouard Pauwels. Path differentiability of ode flows. arXiv preprint D.Xiv:2201.03819 2022.
[39] Sheheryar Mehmood and Peter Ochs. Automatic differentiation of some first-order methods in parametric optimization. In International Conference on Artificial Intelligence and Statistics, pages 1584-1594. PMLR, 2020.
[40] Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming. SIAM, 1994.
[41] Peter Ochs, René Ranftl, Thomas Brox, and Thomas Pock. Techniques for gradient-based bilevel optimization with non-smooth lower level problems. Journal of Mathematical Imaging and Vision, 56(2):175- 194, 2016.
[42] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, F. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8035. Curran Associates, Inc., 2019.
[43] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International conference on machine learning, pages 737-746. PMLR, 2016.
[44] Boris Polyak. Introduction to optimization. In Optimization Software, Publications Division. Citeseer, 1987.
[45] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in neural information processing systems, 32, 2019.
12

---

[46] R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science Business Media, 2009.
[47] Halsey Lawrence Royden and Patrick Fitzpatrick. Real analysis, volume 32. Macmillan New York, 1988.
[48] David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. Learning representations by back- propaaaopggg errors. Nature, 323(6088):53335555 -3633,,,,6,,66 October 1986.
[49] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):667-288 1996.
[50] Ryan Tibshirani. The lasso problem and uniqueness. Electronic Journal of statistics, 7:1456- 1490, 2013.
[51] Ryan J. Tibshirani. Adaptive piecewise polynomial estimation via trend filtering. The Annals of Statistics, 42(1):285~ - 323, 2014.
[52] J J Wainwright, John Lafferty, and Pradeep Ravikumar. High-dimensional graphical model selection using 'ell_ -reguularrie logistic regression. In B. Schölkopf, Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems, volume 19, MIT Press, 2006.
[53] R. E. Wengert. A simple automatic derivative evaluation program. Communications of the ACM, 7(8):463 464, August 1964.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Our submission follows the order mentionned in the abstract and introduction.
(b) Did you describe the limitations of your work? [Yes] The two main assumptions are discussed in the main text.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We believe that our work, being fully theoretical, does not bring negative societal impacts, especially points
of the ethics guidelines of NeurIPS 2022.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] Points to 5 are satisfied.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Our analysis requires small number of assumptions: assumption 1 on contraction and assumption on semialgebraic regularity.
(b) Did you include complete proofs of all theoretical results? [Yes] Most of the appendices are dedicated them.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] The (self-contained) jupyter notebook to generate the figures is submitted in supllemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [Yes] See appendix H.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] See appendix H. Every curves report the median over 100 repetitions, along with first and last deciles.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See appendix H.
4. If you using existing assets (c.g., code, data, models) or curating/releasnng assets...
13

---

(a) If your work uses existing assets, did you cite the creators? [Yes] See appendix I.
(b) Did you mention the license of the assets? [Yes] See appendix I.
(c) Did you include any assets either in the supplemental material URL? [N/A]
No new assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] No nonpublic data used.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] No personally identifiable information.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals. if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "q0kmzAL6YHu", "reviewer": "Reviewer_nZjc", "summary": "The authors investigate the differentiation of iterates $x_k(\\theta)\\in \\mathbb{R}^p$ of nonsmooth optimization algorithms with respect to algorithm parameters $\\theta \\in \\mathbb{R}^m$. This task is motivated by the need to differentiate through the argmin of objectives that give rise to nonsmooth algorithmic iterations $x_{k+1} = F(x_k(\\theta), \\theta)$. Differentiation with respect to algorithmic iterates is frequently used because the argmin itself might for example be incaccessible to explict differentiation or alternative approaches.\n\nAn important question is whether Jacobians with respect to algorithmic iterates converge to classical Jacobians at fixed points $\\bar x(\\theta)$. This has previously been answered for the case of smooth iterations and the authors consider the nonsmooth case in this paper. To that end, they first introduce conservative Jacobians that are set-valued and enable a recursive differentiation framework for nonsmooth iterations. Under assumptions, they show that the defined recursion converges to a nonempty and compact set of fixed points in $\\mathbb{R}^{p\\times m}$ that is a conservative Jacobian of $\\bar x(\\theta)$. The limit of conservative Jacobians of $x_k(\\theta)$ is therefore equal to a conservative Jacobian at $\\bar x(\\theta)$. In other words: Limit formation and differentiation can be exchanged here.\n\nAfterwards, the authors also provide a linear convergence result for a specific class of functions (where the iteration is a Lipschitz gradient selection function), they show that their framework is applicable to several splitting algorithms including numerical examples, and they finally provide a concrete counterexample using the heavy-ball algorithm, where the sequence of derivatives diverges although the iterates themselves are linearly convergent.", "questions": "Line 77: Should it be $x\\in\\mathbb{R}^p$ rather than $x\\in\\mathbb{R}^n$?\n\nLine 89: Should it be $\\mathbb{R}^{m\\times p}$ rather than $\\mathbb{R}^{p\\times m}$?\n\nLine 110: How do you initialize $J_{x_0}(\\theta)$?\n\nLine 131: Should it be $X \\in \\mathbb{R}^{p\\times m}$ rather than $\\mathbb{R}^{p\\times n}$?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think that this is an interesting and well-written paper. To the best of my knowledge, the presented results for nonsmooth algorithms are novel and also relevant (from a theoretical point of view but also in view of a growing number of use-cases of algorithm unrolling). Moreover, the authors provide rigorous proofs of their results in the appendix. One small weak point is, according to my personal impression, that the paper is partially not self-contained. For example the inputs of algorithmic differentiation in Section 3.3 could at least be briefly explained. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ow-Phwz5Gk", "reviewer": "Reviewer_8Cko", "summary": "In this paper, the authors consider a possibly non-smooth but structured iterative algorithm which additionally depends on some parameter $\\theta$, also in a possibly non-smooth but structured manner; the structure being defined in Assumption 1. They used the tools developed in [1, 2] to differentiate this parametric fixed-point iteration through Chain Rule. This defines a (so-called) piggyback recursion, where the sequence being generated is set-valued. They show that the conservative jacobian of the fixed-point $\\bar x (\\theta)$ of the algorithm satisfies a set-valued, affine fixed-point equation. They show the convergence of the resulting sequence to the conservative jacobian of the fixed-point of the algorithm for all $\\theta$ with respect to the gap metric defined in Section 3.1. They also link the implicit differentiation of the fixed-point $\\bar x (\\theta)$ by using the conservative calculus in [3] to the limit of the set-valued sequence. They show linear convergence of this sequence under additional Lipschitz-gradient-selection assumption of the algorithm mapping $F$. Finally, the consider instances of the iteartive algorithm to solve a composite optimization problem, namely, Forward-Backward Splitting, Douglas Rachford and ADMM. They put another assumption on the optimization problem (Assumption 2) and show that Assumption 1 is satisfied by the above listed algorithms. They also show the failure of convergence of the derivative sequence for inertial methods.\n\n[1] Jerome Bolte and Edouard Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning. Mathematical Programming, 2020.\n\n[2] Jerome Bolte and Edouard Pauwels. A mathematical model for automatic differentiation in machine learning. In Conference on Neural Information Processing Systems, Vancouver, Canada, 2020.\n\n[3] Jerome Bolte, Tam Le, Edouard Pauwels, and Antonio Silveti-Falls. Nonsmooth Implicit Differentiation for Machine Learning and Optimization. In Advances in Neural Information Processing Systems, Online, 2021.", "questions": "- What do the authors think of the difference in using Automatic and Implicit Differentiation for non-smooth fixed-point iterations and equations respectively in terms of\n    - the computational efficiency of the algorithms in their setting, and\n    - the correct evaluation of the derivative of the fixed-point (or something \"reasonable\" when that does not exist) in a more general setting.\n- If the answer to the previous question is hat Implicit Differentiation behaves atleast as well as Automatic Differentiation then why even use Automatic Differentiation since Implicit Differentiation is memory efficient.\n\nMinor Typos and other Confusions\n- Page 3, Line 94: \"...classes convex functions...\" -> \"...classes of convex functions...\".\n- Page 3, Line 110: $J_{x_1}$ was not defined.\n- Page 4, Line 132, Equation (6): \"$[A, B] \\in J$\" -> \"$[A, B] \\in \\mathcal J$\".\n- Page 4, Line 145: \"...Jacobian of the fixed-point of $F_\\theta$\" is misleading -> \"...Jacobian at the fixed-point of $F_\\theta$\" is more suitable perhaps.\n- Page 5, Line 153: \"...this a limit...\" -> \"...this is a limit...\".\n- Page 7, Line 220: \"...Proposition~1, as well Corrollar~3...\" -> Sentence does not look correct gramatically.", "limitations": "See Weaknesses. Other than that, in my opinion their work is sound.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts\n- The paper provides a fairly general result for non-smooth iterative algorithms. This is useful for instance in a bilevel framework since their result along with [1, 2] provides theoretical guarantees for correctly evaluating the gradient of the upper level problem by differentiating through the argmin of the lower problem by using Automatic Differentiation.\n\nWeaknesses\n- A comment on the difference between the convergence speed of Piggyback iterations for the mentioned optimization algorithms is missing.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9-RY--2VZKU", "reviewer": "Reviewer_F1Pw", "summary": "This paper introduced a theory for the piggyback iteration of nonsmooth functions. While existing asymptotic analysis for the piggyback AD procedure only works for twice continuously differentiable functions, with the conservative derivative framework, this paper provided the asymptotic convergence results for nonsmooth path-differentiable functions under a nonexpansive condition (in Assumption 1). They formally defined the notion of general Clarke Jacobian for piggyback and its fixed point, with which the convergence of an infinite piggyback iteration is proved in Corollary 1. For mapping with a Lipschitz gradient selection, they proved a non-asymptotic convergence rate. They also showed applications by applying the piggyback iterations to various methods for convex problems.", "questions": "See above.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written with a clear introduction to various new and existing notions in the conservative derivative framework. The problem studies are timely and important. The theoretical results are nontrivial and demonstrate wide extensibility, which also suggests important applications. The failure example discussed in Section 5 is interesting. It shows that even functions with a Lipschitz gradient cannot ensure the convergence of the piggyback procedure. For assumption 1, how does this assumption compare with these in the smooth cases? For example, in [37], they assume the Hessian at optimum is positive definite and they use the gradient descent method. So it would be better to discuss the strength of assumption 1 in various situations where we assume the function is C^2 and fixed the algorithm. Is Assumption 1 for the nonsmooth procedure stronger or weaker than that in existing papers? Some minor points:\n\nL131: \"X\\in R^{p \\times n}\" -> \"X\\in R^{p \\times m}\"\nL153: \"this a\" -> \"this is a\"", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0bQlpiavAJK", "reviewer": "Reviewer_Sht3", "summary": "In this paper, the authors present a theoretical framework based on nonsmooth analysis concepts to analyze the asymptotic behavior of « piggyback » derivatives for nonsmooth iterations, i.e. how we can define the automatic differentiation of the iterates of unrolled iterations of an algorithm with nondifferential updates. Cases of practical interest include most popular proximal algorithms : proximal gradient descent, Douglas Rachford splitting and the ADMM. The authors show that a notion of set-valued Jacobians can be defined for these algorithms, and that they coincide with classical Jacobians almost everywhere. What is more, they show that, under suitable assumptions, the fixed point admits a derivative in this sence, and the derivatives of the iterates converge towards the derivatives of the fixed point. They prove, again under suitable assumptions, that there is a linear convergence of the derivatives towards those of the fixed point. They also show that this does not apply to other optimization methods with momentum, the given example being the heavy ball methods for which Jacobian iterates can become unstable for an objective that is not regular enough.", "questions": "- Is it possible to find a case of practical interest where the heavy ball algorithm (or other momentum algorithms) will fail ? I feel like, from the example given, than in most cases the cost functions are regular enough for this not to happen, but I would appreciate to be proven wrong.\n\n- How hard would the analysis get in the case where there are multiple fixed points of F ? E.g. when minimizing a nonconvex function ? I understand the analysis would get much more complex, and is probably out of the scope of the paper, but this could have been discussed a bit.", "limitations": "The authors state clearly the assumptions they need for their framework and discuss their relevance and connections to practical cases. Some important cases are not covered by the analysis, such as multiple fixed points (useful e.g. for nonconvex bilevel optimization), but this remark is quite minor since results in this case are scarce (to my knowledge) in the literature, and the analysis probably gets much harder. The connection to implicit differentiation is drawn and is interesting but unfortunately not equivalent to the piggyback differentation presented here.\n", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths :\n\n- The proposed framework gives a precise meaning to procedures that are now frequently used in practice of unrolling (potentially nonsmooth) iterative algorithms programmed in modern autodiff packages (Tensorflow, Pytorch, JAX…) and were shown to work and give good results when optimizing some of their parameters, but without a firm theoretical explanation of why it worked and the derivatives were well defined. In this sense, the work is a valuable theoretical contribution\n\n- The linear convergene of piggyback derivatives is proven for a number of classical algorithms of interest, and is experimentally confirmed through simple examples. A counterexample is given, showing that one must be careful with momentum methods (though I assume that in most practical cases the functions will be regular enough for this not to happen).\n\n\nWeaknesses :\n\n- I believe the authors should have provided more references to works actually using piggyback derivatives of nonsmooth algorithms in different contexts, to give precide illustrations beyond the toy examples used in the experiments. This would strengthen the impact of the paper and point practical cases for which we now have guarantees.\n\n- The presentation is clear enough to understand the general ideas, but the paper is not exactly self-sufficient. In particular, I believe one must already be very familiar with concepts developed in [12] to understand the tools that must be leveraged. Maybe it would have been nice to include a crash-course exposition to these concepts in the appendices.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept