SHINE: SHaring the INverse Estimate from the forward pass for bi-level optimization and implicit models
Authors: Zaccharie Ramzi
Florian Mannel
Shaojie Bai
Jean-Luc Starck
Philippe Ciuciu
Thomas Moreau
Venue: ICLR 2022 Spotlight (2022)
Keywords: implicit models
bi-level optimization
quasi-newton methods

Abstract: In recent years, implicit deep learning has emerged as a method to increase the depth of deep neural networks. While their training is memory-efficient, they are still significantly slower to train than their explicit counterparts. In Deep Equilibrium Models~(DEQs), the training is performed as a bi-level problem, and its computational complexity is partially driven by the iterative inversion of a huge Jacobian matrix. In this paper, we propose a novel strategy to tackle this computational bottleneck from which many bi-level problems suffer. The main idea is to use the quasi-Newton matrices from the forward pass to efficiently approximate the inverse Jacobian matrix in the direction needed for the gradient computation. We provide a theorem that motivates using our method with the original forward algorithms. In addition, by modifying these forward algorithms, we further provide theoretical guarantees that our method asymptotically estimates the true implicit gradient. We empirically study this approach in many settings, ranging from hyperparameter optimization to large Multiscale DEQs applied to CIFAR and ImageNet. We show that it reduces the computational cost of the backward pass by up to two orders of magnitude. All this is achieved while retaining the excellent performance of the original models in hyperparameter optimization and on CIFAR, and giving encouraging and competitive results on ImageNet.

