Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
Authors: Sheheryar Mehmood
Peter Ochs
Venue: ICML 2025 poster (2025)
Keywords: Bilevel Optimization
Algorithm Unrolling
Automatic Differentiation
Machine Learning
Primary area: optimization

Abstract: Numerous optimization algorithms have a time-varying update rule thanks to, for instance, a changing step size, momentum parameter or, Hessian approximation. Often, such algorithms are used as solvers for the lower-level problem in bilevel optimization, and are unrolled when computing the gradient of the upper-level objective. In this paper, we apply unrolled or automatic differentiation to a time-varying iterative process and provide convergence (rate) guarantees for the resulting derivative iterates. We then adapt these convergence results and apply them to proximal gradient descent with variable step size and FISTA when solving partly-smooth problems. We test the convergence (rates) of these algorithms numerically through several experiments. Our theoretical and numerical results show that the convergence rate of the algorithm is reflected in its derivative iterates.

Automatic Differentiation of Optimization Algorithms with Time- Varying Updates
Sheheryar Mehmood
Peter Ochs
Abstract
where we define A(x, u) == a Fa, u) for solving
parametric optimization problem of the form
Numerous optimization algorithms have time- varying update rule thanks to, for instance, a changing step size, momentum parameter or, Hes- sian approximation. Often, such algorithms are used as solvers for the lower-level problem in bilevel optimization, and are unrolled when com- puting the gradient of the upper-level objective. In this paper, we apply unrolled automatic differ- entiation time-narying iterative process and provide convergence (rate) guarantees for the re- sulting derivative iterates. We then adapt these convergence results and apply them to proximal gradient descent with variable step size and FISTA when solving partly-smooth problems. We test the convergence (rates) of these algorithms numeri- cally through several experiments. Our theoretical and numerical results show that the convergence rate of the algorithm is reflected in its derivative iterates.
min F(x, u) #E
(P)
with a smooth objective F: X x 4 + R. In this case (Re)
reduces to the optimality condition V F(x u) = 0.
There wide range of practical applications in which, problems of type (R,) or (P) appear as a constraint within minimization problem with respect the parameter u. Usually, for some smooth l: X x U - R, this can be compactly stated as
min ((vb(u), u) uEM
(1)
where, given any U, (u) is a solution of (R.)) (P). This kind of optimization, formally known as bilevel opti- mization (Dempe et al., 2015; Dempe & Zemkoho, 2020) has emerged as crucial tool in machine learning, playing foundational role in various applications such as hyperpa- rameter optimization (Bengio, 2000; Domke, 2012; Maclau- rin al., 2015), implicit neural networks (Amos & Kolter, 2017; Agrawal et al., 2019; Bai et al., 2019; 2020; Winston & Kolter, 2020), meta-learning (Hospedales al., 2021), and neural architecture search (Liu et al., 2019).
1. Introduction
For some parameter U, we consider the following parametric iterative process
Solving (1) through gradient- gradient-based methods requires com- puting the gradient of the upper objective ((b((), u) with respect to u which, in turn, requires computing the deriva- tive of the solution mapping u + vku)). that is, (v)( by using the chain rule. When & and F (or A) satisfy cer- tain smoothness and regularity assumptions, this can be achieved by two different methods. (i) One is known as Implicit Differentiation (ID) which leverages the classical Implicit Function Theorem or IFT (Dontchev & Rockafellar, 2009, Theorem IB.1) applied to (R.) to estimate
(k+1)) (1) ((x) u)
(R)
for 2 O, where (0) E X' the initial iterate and A: X'Ul + X is the update mapping. The iterates az (u) generated by (R) depend on due to the dependence of A on u. The goal of performing the iterations (R) is mainly to solve the non-linear fixed-point equation
x A(x, ut,
(R.))
with respect to for each parameter u. A simple exam- ple is gradient descent with appropriate step size a > 0
Dib(u) = (T - DaA(e u)) DuA((x, = = - F, F(r,
DDpaatmeent of Mathematics Computer Science, Saarland University, Saarbrücken, Germany. Correspondence to: Shcheryar Mehmood <mchmood math. wnw..uuni-sdd......
where æ = (u) (see Theorem A.10 for more details). The key assumption for IFT is the strict bound on the spec- tral radius p (b), u)) < 1, which we call the con- traction property since a sufficient condition for A
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
to be 1-Lipschitz or contractive. A direct consequence is the linear convergence of a: (x()) to rb(u) (Polyak, 1987, Section 2.1.2, Theorem 1). The output of ID (2) depends on accurately solving (R.) - possibly through (R) - and solving the linear system efficiently. (ii) The other technique is known as Unrolled, Iterative or Automatic Differentia- tion (AD) or simply Unrolling where Du)(u) is estimated by applying automatic differentiation (Wengert, 1964; Lin- nainmaa, 1970; Griewank & Walther, 2008) to the output (u) of (R) after K E N iterations. The update rule for forward mode AD applied to (KK)) is given by
ally, the proof of convergence of (ay()(u)) (u) relies on the contraction property in each of the above works with an exception of Pauwels & Vaiter (2023). The linear rate of convergence requires (local) Lipschitz continuity of D.A. A slightly different line of study on the problematic be- haviour of automatic differentiation in the earlier iterations was carried out by Scieur et al. (2022).
1.2. Iteration-Dependenn Updates
Most iterative algorithms for solving (P) which include gra- dient descent with line search, Nesterov's 's accelerated gradi- ent (Nesterov, 1983), and Quasi-Newton methods (Davidon, 1959; Fletcher & Powell, 1963; Broyden, 1970; Fletcher, 1970, etc.) cannot be modelled by (R). This happens be- cause the update mapping is changing at every iteration; A in (R) is replaced by Ax: X x ul - X' giving us the update
(z( (u) == -eA((x!))) (1) (w), (x)
(DR)
+ +DuA(x())u))).
for 0 S k: < K where we may assume (o)(0) = 0. The effective use of AD relies on the guarantee that (zx(0 (u) accurately estimates Dr(()) for a preferably small K. More formally, we require the convergence of (x) to (u)( as K - 0o, with a convergence rate comparable to that of oz (u).
xx(+11 (u) As (z) (u)), u).
(Rx)
For example, for gradient descent with line search, As u) == x as Vx, u). When As is -smothh for all k E N. the modified update rule for performing forward mode AD on (Rx) reads:
The reverse mode AD or Backpropagation (Rumelhart et al., 1986; Baydin et al., 2018) has different update rule, how- ever, the result computed is the same in the end (Griewank & Walther, 2008). Due to the nature of the iterations (DR), we will use (KK) and (k) interchangeably. The reverse mode AD has a memory overhead since it requires storing the iterates (z=*)) Josk<K Even though this is in contrast with ID which only depends on (K))), AD is still popular choice for estimating (v(u). A crucial advantage of AD is that it provides a nice blackbox implementation thanks to the powerful autograd libraries included in PyTorch (Paszke et al., 2019), TensorFlow (Abadi et al., 2016), and JAX (Bradbury et al., 2018) whereas ID requires either a custom implementation (Bolte al., 2023, see Remark 2) or using special libraries (Blondel et al., 2022; Ren et al., 2023, etc.).
Dx (x) = (x ux) (z)
(DRx)
+ Du (u).u).
Beck (1994) studied this problem for the Cm-smooth se- quence of functions As with uniformly bounded derivatives and DAr converging to DA pointwise. They showed that for such a sequence, when (z:()(u)) (u))ken is generated by (Rş) to solve the system (R.). then (Dx (u)) kkEN gener- ated by (DR;) converges (ub(u) defined in (2). However, their results cannot account for the linear convergence of (z(h) in their given setting (see Section A.3). More- over, their setting excludes the more general cases where As does not converge, for instance, gradient descent with line search.
1.1. Convergence of Automatic Differentiation
Griewank et al. (1993) studied the special setting for solv- ing the non-linear system G(æ, u.) O with respect to æ through preconditioned Picard iterations, that is, As (æ u) := x - Pa. (u)) u). The parameter-dependent preconditioner Ps: u + x)) is changing at every it- eration and may not converge. They demonstrated linear convergence of Dz (k) (w) for -smoohh G: X xul - X' with bounded maps Dt. and (ar, u) + G( u) and Lipschitz continuous map DG. The map Ps is assumed to be C' -mooth with bounded (potentially 0) derivative for every & E N.
The convergence of the derivative sequence (*) for AD of (R) were studied classically for linear (Fischer, 1991) and general iteration maps (Gilbert, 1992). More recently, the convergence amalysis was provided for gradient descent (Lorraine et al., 2020; Mehmood & Ochs, 2020), the Heavy- ball method (Mehmood & Ochs, 2020), proximal gradient descent for lasso-like problems (Bertrand et al., 2022), the Sinkhorn- Sinkhorn-Knopp algorithm (Pauwels & Vaiter, 2023), the super-linearly convergent algorithms (Bolte et al., 2023), and stochastic gradient descent (lutzeler et al., 2024). The convergence results were extended to non-smooth iterative processes by Bolte et al. (2022) using conservative calculus (Bolte& & Pauwels, 2020; 2021). Ablin et al. (2020) theoreti- cally established the better convergence rate for computing the gradient of the value function through AD and ID. Usu-
Riis (2020); Mehmood & Ochs (2022) considered apply- ing AD when Ar denotes the update mapping of FISTA (Beck & Teboulle, 2009) (which we will call Accelerated Proximal Gradient or APG) applied to (P) for non-smooth
2

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
F= f + 9 with step size ag and extrapolation parameter 3e- They adapted the results of Beck (1994) and demon- strated the convergence of (x(()(() to DT((u) when f is C²-smooth with Lipschitz continuous gradient, g is partly smooth (Lewis, 2002), the sequences (oxx keN and (3k) keN converge and F additionally satisfies restricted injectivity and non-degeneracy conditions (see, for example, Lewis, 2002). Deb(u) (u) computed by applying the Implicit Func- tion Theorem for partly smooth functions (Lewis, 2002, Theorem 5.7). Partly smooth functions are class of spe- cial non-smooth functions which exhibit smoothness when restricted to a oow-dimeniional manifold M and model var- ious practical regularization functions (Vaiter et al., 2017). The non-smooth or sharp behaviour occurs only when we move orthogonal to M. The combination of restricted injec- tivity and non-degeneracy assumptions induces the contrac- tion property in proximal gradient descent or PGD (Liang et al., 2014) and APG (Liang et al., 2017) near the solution. The results of Rits (2020); Mehmood & Ochs (2022) do not explain the linear convergence of AD of APG or even the convergence of AD of PGD with non- converiggg variable step size.
on the framework of Beck (1994), our results provide convergence and convergence rafe guarantees for PGDD with variable step size and convergence rate guaran- tees for APG, We show that the rate of convergence of (x(*) (u) is reflected in that of (xx))(()) for both algorithms.
1.4. Notation
In this paper, X' and U are Euclidean spaces and == [o], With a slight abuse of notation, || - denotes any norm each of the spaces X' and I including the one induced by the inner product (:.-). The space of linear operators from /I to X is denoted by C((,,x)), Any operator norm on the spaces [(U, 22) and (()) is also denoted by
|| ||- We say that w (4) = -(2 iff || = o[I []
and (A) = (x)) iff (|wx( = O (()0 I).
The affine hull of a set C C. X' denote by aff C whereas
par C = aff C aff C is linear subspace parallel to C. The relative interior of a convex set C (Rockafellar, 1970, p. 44) is denoted by ri C. and is always non-empty whenever C' is non-empty (Rockafellar, 1970, Theorem 6.2). For any a > O and proper and lower comi-continuous g: X x U + R where g(, u) is convex for all u E U C U, we define Pag: : X U - X by (.)(;.) = proxagt- that is,
Jutzeler et al. (2024) tackle the problem of applying AD on Stochastic Gradient Descent or SGD and ensure conver- gence of the derivative sequence by considering the deriva- tive recursion as a so-called "inexact SGD" applied to solve a stochastic quadratic problem whose solution is the de- sired derivative of the solution mapping. Although, our deterministic and their stochastic settings both work with time-varying algorithms, we can not simply deduce one from the other in trivial manner.
1 P Pay(w, = argmin ag (x, u) + 221 | w|l (3)
#Ex
In this paper we use the notion of regular subdiffcrential (Rockafellar & Wets, 1998, Definition 8.3) of g. When U is open and for any E X, g( is differentiable u E U. we obtain 0g xx u) = 0zg(æ, u) x (Vug(v, u)} (Mehmood & Ochs, 2022, Lemma 1).
1.3. Contributions
In this paper, we aim resolve the theoretical gaps pre- sented in Section 1.2 and therefore reinforce the usefulness of AD. In particular, the main contributions of this paper are the following:
We use standard notions of Riemannian Geometry, which we define in Section A.4 in the appendix. We refer a Ck_ smooth m-dimensional submanifold by simply C*-smooth manifold. Furthermore. the natural embedding of M in X' allows us define a Riemannian metric on M, mak- ing it Riemannian manifold. For any E M, the map I: M + L(X', X²) outputs the orthogonal projection onto the tangent space of M at x, that is. II(x)) = projr.M while IT- : : - L(X,, X¹) gives us the orthogonal projec- tion onto the normal space of M at æ. that is, II-(w) = projn.,. For a function g: X U + R with values g( u) which is Cm-smooth when restricted to M x U where M C X is C²-smooth manifold and U C U is an open set, we respectively denote by VMn and V3ng. the Riemannian gradient and Hessian of relative to M with respect to æ. We follow Mehmood & Ochs (2022, Re- mark 22(iv)) to express the Riemannian gradient V M.xug and Hessian MxxU of g.
(i) We strengthen the results of Beck (1994) by providing a convergence rate analysis for (k) (u) generated by (DR₂) after equipping their setting with an addi- tional assumption that is satisfied by most optimization algorithms (see Assumption 2ii and Remark 1..
(ii) We establish (linear) convergence of (*)( (u) beyond the setting in (i) without the pointwise convergence condition of As to A (see Assumption 2.2 and 2.3).
(ii) We demonstrate the convergence of (+) (u) for Proximal Gradient Descent (Lions& & Mercier, 1979) or PGD with variable step size and Accelerated Proximal Gradient (Beck& & Teboulle, 2009) or APG by adapting the results for (ii) and (i) respectively. In contrast to Riis (2020) and Mehmood & Ochs (2022), which rely
3

---

Automatic Differentiation of Optimization Algorithms with Time-Varylin Updates
2. Differentiation of Iteration-Dependent Algorithms
x² = A(w"; u²), DARx(at u²) + DA(x" u²) and dDzA(a" (a)))=")))))))))))))))))) < 1.
In this section, we lay down the assumptions on the sequence and provide convergence and convergence rate guarantees for the derivative iterations defined in (DRR). In particular we establish (i) convergence rates when A has a pointwise limit A, and (ii) convergence and convergence rates when A& does not have a pointwise limit. For better comparison and understanding, this section is adapted to follow the same pattern as Section A.3, which summarizes the results by Beck (1994).
2.2. Implicit Differentiation
Combining Assumptions 2.1(())(iii) allows us invoke the Implicit Function Theorem x* (x",, uu) for every k large enough and obtain a Cm-smooth fixed-point map the on a neighbourhood Us E NNu.. In particular, we have the following result.
Lemma 2.2. Let (a", uu, x.) E x x x(X,)), V E Ni uu)) (AK)KEN, and |1 be such that Assump- tion 2.1 ((i)(itt)) is satisfied. Then there exists K E N such that Vk: 2 K. there exists UR E NNw and a Ca -mmooth th: Us - X such that Yu E UR. (h((u) Ac((buuu) u).
2.1. Problem Setting
For given u", assume that x² is the solution that we are trying to estimate through (Rt). Because the pointwise limit A of AA may not exist, we assume that x' is a fixed point of (x u²) for every & E N. This seemingly restric- tive assumption is satisfied by the optimization algorithms highlighted in Section 1.2. The application of the Implicit Function Theorem on this sequence of fixed-point equations requires the contraction property, that is, the strict bound some operator norm |DD (x=", u²") < 1 eventually for all & E N. Furthermore, we assume that the sequence of affine maps (X + Az (x", , u²' x share a common fixed-point X. E C(X, - the reason will become clear shortly. Finally, to show the convergence of the derivative sequence (bo(k((u)) (u=)))E), we assume that the sequence (xx() (2)))NN converges to x". More for- mally, given (zx x=, uu, X.) E X' x X x 21 x C(X, X), V E N(z-,u)) (At) and norm || on X(X induced by some vector norm, we assume that the following conditions hold.
and
Dvh((u)= ( " (v)())))
that Diha(u") X..
Proof. The proof is in Section B.1 in the appendix.
Remark 2.3. If we replace Assumptions (ii and 2.
by a slightly stronger assumption, that is, "there exists U e Nu- such that for any (æz, u) E X x U, x = As u) for some E N implies æ Ax u) for every k N. and lim sup |a (ax u)ll < 1", we obtain shared C' smooth fixed -oint map th: U - X, such that, U* U and the = 1/ for all & E N.
u²) kEEN
2.3. Automatic Differentiation
In Lemma 2.2, we just showed that under Assumption 2.1, the common fixed-point X. of the mappings X + DeAA(x"", u² u')x + DuA u²) for k E N represents the derivative of the solution at u = uz. We now show that the derivative sequence generated by (DRR) for u = u² converges to X.. Instead of assuming a pointwise limit for DAR, we assert that DA (x)))))) tends to O.
Assumption 2.1.
Aulv is Cmmsmooth for all k;
(ii) x= = Ax u²) and X, = DuAA( u²) + D Du ) for all k,
(iii) lim s (a.A( uz)l < 1, and
(u*), ),u") DAu u*)
(iv) xf (*))) (u*) generated by (Rş) has limit x" such that (zo()) (u"), ), u²) E V for all k.
Assumption 2.2. The sequence (z))(z( u²) DAx (a=", u²)) kkENo converges to O. Remark 2.4. (i) In Assumption A.2 of Beck (1994).
Remark 2.1. (i) Unlike Assumption A.1 from Beck (1994), where the existence of A gives us both the fixed-point and its derivative at u" (see Aiii) our Assumption 2.1 does not require the existence of such limit which allows us to work directly with the family (Ax)een, each of which provides the solution and its derivative at u* (see 2. (ii).. Moreover, the spectral radius condition is imposed on the lim sup of the spec- tral radii of derivative of As (see 2. (iii) rather than on the derivative of A (see (iii).
where A exists, the sequence (DAe(z(()(u u²)
DA(x", u²) k"))N, is assumed to converge to 0. Rewriting
(xx (u"), (u"), u²) DA(x", u²) + DA*x u²) ) -DA(x", uu)
= (D ())))")) - DAu u²) (5)
(ii) A special case of Assumption 2. 2.i arises when for some -m-ooh mapping A: :: V >> X,, we have
suggests that this convergence follows, for instance, when our Assumption 2.2 holds and D.Ag converges
4

---

Automatic Differentiation of Optimization Algorithms with Time-Varyine Updates
pointwise to DA (x*, u²). We demonstrate this difference for Gradient Descent with variable step size in Example A.2.
where p lim lim sup pl DeAat u²)), and qu < the convergence rate of (xx(k) ())) (u"
(U))))E ))EENo
Proof. The proof is in Section B.3 in the appendix.
(ii) Combining Assumption 2.2 with the special case of Remark 2.1, we obtain the setting of Assumption A.2 (see Remark 2.4()))
Remark 2.8. In (7), &i depends on the derivative error
Dz (u" X while &g depends on the derivative enrors (x.(K) (u" - - D.Ax (x:(k) (u"), u²) DAx (a*, u"), and the derivative of the solution X.. All of these terms are computed at l: = K and therefore, are fixed. The explicit expressions can be found in the proof.
(iii> A sufficient condition for Assumption 2.2 is equiconti- nuity (see Section A. 1 for definition and an example) of (At) (AN)) at uu").
We are now ready to establish the convergence of the derivative sequence (Dz( (Dx)")(""))eee (u")) to X. when Assump- tions 2.1 and 2.2 hold.
Owing to Corollary A.7 and our discussion in Remark 1. the following result shows that the work of Beck (1994) is re- produced and strengthened with a convergence rate guaran- tee under the additional requirement of Assumption 2ii..
Theorem 2.5. Let (x("),x'' ,²,"") E X X x U, V E Niwe,,'' ,."), and (As)kEN, be such that Assumptions 2.1 and 2.2 are satisfied. Then the sequence (Dx(*) NeNN generated by (DRR)) converges to X. which is equal to DuAulæ", uu' for all k E N (see
also hold when, in their respective hypotheses, Assump- Corollary 2.9. The conclusions of Theorems 2.5 and 2.7
tion 2.i(i is replaced by "there exists C*-smooth A: V X, such that DAx(x=", u²) converges to DA(#", u²) and p(DrnAAa::" "x="""")))) <.".
Da-uAa ,u")) ,")""")))
Assumption 2ii().
Remark 2.10. The conclusions of Theorems 2.5 and 2.7 and Corollary 2.9 do not require the neighbourhood V of (x uu" ) to be a connected set as long as Assump- tions 2.2 and 2.3 are respectively satisfied along with As- sumption 2iv).
Proof. The proof is in Section B.2 in the appendix.
The derivative iterates (x( (u*) additionally converge with a linear rate when the sequences (u²)()) and (x. (u") u²) - DAx (a=,, ==") converge linearly.
Assumption 2.3. The sequence (z²()( keNN converges linearly to xx and
3. Differentiation of Proximal Gradient-type Methods
DAA (1) (u") (,)),"))) - uu) -x (8()) x²)
We now turn our attention to unrolling PGD with variable step size and APG when solving
(6)
Remark 2.6. (i) Assumptions A.3 (from the appendix) and 2.3 (ours) both require the corresponding se- quences in Assumptions A.2 and 2.2, respectively, to converge linearly. From (5), we see that As- sumption A.3 holds when Assumption 2.3 holds and (x* ( + DAA(x", =²) converges linearly (see also Example A.4). Since the latter condition is not practical in general, Assumption A.3 does not appear in Beck (1994) and is given here only for completeness.
min xEX'
u), F F=
(8)
and aim at providing convergence (rate) guarantees for the corresponding derivative sequences. The idea is to con- sider the class of partly smooth functions (Lewis, 2002) which models a wide range of non-smooth regularizers and constraints appearing in practice (Vaiter et al., 2017). Fur- thermore, this setting (see Assumption 3.1) under some ad- ditional assumptions (see Assumptions 3.2 and 3.3) yields more general IFT (see Theorem 3.1) for differentiating the solution mapping of (8). This in turn allows us to differen- tiate the update mappings of PGD (see Theorem 3.4) and APG (see Theorem 3.10), since they are also the solution mappings of partly smooth functions (see Equations 3, 10 and 13).
(ii) A sufficient condition for Assumption 2.3 is the Lip- schitz continuity of (DAR)REN, in æ uniformly in u and i (see Section A. for definition and an example).
Theorem 2.7. Let (x) x., ,,) E X x X x U, V e Ni ,.)), and (Ak)kEN, be such that Assumptions 2.1 and 2.3 are satisfied. Then the sequence (R) (M=))ke gen- erated by (DRx) converges linearly to X.. In particular, for all 5 E (0, 1 - p), there exist En, Ez. and K E N. such that for all k 2 K, we have
Examples of partly smooth functions include norms defined on vector space including é,, f2, and fox norms, as well as their combinations. These norms are commonly used as regularizers in machine learning: e and Eoo promote spar- sity and aati-spprsity, respectively, while the combined f2,1 norm induces group sparsity. Analogous norms defined on
D! (K)(( (u") - X.1l S -))
+ Ekk - K) max(p + j.gg))/KK
5

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
matrix space which include nuclear norm, Frobenius norm, and spectral norm and their combinations are also partly
3.2. Implicit Function Theorem
The following theorem is thanks to Lewis (2002) which furnishes C' "smooth solution map for (8) near u². The expression for the derivative can be found in Vaiter et al. (2017); Mehmood & Ochs (2022).
smooth and promote similar forms of streutred-sparsity for
matrices. The formal definition of partial smoothness is provided in Section A.5 in the appendix.
3.1. Problem Setting
Theorem 3.1 (Differentiation of Solution Map). Let f and g satisfy Assumption 3.1 and (x" ,u)) E M x Q2 be such that Assumptions 3.2(i) and 3.3 are satisfied. Then there exist an open neighbourhood U C Q of u² and a continuously difserentiable mapping sh: U + M such that for all u E U,
We first define our setting in more precise manner. Let M be a C²-smooth manifold and Ω C U be an open set, we need f and g to satisfy the following assumption.
Assumption 3.1 (Convex Partly Smooth Objective). f: X x u + R is C² g: X' x U - R is partly smooth relative to M x Ω and for every u E Ω f(: u) and g(-, u) are convex, f(; u) has an L-Lipschitz continuous gradient, and g(: u) has a simple proximal mapping.
(i) (u() is the unique minimizer of F(;,u))x
(ū) (ND) and (RPD-i) are satisfied at (sb(u), u), and
(iii) the derivative of v is given by
When Assumption 3.1 is satisfied, use Mehmood & Ochs (2022, Remark 22(iv)) to denote the Riemannian gradient and Hessian of F. Let x² E M be solution of (8) at u E Ω. When g 0, IFT requires V2/ =²) > 0 which is also a sufficient condition for the linear con- vergence of gradient descent and the Heavy-ball method (Polyak, 1987). When g is partly smooth, IFT requires posi- tive definiteness of V F(x=" u²) (Lewis, 2002) while the linear convergence of PGD and APG is established by the positive definiteness of [Tx=") V2 fx=" u" (=)") (Liang et al., 2014; 2017).
Db(()) --V FVMFFbbuu u) DuV M u)
where (()F(((u), u)t denotes the pseudoimersse of F(b(u))) u).
3.3. The Extrapolated Proximal Gradient Algorithm
Although Theorem 3.1 is not practical when computing the derivative of the solution map, allows us to differentiate the update mappings of PGD and APG as we will see shortly. Algorithm provides the update procedure for proximal gradient with extrapolation where P Tg is defined in (3). This algorithm reduces to (i) PGD when 3g = 0 for all k E N, and (ii) APG when the sequence 33 ensures acceleration in PGD (Beck & Teboulle, 2009; Chambolle & Dossal, 2015).
Assumption 3.2 (Restricted Positive Definiteness). Let (x", u²) M x Ω be given point.
(i) The Hessian VM u²) is positive definite on T, that is,
V F(" ,") > 0.
(RPD-i)
Algorithm 1 Proximal Gradient with Extrapolation
Initialization: (0) x E X, U. 0 <
ā < 2/L.
(ii Moreover, V u²) is positive definite on Ta-M, that
Parameter: (aK)NEN E [a, and (Ba) [0, 1].
[(x')Vaf(a" u') mg.M > 0. (RPD-ii)
Update k 2 0:
y (k) = (1 + 31 )x: (k) Bexr
Finally, for partly smooth problems, IFT and linear con- vergence of PGD and APG also require a non-degeneracy assumption to hold which ensures that the solution stays in M for any near u."
(k) y (k) a4 (g) (k),
(APG)
x (k+1) = P Pasy(u (w (2), u).
Assumption 3.3 -oon-degeneracy). The non-degeneracy condition satisfied at (x",u") E M x Ω that is,
3.4. Proximal Gradient Descent
E (i0,F((",,u")
(ND)
We first extend our results from Section and provide con- vergence rate guarantees for AD of PGD. For a given step size a > O, we write the update mapping for PGD in more
In (ND), denotes the relative interior of a convex set.
6

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
compact manner through the map Aa X + X' defined by
3.4.1. IMPLICIT DIFFERENTIATION
Under Assumptions 3.1-3.3, Mchmood & Ochs (2022, The- orem 34) provided an IFT for the fixed-point equation of PGD which is more practical for using ID than (9) and is restated below.
Aa (a, u) == Pag( (2z - a av u), u),
(10)
Liang et al. (2014) established that under Assumptions 3.1, 3.2(ii) and 3.3, all the iterates (xx) (u)) of PGD lie on M after a finite number of iterations and exhibit a local linear
Theorem 3.6. Let f and g satisfy Assumption 3.1 and (x",u') E M x S be such that Assumptions 3.2(i) and 3.3 are satisfied. Then for any a E [a al. Ao ,""),(("""))) < 1. Additionally when Assump- tion 3.2(i) is also satisfied, the (possibly reduced) neigh- bourhood U and the mapping up from Theorem 3.1 satisfy x AA (2,, u) and
convergence behaviour as summarized by the following lemma.
Lemma 3.2 (Activity Identification and Linear Conver- gence of PGD). Let f and g satisfy Assumption 3.1 and (x',u") E M x Qt be such that Assumption 3.3 is satisfied. For ok E [a, and By == O, let the sequence (xll)(" generated by Algorithm I con- verges to x². Then there exists K E N, such that (u)) .M for all k 2 K. Moreover when As- sumption 3.2(ii) is also satisfied and ā < L2 where M = Amax (I(x²) V u²" II))))))) then ((0(())) converge linearly to x=.
Dv(u) = (I- (z, D (x, for all u E U and x = tlu).
(11)
3.4.2, AUTOMATIC DIFFERENTIATION
Remark 3.3. The precise rate of convergence of PGD can be found in Liang et al. (2014, Theorem 3.1).
Using Theorems 3.4, and 3.6 and our results from Section 2. obtain the convergence (rate) guarantees for AD of PGD.
Theorem 3.7. Let f and g satisfy Assumption 3.1 and (x" ux), E M x Z be such that Assumptions 3.2 and 3.3 are satisfied. Lei or la, ū). BR == 0, the se- quence (a:()("""))e (u"))en generated by Algorithm I con- verges to x' with x( sufficiently close to x", and lim supp Aaz (z","")) < 1. Then the se- quence (Da (u") )kEN) converges to Dib(")). Addition- ally (k) (kKN) converges linearly with rate max(p ö, qm)) where p lim simsupk->ss pl DDa (æ", ,u))), )), when (x)) (u') converges linearly with rate qu < 1. M is CO. smooth, and Mgg. Vaf. Vagg. Du VaJ, and Du V Mg are locally Lipschitz continuous near (x",""). In partic- ular, for all ó E (0, 1 - p), there exist Eo, E2. and K E N, such that for all k 2 K, we have
Mehmood & Ochs (2022, Theorem 34) provide a foundation for proving the following crucial differentiablity result for Aa by combining Theorem 3.1 and Lemma 3.2. However, the result below is novel since it establishes differentiabil- ity of Aay at the iterates (u)) of PGD for all l N and also shows that the derivative sequence Da,, is well- behaved.
Theorem 3.4. Let f and g satisfy Assumption 3.1 and (a",, )²) E M x Q be such that Assumption 3.3 are sat- isfied. For Ogk E Ja, al and 8x == O, let the sequence generated by Algorithm I converges to x² Then there exists K E N, such that,
(alk)- = (()))u))))
(i) the mapping (x, u, a)) + Ax(x, u) defined in (10) is Cl -mmooot near (x) u², oak and (x", u", okk) for all k 2 K.
[xx (k) (u)) Dup(u*)) S ( 8)+
(12)
+ Ea K) max(p + 8, qm) k
(ii) (DAn, (x)( - DAa,, (x" u )22k converges to 0, and
Proof. The proof is in Section C.2 in the appendix.
Remark 3.8. (i) The constants &1 and E2 in (12) de-
(i additionally, when M is C9 -s-moothh Mg. V2J, Vug. Da Vaf. and D V Mg are locally Lipschitz continuous near (x) and kEEN converges linearly, then DAn, (x(k), u²) - D (x","") (x) x²))
pend on derivative errors Dar (u²) Del("", DAax (x(() u²) - D. derivative of the solution Dv(u") in the same manner as described in Remark 2.8.
and the
(ii) Because x. is not close enough to x:" in practice, one may resort to late-starting (Mchmood & Ochs, 2022, Section 1.4.2).
Proof. The proof is in Section C. in the appendix.
Remark 3.5. The C -mootthnss of M is a sufficient con- dition for the local Lipschitz continuity of the Weingarten map (z. v) + ())
(iii) In practice, we do not need x (0) to be close enough to x= because even when the update map Aa. is not differentiable in the earlier iterations of Algorithm 1,
7

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
the autograd libraries still yield a finite output as the derivative (Bolte & Pauwels, 2020; 2021). Hence, AD of Algorithm can still recover good estimate of (e) as long as Algorithm 1 is run for sufficiently large number of iterations (see also Mehmood & Ochs, 2022, Remark 45()).
result is mostly derived from Mehmood & Ochs (2022, Theorem 39).
Theorem 3.10. Let f and g satisfy Assumption 3.1 and (x", u²) E EMx S2 be such that Assumption 3.3 are satisfied. For [e.a] akk 7 ax and [0,1] e Bx + Be. let the sequence (xx == xx( (u"))Ke generated by Algorithm I converges to x². Then there exist Vo. E &N(wr ,et,",,a.))
(iv) When 0g is generated through line-search methods, it also depends on u in possibly non-differentiable way.
and K E N, such that
Therefore, the total derivative of (*))) with respect to u may not make sense. However computing (4) (u)
(i) the mapping (z, u. a)) + AA, u) defined in (13) is C* -mmooth on Va. and (z(0), (xx)) E Va, for all k 2 K,
by ignoring this dependence for instance, in practice, through routines like stop_gradi (Bradbury et al., 2018; Ahadi et al., 2016) and detach (Paszke et al., 2019) - the true derivative is still recovered in the limit provided that conditions of Theorem 3.7 are met. This fact was first explored in Griewank et al. (1993).
(ū) (D (DAa Sr (2) - DA (2", uu ))2k con- verges to O and (D (z", u D22K converges to 8. ,z",²") and
(iii) additionally, when M is C--mooth, V MM Va.. Vig D Val and Du vg are locally Lipschitz continuous near (x" ,u)) and (ax (z. kEN converges lin- early, then D DaniB (2lk) u²) Dax ( (xx(h) - x²).
(v) All of the non-smooth functions provided in, for in- stance, Vaiter et al. (2017) satisfy the local Lipschitz continuity condition of V MMg and Vang and the C3 smoothness of M.
(vi) The conditions like the linear convergence of az (1²" and lim supx p(D (x",, u²)) < 1 are not re- quired if the step size sequence og is bounded as in the hypothesis of Lemma 3.2.
where: 2 == (m1, (2), =(k) = (ax(A)),x(( and 2² = (x* x)))
Proof. The proof is in Section C.3 in the appendix.
3.5. Accelerated Proximal Gradient
We similarly compute AD of APG and show (linear) con- vergence of the corresponding derivative iterates. Given step size a >> and extrapolation parameter B E [0, 1], we define the update mapping Aa,g: X X x U + X X by
3.5.1. IMPLICIT DIFFERENTIATION
Similarly Theorems 3.1, and 3.10 can be used to yield an IFT for the fixed-point equation of APG (Mehmood & Ochs, 2022, Theorem 39), which we recall below.
Theorem 3.11. Let f and g satisfy Assumption 3.1 and (x" u²) E -M x Ω be such that Assumptions 3.2(ii) and 3.3 are satisfied. Then for any a E [a, ō] and 8 E [0. 1] with -1/(1 + 23) < Amin (Dr (x", u)). we have ( xx, u "[[(((x.,,, x))) < 1. Additionally when Assumption 3.2(i) is also satisfied, the (possibly re- duced) neighbourhood U and the mapping tp from Theo- rem 3.1 satisfy A u) and
(13) for x2) E X' x X. Just like PGD, APG also exhibit activity identification property and local linear con- vergence under Assumptions 3.1, 3.2(ii, and 3.3 (Liang et al., 2017).
Au, == (Aa (I1 + 3(x1 x2), 1), x1)
Lemma 3.9 (Activity Identification and Linear Conver- gence of APG). Let f and g satisfy Assumption 3.1 and (x', u²)= E M x Q be such that Assumption 3.3 is satis- fied. For ag E [a, ā) and 3x E [0, 11, let the sequence (u"))) generated by Algorithm I converges to x". Then there exists K E N, such that (*k) (u*) ) E for all k 2 K. Moreover when Assumption 3.2(ii) is also satis- fied, as + ar and 3y + Be such that -1/(1+ 28.)= <
Del(u)
Deb(u) = =I -I- -D- 2(z u)I[()))- DmA u)
(14)
for all u E U and == (vbu), v())).
3.5.2. AUTOMATIC DIFFERENITATION
Amin (Da (x", (,,")) ,)"),, then ((k) (u²) converge linearly to
x² with rate pl Dz S. (x=,, x², u² "I")""("""""" "))
Mehmood & Ochs (2022, see Theorem 44) established the convergence of the derivative iterates of APG. We strengthen their results by providing convergence rate guarantees in our final result below.
Using Theorem 3.1, and Lemma 3.9, we can differentiate A near (x: xx, u²) for all l E N. The following
8

---

Automatic Differentiation of Optimization Algorithms with Time- Updates
Theorem 3.12. Let f and g satisfy Assumption 3.1 and (ar,, ,u)) E M x 52 be such that Assumption 3.3 sat- isfied. For [ax ūi ag + a, and [0,1] 3 Br B. such that 11(11 23x) < ADia(Da (x", u))), let the sequence (x(l)(()) )kEN generated by Algorithm I con- verges to x² with x!!)) sufficiently close to x² Then the sequence (Da(() ((())))))))))))))()) RREN converges to Di)(u"). Ad- ditionally, (Dalf) (u") )EEN converges linearly with rate max(p 8, 9a) where p p(DzAa.... (x², )))), when (eti)) (u") converges linearly with rate Qn < 1, M is C smooth, and Mgg. Val. Viug. DuVal JnJ, and Du Mg are locally Lipschitz continuous near (x" ,u)). In partic- ular, for all 5 E (0,1-1)
PGD
PGD
PGDs,
PGDμ,
APG
33-1
13"1
38-
33"
330
154
330
16
10-4
-1--p p). there exist En, E2, and K E N, such that for all 2 K, we have
|i (1) (u') - Dv(("))l S 51(p+00 k)k-K
Figure I. Error plots of iterates (top row) of PGD and APG for lasso (left column), logistic (middle column), and multinomial lo- gistic (right column) regression along with their derivative iterates (bottom row). Similarity in the convergence rates of the original and the derivative iterates is clearly visible.
(15)
+ E2 K) max(p + ó, (w) K.
Proof. The proof is in Section C.4 in the appendix.
Remark 3.13. The arguments made in Remark 3.8 naturally extend to Theorem 3.12.
By (k- (depicted by APG in Figure 1). This generates five different algorithm sequences (xx(*) (x)))())) (u))keN for each problem. In Figure 1, PGD represents step size Og set to fixed optimal value o., whereas PGD,, repre- sents varying step size ag drawn from uniform distribution with parameters 2(i-1) 3L_, and 2 for all k E N and for all 3E E (1,2,3) We solve (16) for 50 randomly generated datasets, (17) for 50 perturbed instances of MADELON dataset (Dua & Graff, 2017), and (18) for a single instance of CIFAR1O dataset (Krizhevsky, 2009). For each problem, we initialize (()) Bio =(w") by first solving it partially,
4. Experiments
To test our results, we provide numerical demonstration on a few examples from classical Machine Learning. These include lasso regression, that is,
1 Xw 21l2 + A||w||,, w N 2
min
(16)
with parameters u == (X, y, A). binary classification using fz-regularized logistic regression, that is,
In Figure 1, the top shows the median error plots of the five algorithms and the bottom row shows the errors of the corresponding derivatives with the same colour. The three columns correspond to the error plots for (16), (17), and (18) respectively. The figure clearly shows that the derivative error decays as fast as the algorithm error for each problem. In particular, the linear convergence behaviour of AD of A PG for all the problems and PGDs; with i (1,2,3) for the lasso problem are only explained by our results.
1 M
min WERN
Σ M
log (1 + exp( pesp(-yxx' w)) + 11 (17)
with parameters u = A), and finally multiclass classifi- cation using Ez-regularized multinomial logistic regression, that is,
M
A log(ps. (2:)) + 2 F
min WERNXC
(18)
M
5. Conclusion
with parameters u = (X, In (18), I1 is the Frobenius norm and (a)) denotes the 7hhh element of the predicted output p(x) == o(WTx) æ) for each input x E N with o being the softmax activation function. In all the problems, X E M and y E R.M represent the dataset and the parameters are selected in such a way that Assumptions 3.1- 3.3 are satisfied.
We applied automatic differentiation on the iterative pro- cesses with time-varying update mappings. We strengthened previous result (Beck, 1994) with convergence rate guar- antee and extended them to new setting. As an example for each setting, we adapted our results to proximal gradient descent with variable step size and its accelerated counter- part, that is, FISTA. We showed that the convergence rate of the algorithm is simply mirrored in its derivative iterates which was supported through experiments on toy problems.
We solve the three problems through PGD with four differ- ent choices of step sizes and APG with fixed step size and
9

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
Acknowledgements
Baydin, A. G., Pearlmutter, B. A., Radul, A. A., and Siskind,
J. M. Automatic differentiation in machine learning: survey, Journal of Marchine Learning Research, 18:1-43, 2018.
Sheheryar Mehmood and Peter Ochs are supported by the German Research Foundation (DFG Grant OC 150/4-1).
Beck, A. and Teboulle, M. A fast iterative shrinkage- thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183-202, March 2009,
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Beck, T. Automatic differentiation of iterative processes.
Journal of Computational and Applied Mathematics, 50 (1-3):109-118, 1994.
References
Bengio. Y. Gradient- based optimization of hyperparameters, Neural computation, 12: 1 1889-00,, 09 2000. doi: 10.
Abadi, M., Barham, P., Chen, J., Chen, Z.,, Davis, A., Dean,
16220899966000000015111111
J., Devin, M., Ghemawat, S., Irving, G., Isard, M., Kudlur,
M., Levenberg, J., Monga, R., Moore, S., Murray, D. G., Steiner, B., Tucker, P., Vasudevan, V., Warden, P., Wicke, M., Yu, Y., and Zheng, X. Tensorflow: A system for large- scale machine learning. In 12th { (USENIX) Symposium on Operating Systems Design and Implementation ( ((OSDI) 16), pp. 265-283, 2016.
Bertrand, Q., Klopfenstein, Q., Massias, M., Blondel, M., Vaiter, S., Gramfort, A., and Salmon, J. Implicit differen- tiation for fast hyperparameter selection in non-smooth convex learning. Journal of Machine Learning Research, 23(149):1-43, 2022.
Blondel, M., Berthet, Q., Cuturi, M., Frostig, R., Hoyer, S., Llinares-Lopez, F., Pedregosa, F., and Vert, J.-P. Efficient and modular implicit differentiation. In Koyejo, S., Mo- hamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 5230-5242 Inc., 2022.
Ablin, P., Peyré, G., and Moreau, T. Super-efficienc, of automatic differentiation for functions defined as a mini- mum. arXiv preprint arXiv: 03722, 2020.
Curran Associates,
Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, J. Z. Differentiable convex optimization layers. In Advances in Neural Information Processing Sys- Curran Associates, Inc., 2019.
Bolte J. and Pauwels, E. A mathematical model for auto- matic diffcrentiation in machine learning. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 10809-10819. Curran Asso- ciates, Inc., 2020, URL neurips. cc/ /uuripps.cc/ppperr//0///EEE htt.:4/Sccccccfafaaoooo022221aa0 pdf.
tems 32, pp. 9562-9574,
Amos, B. and Kolter, J. Z. OptNet: Differentiable optimiza- tion as a layer neural networks. In Precup, D. and Teh, Y. W. (eds.), Proceedings of the 34th International Con- ference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 136-145 145, Interna- tional Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Bolte, J. and Pauwels, F. Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning. Mathematical Programming, 188(1); 19-51, 2021.
Bai, S., Kolter, J. Z.,, and Koltun, V. Deep equilibrium models. In Wallach, H., Larochelle, H. Beygelz- imer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Pro- cessing Systems, volume 32. Curran Associates, Inc., 2019. URL neurips. neexzppe.cc/oppe///0///ii.. 01 11336akkBe0091cccaeee77777666663 Pape. pdf.
Bolte, J., Pauwels, E., and Vaiter, Automatic differ- entiation of nonsmooth iterative algorithms. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https: htttp:://opeereeee /owerevveeweeeeeeeeeeeeeee net/ forum? id- WUMH5x1cMr.
Bai, S., Koltun, V., and Kolter, J. Multiscale deep equi- librium models. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5238- 5250. Curran Associates, Inc., 2020.
Bolte, J., Pauwels, E., and Vaiter, S. One-step dif- ferentiation of iterative algorithms. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL attpps://ppenzeviee net/ forum? id=81 snF FE3vR.
10

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
Bradbury, J., Frostig, R., Hawkins, P.,, Johnson, M. J., Leary, C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., Wanderman-Milne, S., and Zhang, Q. JAX: composable transformations of Python+NumPy programs, 2018. URL http:/ / thub. com goom/ 1e/eeee////e e jax.
Gilbert, J. C. Automatic differentiation and iterative pro- cesses. Optimization Methods and Software, 1(1):13-21, 1992.
Griewank, A. and Walther, A. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, Philadelphia, 2nd edition, 2008
Broyden, C. G. The convergence of single-rank quasi- newton methods. Mathematics of Computation, 24(1 24)1 365-382, 1970.
Griewank, A., Bischof, C., Corliss, G., Carle, A., and Williamson, K. Derivative convergence for iterative equa- tion solvers. Optimization methods and software, 2(3-4): 321-355, 1993.
Chambolle, A. and Dossal, C. On the convergence of the iterates of the "fast iterative shrinkage/thresholdiin algo- rithm". Journal of optimization theory and applications, 166(():968-99)) 982,, 2015. ISSN 0022-3239.
Hospedales, T., Antoniou, A., Micaelli, P., and Storkey, A. Meta-learning in neural networks: A survey. IEEE Iransactions on pattern analysis and machine intelligence, 44():5149-5169, 2021.
Chavel, I. Riemannian Geometry: Modern Introduction, volume 98. Cambridge University Press, 2006.
Iutzeler, F., Pauwels, E., and Vaiter, S. Derivatives of stochastic gradient descent in parametric optimization. In The Thirty-eighth Annual Conference Neural Infor- mation Processing Systems, 2024.
Davidon, W. Variable metric method for minimization. Technical report, Argonne National Lab., Lemont, III., 1959.
Dempe S. and Zemkoho, A. Bilevel optimization. In Springer optimization and its applications, volume 161. Springer, 2020.
Krizhevsky, A. Learning multiple layers of features from tiny images. 2009.
Lee, J. Introduction to Smooth Manifolds. Graduate Texts in Mathematics. Springer, 2003. ISBN 9780387954486.
Dempe, S., Kalashnikov, V., Prez- Valds, G. A., and Kalash- nykova, N. Bilevel Programming Problems: The- ory, Algorithms and Applications Energy Networks. Springer Publishing Company, Incorporated, 2015. ISBN 3662458268, 97836624526666
Lewis, A. S. Active sets, nonsmoothness, and sensitivity. SIAM Journal on Optimization, 13(3):702-725, 2002. doi: 10. 10.11377510022224413336666
Domke, J. Generic methods for optimization based mod- cling. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, vol- ume 22 of Proceedings of Machine Learning Research, pp. 118-326, La Palma, Canary Islands, 21-23 Apr 2012. PMLR. URL http: httpp:////cccecosssscoooe .ml.. press/ v22/ wtm//12...eee/c/. html.
Liang. J., Fadili, J. M., and Peyré, G. Local linear conver- under partial smoothness. In
gence of Proceedings of the 27th International Conference on Neu- ral Information Processing Systems- Volume 2, NIPS' 14, pp. 1970-1978, Cambridge, MA, USA, 2014. MIT Press.
Liang, J., Fadili, J., and Peyré, G. Activity identification and local linear convergence of forward backward methods. SIAM Journal on Optimization, 27(1):408 437, 2017. doi: 10.1 11113/166M063340X
Dontchev, A. L. and Rockafellar, R. T. Implicit Functions and Solution Mappings, volume 543. Springer, 2009.
Dua, D. and Graff, C. UCI machine learning repository, 2017. URL http: /ttp::////rcvieeeeeee ics. uci. edu/ml.
Linnainmaa, S.
The representation of the cumulative round- ing error of an algorithm as a Taylor expansion of the local rounding errors. PhD thesis, Master's Thesis (in Finnish), Univ. Helsinki, 1970.
Fischer, H. Automatic differentiation of the vector that solves a parametric linear system. Journal of Computa- tional and Applied Mathematics, 35(1-3)::69-1) 1991.
Lions, P.-L. and Mercier, B. Splitting algorithms for the sum of two nonlinear operators. SIAM Journal Numerical Analysis, 16(6):964499 9799, 1979.
Fletcher, R. A new approach to variable metric algorithms. The computer journal, 13(3):317-322, 1970.
Liu, H., Simonyan, K., and Yang, Y. DARTS: Differ- entiable architecture search. In International Confer- ence on Learning Representations, 2019. URL https: / /opprreveew net forum? d=t.iddssseeeeeeeee
Fletcher, R. and Powell, M. J. A rapidly convergent descent method for minimization. The computer journal, 6(2): 163-168, 1963.

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
Lorraine, J., Vicol, P., and Duvenaud, D. Optimizing mil- lions of hyperparameters by implicit differentiation. In International conference artificial intelligence and statistics, pp. 1540-1552. PMLR, 2020.
Rockafellar, R. and Wets, R. J.-B. Variational Analysis. Springer Verlag, Heidelberg, Berlin, New York, 1998.
Rockafellar, R. T. Convex analysis. Princcton Mathematical Series. Princeton University Press, Princeton, N. J., 1970.
Maclaurin, D., Duvenaud, D., and Adams, R. Gradient- based hyperparameter optimization through reversible learning. In International conference machine learn- ing, pp. 21 2112-2122. PMLR, 2015.
Rumelhart, D. E., Hinton, G. E., and Williams, R. Learning representations by back-propagating errors. Nature, 323(6088):533--34) 1986. doi: 10. 1038/323533a0. URL, http:// http:///wwww.// http://wwwtttte.o. articles/323533er
Mchmood, S. and Ochs, P. Automatic differentiation of some first-order methods in parametric optimization. In Chiappa, S. and Calandra, R. (eds.). The 23rd Interna- tional Conference on Artificial Intelligncce and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sieily. Italy], volume 108 of Proceedings of Machine Learning Research, pp. 1584-1594. PMLR, 2020.
Scieur, D., Gidel, G., Bertrand, Q. and Pedregosa, F. The curse of unrolling: Rate of differentiating through opti- mization. Advances in Neural Information Processing Systems, 35:17133-17145, 2022.
Vaiter, S., Deledalle, C., Fadili, J., Peyré, G., and Dossal, C. The degrees of freedom of partly smooth regularizers. Annals of the Institute of Statistical Mathematics, 69(4): 791-8331 2017.
Mehmood, S. and Ochs, P. Fixen-point automatic differenti- ation of aeward-backward splitting algorithms for partly smooth functions. arXiv preprint arXiv:2208.03107, 2022.
Wengert, R. E. A simple automatic derivative evalu- ation program Communications of the ACM, 7(8): 463-464, aug 1964. ISSN 0001-0782, doi: 10. 1145/355586.364799, URL https: htttt:::/ddo..ro//// 1145/355588 364791.
Mosco, Convergence of convex sets and of solutions of variational inequalities. Advances in Mathematics, 3(4): 510-585, 1969.
Nesterov, Y. A method for unconstrained convex minimiza- tion problem with the rate of convergence o (1/k*) 2). In Doklady an ussr, volume 269, pp. 543-547, 1983.
Winston, E. and Kolter, J. Z.. Monotone operator equilibrium networks. Advances in neural information processing systems, 33:10718-10728, 2020.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf. A., Yang. E., DeVito, Z., Rai- son, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang. L., Bai, J., and Chintala, S. Pytorch: An imperative style, nigh-performance deep learning library. In Wal- lach, H., Larochelle, H., Beygelzimer, A., "'lché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural In- formation Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
Pauwels, E. and Vaiter, S. The derivatives of sinkhorn- knopp converge. SIAM Journal on Optimization, 33(3): 1494-1511, 2023. doi: 10.1117722M15512033. URL http:/:///oi.or/1..11111111 011.0.1111322221121771 512003
Polyak, B. T. Introduction to Optimization. Optimization Software, 1987.
Ren, J., Feng, X., Liu, B., Pan, X., Fu, Y., Mai, L., and Yang, Y. Torchopt: An efficient library for differen- tiable optimization. Journal of Machine Learning Re- search, 24(367):1-14, 2023. URL http:// jmmr. arg/paperss/24/23-- 0191 html.
Riss, S. Geometric numerical integration for optimisation. PhD thesis, University of Cambridge, 2020.
12

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
A. Preliminaries & Related Work
Before we move on to the proofs our main results, we present some preliminary results which will useful later. We also provide a recap of the results of Beck (1994) for a better understanding of our work.
A.1. Real Analysis
In Section 2, we refer to equicontiniity and uniform Lipschitz continuity as cases where Assumptions 2.2 and 2.3 respectively hold. In this section, we provide defintion along with an example for each of these notions. Note that, in the definitions and examples below, x" is not necessarily the fixed-point of any of A& (+, u²). Let X, 24 be Euclidean spaces as in Section 1.4 and Ω 2 be an open set. We first define equicontinuity of sequence of functions.
Definition A.1 (Equicontiniity). A sequence of functions (B,: x Ω > KEN with values (x u) is equicontinuous in æ at some (a",, ut*) X Ω if for any & > 0, there exists a 8 0 such that ||B (x, u²) (a("", ,=)" < & for all N and for all X' such that | x²1 8. The sequence (Bx)eeN kEN equicontinuous in if it equicontinuous in every (x* 2x" X x Ω
Intuitively speaking, an equicontinuous sequence of functions behaves uniformly in terms of continuity because the neighbourhood {æ || - x=I < 8) in Definition does not depend on h E N. Below, we provide an example for equicontinuous functions.
Example A.2. Let F in (P) be C²-smooth. Given (ee) such that on S ā for all ls E N and some ā > 0, we define A X x X + by
Ac(a,, u) = on v F(r,
(19)
and Bg: X x Ω + X by
(x u) = DAc(a, [T 0 Ds
(20)
where P) E L(X X) is the derivative (with respect to both a and u) of V and [T 0 E L(X x X) defines the canonical projection onto X. Essentially, (19) defines A as the update mapping of gradient descent with bounded step size sequence while (20) defines Bn as its derivative with respect to x and u. For any x, x² E X and u² E u, we find that
(x, u²) Ba(x", u²) =ax==<ax(DD)) (D(VV
D(V=
(21)
But since the sequence (aл)KEN is bounded and D(V&F) is continuous, for any O, easily find 8 independent of h E N such that [|, u²) , < whenever || x=1| < 8. Moreover, we also find from (21) that, for any sequence (xx))) BEN converging to x=, the sequence By (xx( ) (x u²) converges to 0 therefore satisfying our Assumption 2.2 for Gradient Descent. Note that, when additionally, the step size sequence converges, Assumption A.2 of Beck (1994) is also satisfied.
We similarly define the notion of uniformly Lipschitz continuous sequence of functions.
Definition A.3 (Uniform Lipschitz Continuity). A sequence of functions (BR: X x + X)xEN with values Ba (zx, u) Lipschitz continuous in æ uniformly in u and if for all Q and ls N, there exists L E E, such that, (x u) L-Lipschitz continuous. That is, for all x, x= E X,
[B u) - (x=, wull S L||x=x* - x=I| -
Example A.4. Consider the setting of Example A.2 where D(V a) is additionally M M-Lipschitz continuous. Clearly, from (21), every k N and u E U. (x u) aM -Liishhhtt continuous. Therefore, (Be) is Lipschitz continuous i uniformly in u, and k and for any sequence (xx()) kEN converging x", Gradient Descent with bounded step size sequence satisfies Assumption 2.3 because
(z) uu) -x 4Ill S aM ax x²1
Finally, Assumption A.3 is satisfied when the step size sequence converges linearly which does not happen in general when employing line-search strategies for Gradient Descent.
13

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
A.2. Matrix Analysis
This section provides few preliminary results on Matrix Analysis. We start by recalling a classical result from Linear Algebra which forms the foundation for the implicit differentiation applied to (R,)) when combined with the Implicit Function Theorem (Dontchev & Rockafellar, 2009, Theorem IB.1).
Lemma A.5. For any linear operator B: X X' with (( < 1, the linear operator - B is invertible.
We now provide some results which will be used in the proofs of convergence of automatic differentiation of the fixed-point iterations. In particular, provide convergence guarantees of sequences generated through linear iterative procedures including (26), and (22) which bear strong resemblance with (DR) and (DR;) (see the proofs of Theorems A.12 and 2.5 for a more detailed comparison). These convergence results are mainly derived from Polyak (1987, Section 2.1.2, Theorem 1), Rii (2020, Proposition 2.7), and Mehmood & Ochs (2022, Theorem 8). The following theorem will be used to prove convergence results in Section 2.
Theorem A.6. Let (BR) (CK)REN, and (d(*) JREN be sequences in _(X,X) L(X,X) and X respectively such that C 0, (k +0 and = lim s |B < 1 where the sequence (e(*)))ENo with ( E X, generated by
||
a norm on C(X, X) induced by some vector norm. Then
(k+1) (k) Cke + dkk)
(22)
converges to 0. The convergence linear when Og and th converge linearly with rates qa and qa respectively, In fact, for all E (0, 1 - p), there exist K N, such that for all K, we have
| S 5: k)p + Ea(k - K)4 k
(23)
where
= max(p + E, 90, qa)
(x)
(24)
& = (K) + +
Proof. From classical analysis, given E (0. 1 p), there exists K E N such that || < x e/2 2 for all k: 2 K. Also, with K large enough we have e|Cee()) (k) // [1) < e/2 since Cj + 0. Therefore, from (22), we get
(k(+1))
(p / c/2)]le(k) + (| |
$ (p + ()) + ||
The convergence of (k)) then follows from the arguments following Equation 34 in the proof of Theorem 8 in Mchmood & Ochs (2022).
For the rate of convergence, we note that (k) = Cze(k) + (+) converges linearly to 0 with rate max max qa) and for K E sufficiently large we can write [k) I max(gcc qa) ( (|( for all 2 K. Thus, for any & 2 K, we expand the expression (k+1)) (k) + e(k) to obtain
k ((+1) = B + Σ Bks
where Best denotes the ordered product Bx B,41
when i & k and identity operator when i k. Observe that, for any E (0, 1 - p) and K N large enough, B&ll < + e for all k 2 K and therefore for any K < 1, we
14

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
have |B (p 1-1 Therefore, setting y max(p + 8, 9, (,)0:9a), end up with
|| 1 B ||e
|Battillle(01
&
S (|e(())]( + -)) ---
Σ
+ e)
max(qo,
i=
(25)
k
- [| + e)a-Kt1 + ||
Σ qt-K
i=K
= ||(p + e) c)*-k+1 + +1|e ||((K))
K + 1)g K
K+1 = =(( k- + Ez - K + 1) k-K+1
where E = ||e( and E2 = 1|/9.
The result below is direct consequence of the above theorem and will find its use when proving Corollary 2.9. Corollary A.7. The conclusion of Theorem A.6 also holds when the assumptions on the sequence (B&)kEN, are replaced with Bg + E C(X,)) and p B) < 1.
Proof. This a special case of Theorem A.6 because for any 5 E (0,11-p(B)) there exists a norm on L(X, induced by some vector norm, both denoted by || [la. such that |B S p(B) + and == limg- B = B|||| I p(B) + 8 <
The following result a special case of the setting of Corollary A.7 and is straightforward to show. Corollary A.8. The conclusion of Theorem A.6 also holds when the assumptions on the sequence (Be)ReNo are replaced with Bg= B L(X, X) for all
and p(B) <
Using Corollary A.8, can prove the following statement which will be useful in the convergence proofs of Section A.3. Theorem A.9. Let (Bx)keNo and (b(k) JeENo be sequences L(X,X) and X with limits B and respectively. If p (B) the sequence ( with (9) E X, generated by
x (k+1) = Bxxx(() + (k))
(26)
The convergence linear when (Bx)KEN, and (b (bLR)) JKEN, converge linearly with rates qB
converges to x = and qb, respectively. In fact, for all 8 E (0, p). there exist (5), C2(8) and K N, such that for all K, we have
(k) - æ|l s (z) K)ga-K C2(0)(p + 5)
(27)
where q = max(p + 8 9B).)).
Proof. The expression æ = (I -1---i- is well-defined thanks to Lemma A.5 and solves the linear equation x = Bx + b
for x. By setting (k)) = [(k) x. Cs == B₁ B, and (k) = (Bx- - B)x + (A)) b, we obtain,
(k++1) = (B) + (16)) - (Bx + b) (k()) Cze d(k)
Since the above recursion matches (22) and the setting of Corollary A.8 applies, the result follows.
A.3. Differentiation of Iteration-Dependent Algorithms: Classical Results
In this section, we briefly recap the results of Beck (1994) in way that aligns with those of Section 2, allowing for clearer comparison between the two sets of results. We first lay down the assumptions on the sequence of mappings Ag in (R₂) and the mapping A in (R.) which will ensure the convergence of the sequence (x (u) generated by (DR+). The main requirement in the work of Beck (1994) that of the pointwise convergence of the sequence DAAg to D.A.
15

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
1.3.1. PROBLEM SETTING
Given u² &,, we assume that x* solves (R,) for with u u and is the desired limit of (x() (u") generated by (Rx).
Furthermore, assume that for all k, Ag and A are -smooohh near (æ* u²) and the contraction property holds for DzA at (x", u²) In particular, given (x("), x,, u²) E X' x x U, V E (u)) (As) and A we assume that the following assumption holds.
Assumption A.1. (i) Auly and Aly are -mooth for all l;
(ii x- A(x", u*).
(ii1) p( D22((x" )) < 1, and
(iv) 2 (8) (u") generated by (Rx) has limit xx such that (a=)) u²) V for all ls E N.
A.3.2. IMPLICIT DIFFERENTIATION
From Assumption A.I, Lemma A.5, and (Dontchev & Rockafellar, 2009, Theorem IB.1), we obtain the Implicit Function Theorem for (R.).
Theorem A.10 (Implicit Function Theorem). For some (x",""), let A be C* -m-woothh near (æ", u²), x² = =A(x", u²) and P(DaA(x" uu)) < 1. Then U E Nu- and -smoooth mapping v U + X such that Vu E U, vb() A(v(u), u) and
D*(()= = (T- -0--Daan D=n((b(u) -1 DuA((b(u)))
(28)
A.3.3. AUTOMATIC DIFFERENTIAION
As stated in Section A.2, the update procedure generate the derivative iterates in (DR2) takes after the iterative process (x)))))))
defined by (26) in Theorem A.9. That is, for some u² E U and ú E U, if we set BN == Am (x) (u"), u²) and (()) = (z)",, u" )ú, the resulting sequence is y (8) (k) (u )ú. Similarly, the limit y" = [[ (J-B) B) of the se- quence y generated by (26) matches Dub(" ) from (28), if we set B = D2A(V((') u²) and b = DuA(((u)) w*)u. One way to prove the convergence of (M) (u" ju to Dzb("") u is by asserting that D.A, (x (u²), u²) converges to DA(v((")) uu)) u²).
Au (x (x(
u²) ))eeoo converges to DA(x", u.). Remark A.11. When the sequence of functions (D.s) is equicontinuous at (x", u²) and has pointwise limit DA near (x", u²), then Assumption A.2 naturally holds thanks to (5).
Assumption A.2. The sequence (D.AA (xx( (xx
The main result of Beck (1994) can then be stated below.
Theorem A.12. Let (x("), xx, u²) be such that Assumptions A.I and A.2 are satisfied by As and A. Then the sequence (bx()) (u") )KEN, generated by (DRx) converges to Dv"(")..
Proof. The proof is a direct consequence of Assumptions A.I and A.2, Theorem A.9 and the arguments following Theorem A.9.
For linear convergence we require a stronger assumption on DAA That is, it is linear convergence as given below. Assumption A.3. The sequence (x) (u))) converges linearly to xx and
DAc( (u')), )²) DA(x", u²) = (xx (u') (xx))) xx))
(29)
Theorem A.13. Let (0), xx, u²) be such that Assumptions A.I and A.3 are satisfied by As and A. Then the sequence (Da( (u") )eEN, generated by (DRR) converges linearly Drb(u"). In particular, when the sequence (ar keN converges with rate qu < then for all 8 E (0, p). there exist (ō)) C2(6) and K E N, such that for all k > K, we have
[Dz Dib(u*)) s (K - K)gx-K C2(0)(p +5)
(30)
where p== A(DxA((x" u²)) and q = max(p + 6, gm).
16

---

Definition A.16 (Riemannian Gradient). For any k E N. let M C. X be a C*-smooth manifold, f: M - RR be a function and æ E M.. We say that f is C* -moooh at æ there exist a neighbourhood X C X of æ and a -mmsmooth function f: X + R such that ff agrees with f on M 7 X. In this case, we call f smooth extension of f around æ. We call V [a: E T2,, the Riemannian gradient of f at x: if for all v E TaM, (V = (f o (0), where 7: (-e,e) + .M is any CC-curve with 70)= and (0) v. Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
Proof. Assumption A.3 asserts that the sequences Da (x(()() (u"),") and DuAAgar (u"), u" ) respectively converge to DaA( PaA(""; =²") and A (ar", u²) u")ú for any i E U. Furthermore, the rate of convergence of the two sequences is linear and is the same as that of (18), that is, fx. Therefore, the proof follows by simply invoking the second part of Theorem A.9.
Remark A.14, Assumption A.3 is not practical and therefore we rarely see any application of the above result in practice. For instance, for gradient descent with line search, it requires linear convergence of the step size sequence which does not hold in general.
A.4. Riemannian Geometry
We briefly recall a few definitions and results from Riemannian Geometry. For further details, the reader is referred to standard texts such as Lee (2003); Chavel (2006).
Definition A.15 (Manifold, Tangent and Normal Spaces). For any k E N, we say that M c X is a C+ C*-smooth m- dimensional submanifold of X, if for every a: E M there exist an open set X C X and a C* -moothh map c: X - R- such that æ E Xx the derivative (2 surjective, and X M = - (0) defining function of M at æ. We say that X is tangent vector of M at if there exist e > 0 and -m-sohoth curve 7: (-e,e) - .M on M with 7(0) x and +(0) = v. The set of all tangent vectors of . at x constitute T,M, the tangent space of M at æ. We define the normal space of M at æ by NaM = (T.M))+ the orthogonal complement of T.MM.
{y E X ((y) 03. We call Φ, the local
For any x E M and a local defining function Tb for . at x, we have T..M- = ker (xx
The Riemannian Gradient of f can also be expressed in terms of the gradient of the smooth extension f of f by
Vmf(x) ((x))
Note that this gradient neither depends on the choice of the curve y nor the smooth extension f. Definition A.17 (Riemannian Hessian). Let M C X' be a -m-oooh manifold, f: . - IR be a C2 -mmooth function and x E M. We call (=)) T + T,M, the Riemannian Hessian of f at æ if for all v E T,M, (V'M( (0), where y: (-e, c) + M is any -curvee with 7(0) x and {(0) = v.
We can similarly express the Riemannian Hessian
(a)) E M(T,,, M) by using the smooth extension f. that is,
(M)()) (xx) + 2.
(.. IT (a) (
(31)
where the mapping w)) E C(T, T Mn for w E M is called the Weingarten map. It is defined by
v + 21 U. w) = II [[x)dW[[))
where Win is a local extension of u normal vector field on M. 20 w) is independent of the choice of normal field W (Chavel, 2006, Proposition II.2.1) and caters for the change of the tangent space as move away from æ. It vanishes when the manifold is affine, that is, M = x + T or linear, that is, M = Mr The Hessian expression then reduces to f()((=) = V2
A.5. Partial Smoothness
Introduced by Lewis (2002), partial smoothness describes broad class of non-smooth functions, including many commonly used loss and regularization functions in Machine Learning. It extends ideas like active set methods which were originally developed for smooth constrained optimization to a more general setting that includes non-smooth functions, by identifying smooth behavior along certain submanifolds.
Definition A.18 (Partial Smoothness). Let f: X + R be proper and lower semi-continuous and M C X be a set. We say that f is partly smooth at a point x E M relative to M if the following conditions hold:
17

---

Automatic Differentiation of Optimization Algorithms with Time-Varyine Updates
(Regularity:) is regular at every point close to æ and (f()) + 0.
(ii) (Smoothness:) M is C2-smooth manifold and JlM is C²-smooth around æ.
( (Sharpness:) M par (f))..
(iv) (Continuity:) 0 is continuous at a relative to M.
We call f partly smooth relative to .M if f is partly smooth at every a M relative to M.
B. Proofs of Section
B.1. Proof of Lemma 2.2
Proof. From Assumption 2.1(ii), given E (0, 1 p). there exists K N such that p(DaAs(x* u²)) S [|D=,A(<",, u²)l < + for all k 2 K, where = limssp De (xx,, (x))" The existence of the neigh- bourhood U and the C*-smooth mapping vh: U + X' is guaranteed by Theorem A.10 applied to A, for some n 2 K, thanks to Assumption 2.1 (i)-ii)). In particular, for all u E U, ((u) = A, (v((), u) and Dv(()) is given by (28) with A replaced by An. From Assumption 2. 2ii( for any 2 K and u E U, we have vu(u) = An (vb(),, u) (s(((u), u) and with possibly reduced, Ax u)) < Therefore, by using the Chain rule and Lemma A.5, we obtain the expression in (4).
B.2. Proof of Theorem 2.5
Proof. From Lemma 2.2 and Remark 2.3, there exists K E N such that for any k: 2 K, the fixed-point mapping ths of Au ( u) is Cm-smooth near u" and Diba(u") X. (see Assumption 2. 2.)() We denote ax(k) = =x(( for simplicity and define
- x..)
Bg (20"
(32)
Cs Da _u)) D=AAex"' x,ú
u²) ((h) (DAu(o(()) uu) -DAu(a", (20)))))))))))))
to obtain
(b+1))
(Dars(ac Dz) (u") + Du , )()
(DaAAlaa u' x')Xú DuAA(a" ,a=""""" u²)()) Bie((t) + Cxa(1)) + d)
(33)
From Assumption 2.2 and the definitions of C and y (k), we note that Ck and ((() -. 0. Therefore, from Theorem A.6, (R) (u" (u))ú)ke,, converges X. ú for any U.
B.3. Proof of Theorem 2.7
Proof. From Assumption 2.3, we have (x) (u"), u²) DAA (a= u²) - and the rate of convergence of the two sequences is qu- For any à E 24 by using the definitions in (32), we note that both C₃ and (k) converge linearly with rate 4z Thus, invoking the second part of Theorem A.6, we obtain the convergence rate of (Dx (u") Ju) In particular, from (23), obtain the bound in (7). The expressions for and & can be computed from (24) using Ck. d(K) and ( defined in (32).
C. Proofs of Section 3
C.1. Proof of Theorem 3.4
The proof of Theorem 3.4 relies on the following preliminary result from set-valued analysis.
18

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
Lemma C.I. Given a sequence of non-emply, closed, convex sets Cg C X which converges C C X such that all Cj also converges aff C. Let (x(k) E C2 be sequence with limit x E ri Then there exists K E N such that ax() ri Ca for all k 2 K.
Proof. Because (*)) + x and E ri ri there exists compact set V and K E I4 such that (0*) x E int V * 0 for all k 2 K and V n aff C C C. Moreover, aff Cs - aff C' implies V n aff C + V aff C' (Mosco, 1969, Lemma 1.4). Once we show that V n aff C& C Cg eventually, we are done. Assume for contradiction, that there exists a subsequence (Cx, JeN such that for all i E N. y E V O aff Ck, and y & Ck.- The compactness of V and convergence of V aff Ck2 implies the existence of y V O aff C' such that (0))) + y. possibly through a subsequence. We define the bounded sequence 6(*) == ala)/||((| where a = y projc., (1) which lies in par C₁, and has limit o E par C. again, possibly
through a subsequence. For all E N and for all w E Ck.,
(600 w - y y11)
(1) - projc., (1)))) = (6) w - proje., (1)))) - (BCO, y
(b)) w projcr, (y (v))) | (al), al())
( w proicr, (v))) ||a
5 0,
where the inequality follows because ( and therefore (00 lie in Nea, (proicm, (1)) The above inequality leads to (b, w- y) S for all w C. In other words, we obtain 0 o b E No(y) par C which is a contradiction because
y r...
Remark C.2. The condition aff C₁ + aff C is necessary for the conclusion of Lemma C.I to hold. To see why, we define the sequence of closed intervals (Ck- == [-1/k, /k, 1/E))REN in R which converges to C == {0}. Consider the sequence
Ik = 1/k which converges to == 0. Notice that, all Ck- = IR for all & E N, all C {0} and even though x E C = ri C, x (k) & ri Ci for all k E N.
Proof Theorem 3.4. (i) From the convergence of (a) = (²()(())) Lemma 3.9 ensures that for 5 >> 0 small enough, there exists K' E such that (kk) E EM Bs(x*) for all & 2 K. We define the maps G: X' x Ω x (0, L) + X' by
G(x, a. = x - af u) and H: X x X x Ωx x (0, 2/ + by
Vly,v.u,ok = ag(y, u) + ž b x + v. u))
and note that x (*+11 = Acs (x) u²) = argmin, H (()) u,, ax), which, from Fermat's rule, is equivalent to 0 0, (z)h+))) (0))), u², ,n) or tk) E o F (2)b+t2) u²), where
n (
(Glal ui, axs) ((at(k+1), _u", ur,a))) ak
1 -
(34)
Notice that 1e()) + 0 because G(,,u", aa)a)) is non-expansive when E (022/L) and we have | || 1 a [|x)(M] - [k1t1)]. Moreover, aff Og (x)(t+11, u²) = 1(()) + par Oz ((x(++))) u²) = (x()) + Tautn:M M con- verges aff FxF((*,,'* = par Fx u²) TT M (Mosco, 1969, Lemma 1.6). Therefore, from (ND) and Lemma C.1, we have (2(²) ri (( u²) or 0 H
<
(x)), u² ax), for all is E N large enough. Since H is partly smooth relative to M x X' x Ω x 20 and H x, u, a) is strongly convex for all (x, u.aa a) E X x Ω x L0,)/L), and non-degeneracy condition holds, the C² -m-sooothness of the update map near (x)) u." , au) follows by invoking Theorem 3.1. The C'-smoothness of An near (x", uu, a) under given assumptions was shown in Mehmood & Ochs (2022, Corollary 32) for any a E [a,
iii We define
Qx = HM (x)(11)) ( (k), u. ak);
Q = VMHl(a, x=" "u" .ak)
Pa,k = D. V. (k+1)
(b++1) (1)) u" ak),
Pw,k = Da VM x², u",as)
H = (1x
II. = I(x",, II
= IT (x) II. = (x"),,
19

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
where far, u, at and evaluate Qs to obtain
Qx an (mg(x((+1) u²) + 11++1 + 28 (1++)) (s (20()+1)))))))))))))) G(x u", axl))
- on Vmg(o" u ) + on 2 (++) (- + Val V=s(x((ttl) uu))
,()) + Il++1+
2 (: k (G (++1) u og) ((x(()) u,, ,k)))
= oz FM u²) k V (x (k+1)) I + I++++
2 m0t (, (, (G(z (k+1), ui as) G(x(h) u, ox)))
Similarly, Qu is given by
ax PM 04.
III. + II.
From Liang et al. (2017, Lemma 4.3), ag Vyf( x²) a+ll. (= , ul) is positive semi-definite and the
eigenvalues of Q lie in (0, 1]. Moreover, the non-expansiveness of G(-, u², u.,a)) and the continuity of (x, v) + (- v) due to the C²-smoothness of M implies that 2 n (1 + (G(xr(++1, uu, ,ax) -G(x(*) u,,, aa))) - O.
This entails that Qx Qu + 0 and the eigenvalues of Q] are also eventually bounded. Hence, Q 2 which can be
rewritten as
Q Q = =Q] Q. + Q & =T - Q
= Q/ Ql + 0,0x01 QIQ.Q. -Q
= of (1l, - 11.) - 0% (oc 2x) Φt + +Ll+ 11,) 0%
also converges to O. Similarly Park Pa,k + 0 for all w E {æx, eu a} because
Pa.k Pa,k [T&+1 (1 (T- 0r V (xx(1t u²) IT. (T a& V2l Vaj("" ,u))
=(1x+11 11.) ap (I4-1 V (z) (8), u²) - 11. V2 V2 u²))
Pu,k Pu,k = ak (uu V. u²) + Dullk+1 (al( u²) D DuV
Pa.k Park = (x+(x(()11)) u²) + 11++1 Va. V (1), u V (nF(x",")
(x)
This concludes the proof because from (9), DA (x, u) is given by,
(1, -V (x, w) x. u, D( V (An (x, u), x, a).
(35)
(iii The expressions for Qk - Qx and Pu.k - Pa,k for w E fxx u. a} clearly indicate that these sequences converge linearly under the given assumptions.
C.2. Proof of Theorem 3.7
Proof. We again set (k) = (1)()) for simplicity. Thanks to Theorem 3.4(i) Ad, are C'-smooth near (zx( u², axx) for all k E N provided that (0) is sufficiently close x.. Differentiation of the fixed-point iteration (l++1) Aos (z)(k) w) with respect to yields
(x+))) = DarA, (x), u (T=) (a) (u²" + DuAAn (x: "00) u²),
(36)
and Theorem 3.6 asserts that under the given assumptions, for all l E N,
De(u") Aa, (a", u IT"[[(()))) Dub"""""""""") + DuAan (a ;a=,,")) u²)
(37)
Just like the arguments made in the proof of Theorem A.1 for any à U, if we define
(A)) (1) (u" jú Dvl("))
B₁ = D DaAa, (x" I²)))("")
(38)
C = DaAa, (k), u (²)))(x(()) D= (xx" u² (²)))("")
d = (Z)) u²) - (D"""""") ú),
20

---

Automatic Differentiation of Optimization Algorithms with Time-Varyinn Updates
and subtract (37) from (36), we obtain the recursion e(k+1) Bge(k) + Cge( + d From Theorem 3.6, the continuity of p and Aa suPkeN B 1 for all & N and from Theorem 3.4 Ck 0 and d 0. Under the additional assumptions, C and (b) converge linearly with rate da due Theorem 3.4 Therefore, the (linear) convergence of the derivative sequence (Dz())("))) k)EN follows from Theorem A.6. The error bound in (12), as well as the expressions for the constants & and Σ2. can be derived from (23) and (24), respectively where Ck, e(K), and d(K) are defined in (38).
C.3. Proof of Theorem 3.10
Proof. (i) This part follows from Mehmood & Ochs (2022, Corollary 33) and the convergence of (u') and og.
(ii) We set == (01,02) and y æ1 + ((x) w2) and write the expression for D u) for (z, u, B)
Va. x [0, 1]:
(1 + Da (3. u) -BDzAA u)
o2
I
DuAa (y,, u)
DuAa,p(2,2)
0
DaAa(y. (y,
(2
0
as provided in Mehmood & Ochs (2022, Corollary 33), where D.aa (y. u) is given in (35). It is easy to see that the mapping (z, u. at 3) + D u) is continuous on V., [0, Therefore, the sequences (D &. (x())( x ((=-1(("") (u") ), u²) u))))x and (D (x", ",,x""")) ,2)))k both converge to DA. p. (x", x², u*)
and their difference converges to 0.
(iii) Because 3x E [0, 1] and under the additional assumptions, DA (y)))))))))))) established in Theorem 3.4(iii, where y())) == (x() + Ba (x:() (((k-)((i) the result follows directly from the expressions of DAA.,B.
,u)) DA (a", ,u") - Oly xx) as
C.4. Proof of Theorem 3.12
Proof. From Theorem 3.10 the mapping (x1, x2, u, a:) + Aan. (2)1, x2, u. a.) is C -m-ooh on Va. Therefore, when (0) is close enough to x", we have (2x(), (l--1) u cas) E Va. where x(k) = (8) (x)(())) and we obtain the following recursion for the derivative iterates
Dac(k+1 (u²) D2 D2 uu" (x))) (0((0))))))))1))) (xx()())))
Dor(t) Dac (8- (2t") + (2) ,())
From Theorem 3.11, we have
Dvb(u))
Dib(u)) Dú(ut)) + pu u²),
DzAn, u "=))M("",,""" Dú(ut))
for 3 = B. and B = 3& for all le E N. Therefore, for any i E U, we define
(k) (Dzrlt) (1") - Dup(u"), (t- (u²) Drf((e)) xx, u²
B₁ DerAs on (x",
B. = Dz a (x" ,x", "=,"""""""""""" ","""("".""""
C. Dæras dn (2)( (1(--1), u (() .0(-1))) D D (x" "a""", u M[)", ((=""==))))
d (DAr Be (20()) (1(1))x((k)) (k-1)) u²) DA (x" xx, "r,""") ()) (1 (u))ú, (p")),
and obtain the recursion e (k+1) = (k) + Cze + (kk) Notice that ((B.) < from Theorem 3.11 and By + B. from Theorem 3. 10(). Moreover C₂ + 0, and (()) + 0 owing to Theorem 1.ii and under the additional assumptions, the convergence Cs and d is linear with rate du thanks to Theorem 3.10(ii). Therefore, from Corollary A.7, the sequence (k) (u" ) converges (linearly) to Dup(u") ) for all ú E U.
21

---

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
D. Experimental Details
In this section, we fill out some missing details from Section 4. We do not perform any feature transformation apart from batch normalization. For (16), the dataset is artificialll generated with 70 S M I 90 and N 200. In particular, for each of the 50 problems, we generate X and a sparse vector w' IR with only 50 non-zero elements. We sample each element of X from standard uniform distribution and each non-zero element of w' from standard normal distribution respectively. We then generate by computing Xw + where each e is drawn from normal distibution with mean O and covariance matrix 10 10-31. The problem has a p(X' X --iischitz continuous gradient but is not even strictly convex. However, for each choice of ~ (0, 10), X, and Assumptions 3.2 and 3.3 were satisfied for each experiment. The spaces and sets mentioned in Assumption 3.1 are X = I U = RMxN x IM X R, Ω = R RMN x R' x (0, +o0), supp(w")) where supp(w) denotes the support of u. For (17), we use MADELON dataset with M 2, 000 samples and N 501 features. For 50 set of experiments, we sample ~ (O 10 10-3) and perturb each element of X with a Gaussian noise with standard deviation 10 The problem is X-strongly convex and has p(X" (4M) ) + X-Lipschitz continuous gradient with M = X' E U P RM*N x R and Q RMX (0, +o0). For (18), we use CIFAR10 10 dataset with M = 50, 000 samples N = 32 x 32 3 features. The problem is X-strongly convex and has a p(X / +X-iipschizz continuous gradient with M = X' = N u MMNN xI and Ω = RM x (0, +20).
and M = {w E TR supp(w)
We obtain a very good estimate of w" for (16) by running APG for sufficiently large number of iterations, for (17) by using Newton's 's method with backtracking line search, and for (18) by running the Heavy-ball method with optimal parameters, also, for large number of iterations. The derivative of the solution Del(") is computed by solving the linear system (2) for (multinomial) logistic regression and solving the reduced system (9) after identifying the support for lasso regression (Bertrand et al., 2022). For each problem and for each experiment, we run PGD with four different choices of step size, namely, (i) ag 2/(L + m) for (17) and = 1/L for (16), (ii) ay ~ (0, 31. ), (ii)) ag ~ U 31. and (iv) 0% ~ U( 37. ). for each E N. We also run APG with Og = 1/L. and Bx = (k: - 1) + 5). Before starting each algorithm, we obtain (o E B10-2(w") by partially solving each problem through APG. For computational reasons, instead of generating the sequence (w(()(u), (u), we compute the directional derivative (w (w))) (u)ú. ú.. The vector ú belongs to the same space as u and is fixed for the 5 different algorithms being compared for each experiment and problem. For each problem, we plot the error sequences (*) (u) eu)) || and (w (u) (u)lll
2
22


Reviews:
[{"review_id": "8XwEaC2fI8", "reviewer": "Reviewer_n3Bk", "summary": "When, for example, solving a bilevel optimization $\\min_{u\\in\\mathcal{U}}l(\\psi(u),u)$ by gradient descent, a derivative of a solution mapping $\\psi(u)$, that is $D\\psi(u)$, needs to be computed. While either the implicit differentiation (ID), using chain rule, or the automatic differentiation (AD) can be used to compute $D\\psi(u)$, the latter may be preferred due to its blackbox implementation. This paper particularly focuses on analyzing the AD. Regardless of the differentiation technique, one needs to iteratively update as $x^{(k+1)}(u) = \\mathcal{A}_k(x^{(k)}(u),u)$ to approximate $\\psi(u)$. And, during this process, the (forward mode) AD additionally updates $Dx^{(k)}(u)$ in a certain way to approximate $D\\psi(u)$. \n\nThis paper's main contribution is to study the (forward mode) AD for time-varying iterative processes $\\mathcal{A}_k$, such as gradient descent with line search, accelerated gradient method, and Quasi-Newton methods, in a unified way. (Beck, 1994) and other cited literatures have studied this setting, but they lack a (linear) convergence rate analysis, which is of main interest of this paper.\n\nSection 2 is a direct extension of (Beck, 1994) that assumed the convergence of $\\mathcal{A}_k$. This paper proves derivative iterate convergence without assuming convergence of $\\mathcal{A}_k$. Moreover, with additional Assumption 2.1(ii), this paper was able to show a linear convergence rate. (Q: Was there a convergence rate analysis for the AD of non-time-varying update? I was not able to figure that out in the paper.) Section 3 then applies the established result in Section 2 to (extrapolated) proximal gradient with variable step size for the class of partly smooth functions. The convergence of the derivate iterates was already shown in (Mehmood & Ochs, 2022) (which does not assume convergence of $\\mathcal{A}_k$), so the rate analysis is new here.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for their valuable comments and suggestions. We will fix minor typos and incorporate the suggested changes to the next version.\n\n> Was there a convergence rate analysis for the AD of non-time-varying update? I was not able to figure that out in the paper.\n\nWe highlight them in Section 1.1. We mention these works right before introducing the time-varying algorithms in Section 1.2.\n\n> Unlike the introduction, the abstract lacks a clear motivation (that should built upon existing limitations), and a complete picture of the paper. Regarding the latter, presenting the necessity of applying automatic differentiation to a (time-varying) iterative process, such as in bilevel optimization, could be helpful.\n\nWe will add the application of our work in Bilevel optimization in the updated version of the abstract. Thank you for pointing it out.\n\n> \"Define $\\mathcal L (\\mathcal X, \\mathcal X)$.\"\n\n$\\mathcal L (\\mathcal X, \\mathcal X)$ is the space of all linear operators from $\\mathcal X$ to $\\mathcal X$. We will update our preliminaries and the notation section to make the paper more readable. Thank you for the suggestion.\n\n> \"Contributions: Although the assumptions of Beck(1994) are given in the appendix and one can compare them with new assumptions, I suggest adding comments after the assumptions so that one can clearly identify contributions (i) and (ii) from Beck(1994) after they are introduced.\"\n\nThat will definitely make our contributions more explicit. Thank you for the recommendation. We will do it in the updated version.\n\n> Contibution (ii): I think Assumptions 2.2 and 2.3 should be added here.\n\nThat's a typo actually. Thank you for spotting that.\n\n> p3 left line 125: Does this mean that the analysis in (Riis, 2020) and (Mehmood & Ochs, 2022) that showed the convergence of the AD of APG cannot be applied to the AD of PGD with non-converging variable step size? If yes, then does Section 2 (especially Theorem 2.5) generalizes the result in (Riis, 2020) and (Mehmood & Ochs, 2022), so that you can provide guarantee for the AD of PGD with non-converging variable step size? I suggest explaining what is new in Section 2, in comparison to (Riis, 2020) and (Mehmood & Ochs, 2022) and particularly in terms of contribution (i).\n\nRiis (2020) and Mehmood & Ochs (2022) do not consider a general time-varying update rule. They consider APG or FISTA with converging step size and extrapolation parameter sequences by employing the analysis of Beck (1994). Their results can not be easily applied to PGD with a general non-converging step size sequence. Therefore, we provide an update on the results of Beck (1994) in Section 2 using Assumption 2.1(ii) and Assumption 2.2 and use it to provide stronger results than Riis (2020) and Mehmood & Ochs (2022) in Section 3.\n\n> p4 right line 215: Could you further explain why, without such additional condition, the AD will not have a linear rate?\n\nActually, the correct statement should be that without such additional condition, it will be very challenging to *prove* that AD will have a linear rate.", "claims_and_evidence": "All claims are theoretically proven.", "methods_and_evaluation_criteria": ".", "theoretical_claims": "I was not able to check correctness of proofs.", "experimental_designs_or_analyses": "This paper presents experiments on three classical machine learning problems. The numerical results align with the theory and seem sufficient, especially given the paper's theoretical focus.", "relation_to_broader_scientific_literature": ".", "essential_references_not_discussed": ".", "other_strengths_and_weaknesses": ".", "other_comments_or_suggestions": "- Unlike the introduction, the abstract lacks a clear motivation (that should built upon existing limitations), and a complete picture of the paper. Regarding the latter, presenting the necessity of applying automatic differentiation to a (time-varying) iterative process, such as in bilevel optimization, could be helpful.\n- Define $\\mathcal{L}(\\mathcal{X},\\mathcal{X})$\n\n- Contributions: Although the assumptions of (Beck, 1994) are given in the appendix and one can compare them with new assumptions, I suggest adding comments after the assumptions so that one can clearly identify contributions (i) and (ii) from (Beck, 1994) after they are introduced. \n- Contibution (ii): I think Assumptions 2.2 and 2.3 should be added here.", "questions_for_authors": "- p3 left line 125: Does this mean that the analysis in (Riis, 2020) and (Mehmood & Ochs, 2022) that showed the convergence of the AD of APG cannot be applied to the AD of PGD with non-converging variable step size? If yes, then does Section 2 (especially Theorem 2.5) generalizes the result in (Riis, 2020) and (Mehmood & Ochs, 2022), so that you can provide guarantee for the AD of PGD with non-converging variable step size? I suggest explaining what is new in Section 2, in comparison to (Riis, 2020) and (Mehmood & Ochs, 2022) and particularly in terms of contribution (i).\n- p4 right line 215: Could you further explain why, without such additional condition, the AD will not have a linear rate?", "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": "", "extra_scores": {}}, {"review_id": "6cOfVXdD9c", "reviewer": "Reviewer_QxMK", "summary": "This paper studies automatic differentiation which is widely used and fundamental in bilevel optimization. The focus of this work is on the case where the algorithm may have changing parameters at each iteration, such as step-sizes. Under this setting and some assumptions, they analyzed the convergence of the automatic differentiation scheme.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for their valuable comments and suggestions. We will incorporate the suggested changes to the next version.\n\n> I did not check the proof, while I have some concerns regarding the assumptions 3.1 - 3.3, which seem quite strong. Can the authors list some functions that satisfy these assumptions? Some discussions should be provided below these assumptions. For example, if the function F is strongly convex and smooth, will these assumptions hold? **...** it is difficult for me to judge whether this paper made significant contributions. The main reason is the lack of discussions on Assumptions 3.1 - 3.3 (looks restrictive for me), which determines the applicability of their results. **...** More discussions on the assumptions.\n\nAssumptions 3.1 - 3.3 are quite less restrictive when we compare them to the smooth setting ($g=0$) where $F = f$ is $C^2$-smooth and strongly convex. Many practical regularizers which induce some form of sparsity, satisfy Assumption 3.1. These include $\\ell_1$ norm, $\\ell_{2, 1}$ norm, and the nuclear norm etc. More examples can be found in, for instance, Vaiter et al. (2017; see Section 3). The obtained sparsity is such that the solution lies on a low dimensional manifold as compared to $\\mathrm{dim} \\ \\mathcal X$ thus making it easier for Assumption 3.2 to be satisfied. Even though it is possible that this assumption may not satisfy, it is still way more general than the usual strongly convex, $C^2$-smooth, lower level objective assumption. Assumption 3.3 is satisfied almost everywhere by a solution for many practical regularizers (Vaiter et al. 2017; Definition 3 & Theorem 3). For linear convergence rates, in Theorems 3.7 and 3.12, we also assume local Lipschitz continuity of the second derivatives of $f$ and $g$ and $C^3$-smoothness of $\\mathcal M$ which is also satisifed for the same problems listed above and more in Vaiter et al. (2017). In the udpated version, we will add these concrete examples for a better understanding of our assumptions. \n\n> I can see that in page 2, the expression of $D x^{(k+1)} (u)$ includes three parts: $D_x \\mathcal A (x^{(k)} (u), u)$, $D x^{(k)} (u)$, and $D_u \\mathcal A (x^{(k)} (u), u)$. The convergence of $D x^{(k+1)} (u)$ requires all these three terms to converge. Which one is the most difficult part to prove the convergence?\n\n$D x^{(k)} (u)$ and $D x^{(k+1)} (u)$ are elements of the same sequence $(D x^{(k)} (u))_{k\\in\\mathbb N}$, which is generated by Equation $\\mathcal{DR}$ in a recursive manner whose convergence is desired. It is possible that even though the sequences \n\n$(D_{x} \\mathcal{A} (x^{(k)} (u), u))_{k\\in\\mathbb{N}}$, and\n\n $(D_u \\mathcal{A} (x^{(k)} (u), u))_{k\\in\\mathbb{N}}$\n\nconverge (which is straightforward when $\\mathcal A$ is $C^1$), the sequence $(D x^{(k)} (u))_{k\\in\\mathbb N}$ does not converge. So in the end, it is $D x^{(k)} (u)$, whose convergence requires more effort to show.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "This is a theoretical paper and there is no method proposed.", "theoretical_claims": "I did not check the proof, while I have some concerns regarding the assumptions 3.1 - 3.3, which seem quite strong. Can the authors list some functions that satisfy these assumptions? Some discussions should be provided below these assumptions. For example, if the function F is strongly convex and smooth, will these assumptions hold?", "experimental_designs_or_analyses": "Experiment settings are simple, but it is fine for a theoretical paper.", "relation_to_broader_scientific_literature": "No", "essential_references_not_discussed": "Not find.", "other_strengths_and_weaknesses": "This paper seems quite technical, and the results are not trivial. However, it is difficult for me to judge whether this paper made significant contributions. The main reason is the lack of discussions on Assumptions 3.1 - 3.3 (looks restrictive for me), which determines the applicability of their results.", "other_comments_or_suggestions": "More discussions on the assumptions.", "questions_for_authors": "I can see that in page 2, the expression of $D x^{(k+1)}(u)$ includes three parts: $D_x A(x^{(k)}(u), u)$, $D x^{(k)}(u)$, and $D_u A(x^{(k)}(u), u)$. The convergence of $D x^{(k+1)}(u)$ requires all these three terms to converge. Which one is the most difficult part to prove the convergence?", "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": "", "extra_scores": {}}, {"review_id": "VdLVwZ3mSV", "reviewer": "Reviewer_YwLr", "summary": "Automated differentiation (AD) is a little studied workhorse behind all major deep-learning frameworks (PyTorch, TensorFlow, JAX). The authors show linear convergence for forward-mode AD for algorithms, where the iteration's parameters change over time. This is a very neat theoretical result.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for their valuable comments and suggestions. We will fix minor typos and incorporate the suggested changes to the next version.\n\n> ... the authors could ... Riis (2020) and Mehmood & Ochs (2022) better.\n\nThe key difference presented in Section 1.2, Paragraph 4 (last on the page) is that \"the sequences $\\alpha_k$ and $\\beta_k$ [must] converge\" for their analysis and that \"[they] do not explain the *linear* convergence of AD of APG\". These are the two main points that we address in this paper. We will make it more intelligible in the updated version.\n\n> I would prefer to have ... material presented clearly original.\n\nWe recall many results from other papers (Lemmas 3.2, and 3.9, Theorems 3.1, 3.6, and 3.11) and split our main results in Section~3 into intermediate results (Theorems 3.4, 3.7, 3.10, and 3.12), for a better understanding. We can change Theorems 3.4, 3.6, 3.10, and 3.11 into lemmas.\n\n> The introduction could spell ... Rockafellar and Wets\"?\n\nWe will update our preliminaries and the notation section to make the paper more readable. Thank you for the suggestion.\n\n> ... It would be great to relate ... definable in o-minimal structures...\n\nCan you please share a reference which relates partly smooth functions to semismooth functions?\n\n> ... In Lemma C.1, intermediate ... mistake in the paper.\n\nThat is a typo. We will fix that. Thank you so much.\n\n> In Theorem 2.7, the proof ... bounding $\\lVert D x^{(k)} (u^*) - X^*\\rVert$.\n\nInitially, we were going to put Theorem A.2 in the main part of the paper. That would have allowed us to motivate the proof of Theorems 2.5 and 2.7 in the main part. However, the space constraints did not allow us to go through with it.\n\n> In Theorem 3.7, ... $D_{x} A_{\\alpha_k}(x^*, u^*)$ remains bounded ... stated explicitly.\n\nYou are right. Under the conditions of Lemma 3.2, this follows naturally. However, without imposing those assumptions, we need to explicitly assume that $x^{(k)}$ converges linearly to $x^*$ and $D_{x} A_{\\alpha_k}(x^*, u^*)$ eventually has a norm less than 1.\n\n> Explicit rate bounds for Theorems 2.7 and 3.7\n\nThanks a lot for the suggestion. We will provide the explicit error bounds with $C_1$ and $C_2$ clearly defined.\n\n> The discussion of Implicit differentiation could be ...\n\nIndeed, there is no doubt about the benefits and popularity of implicit differentiation in, for instance, the training of equilibrium models. However, because we focus on automatic differentiation, we chose to list the reasons where AD shines more than ID. We will revise our discussion on implicit differentitation.\n\n> In Algorithm 1 (Proximal Gradient with Extrapolation), conditions under ...\n\nThe assumptions on the choice of the step size and extrapolation parameter in Algorithm 1 are made explicit in our lemmas and theorems by recalling the work of Liang et al. (2014; 2017) or other classical results wherever necessary. Algorithm 1 in itself is an abstract algorithm and is hence named \"Proximal Gradient with Extrapolation\" which only mentions the three important steps in the algorithm.\n\n> In Theorem 3.6, equation (10) ... (i.e., ensuring positive definiteness).\n\nIn Theorem 3.6, because $\\rho (D_{x} \\mathcal A_{\\alpha} (x^*, u^*) \\Pi (x^*)) < 1$, we obtain $\\rho (D_{x} \\mathcal A_{\\alpha} (x, u) \\Pi (x)) < 1$ for all $u$ near $u^*$ and $x = \\psi (u)$ from Theorem 3.5(i) which implies the invertibility of $I - D_{x}\\mathcal A_{\\alpha} (x, u) \\Pi (x)$ from Lemma A.1.\n\n> The use of projection operators ... the Euclidean norm or not.\n\nThe orthogonality is indeed with respect to the Euclidean inner product. The Riemannian metric is inheritied from the natural embedding of $\\mathcal M$ in $\\mathcal X$. We will make it clear in the paper.\n\n> In Assumption 3.3, the relative interior ... in high dimensional problems.\n\nThe relative interior of a non-empty convex set is always non-empty (Rockafellar, 1997; Theorem 6.2).\n\nWe assume that the reviewer mean $0\\in \\mathrm {ri} \\ \\partial_{x} F (x^*, u^*)$. For many practical partly smooth functions, it is satisfied almost everywhere by a solution (Vaiter et al. 2017; Definition 3 & Theorem 3).\n\n> Would the method generalize to multi-level optimization?\n\nIf needed, our work can be put into use in multi-level optimization because we mainly analyze the problem at the lowest level. Bilevel optimization is only emphasized as an *application* of our results.\n\n> Rather than the experiments ... this be possible, please?\n\nWe are sorry we could not comprehend the comment well. Should we provide the implementation details of our experiments in PyTorch?\n\n**References**\n\nLiang et al., 2014. Local linear convergence of forward--backward under partial smoothness.\n\nLiang et al., 2017. Activity identification and local linear convergence of forward--backward-type methods.\n\nVaiter et al., 2017. The degrees of freedom of partly smooth regularizers.", "claims_and_evidence": "The theory is solid and its discussion is ok, although the authors could perhaps explain the relationship (overlap) with https://www.repository.cam.ac.uk/items/271dad6b-c165-434e-a4ae-74cac4129604 and https://arxiv.org/abs/2208.03107\n better. I would prefer to have a theorem or two less in the main body of the text, while having the material presented clearly original.", "methods_and_evaluation_criteria": "The empirical results are rudimentary, but illustrative.", "theoretical_claims": "The introduction could spell out that they consider Clarke subdifferential, rather than to say \"We use the terminology of Rockafellar and Wets\"?\n\n\"Partly smooth\" functions are a bit neglected in the literateure. It would be great to relate the \"partly smooth\" functions to the better known semismooth functions and functions definable in o-minimal structures. (Partly smooth functions are a subclass of semismooth functions, which are a subclass of functions definable in o-minimal structures. \n\nThe proofs are mostly ok. In Lemma C.1,  intermediate equation should be:  \n\n$\\Big\\langle b(i), w - y(i)\\Big\\rangle &= - \\|a^{(i)}\\|\\Big(\\left\\langle a^{(i)}, y(i) - \\operatorname{proj}_{C_{k_i}}(y(i)) \\right\\rangle + \\left\\langle a^{(i)}, \\operatorname{proj}_{C_{k_i}}(y(i)) - w \\right\\rangle\\Big)$\n\n$=-\\frac{1}{\\|a^{(i)}\\|}.\\|a^{(i)}\\|^2+\\frac{1}{\\|a^{(i)}\\|}\\left\\langle a(i), w-\\operatorname{proj}_{C_{k_i}}(y(i)) \\right\\rangle\\Big)\\leq 0$\n\n(where the second term is negative because of projection property). The inequality $\\le-\\frac{1}{2}\\|a^{(i)}\\|$ is a mistake in the paper. \n\nIn Theorem 2.7, the proof relies on Assumption 2.3. It might be beneficial to explicitly show how the linear convergence assumption is used in bounding  $\\|Dx^k(u^*)-X^*\\|$. Also, it is unclear how the dependency on $C_1$ and $C_2$ is computed; explicit bounds should be provided.\n    \nIn Theorem 3.7, the assumption that $D_xA_{\\alpha_k}(x^*,u^*)$ remains bounded over iterations is reasonable, but should be stated explicitly. Also, the result extends previous work naturally, but the proof would benefit from a more explicit rate bound rather than an asymptotic argument.", "experimental_designs_or_analyses": "The empirical results are rudimentary, but illustrative.", "relation_to_broader_scientific_literature": "The discussion of Implicit differentiation could be less dismissive, perhaps? For deep learning, it is rather elegant.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "There are some minor typos, e.g. lines 142-143: one of \"without\" and \"removed\" should be dropped?", "other_comments_or_suggestions": "In Algorithm 1 (Proximal Gradient with Extrapolation), conditions under which the step sizes ensure contraction are not apparent. If step sizes $\\alpha_k$ oscillate too much, the contraction property may not hold. \n\nIn Theorem 3.6, equation (10) states that the inverse is assumed to exist, but it would be good to clarify the conditions under which this holds (i.e., ensuring positive definiteness).\n\nThe use of projection operators \\(\\Pi(x)\\) and \\(\\Pi^{\\perp}(x)\\) from manifold-based optimization does not state whether these projections are orthogonal with respect to the Euclidean norm or not. \n\nIn Assumption 3.3, the relative interior may be empty. Is there a condition under which the relative interior is non-empty? Also, checking whether $0\\in\\partial_xF(x^*,u^*)$ holds can be difficult, especially in high dimensional problems. \n\nWould the method generalize to multi-level optimization (https://arxiv.org/abs/2207.02849, https://proceedings.neurips.cc/paper/2021/hash/3de568f8597b94bda53149c7d7f5958c-Abstract.html, https://doi.org/10.1007/s00186-024-00852-5)?\n\nRather than the experiments presented, I would appreciate some discussion of the AD implemented in PyTorch etc.", "questions_for_authors": "Rather than the experiments presented, I would appreciate some discussion of the AD implemented in PyTorch etc. Would this be possible, please?", "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": "", "extra_scores": {}}, {"review_id": "UISDGqLypb", "reviewer": "Reviewer_6V9C", "summary": "The paper studies the convergence of the gradient of algorithm iterates with respect to the hyperparameters in settings where optimization algorithms employ time-varying update rules, such as changing step sizes or momentum parameters. The authors provide convergence guarantees for the derivative of the iterates under more general assumptions on the update mapping. They adapt these results to proximal gradient descent with variable step sizes and its accelerated counterpart, FISTA, under partially smooth assumptions.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "We thank the reviewer for their valuable comments and suggestions. We will fix minor typos and incorporate the suggested changes to the next version.\n\n> It would be more understandable if the authors added more details on the results of Beck (1994) that they claim to improve upon.\n\nIn the appendix, we dedicate the entire Section A.2 to the results of Beck (1994) by presenting them in a way which makes the comparison between the two works easier. We could not do that in the main text due to the page limit.\n\n> (a) The key assumption, Assumption 2.2, requires the derivative ...\n\nPlease see the answer to \"Difficult to read. Mathematical concepts are not well explained...\" below.\n\n> (b) The assumption regarding the related interior is not supported by examples ...\n\nThe relative interior of a non-empty convex set is always non-empty (Rockafellar, 1997; Theorem 6.2). When $C$ is a singleton, $\\mathrm {ri} \\ C = C$. For practical non-smooth functions, this assumption (Assumption 3.3) is satisfied almost everywhere by a solution (Vaiter et al., 2017; Definition 3 & Theorem 3).\n\n> (c) The analysis would be more convincing if concrete examples were provided ...\n\nPlease see our response \"Assumptions 3.1 - 3.3 are quite less restrictive ...\" to Reviewer QxMK for the question \"I did not check the proof ...\"\n\n> Unclear motivation. This work briefly mentions in the introduction ...\n\nWhen we apply AD on the algorithm for solving the lower level problem, we really are replacing the lower level problem with $$\nx^{(K)} (u) := \\mathcal B (x^{(0)}, u; K) \\,,\n$$ where, for a given $u$, $\\mathcal B (x^{(0)}, u; K)$ performs $K$ iterations of the algorithm defined by the update mapping sequence $\\mathcal A_k$, starting with $x^{(0)}$. To show that, by doing this, we are actually solving the original bilevel optimization (which does not depend on the algorithm being used to solve the lower level problem), the convergence of $x^{(k)} (u)$ to the solution $\\psi (u)$ (that is, the forward pass computes the correct solution) won't suffice. We also require the guarantee that $D x^{(k)} (u)$ converges to the derivative of the solution mapping $D \\psi (u)$ (that is, the backward pass computes the correct derivative) .\n\n> Difficult to read. Mathematical concepts are not ...\n\nThank you for the suggestion. We will update our preliminaries and the notation section for a better understanding of our paper.\n\nThe notion of Equicontinuity for a collection of functions (Rudin 1987; Definition 11.27) means that such a collection behaves \"uniformly\" in terms of continuity. For example, when $f$ is $C^2$-smooth and $g=0$ in Equation $\\mathcal P$ in the paper, the update mapping of gradient descent with variable step size $\\mathcal A_k (x, u) := x - \\alpha_k \\nabla_{x} f (x, u)$ has an equicontinuous derivative $D \\mathcal A_k$.\n\n$\\mathcal L (\\mathcal X, \\mathcal X)$ is the space of all linear operators from $\\mathcal X$ to $\\mathcal X$.\n\nRelative interior of a convex set is defined in, for example, Rockafellar (1997; p. 44).\n\n\"Lipschitz continuity in $x$ uniformly in $u$ and $k$\" means that the given collection of maps are Lipschitz continuous in $x$ where the Lipschitz constant is fixed for all $u$ and $k$. Formally, for all $u \\in \\Omega$, and $k \\in \\mathbb N$, there exists $L \\in \\mathbb R$, such that, for all $x, y \\in \\mathcal X$,\n$$\n\\lVert D \\mathcal A_k (x, u) - D \\mathcal A_k (y, u) \\rVert \\leq L \\lVert x - y \\rVert \\,.\n$$\nFor the gradient descent example above, $D \\mathcal A_k$ is Lipschitz continuous in $x$ uniformly in $u$ and $k$, when $\\nabla_{x} f (\\cdot, u)$ is $L$-Lipschitz continuous for all $u$.\n\n> Typo on line 264 ...\n\nYes, that is a typo. It should be the Hessian of $f$ and not the gradient. Thank you for pointing it out.\n\n> Typo on the 4th line of the first paragraph ...\"\n\nIt should be Algorithm 1. Thank you for pointing it out.\n\n**References**\n\nRudin, W., 1987. Real and complex analysis.\n\nRockafellar, R.T., 1997. Convex analysis.\n\nVaiter, S., Deledalle, C., Fadili, J., Peyré, G. and Dossal, C., 2017. The degrees of freedom of partly smooth regularizers.", "claims_and_evidence": "Please refer to \"Other Strengths And Weaknesses\" section.", "methods_and_evaluation_criteria": "Please refer to \"Other Strengths And Weaknesses\" section.", "theoretical_claims": "Please refer to \"Other Strengths And Weaknesses\" section.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "I'm not sure if there is a strong relation between this paper with the broader scientific literature. Please refer to \"Other Strengths And Weaknesses\" section.", "essential_references_not_discussed": "It would be more understandable if the authors added more details on the results of Beck (1994) that they claim to improve upon.", "other_strengths_and_weaknesses": "Strengths:\n1. It provides convergence guarantees for the gradient of the algorithm iterates, extending its analysis in Beck (1994).\n2. The assumption on the update mapping for convergence guarantees of the derivative of the iterates is more general.\n\n\nWeaknesses:\n1.  Too many assumptions. For example:  \n    (a) The key assumption, Assumption 2.2, requires the derivative of the update mapping $A_k$ to converge while $x^k$ is also approaching $x^*$. It is hard to understand how this condition can be satisfied. The sufficient condition, given as the equicontinuity of $\\mathcal{A}_k$, is not well defined, and its meaning is unclear.  \n        \n    (b) The assumption regarding the related interior is not supported by examples. Moreover, this assumption is difficult to satisfy. For instance, when $x \\neq 0$, $\\text{ri} (\\partial \\|x\\|_1)$ is empty. Therefore, more successful examples are needed to justify this assumption.  \n        \n    (c) The analysis would be more convincing if concrete examples were provided, particularly in the partly smooth setting. This is especially important in Theorem 3.4 (iii), where the function is required to be $C^3$ on $\\mathcal{M}$.  \n    \n\n2. Unclear motivation. This work briefly mentions in the introduction (lines 65--67) that the effective use of automatic differentiation (AD) relies on the convergence of the derivative of iterates. However, it would be more convincing if examples were provided to illustrate why the convergence of $Dx^k(u)$ is important. What do the authors mean by \"effective use\"? In bilevel optimization, for example, the convergence of $x^k(u)$ can be analyzed without considering the convergence of $Dx^k(u)$. Why, then, is it necessary to analyze the convergence of $Dx^k(u)$?  \n\n3. Difficult to read. Mathematical concepts are not well explained or supported by examples. The paper assumes familiarity with numerous optimization notations and concepts without providing definitions. For example, there is no definition of $\\mathcal{L}(\\mathcal{X},\\mathcal{X})$, the relative interior mentioned in lines 237--238, or equicontinuity in line 166. Additionally, the meaning of \"Lipschitz continuity in $x$ uniformly in $u$ and $k$\" is unclear.  \n\\end{enumerate}", "other_comments_or_suggestions": "1.Typo on line 264: if I understand correctly, it should state that the Hessian of $f$ is positive definite.  \n2.Typo on the 4th line of the first paragraph in Section 3.3: what is Algorithm 3.3?", "questions_for_authors": "None.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The main content of the paper is to study the (forward mode) AD for time-varying iterative processes, which covers various optimization schemes from the literature such as inertial acceleration schemes and quasi-Newton method. The paper proposes a unified approach of AD with convergence guarantees. Numerical experiments validate the efficiency of the proposed method. The paper presents a significant development over the existing literature, expanding the applicability of the method. During the discussion period, the concerns from the reviewers are properly addressed. The authors should modify the paper properly, including improving the readability of the paper and adding necessary discussions.
Decision: Accept (poster)