Published as a conference paper at ICLR 2022
SHINE: SHARING THE INVERSE ESTIMATE FROM THE FORWARD PASS FOR BI-LEVEL OPTIMIZATION AND IM-
PLICIT MODELS
Zaccharie Ramzi
Florian Mannel
Shaojie Bai
CEA (Neurospin & Cosmostat)
University of Graz Graz, Austria
Carnegie Mellon University Pittsburgh, USA
Inria (Parietal)
Gif-sur- Yvette, France zaccharie. ramzi@inria.F
Jean-Luc Starek
Philippe Ciuciu
Thomas Moreau Inria (Parietal) Gif-sur-Yvette, France
AIM, CEA, CNRS Gif-sur-Yvette, France
CEA (Neurospin), Inria (Parietal) Gif-sur-Yvette France
ABSTRACT
In recent years, implicit deep learning has emerged as method to increase the effective depth of deep neural networks. While their training is memory-efficien they still significantly slower to train than their explicit counterparts, In Deep Equilibrium Models (DEQs), the training is performed as a bi-level problem, and its computational complexity is partially driven by the iterative inversion of huge Jacobian matrix. In this paper, we propose a novel strategy to tackle this computational bottleneck from which many bi-level problems suffer. The main idea is to use the quasi-News Newton matrices from the forward pass to efficiently approximate the inverse Jacobian matrix in the direction needed for the gradient computation. We provide theorem that motivates using our method with the original forward algorithms. addition, by modifying these forward algorithms, we further provide theoretical guarantees that our method asymptotically estimates the true implicit gradient. We empirically study this approach and the recent Jacobian- Free method in different settings, ranging from hyperparameter optimization to large Multiscale DEQs (MDEQs) applied to CIFAR and ImageNet. Both methods reduce significantly the computational cost of the backward pass. While SHINE has a clear advantage on hyperparameter optimization problems, both methods attain similar computational performances for larger scale problems such as MDEQs at the cost of a limited performance drop compared to the original models.
INTRODUCTION
Implicit deep learning models such as Neural ODEs (Chen et al., 2018), OptNets (Amos and Zico Kolter, 2017) Deep Equilibrium models (DEQs) (Bai et al., 2019; 2020) have recently emerged as a way to train deep models with infinite effective depth without the associated memory cost. Indeed, while has been observed that the performance of deep learning models increases with their depth (Telgarsky, 2016), an increase in depth also translates into an increase in the memory footprint required for training, which is neural networks (Gomez et al., 2017: Sander et al., 2021) or gradient checkpointing (Chen et al., 2016) also tackle this issue, implicit models bear an ((1) memory cost and with constraints on the architecture that are usually not detrimental to the performance (Bai et al., 2019). These models have been successfully applied to large-scale tasks such as language modeling (Bai et al., 2019), computer vision (Bai al., 2020) and inverse problems (Gilton et al., 2021; Heaton et al., 2021).
While other works such as invertible
In general, the formulation of DEQS can be cast as a bi-level problem of the following form:
arg min [(2*) subject to
go (2") 0.
We will refer to the root finding problem (x() = as the inner problem, and call its resolution the forward pass. On the other hand, will refer to arg ming L(=*) the outer problem, and

---

Published as a conference paper at ICLR 2022
call the computation of the gradient of [(2*) w.r.t. 0 the backward pass. The core idea for DEQs is that their output 2* is expressed
fixed point of a parametric function fo from Rd to R i.e., go(=") = x² - [=²) = O. This model is said to have infinitely many weight-tied layers as =* can be obtained by successively applying the layer fo infinitely many times, provided fo is contractive. In practice, DEQs' forward pass is not computed by applying successively the function but usually relies on quasi-Newton (qN) algorithms, such as Broyden's 's method (Broyden, 1965), which approximates efficiently the Jacobian matrix das and its inverse for root-finding.
2g To compute DEQS' gradient efficiently and avoid high memory cost, one does not rely on back- propagation but uses the implicit function theorem (Krantz and Parks, 2013) which gives an analytical expression of the Jacobian of xt with respect 0, 0z" 200 While this method is memory efficient, requires the computation of matrix-vector products involving the inverse of a large Jacobian matrix, which is computationally demanding. To make this computation tractable, one needs to rely on an iterative algorithm based on vector-Jacobie products, which renders the training particularly slow, as highlighted by the original authors (Bai et al., 2020) (see also the break down of the computational effort in Section E.4).
Moreover, the formulation (1) allows us to also consider general bi-level problems such as hyper- parameter optimization under the same framework. For instance, hyperparameter optimization for Logistic Regression (LR) can be written as
min (va) subject to
= min ro(z) é (zran(z) + 01
(2)
where Lirain and Liaa correspond to the training and validation losses from the LR problem (Pedregosa, 2016). Here, = corresponds to the weights of the LR model while @ is the regularisation parameter. As the training loss is smooth and convex, the inner problem can be written as in (1) with go = Vera to fit (1). Similarly to DEQ, the inner problem is often solved using qN methods, which approximate the inverse of the Hessian in the direction of the steps, such as the LBFGS algorithm (Liu and Nocedal, 1989), and the gradient computation suffers from the same drawback as it is also obtained using the implicit function theorem. Lorraine et al. (2020) review the different hypergradient approximations for bi-level optimization and evaluate them on multiple tasks.
With the increasing popularity of DEQs and the ubiquity of bi-level problems in machine learning, a core question is how reduce the computational cost of the resolution of (1). This would make these methods more accessible for practitioners and reduce the associated energy cost, In this work, we propose to exploit the estimates of the (inverse of the) Jacobian/Hessian produced by qN methods in the hypergradient computation. Moreover, we also propose extra updates of the qN matrices which maintain the approximation property in the direction of the steps, and ensure that the inverse Jacobian is approximated in an additional direction. In effect, we can compute the gradient using the inverse of the final qN matrix instead of an iterative algorithm to invert the Jacobian in the gradient's direction, while stressing that the inverse of a qN matrix, and thus the multiplication with it, can be computed very efficiently.
We emphasize that the goal of this paper is neither to improve the algorithms used to compute 2", nor is it to demonstrate how to perform the inversion of a matrix in a certain direction as a stand-alone task. Rather, we are describing an approach that combines the resolution of the inner problem with the computation of the hypergradient to accelerate the overall process. Our work is the first to consider modifying the inner problem resolution in order to account for the bi-level structure of the optimization The idea to use additional updates of the qN matrices to ensure additional approximation properties not new, and it also known that a full matrix inversion can be accomplished in this way. For instance, Gower and Richtárik (2017) used sketching to design appropriate extra secant conditions in order to obtain guarantees of uniform convergence towards the inverse of the Jacobian. The novelty in our work is that we integrate additional update to yield the inverse in specific direction, which is substantially cheaper than computing the inverse. A concurrent work by Fung et al. (2021) is also concerned with the acceleration of DEQS' training, where the inverse Jacobian is approximated with the identity. Under strong contractivity and conditioning assumptions, it is proven that the resulting approximation is descent direction and the authors show good empirical performances for small scale problems.
The contributions of our paper are the following:
Herre, we do not explicitly write the dependence of fo on the input of the DEQ, usually referred to as the injection.
2

---

Published as a conference paper at ICLR 2022
We introduce method to greatly accelerate the backward pass of DEQs (and generally, the differentiation of bi-level problems) using qN matrices that are available as a by by-product of the forward computations. We call this method SHINE (SHaring the INverse Estimate).
We enhance this method by incorporating knowledge from the outer problem into the inner problem resolution. This allows us to provide strong theoretical guarantees for this approach various settings.
We additionally showcase its use in hyperparameter optimization. Here, we demonstrate that it provides a gain in computation time compared to olate-of-the-at methods.
We test it for DEQs for the classification task on two datasets, CIFAR and ImageNet. Here, we show that it decreases the training time while remaining competitive in terms of performance.
We extend the empirical evaluation of the Jacobian-Free method to large scale multiscale DEQs and show that it performs well in this setting. We also show that is not suitable for more general bi-level problems.
We propose and evaluate natural refinement strategy for approximate Jacobian inversion methods (both SHINE and Jacobian-Free)) that allows a trade-off between computational cost and performances.
HYPERGRADIENT OPTIMIZATION WITH APPROXIMATE JACOBIAN INVERSE
2.1 SHINE: HYPERGRADIENT DESCENT WITH APPROXIMATE JACOBIAN INVERSE
Hypergradient Optimization Hypergradient optimization is first-order method used to solve
Algorithm 1: qN method solve go(2")
Result: Root 2", qN matrix B
(1). We recall that in the case of smooth convex optimization, Oge is the Hessian of the inner op- timization problem, while for deep equilibrium models, it is the Jacobian of the root equation. In the rest of this paper, with a slight abuse of notation, we will refer to both these matrices with Jgo whenever the results can be applied to both contexts. To enable Hypergradient Opti- mization, i.c. gradient descent on L with respect to 8, Bai et al. (2019, Theorem 1) show the following theorem, which is based on implicit differentiation (Krantz and Parks, 2013):
b = true if using Broyden's s method,
b ea if using BFGS
n = 0, my = 0, By = while not converged do
Pn = B, 1 (z(),, 2n+1 = 2n + anPa // an can be I or determined by line-search
Yn = go(=n))) - go()))
Sn = 2n-1 2n
then
Bu+1 arg min ||- - BullF
X: Ns,
Theorem 1 (Hypergradient (Bai et al., 2019;
else
Krantz and Parks, 2013)), Let 0 E Rº be a set of parameters, let C Rd + R be a loss function and go R + Rd be root-defining function. Let 2* Rd such that go(2") 0 and J (z*) is invertible, then the gradient of the loss wrt. 0, called Hypergradient, given by
Bn+1
arg min
1X-1-B
X: X= x=x" A Axs
// The norm used in BFGS is weighted Frebenius nerm
end
JC
0e 2. = =V=[(2") Jg. (2*) Ogo
n f- n +
(3)
00
end
on. B Ba.
In practice, we use an algorithm to approximate =", and Theorem 1 gives plug-in formula for the backward pass. Note that this formula is independent of the algorithm chosen to compute 2t. Moreover, opposed to explicit networks, we do not need to store intermediate activations, resulting in the aforementioned training time memory gain for DEQs. Once =* has been obtained, one of the major bottlenecks in the computation of the Hypergradient is the inversion of Jgo (2") in the directions age or V L(=*).
Quasi-Newton methods In practice, the forward pass is often carried out with qN methods. For instance, in the case of bi-level optimization for Logistic Regression, Pedregosa (2016) used L- BFGS (Liu and Nocedal, 1989), while for Deep Equilibrium Models, Bai et al. (2019) used Broyden's.
3

---

Published as a conference paper at ICLR 2022
method (Broyden, 1965), later adapted to the multi-scale case in limited-memony version (Bai et al., 2020).
These quasi-Newton methods were first inspired by Newton's method, which finds the root of go via the recurrent Jacobian-based updates Zn+1 = Z/ gg,.),))) (=.)))) Specifically, they replace the Jacobian 'g (2n) by an approximation Bn that is based on available values of the iterates 2n and ge rather than its derivative. These B,. called qN matrices, are defined recursively via an optimization problem with constraints called secant conditions. Solving this problem leads to expressing B,, rank-one or rank-two update of B, so that B, is the sum of the initial guess Bo (in our settings, the identity) and low-rank matrices (less than in limited memory settings). This low rank structure allows efficient multiplication by B, and B We now explain how the use of qN methods as inner solver can be exploited to resolve this computational bottleneck.
SHINE Roughly speaking, our proposition is to use B-1 lim, B, as replacement for Jg (z*)-² in (3), i.c. to share the inverse estimate between the forward and the backward passes. This gives the approximate Hypergradient
0ge
pe V V
00
In practice we will consider the nonasympiotical direction Pa
(n)
(2,)),)BB
89g
Thanks
89
to the Sherman-Morrisse formula (Sherman and Morrison, 1950), the inversion of B, can be done very efficiently (using scalar products) compared to the iterative methods needed to invert the true Jacobian Jo (=*). In turn, this significantly reduces the computational cost of the Hypergradient computation.
Relationship to the Jacobian-Free method Because Bo = in our setting, we may regard as an identity matrix perturbed by few rank-one updates. In the directions that are used for updates, B is going to be different from the identity, and hopefully closer to the true Jacobian in those directions. However, in all orthogonal directions we fall exactly into the setting of the Jacobian-Frre Free method introduced by Fung et al. (2021). In that work, Jn, (=*)-1 is approximated by 7, and the authors highlight that this is equivalent to using preconditioner on ge they show that this preconditioned gradient is still a descent direction.
the gradient. Under strong assumptions
Transition to the exact Jacobian Inverse. The approximate gradient (()) can also be used as the initialization of an iterative algorithm for inverting Jo (=*) in the direction v=C(z"). With good initialization, faster convergence can be expected. Moreover, if the iterative algorithm is also a qN method, which is the case in practice in the DEQ implementation, the forward pass to initialize the qN matrix of this algorithm. We refer to this strategy as the refine strategy. Because the refine strategy is essentially smart initialization scheme, it recovers all the theoretical guarantees of the original method (Bai et al., 2019; 2020; Pedregosa, 2016).
the qN matrix B from
2.2 CONVERGENCE TO THE TRUE GRADIENT
(m)
To further justify and formalize the idea of SHINE, we show that the direction Pa converges to the Hypergradient ac
We now collect the assumptions that will be used for this purpose.
30
Assumption 1 (Uniform Linear Independence (ULI) (Li et al., 1998)). There exist positive constant P > and natural numbers no and m d with the following property: For any n 2 no we can find indices n S. nh S... S Rd S n + m. such that, for Pn. defined in Algorithm 1, the smallest singular value of the d d matrix
Pos Pan
Pug Pog
Prd IP
T
is no smaller than Assumption 2 (Smoothness and convergence to the fixed point). (i) Eneo || 20 < oo for some zn with go (=*) = 0; (ii) go is C², Jg is Lipschitz continuous near 2,, and Jg (2*) is invertible; (iii) V.L is continuous, and V0, 0gs is continuous.
50
Remark. The Assumption 2 (i) implies lim Fn = =² The existence of the Jacobian and its
inverse assumptions that are already made in the regular DEQ setting just to train the model.
4

---

Published as a conference paper at ICLR 2022
Theorem 2 (Convergence of SHINE to the Hypergradient using ULI). Let denote Pg direction for iterate n in Algorithm with = true. Under Assumptions and 2, for given parameter 0, (2n) converges q-superlinearly to z* and
(x)) the SHINE
0c
lim R2 2=000
Pg
(n)
00 1-*
Proof. From More and Trangenstein (1976, Theorem 5.7) we obtain that lim B, = Jg. (z*). We can then conclude using the continuity of the inversion operator the space of invertible matrices and of the right and left matrix vector multiplications. A complete proof is given in Section B. 0
Theorem 2 establishes convergence of the SHINE direction to the true Hypergradient, but relies on Assumption 1 (ULD) While ULI is often used to prove convergence results for qN matrices, e.g. in (Conn et al., 1991; Li et al., 1998; Nocedal and Wright, 2006), it is strong assumption whose satisfaction in practice is debatable, cf., e.g., (Fayez Khalfan et al., 1993). For Broyden's method, ULI is violated in all numerical experiments in (Mannel, 2020; 2021a;b), and those works also prove that ULI is necessarily violated in certain settings (but the setting of this work is not covered). In the following we therefore derive results that do not involve ULI.
2.3 OUTER PROBLEM AWARENESS
The ULI assumption guarantees convergence of B to Jg. (z*)-1, However, (3) only requires the multiplication of J (=*)-1 with dge
2y from the right and V=f(=*) from the left.
BFGS with OPA In order to strengthen Theorem let us consider the setting of bi-level op- timization with single regularizing hyperparameter 0. There, the partial derivative dgg
80 I2- is
d-dimensional vector and it is possible to compute its approximation 8ge 1=. at a reasonable cost. ae
We propose incorporate additional updates of the quasi-Newton matrix Bn into Algorithm I that improve the approximation quality of B in the direction 0go l=., (thus asymptotically in the direction B9e 2+)). Given a current iterate pair (zn, B,), these additional updates only change B,, but 86
0ge
not Zn. We will demonstrate that a suitable update direction en E IR is given by
On = B, B- 8ge
(5)
00
where (tn) C [0, xo) satisfies Σn, in < 0.. This update direction will be used to create an extra secant condition X- (go(Zn + e,,) go (2x)) = en for the additional update of B,, Since this extra update is based on the outer problem, we refer to this technique Outer-Problenn Awareness (OPA). The complete pseudo code of the OPA method in the LBFGS algorithm (Liu and Nocedal, 1989) is
given in Appendix A.
We now prove that if extra updates are applied at a fixed frequency, then fast (q-superlinear) conver- gence of (2,)) to 2* is retained, while convergence of the SHINE direction to the true Hypergradient is also ensured. To show this, we use the following assumption.
Assumption (Assumptions for BFGS). Let go(z)= V (zz for some C2 function re d R. Consider Algorithm I with b = false. We assume some regularity on r and that an appropriate line search used. An extended version of this assumption is given in Section B.2 (Assumption 5).
(m)
Theorem 3 (Convergence SHINE to the Hypergradient for BFGS with OPA), Let us consider Pe the SHINE direction for iterate n in Algoritium 1 that is enriched by extra updates in the direction en defined in (5). Under Assumptions 2 (ūi-iü)) and 3, for a given parameter 0, we have the following: Algorithm 1, for any symmetric and positive definite matrix Bo, generates sequence (zn) that converges q-superlinearly to z,, and there holds
lim 22030
Pg
(n)
OL
(6)
00
Proof. It follows from known results that the extra updates do not destroy the q-superlinear conver- gence of (z.). The proof of (6) relies firstly the fact that by continuity of the derivative of ge. Bgg
we have lim,-+oc 0gg s.. Ø6 I Due to the extra updates can show convergence of the qN matrices to the true Hessian in the direction of the extra steps e,, from which (6) follows. A full proof is provided in Section B.2.
5

---

Published as a conference paper at ICLR 2022
Remark. Theorem 3 also holds without line searches (i.e., on = for all n.) and any C² function re (such that (z) = vo (a(()) (2)) with locally Lipschitz continuous Hessian if 2g is close enough to some and T==T=(2") positive definite.
2" with V V=ro(2*)
We note that Theorem 3 guarantees fast convergence of the iterates (z,) and that does not have to be close to 2" for that guarantee. Also, there is no restriction on Bg other than being symmetric and positive definite (which is satisfied for our choice Bo = I). Finally, Theorem 3 does not rely on ULL. From a practical standpoint we thus regard Theorem as a much stronger result than Theorem 2.
Adjoint Broyden with OPA It is not practical to use the partial derivative dge the DEQ setting D0 because it is a huge Jacobian that we do not have access to in practice. In order to still leverage the core idea of OPA, we propose to use extra updates that ensure that B,," approximates Ngs (z*)* in the direction V v=*(=*) applied by left left-multiplicttonn, condition given by
required by (3). An appropriate secant
6n Ba+1 = TT. Jao (2n+1),
where
(8) To incorporate the secant condition (7), we use the Adjoint Broyden's method (Schlenkrich et al., 2010), a qN method relying on the efficient vector-Jacobian multiplication by Jgs using auto- differentiation tools. To prove convergence of the SHINE direction for this method, we need the following assumption.
o (
Assumption 4 (Uniform boundedness of the inverse qN matrices). The sequence (Bn) generated by Algorithm I satisfies
B co.
sup EEN
Remark. Convergence results for quasi-Newton methods usually include showing that Assumption 4 holds, cf. Broyden et al. (1973, Theorem for Broyden's 's method and the BFGS method, respectively, Schlenkrich et al. (2010, Theorem 1) for the Adjoint Broyden's 's method. It can also be proved that Assumption 4 holds for globalized variants of these methods, e.g., for the line-search globalizations of Broyden's 's method proposed by Li and Fukushima (2000). We point out that Assumption I entails lim Bn = Jge (z*) and thus lim B = Jg (zt)= so it is clearly stronger than Assumption 4.
Theorem (Convergence of SHINE to the Hypergradient for Adjoint Broyden with OPA). Let us (n) the SHINE direction for iterate in Algorithm I with the Adjoint Broyden secant condition (7) and extra update in the direction v, defined in (8). Under Assumptions and 4, for a given parameter have g-superlinear convergence of (zn) to z and
consider Pe
OL
lim Pg
(n)
30
Proof. The g-superlinear convergence of (zn) follows from Schlenkrich et al. (2010, Theorem 2). To establish convergence of the SHINE direction, we proceed in three steps. First, is shown that for v=L(=*) = the claim holds due continuity and Assumption 4. Then V=L(=*) * O is considered and it is proved that the desired convergence holds on the subsequence that corresponds to the additional updates. Lastly, this result transferred the entire sequence by involving the fixed frequency of the additional updates. The complete proof is provided in Section B.3.
Using the Adjoint Broyden's method comes at a computational cost. Indeed, because we now rely on g we have to store the activations of go()) (which has a computational cost in addition to memory cost), but also perform the vector-Jacobian product in addition to the function evaluation.
RESULTS
We test our method in 3 different setups and compare it to the original iterative inversion and its closest competitor, the Jacobian -eree method (Fung et al., 2021). We draw the reader's 's attention to the fact that although the Jacobian-Fres method (Fung et al., 2021) used outside the assumptions needed to have theoretical g of descent, it still performs relatively well in the Deep Equilibrium setting. The same is true for SHINE: While the ULI assumption is not met (and we are in practice far from the fixed point convergence), it performs well in practice.
"Se the results contractivity in Scction F.3.

---

Published as a conference paper at ICLR 2022
SHINE (ours)
SHINE refine (ours)
HOAG
Jacobian-Free
Grid search
20news
real-sim
10a
Test, Loss Suboplimality
10a
10a
102
10
10
10
100
10
10-1
10
20
30
40
50
60
0 5
10
15
20
25
30
Time (s)
Time (8)
Convergence of held-out test loss for different hyperparameter opti- mization methods the fz-regularized logistic regression problem for the datasets (20news (Lang, 1995) and real-sim (lib)) SHINE achieves the best performances for both problems while the Lacobian-Frea method is much slower, particular 20news. Note that the kink for HOAG real-sim does not mean it is better as the optimization stops once the validation loss has converged and not the one. The typical loss order of magnitude 102. An extended figure with more methods is provided in Section E.
Figure 1: Bi-level optimization:
Implementations. All the bi-level optimization experiments were done using the HOAG code (Pe- dregosa, 2016)', which based on the Python scientific ecosystem (Harris et al., 2020; Pedregosa et al., 2011; Virtanen et al., 2020). Deep Equilibrium experiments were done using the Py- Torch (Paszke et al., 2019) code for Multiscale DEQ (Bai et al., 2020)', which was distributed under the MIT license. Plots were done using Matplotlib (Hunter, 2007), with Science Plots style (Garrett and Peng, 2021). DEQ trainings were done in publicly funded HPC, on nodes with 4 V100 GPUs. In practice, never reach convergence of (z,). hence the approximate gradient might be far from the true gradient. To improve the approximation quality, we now propose a variant of our method.
Fallback in the case of wrong inversion. Empirically, we noticed that using B can sometimes produce bad approximations, although with very low probability. We propose to detect this with by monitoring a telltale sign based on the norm of the approximation, as we verified on several examples that cases with a huge norm compared to the correct inversion also had a very bad correlation with the correct inversion. In these cases, we can simply fallback onto another inversion method. For the Deep Equilibrium experiments, when the norm of the inversion using SHINE is 1.3 times above the norm the inversion using the Jacobian-Fire method (which available at no extra computational cost), we use the Jacobian-Free inversion. We refer to this strategy as the fallback strategy.
3.1 BI-LEVEL OPTIMIZATION MAAAAITONN-YEERRRAAAAAAA HYPERPARAMETER OPTIMIZATION IN LOGISTIC REGRESSION
We first test SHINE in the simple setting of bi-level optimization for fz-regularized LR, using the code from Pedregosa (2016) and the same datasets. Convergence on unseen data is illustrated in Figure 1.5 An acceptable level of performance is reached twice faster for the SHINE method compared to any other competitor. Another finding is that the refine strategy does not provide definitive improvement over the vanilla version of SHINE. In order to verify that the performance gain of SHINE is not simply driven by truncated inversion, we also HOAG with limited number of inversion iteration and showed that this degrades its performances (see HOAG limited backward in Section E. We also tested our implementation of OPA the 20news dataset and present the results in Figure 2. In order to get fair comparison, we implemented both SHINE, SHINE-OPA and HOAG using the same
Phttps:/ / thub. com/ hoom/fal aabiann/hhaag 'https: //g thub. com/ oocu aab/mdds/
'To facilitate the reader's understanding of the figures, we plot the empirical suboptimality, but we do remind them that there is guarantee of convergence on held-out test data the kink present in the case of the real-sim datasct is example of that.
7

---

Published as a conference paper at ICLR 2022
Test Loss Suboptimality
10a
Direction
HOAG
Prescribed
Krylov
Random
10a
SHINE (ours)
SHINE OPA (ours)
1.000
10
cossim (a.
0.998
100
0.996
10-1
0.991
60
100
1.05
1.10
Time (s)
||||//|b||
Figure 2: Bi-level optimization with OPA: (left) Convergence of different hyperparameter opti- mization methods the fg-regularized LR problem for the 20news dataset (Lang, 1995) held-out test data. SHINE with OPA achieves similar performance as SHINE without OPA but with better con- vergence guarantees. (right) Evaluation of the inversion quality in direction using OPA b B compared to the exact inverse a = J9s (2*)=1 ' for 3 different directions: the prescribed direction, the Krylov direction and a random direction. The points represent the cosine similarity between and b as a function of the ratio of their norm and the closer to (1, the better. The inverse in the prescribed direction is better than random direction.
full Python code instead of relying on the original code which relied on the Fortran implementation of L-BFGS from (Virtanen et al., 2020). While SHINE with OPA does not outperform the vanilla SHINE, it reaches similar performances, outperforming HOAG, and comes with strong theoretical grounding. Additional results on hyperparameter optimization for the regularized nonlinear least squares problem are available in Section E.2.
We also showed on a smaller dataset, the breast cancer dataset (Dua and Graff, 2017). that OPA indeed ensures better approximation of the inverse in the prescribed direction. For a given split of the data, we compared the quality the approximation of the inversion in three different direc- tions: prescribed direction chosen randomly but used for the OPA update, the Krylov direction
BBg (zn -1) and a random direction not used in the qN algorithm. The results for 100 runs de
with different random seeds are depicted in Figure 2, where we can observe that OPA indeed ensures better inversion in the prescribed direction compared random direction. We also notice that poor direction for the inversion seems correlated with a small magnitude.
3.2 DEEP EQUILIBRIUM MODELS
Next, we tested SHINE on the more challenging DEQ setup. Two experiments illustrate the perfor- mance of SHINE on the image classification task on two datasets. For both datasets, we used the same model configuration in the original Multiscale DEQ paper (Bai et al., 2020) and did not fine tune any hyperparameter. For the different DEQ training methods, models for a given seed share the same unrolled selllee-pretainingg steps. We do not include OPA in the DEQ results because while the gradients are well correlated with the true ones (see Figure E.3), we observe sharp initial performance drop that reduces its performance on Imagenet. We provide partial results Section E.5.
CIFAR-10. The first dataset is CIFAR-I0 (Krizhevsky, 2009) which features 60,000 32x32 images representing 10 classes. For this dataset, the size of the multi-scale fixed point is d = 50k. We train the models for five different random seeds.
The results in Figure 3 show that for the vanilla version, SHINE slightly outperforms the Jacobian- results suggest that SHINE (in its vanilla version)
Free method (Fung et al., 2021). Additionally, is able to reduce the time taken for the backward pass almost 10-fold compared to the original method while retaining a competitive performance (on par with Res-Net-18 (He et al., 2016) 92.9% Finally, we do highlight that the Jacobian- -Feee method (Fung et al., 2021) 1) is able to perform well outside the scope of its theoretical assumptions, albeit with slightly worse performance than SHINE. We conjecture that the batched stochastic gradient descent helps accelerated methods by averaging out the errors made in the approximation.
ImageNet. The second dataset is the ImageNet dataset (Deng al., 2009) which features 1.2 million images cropped to 224 x 224, representing 1000 classes. This dataset is recognized as a large-scale computer vision problem and the dimension of the fixed point to find is d 190k.
8

---

Published as a conference paper at ICLR 2022
CIFAR10
Vanilla
Refied
93.5
Methods
Original Method
Jacobian-Free
03.0
Top-1 accuracy (%)
SHINE (ours)
92.5
25
50
75
100
125
150
175
200
#
Backward iter.
ImageNet
Vanilla
Vanilla
Refined
2
10
74
Full backward
0
100
200
300
400
500
600
700
800
Backward pass wall-clock time [ms]
Figure 3: DEQ: Top-1 accuracy function of backward pass runtime for the different methods considered to train DEQs, on CIFAR (Krizhevsky. 2009) and ImageNet (Deng et al., 2009). The original DEQ training method corresponds to the Full backward pass points and the vanilla SHINE and Jacobian-Free methods correspond to direct use of the inverse approximation without further refinement. The other points correspond to further refinements of the different methods with different number of iterations used to invert Jne (z*) ) in the direction of (z²(,,). This highlights the trade-off between computations and performances driving the refinement choice.
For this challenging task, we noticed that the vanilla version of SHINE was suffering a big drop just after the transition from unrolled pre-training actual equilibrium training. To remedy partly this problem, we introduced the fallback to Jacobian- inversion. The results for a single random seed presented in Figure for the ImageNet dataset are given for SHINE with fallback. The fallback is barely used: in 1000 batches of size 32, only 2 samples used fallback, a proportion of 6.25 x 10-5. Despite the drop suffered at the beginning of the equilibrium training, SHINE in its refined version is able to perform on par with the Jacobian-Free method (Fung et al., 2021). We also confirm the importance of choosing the right initialization to perform accelerated backpropagation, by showing that with limited iterative inversion, the performance of the original method deteriorates. Finally, while the drop in performance for the accelerated methods is significant when applied in their vanilla version, we remind the reader that no fine-tuning was performed on the training hyperparameters, making those results encouraging (on par with architectures like ResNet- 18 (He et al., 201
The key take-away from Figure 3 is that both SHINE and Jacobian-Free approximation methods allow accelerate the DEQ's s backward pass at relatively low accuracy cost." 6 Moreover, using the proposed refined versions of these methods, the performance drop can be traded-off for acceleration.
4 CONCLUSION AND DISCUSSION
We introduced SHINE, a method that leverages the qN matrices from the forward pass to obtaín an approximation of the gradient of the loss function, thereby reducing the time needed to compute this gradient. We showed that this method can be used on a wide range of applications going from bi-level optimization to small and large scale computer vision tasks. We found that both SHINE and the Jacobian-Free method reduce the required amount of time for the backward pass of implicit models, potentially lowering the barriers for training implicit models.
As those methods still suffer from small performance drop, there room for further improvement. In particular, a potential experimentation avenue would be to understand how to balance the efforts of the Adjoint Broyden method in order to come closer to guaranteeing the asymptotical correctness of the approximate inversion. On the theoretical side, this may involve the rate of convergence of the approximated gradient. It also seems desirable to develop a version of Theorem 4 in which convergence of (z,,) to 2" is not assumption but rather follows from the assumptions, as achieved in Theorem 3. We have no doubt that the contraction assumption used for the Jacobian-Free method would allow to prove such a result, but expect that significantly weaker assumption will suffice.
Moore on the overall computational effort be found in Table E.2

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
We provide with the submission of this paper the full code necessary to reproduce the figures and the other quantitative results of the paper, from the training, the evaluation and the actual figure drawing. We made sure to use seeds and verified that the seeding was indeed allowing reproducible results. We also provide time estimates for the reproduction of the figures. We made sure provide the full proofs for our theorems in the supplementary material of this manuscript. The core concepts used in the proofs, and their sketches are also laid out in the main text.
REFERENCES
Libsvm datasets. datasets/. Accessed: 2021-05-06.
B. Amos and J. Zico Kolter. OptNet: Differentiable Optimization as a Layer in Neural Networks, In ICML, 2017.
S. Bai, J. Z. Kolter, and V. Koltun. Deep equilibrium models. In NeurlPS, 2019.
S. Bai, V. Koltun, and J. Z. Kolter. Multiscale deep equilibrium models. In NeurIPS, 2020.
A. Berahas, M. Jahani, Richtárik, and M. Takáč. Quasi-Newton Methods for Machine Learning: Forget the Past, Just Sample. Optimization Methods and Software, 2021.
J. Bergstra and Y. Bengio. Random Search for Parameter Optimization Yoshua Bengio. Journal of Machine Learning Research, 13:281-305, 2012.
C. G. Broyden. A Class of Methods for Solving Nonlinear Simultaneous Equations. Mathematics of Computation, 19(92):577-58) 1965.
C. G. Broyden, J. E. jun. Dennis, and J. J. More. On the local and superlinear convergence of quasi-Newton methods. Journal of the Institute of Mathematics and its Applications, 12:223-245, 1973.
R. H. Byrd and J. Nocedal. A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM Journal on Numerical Analysis, 26(3):727-739, 1989.
R. H. Byrd, R. B. Schnabel, and G. A. Shultz. Parallel quasi-Newton methods for unconstrained optimization. Mathematical Programming. Series A. Series B, 42(2 (B)):273-306, 1988.
R. T. Chen, Y. Rubanova, J. Bettencourt, and D. Duvenaud. Neural Ordinary differential equations. In NeurlPS, 2018.
Chen, Xu, Zhang, and C. Guestrin. Training Deep Nets with Sublinear Memory Cost. Technical report, 2016.
A. R. Conn, N. I. Gould, and P. Toint. Convergence of quasi-Newton matrices generated by the symmetric rank one update. Mathematical Programming, 50(1-3):177-195, 1991. ISSN 00255610. doi: 10.1007/BF015594944
Deng, W. Dong, R. Socher, L.-J Li, Kai Li, and Li Fei-Fei. ImageNet: large-scale hierarchical image database. In CVPR. Institute of Electrical and Electronics Engineers (IEEE), 2009.
D. Dua and C. Graff. UCI machine learning repository, 2017. URL http::/archive. uci. edu/ml.
H. Fayez Khalfan, R. H. Byrd, and R. B. Schnabel. A theoretical and experimental study of the symmetric rank-one update. SIAM Journal on Optimization, 1124 1993.
S. W. Fung, H. Heaton, Q. Li, D. Mckenzie, S. Osher, and W. Yin. Fixed Point Networks: Implicit Depth Models with Jacobian-Fres Backprop. Technical report, 2021.
D. Garrett and H.-H. Peng. garreti4033SciencePlos,, Feb. 2021. URL htthtp///doi..o///// 5281 2011/zenode 41 4106649.
10

---

Published as a conference paper at ICLR 2022
D. Gilton, G. Ongie, and R. Willett. Deep Equilibrium Architectures for Inverse Problems in Imaging. Technical report, 2021.
A. N. Gomez, M. Ren, R. Urtasun, and R. B. Grosse. The Reversible Residual Network: Backpropa- gation Without Storing Activations. In NIPS, 2017.
R. M. Gower and P. Richtárik. Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms. SIAM Journal on Matrix Analysis and Applications, 38(4):1380-1409, 2017.
C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, Taylor, Berg, N. Smith, R. Kern, M. Picus, Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant, K. Sheppard, T. Reddy, W. Weekesser, H. Abbasi, C. Gohlke, and E. Oliphant. Array programming with NumPy. Nature, 585(7825):357-362, 2020.
K. He, X. Zhang, Ren, and J. Sun. Deep residual learning for image recognition. In CVPR, 2016.
H. Heaton, S. W. Fung, A. Gibali, and W. Yin. Feasibility- based Fixed Point Networks. Technical report, 2021.
J. D. Hunter. Matplotlib: A 2D graphics environment. Computing in Science and Engineering, 9()): 90-95, 2007.
D. P. Kingma and J. L. Ba. Adam: A method for stochastic optimization. In ICLR. International Conference on Learning Representations, ICLR, 12 2015.
S. G. Krantz and H. R. Parks. The Implicit Function Theorem: History, Theory, and Applications. Springer New York, 1 2013.
A. Krizhevsky. Learning Multiple Layers of Features from Tiny Images. Technical report, 2009.
K. Lang. NewsWeeder: Learning Filter Netnews. In ICML, pages 331-339. Elsevier, 1995.
D. Li and M. Fukushima. derivative-free line search and global convergence of Broyden- method for nonlinear equations. Optimization Methods & Software, 13(3):181-201, 2000.
D. J. and Zhou. Convergence of Broyden-Like Matrix. Applied Mathematics Letter, (5):35-37, 1998.
D. C. Liu and Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, Series B, 45(3):003-528, 1989.
Lorraine, Vicol, and Duvenaud. Optimizing Millions of Hyperparameters by Implicit Differentiation. In AISTATS, 2020.
Mannel. On the convergence of the Broyden-like matrices. 2020.
Mannel. Convergence properties of the Broyden-like method for mixed linear-nonlinear systems of equations. Numerical Algorithms, pages 1-29, 2021a.
Mannel. On the convergence of Broyden's method and some accelerated schemes for singular problems. 2021b.
J. More and Trangenstein. On the global convergence of Broyden's method. Mathematics of Computation, 30:523-540, 1976.
Nocedal and Wright. Quasi-Newton Methods. In Numerical Optimization, pages 135-163. 2006.
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch: An Imperative Style, Higg-Perffrmance Deep Learning Library. In NeurIPS, 12 2019.
11

---

Published as a conference paper at ICLR 2022
F. Pedregosa. Hyperparameter optimization with approximate gradient. 33rd International Conference on Machine Learning. JCML 2016, 2: 2:1150-1159, 2016.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine Learning in Python Gaël Varoquaux Bertrand Thirion Vincent Dubourg Alexandre Passos PEDREGOSA, VAROQUAUX, GRAMFORT ET AL. Matthieu Perrot. Journal of Machine Learning Research, 12:2825-288 2830,, 2011.
M. E. Sander, P. Ablin, M. Blondel, and G. Peyré. Momentum Residual Neural Networks. Technical report, 2021.
S. Schlenkrich, den methods. Mathematical Programming, 121(2):221-47,, 2010. ISSN 14364646. doi:
A. Griewank, and A. Walther. On the local convergence of adjoint Broy-
J. Sherman and W. J. Morrison. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. The Annals of Mathematical Statistics, 21(1):124-177, 1950.
M. Telgarsky. Benefits of depth in neural networks. Journal of Machine Learning Research, (9une))) 1517-1539, 2 2016.
P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. Nelson, E. Jones, R. Kern, E. Larson, J. Carey, I. Polat, Y. Feng, E. W. Moore,
J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris,
A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. Mulbregt, A. Vijaykumar,
P. Bardelli, A. Rothberg, A. Hilboll, A. Kloeckner, A. Scopatz, A. Lee, A. Rokem, C. N. Woods, C. Fulton, Olivetti, V. Pasechnik,
C. Masson, C. Häggström, C. Fitzgerald, D. Nicholson, R. Hagen,
E. Martin, E. Wieser, F. Silva, F. Lenders, F. Wilhelm, G. Young, G. A. Price, G. L. Ingold. G. E. Allen, R. Lee, Audren, Probst, J. P. Dietrich, Silterra, J. T. Webber, J. Slavić, Nothman, J. Buchner, J. Kulick, J. L. Schönberger, J. V. de Miranda Cardoso, J. Reimer, J. Harrington, J. L. C. Rodríguez, J. Nunez-Iglesias,
Kuczynski, K. Tritz, M. Thoma, M. Newville, M. Kümmerer, M. Bolingbroke, M. Tartre, M. Pak, N. J. Smith, N. Nowaczyk, N. Shebanov, O. Pavlyk, P. A. Brodtkorb, P. Lee, R. T. McGibbon, R. Feldbauer, S. Lewis, S. Tygier,
Sievert, S. Vigna, S. Peterson, S. More, T. Pudlik, T. Oshima, T. J. Pingel, T. P. Robitaille, T. Spura, T. R. Jones, T. Cera, T. Leslie, T. Zito, T. Krauss, U. Upadhyay, Y. O. Halchenko, and Y. Vázquez-Baeza SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Methods, 1763):261-272. 3 2020.
P. Xu, F. Roosta-Khorasan Khorasani, and M. W. Mahoney. Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study. In Proceedings of the 2020 SIAM International Conference on Data Mining, 2020.
12

---

Published as a conference paper at ICLR 2022
A OPA ALGORITHM
Algorithm LBFGS:
(Limited memory) BFGS method with OPA
Input: initial guess (2o. ") where B symmetric and positive definite, tolerance > 0,
frequency of additional updates M E N, memory limit L N U (oc), (t,) null
sequence of positive numbers with En la < 00
Let F = =90
for n. = 0, U.... do
[ I then let
Zn and let B == Bni STOP
Let B,² : B-
if (n mod M) then
let en = b B,
Oge 80
Un =- Fzn en) (zn) and in (en)² ( In
n then
let ân En B In and let
an (ex) (ān)
(ān) Dn en en (
B_ B
fn
(fn)²
Let B :- B=11
nn 2 then remove update n - L from B=²
Let Ps == F
Obtain an line-search and let 8n anPn
Let Sa+1 Zn + 8n, Un = F(zn+1) F(2n) and r. (sn)
r. then let On Sn B yn and let
Bii B an(sn) sa(an)
(an)
sn (s
(rn)²
Tn
else let B B if n 2 L then remove update L from B Output: z", B
Remark. A possible choice for (1,) is to use an arbitrary to > 0 and L, ||8a-1|| 1nl or 2
B PROOFS OF SHINE CONVERGENCE
To facilitate reading, we restate the results before proving them.
B. CONVERGENCE USING ULI
(a) Theorem (Convergence SHINE to the Hypergradient using ULI). Let us denote Pe p9 the SHINE direction for iterate in Algorithm with b = true. Under Assumptions and 2, for given parameter 0, (zn) converges g-superlinearly to = and
(n) JL
lim Pg n 2=000
00 :.
Proof. Under Assumptions 1 and 2, More and Trangenstein (1976, Theorem 5.7) shows that B, satisfies
lim B, (2")
The inversion operator is continuous in the space of invertible matrices, we have:
lim B- = Jg (=")-1 n-000
Because V.L and Oge tion 2 (i):
continuous 2* by Assumption 2 (ii), we also have thanks to Assump- 89
dge 00 s..
0ge
lim VzL(zn) vzL(=*)
and
lim n-
00 2*
13

---

Published as a conference paper at ICLR 2022
By continuity then deduce that, claimed,
lim Pa (n) lim V 1 Age
0go
0L
(zn) V=L(=") (2*)
00
00
00
B.2 CONVERGENCE FOR BEGS WITH OPA
Assumption 5 (Extended Assumptions for BFGS). Let go(2) = Varo(z) for some C² function
ro R R. Consider Algorithm with b false and suppose that
1. the set Q == {z E R ræ(z) I ra(2o)} is convex;
2. To is strongly convex in an open supersel of S2 (this implies that ve has a unique global minimizer 2*) and has Lipschitz continuous Hessian near zt;
3. there are positive constants n, n2 such that the line search used in the algorithm ensures that for each n 2 O either
Vro(Zn) Pm
ro(Zn+1) S (o(())) 771
ro(2n+1) S re((n) + mp Vro(zn)*
||
is satisfied;
4. the line search has the property that an = 1 will be used if both
[B,,, Jyo (2n (2m))
and
|| - 2"|l
|sa|||
are sufficiently small.
Remark. The requirements 3. and on the line search are, for instance, satisfied under the well-known Wolfe conditions, see Byrd et al. (1988, section 3) for further comments.
(n)
Theorem 3 (Convergence of SHINE the Hypergradient for BFGS with OPA). Let us consider Pa the SHINE direction for iterate in Algorithm I that is enriched by extra updates in the direction en defined in (5). Under Assumptions 2 (ii-ii) and 3, for a given parameter 0, we have the following: Algorithm 1, for any symmetric and positive definite matrix Ba, generates sequence (zn) that converges q superlinearly to 2", and there holds
Oc
lim Pg 22000
(m)
(6)
06
Proof. The proof is divided into four steps. The first step is to establish the qusuperlinear convergence of (2x) ) to z² Denoting by Ne C {0, M, 2M,...] j the set of indices of extra updates that are actually
applied, the second step consists of showing
lim N00
(Bn J9 (2*))
en = O,
|cc,]]
where, in this proof, B, always represents the matrix from Algorithm LBFGS before the update in the direction e, is applied, i.e., the matrix whose inverse appears the definition of en, while B, always represents the matrix from Algorithm LBFGS after the update in the direction 6n has been applied: if the update in the direction e,, is not applied, then B, B,. The third step is to prove that (9) implies the desired convergence (6) of the SHINE direction if the limit n > oo is replaced by Ne -> oc, i.e., the limit is taken the subsequence corresponding to Ne. The fourth step is then to transfer the convergence to the entire sequence.
is easy to check that instead of updating B," respectively, В-1 we can also obtain the sequences (Ba) and (B..) by updating according to
Ba+1 = Bn + Yn
Bn Bnsn(Bn,n)
y 8n
a Bn S 0), respectively,
for the usual update (skipping the update if vIT 8n
B, Bn + Dn1h Bren (Bnen)
07 en
c/. BnCn
for the extra update (skipping the update 8% e, I 0). Here, the quantities yn. In and e, are defined as in Algorithm LBFGS. We can now argue essentially in the proof of Byrd al. (1988,
14

---

Published as a conference paper at ICLR 2022
Theorem 3.1) to show that (2,)) converges q-superlinearly to 2". As part of that proof we obtain that
BR # BB for least [0.5Q] of the indices 0, M, 2,,2M..-. ,...,,,, QM for any Q E N (namely for all
E Ne satisfying - QM) and that we can apply Byrd and Nocedal (1989, Theorem 3.2), which yields
lim (Bn, - Jgo (2*)) 70000
and
lim (B, -go Nean-000
Cn ||e,ll
0.
(10)
|sall
For the third step, we abbreviate Un
age 00
From the definition of en, and (10) we infer that
F..
0
lim (Bn, Jgo (2")) N.0
en
lim N.an-o0
(T- (= B
Un
After multiplication with Jo (=*)-1 this entails
lim Nean-200
BT²
Un
0,
1Br+tppl
which shows that
-
lim Nean
v = lim Io (=-) -ou
Neen-to0
08
by Assumption 2 (iii). Using Assumption (iii) again it follows that
lim (n) lim VeL(2n) N0
Ogo
00 = V=
0go
0L
N.3n-t00
08
00
concluding the third step. To infer that (6) holds, suffices show that lim B,, for any sequence (fn men,, C. N such that (Ja. Jn + .t........................ n- 1--]NN,, = @ for all n E Ne sufficiently
large. Indeed, since for == max [Ba]] sup, B, []], which finite by Byrd and Nocedal (1989, Theorem 3.2), there holds
(B,) c { E Rddd gaxd
A exists, |||| S C, ||
and the set on the right-hand side of the inclusion is compact by the Banach lemma, inversion is a uniformly continuous operation on this set, hence 1im [ BJ 1| = 0, so
lim IPP (n)
(1m)
Po
N.3n
by continuity, and therefore
lim
Pe
(1a)
lim
Pg
(n) ØC
N.an-oc
N.
00
by the third step, establishing the claim.
remains to show the validity of an- || - 0 for any sequence (Jn)NEN, such that {Ja, Jn + 1...., n - 1} n N. = @ for all n E N, sufficiently large. Since at least every second extra update is actually carried out, the condition on the intersection implies n - Jn S 2M 1 for all these n. Now let (Jn)neN, be any such sequence. Then B, - By, = Em= Bm+1 - Bm is a sum of most 2MM BFGS updates in search directions, but contains no extra updates. Hence, the secant conditions Bn-18n 1-1 1n- I {0, 1, ,,, j. are satisfied, allowing to deduce
[1(Bn1 Bp-1-1)8n-1e
Ba-t - Ba-t-1l1
1 ||
|1
g )8n-1-111 [1(Ba-1-1 |
Jgo (2*)))nn--1l
|
for all E {0,1....., In 13. For each of these I, both terms on the right- side tend to zero for No 3 n (for the second term this follows from the first identity in (10) due B,-1-1 B,-1-1). Recalling that B,, Bj, Σm= Br+1 Bm, we find limn |B, B, which finishes the fourth step and thus concludes the proof.
15

---

Published as a conference paper at ICLR 2022
B.3 CONVERGENCE FOR ADJOINT BROYDEN WITH OPA
Theorem (Convergence of SHINE to the Hypergradient for Adjoint Broyden with OPA), Let us consider Pg (x6) the SHINE direction for iterate in Algorithm I with the Adjoint Broyden secant
condition (7) and extra update in the direction Un defined in (8). Under Assumptions and 4, for given parameter 0, we have g-superlinear convergence of (zn) to xt and
0L
lim Pb R=000
(n)
00 2.
Proof. Due Assumption 2, the superlinear convergence of (z^) follows from Schlenkrich al. (2010, Theorem 2). The proof of the remaining claim is divided into two cases.
Case 1: Suppose that V v=[(2*) O. By continuity this implies - v=[(z,) 0. Since the 2gu sequence (Br²) 00
l.,) is bounded by Assumption follows that
(n) lim Pe
lim VoL(zn)
Ago 00 5n
0
0C
00
claimed.
Case 2: Suppose that v=((z*) * By continuity this implies V=L(=n) F 0 for all sufficiently large E N. Let us denote by N₂ C N the set of indices of extra updates. We stress that this set infinite since, by construction, every M-th update is an extra update. We have Un of for all sufficiently large E Ne. hence Schlenkrich et al. (2010, Lemma 3) yields
[V - B ( (21)
(e,,) Jgo MII = 0.
lim N.3
lim
N.3
This implies
IV [V=((zn) (J (2 Br- -,
lim
N.3
(2n) Br
thus necessarily
lim Ne3n-200
[V (2 -2- -B,+)) =
Since Nimm, o0 TzL(z)) (z+) VzL(z*)Ja (zot)= by continuity, we find
lim
VzL(zn) 9=o
Naan
whence
lim N.
Pa
(n) lim V,L(Z,) N_3n-+00
0ge 00 An
(=((=")Jno=²")
Oge
0L
00 --- (11)
0e 2
where we have used continuity again. To prove that these limits hold not only for N n 00
but in fact for all N è + 0o, we establish, as intermediate claim, that for any fixed m E N we have no BBam
B,lll = O. Note that this claim is equivalent to lim BB+1 1 B, Denoting by T. 2 0 the Lipschitz constant of Jgp near z", we find
|| vi (Jgo (2n41) B₂ ||
< (zn41) Jg (==)2l 11 (2*)
BB)" Un
BB,+1 B
|
$ L| - 2*11 + F
unll
||
Both terms the right-hand side go to and the second one since lim "=""".. by Schlenkrich et al. (2010, Lemma 3). This shows that lim || Bnll 0, which concludes the proof of the intermediate claim.
goes to infinity: the first one due to lim, 2n
|
From lim || |Bntm Ba = O for any fixed m E N it follows that for any sequence (jx) N with sup,, jin nl oo there holds lim J B.ll = 0. This implies for any such sequence (in) the limit lim ||__ B
To establish this, note that for C:= max(sup,, sul,, ||B,=1]], which is finite by Assumption 4 and the combination of the bounded deterioration principle (Schlenkrich et al., 2010, Lemma 2) with Assumption 2 (i), the set
{ A E Rddd A exists, ||| < C, ||A-1| sc}
16

---

Published as a conference paper at ICLR 2022
includes the sequence (B,) and is compact by the Banach lemma, inversion is uniformly continuous operation on this set.
Now let construct sequence (ja) C Ne. by defining, for every E J. == arg men [n-m]] That is, for every n, Jn denotes the member of Ne with the smallest distance to n. is clear that I Jnl s M for all n, hence lim | Br O. Using this and, again, continuity is easy to see that
lim 11pg 21000
P6
(1a) )
0,
which implies by (11) that
lim Pg P6
(n)
lim
(in)
lim
P6
(n) 0L
N.
00 ,
thereby establishing the claim.
Remark. An inspection of the proof reveals that if B, is never updated in the direction 2ns but only updated in the direction Un defined in (8), then Assumption 4 can be replaced by the significantly weaker assumption that the sequence (Bn 0ge
38 l2..) is bounded. The price to pay is that the conver- gence rate of (zn) ) to x" will be slower (q-linear instead of q-superlinear) since the updates in the direction on are critical for ensuring fast convergence of (Zn) to 2"
C LOGISTIC REGRESSION HYPERPARAMETERS
For both datasets we split the data randomly (with a different seed for each run) between training- validation-test, with the following proportions: 90%-5%-5% The hyperparameters are the same in the original HOAG work (Pedregosa, 2016), except:
We use memory limitation 30 updates (not grid-searched) for accelerated methods (Jacobian-Free and SHINE), compared to 10 for the original method. This is because the approximation should be better using more updates. We verified that using 30 updates for the original method does not improve the convergence speed. That number is 60 for OPA.
We use a smaller exponential decrease of 0.78 (not grid-searched) for the accelerated methods, compared to 0.99 for the original method. This is because in the very long run, the approximation can cause oscillations.
We also use the setting as Pedregosa (2016) for the Grid and Random Search. Finally, highlight that warm restart is used for both the inner problem and the Hessian inversion in the direction of the gradient.
OPA inversion experiments For the OPA experiments, we used memory limitation of 60, and tolerance of 10-6, The OPA update is done every 5 regular updates.
D DEQ TRAINING DETAILS
The training details are the as the original Multiscale DEQ paper (Bai al., 2020): all the hyperparameters are kept the same and not fine-tuned, and the data split is the same. We recall here some important aspects. For both datasets, the network is first trained in an unrolled weight-tied fashion for a few epochs in order to stabilize the training.
We also underline that the DEQ models, in addition having a fixee-point-defining sub-network, also have a classification and a projection head.
Finally, for Figure 3, the median backward pass is computed with 100 samples single V100 GPU for a batch size of 32.
D. CIFAR
The Adam optimizer (Kingma and Ba, 2015) is used with a 10-3 start learning rate, and a cosine annealing schedule.
D.2 IMAGENET
The Stochastic Gradient Descent optimizer is used with 5 10-2 start learning rate, and cosine annealing schedule. The images are downsampled 2 times before being fed to the fixed-point defining sub-network.
17

---

Published as a conference paper at ICLR 2022
20news
10a
101
10"
Test Loss Suboptimality
0
10
20
30
40
50
60
Time (s)
real-sim
10a
10"
25
Time (s)
HOAG
SHINE (ours)
Grid search
Jacobian-Free
HOAG lim. backward
SHINE refine (ours)
Random search
Figure E.1: Bi-level optimization: Convergence different hyperparameter optimization methods
on the fg-regularized logistic regression problem for two datasets (20news (Lang, 1995) and real- sim (lib)) on held-out test data.
E ADDITIONAL RESULTS
E. BI-LEVEL OPTIMIZATION EXTENDED
In order to make sure that SHINE was indeed improving over HOAG (Pedregosa, 2016), we also looked at the results obtained when performing an inversion with precision lower than that pre- scribed by Pedregosa (2016) originally (i.e. truncating the iterative inversion). These results, also complemented with Random Search (Bergstra and Bengio, 2012), can be seen in Figure E. They confirm that the advantage provided by SHINE cannot be retrieved with a looser tolerance on the inversion.
E.2 REGULARIZED NONLINEAR LEAST SQUARES
In order to further validate the efficiency SHINE compared competing methods, we also benchmarked it on the regularized nonlinear least squares task. For a training set (Itrain,i, )train, and test set (Zreet, M this problem reads
N
M Ii - o((") :t
min 8
(12)
N
arg min
lltraiin 0( Terain. )l
1
2
where a denotes the sigmoid function (2) Ite For fixed hyper- parem-errreeter 6, this task is typically solved using L--BGS (Berahas et al., 2021; Xu al., 2020).
18

---

Published as a conference paper at ICLR 2022
20news
Test Loss Suboptimality
10a
10-1
100
200
300
400
500
600
Time (s)
SHINE (ours)
Jacobian-Free
SHINE refine (ours)
SHINE OPA (ours)
HOAG
Figure E.2: Bi-level optimization on regularized nonlinear least squares: Convergence of dif- ferent hyperparameter optimization methods the fz-regularized nonlinear least squares for the 20news (Lang, 1995) dataset on held-out test data.
Table E.1: Nonlinear spectral radius obtained by the power method for the fixed-point defining sub-network for the different methods.
Method
Nonlinear spectral radius
Original
230.5
Jacobian-Fri Free
193.7
SHINE
234.2
We can see in Figure E.2 that SHINE clearly outperforms the Jacobian-Free method and is also quicker to converge compared to HOAG. We can also notice the benefit of OPA compared to the vanilla SHINE method more pronounced. We hypothesize that this due to the nonconvex nature of the inner problem making the Hessian inverse approximation more difficult, was noted by Berahas et al. (2021).
E.3 CONTRACTIVITY ASSUMPTION
One of the main limiting assumptions in the original Jacobian- FFree method work (Fung et al., 2021). 1), the contractivity assumption. We showed here that it was not important to enforce this in order achieve excellent results, but can wonder whether this assumption is not met in practice thanks to the unrolled pretraining of DEQs. We looked at the contractivity the fixed-point defining sub-network empirically by using the power-method applied nonlinear function, in the CIFAR setting. The results, summarized in Table E.I, show that the fixed-point defining sub-network is not contractive all.
E.4
TIME GAINS
Because the total training time is not only driven by backward pass but also by the forward pass and the evaluation, we show for completeness in Table E.2 the time gains for the different acceleration methods for the overall epoch. We do not report in this table the time taken for pre-training which is clear in Table E.2 that accelerated methods can have significant impact the training of DEQs because see that half the time of the total pass is spent on the backward pass (more on ImageNet (Deng et al., 2009)). We also notice that while SHINE has slightly slower backward pass than the Jacobian-Free Free method (Fung et al., 202 1), the difference is negligible when compared to the total pass computational cost.
equivalent across methods, and not something on which SHINE has an impact.
19

---

Published as a conference paper at ICLR 2022
Table E.2: The time required for each method on the different datasets during the equilibrium training. For the forward and backward passes, the time is measured offline, for single batch of 32 samples, with single GPU, using the median avoid outliers. This time is given milliseconds. For the epochs, the time is measured by taking an average of the 6 first epochs, and given in hours-minutes Imagenet and minutes-secone
for CIFAR. The epoch time for SHINE without improvement on Imagenet is not given because it never reaches the 26 forward steps: the implicit depth is too short. Fallback not used for CIFAR. Numbers in parenthesis indicate the number inversion steps for the refined versions.
Dataset Name
CIFAR (Krizhevsky, 2009)
ImageNet (Deng et al., 2009)
Method Name
Forward
Backward
Epoch
Forward
Backward
Epoch
Original (Bai al., 2020)
256
4min40
644
798
3h38
Jacobian-Fres (Fung et al., 2021)
249
12.9
3min10
621
13.5
2h02
SHINE Fallback (ours)
218
16.0
3min20
622
35.3
1h
SHINE Fallback refine (5, ours)
272
96.6
Smin50
622
212
2h44
Jacobian-Free refine (5)
260
3min40
620
186
2h43
Original limited backprop
281
86.4
3mmn5
653
187
2h40
0.9
cossim(a, b)
0.8
Method
Jacobian-Free
SHINE w. Broyden
0.7
SHINE w. Adj. Broyden
SHINE w. Adj. Broyden / OPA
0.5
||||//|b||
Figure E.3: Quality of the inversion using OPA in DEQs: Ratio of the inverse approximation over the exact inverse function of the cosine similarity between the inverse approximation b = v=((z*) B,, and the exact inverse a v=L(=")J (z*)-1 for different methods. For OPA, the extra update frequency is 5. 100 runs were performed with different batches.
E.5 DEQ OPA RESULTS
We can clearly in Figure E.3 that in the of DEQs, OPA also significantly improves the inversion over the other accelerated methods. We also see that the improvements of SHINE over the Jacobian-Free method without OPA marginal.
Because the inversion is so good, we would expect that the performance of SHINE with OPA would be par with the original method's. However, this is not what in Table E.3. Indeed, OPA does improve on SHINE with only Adjoint Broyden, but it does not outperform SHINE done with Broyden.
in the results presented
Table E.3: CIFAR DEQ OPA results: Top-1 accuracy of different methods on the CIFAR dataset, and epoch mean time.
Methode name
Top-1 Accuracy (%)
Epoch mean time
Original
93.51
4min40
Jacobian-Free
93.09
3min10
SHINE (Broyden)
93.14
3min20
SHINE (Adj. Broyden)
92.89
4min
SHINE (Adj. Broyden/OPA)
93.04
4min40
20


Reviews:
[{"review_id": "kC80UX_2Le6", "reviewer": "Reviewer_mXZ6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The theoretical aspects of the paper especially Theorems 3 and 4 are novel and good ideas. \n- The theoretical part of the paper is written very well for someone unfamiliar with the literature. \n\nQuestions:\n- Figure 1: On the 20 news dataset, the variance around the convergence of SHINE methods is a little concerning. Especially if one wishes to make the claim of \"An acceptable level of performance is reached twice faster for the SHINE method compared to any other competitor\".\n- Again in Figure 2 left: The variance in the convergence curves of SHINE methods requires further comment by the authors. Perhaps it will be a good idea of having N runs and reporting average runtime improvement benefits over other methods along with a standard deviation.\n- Figure 3: it seems that the Jacobian-free method and SHINE are almost equally performant in terms of top-1 accuracy while SHINE takes longer due to additional updates? While this is discussed briefly, I would like the authors to dig a bit deeper on why that is the case. As I understand right now, the authors claims are that the Jacobian free method is working outside the assumptions used to prove its convergence but it seems that even their method is well outside the scope of its assumptions? I am unsure what the claims are here. Why would one use SHINE over the Jacobian-free method for the DEQ models?\n", "summary_of_the_paper": "The paper proposes a way to improve on the computational cost of bi-level optimization problems. These often come up in recently proposed Deep Equilibrium models and in hyperparameter optimization settings in ML.", "summary_of_the_review": "Overall, I like the core idea and theoretical insights of the paper but have questions regarding the experiments as indicated in my main review. I am willing to update my scores based on author responses.\n\nUpdate:\n\nI would like to thank the authors for thoroughly engaging with reviewers on the platform. After reading the author responses to my review and other discussions on this forum, I am convinced that the improved draft should be presented at the conference and vote to accept the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gpdaKWKbOB", "reviewer": "Reviewer_H5f4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points:\n\nThe paper starts with a clear motivation and proposes an interesting approach to combine the computations from the forward and backward pass to accelerate the backward pass. The simplicity of their approach is an strength. Given the method, the paper provides theoretical analysis on the convergence of their forward and backward estimate to the desired computation. The theory is written well, seems correct, and states clear assumptions. The authors discuss the assumptions well (in case of whether they are used in any other works and if they are common). They provide detailed numerical results and experiments. In certain settings, they show faster performance than the original with similar performance.\n\nWeak points:\n\nSome of the experimental results are not convincing. For example, although they outperform Jacobian free method in the regularized logistic regression, they show similar performance to the Jacobian free in the case of classification with DEQ. So, why one may use SHINE which is slower than Jacobian free but have similar accuracy?\n\n- An extensive experimental study is needed to compare the two (SHINE and Jacobian-free). For the proposed method to make practical sense, the author should show the wide settings at which SHINE is better than Jacobian free. For example, is SHINE better in any other bi-level optimization in addition to the regularized logistic regression?\n\n- A discussion in the MAIN paper is needed for experimental studies on the relation between the quality of the inversion and the performance. I recommend to move Figure E.2 to the main text for this matter. Please explain why the quality of the inversion and performance are not correlated.\n\n- Fallback strategy is of concern. Please provide more intuition of this instability and why it is not seen in other methods. How much is \"barely\" in the statement \"we verified that the fallback is barely used?\"\n\n- The bullet points of contributions need to be more precise.\n\n- Figure 1. Fix typo \"Freee\".\n\n\nPost dicussion opinion: see the discussion. Given the additional HO experiment and elaborations in the abstract, I have revised my rating and I recommend acceptance of this paper.", "summary_of_the_paper": "In implicit deep learning such as deep equilibrium models, computing the inverse Jacobian for the forward pass is computationally expensive. This paper propose an interesting approach to combine the information from the forward and backward pass to make an efficient estimate of the Jacobian inverse. In one approach, they propose to replace the Jacobian in the backward update with the quasi-Newton matrix, which is being already used/estimated in the forward pass solved by quasi-Newton method. Additionally, they propose an iterative update to the quasi-Newton matrix such that to helps its estimate toward the direction useful in the backward pass (they call this outer problem awareness).\n\nThey provide theoretical analysis of their proposed method and show that under certain conditions/assumptions, the forward pass still converges to the desired solution and the sequences of backward estimates converges to the loss gradient of needed to parameter updates. They provide numerical results in bi-level optimization (regularized logistic regression) and training DEQ for classification. In certain settings (bi-level optimization), they show that they outperform Jacobian-free and have similar performance to the state-of-the-arts but it is faster than all. For DEQ, they show similar performance to Jacobian-free.", "summary_of_the_review": "The paper's main motivation is to computationally improve the backward pass. They show speed improvement compared to the other methods involving inversion of the Jacobian and minimal decrease in performance. However, they do not show performance improvement compared to the Jacobian free which is faster than the method in DEQ experiment. Given this, why one may SHINE that approximates the inverse Jacobian when their method does not outperform the Jacobian-free method? More experimental results is needed to highlight the advantage of their method against Jacobian-free. This advantage is already shown once in the regularized logistic regression.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "G3TpeJZnpX", "reviewer": "Reviewer_tSim", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I believe that this paper is studying a crucial problem. Both deep implicit/equilibrium models and hyperparameter optimization, which can be formulated as bilevel optimization problems, are important applications in machine learning. In particular, the computational bottleneck in hypergradient computation has long been a stumbling block for their applications in high dimensional settings. The proposed method of this paper borrows ideas from L-BFGS and Broyden’s method, which appears to be natural choices to consider. The authors establish various convergence results showing that the approximate hypergradients converge to the true hypergradients, under different sets of assumptions. Experimentally, the proposed method is comparable to or outperforms the Jacobian-Free method by Fung et al. (2021) in hyperparameter optimization for logistic regression and DEQs. The proposed method is interesting and can be viewed as a complementary method to the recent Jacobian-Free method. \n\nTypos: \n- Add punctuation whenever necessary in display style equations, like (1), Theorem 2, (4) and (6)\n- page 8, Figure 2 caption: “wihtout” to “without”", "summary_of_the_paper": "In various machine learning problems which can be formulated as a bilevel optimization problem and solved using gradient-based methods, the computation of hypergradients is necessary. However, the involved inverse Jacobian matrix in the hypergradient has been a computational bottleneck in high-dimensional settings. This paper proposes to use quasi-Newton matrices from the forward pass to approximate this inverse Jacobian matrix in the direction needed for the gradient computation which appears in the computation of hypergradients. The proposed algorithm is applied to both hyperparameter optimization and deep equilibrium models for CIFAR-10 and ImageNet, showing that it reduces the computational cost of the backward pass by up to two orders of magnitude. ", "summary_of_the_review": "This paper studies the problem of approximating the inverse Jacobian matrix in hypergradient computation for bilevel optimization problems solved with gradient-based methods, in an attempt to reduce the computational bottleneck of computing the exact inverse Jacobian matrix in high dimensions. The proposed method leverages quasi-Newton methods for such approximations. Experimental results have demonstrated the effectiveness of the proposed approach. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the setting of bi-level optimization and proposes a quasi-Newton scheme to reduce the cost of Jacobian inversion, which is the main bottleneck of bi-level optimization methods. The paper proves that the proposed scheme correctly estimates the true implicit gradient. The theoretical results are supported by numerical experiments, which are encouraging and show that the proposed method is either competitive with or outperforms the Jacobian Free method recently proposed in the literature.

Even though the reviews expressed some initial concerns regarding the empirical performance of the proposed method, the authors adequately addressed those concerns and provided additional experiments. Thus, a consensus was reached that the paper should be accepted.
Decision: Accept (Spotlight)