Declarative nets that are equilibrium models
Authors: Russell Tsuchida
Suk Yee Yong
Mohammad Ali Armin
Lars Petersson
Cheng Soon Ong
Venue: ICLR 2022 Poster (2022)
Keywords: deep equilibrium models
deep declarative networks
implicit layers
kernel methods
generalised linear models

Abstract: Implicit layers are computational modules that output the solution to some problem depending on the input and the layer parameters. Deep equilibrium models (DEQs) output a solution to a fixed point equation. Deep declarative networks (DDNs) solve an optimisation problem in their forward pass, an arguably more intuitive, interpretable problem than finding a fixed point. We show that solving a kernelised regularised maximum likelihood estimate as an inner problem in a DDN yields a large class of DEQ architectures. Our proof uses the exponential family in canonical form, and provides a closed-form expression for the DEQ parameters in terms of the kernel. The activation functions have interpretations in terms of the derivative of the log partition function. Building on existing literature, we interpret DEQs as fine-tuned, unrolled classical algorithms, giving an intuitive justification for why DEQ models are sensible. We use our theoretical result to devise an initialisation scheme for DEQs that allows them to solve kGLMs in their forward pass at initialisation. We empirically show that this initialisation scheme improves training stability and performance over random initialisation.

Published as a conference paper at ICLR 2022
DECLARATIVE NETS THAT ARE EQUILIBRIUM MODELS
Russell Tsuchida '
Suk Yee Yong
Mohammad Ali Armin
Lars Petersson 11
Cheng Soon Ongi
Data61, CSIRO
Space & Astronomy, CSIRO
Machine Learning
Canberra, Australia
Epping, Australiat
Artificial Intelligence Future Science Platform
ABSTRACT
Implicit layers are computational modules that output the solution to some prob- lem depending on the input and the layer parameters. Deep equilibrium models (DEQs) output solution to a fixed point equation. Deep declarative networks (DDNs) solve an optimisation problem in their forward pass, an arguably more intuitive, interpretable problem than finding a fixed point. We show that solving a kernelised regularised maximum likelihood estimate as an inner problem in a DDN yields large class of DEQ architectures. Our proof uses the exponential family in canonical form, and provides closed-form expression for the DEQ pa- rameters terms of the kernel. The activation functions have interpretations terms of the derivative of the log partition function. Building existing literature, we interpret DEQs as fine-tuned, unrolled classical algorithms, giving an intuitive justification for why DEQ models are sensible. We use our theoretical result devise an initialisation scheme for DEQs that allows them to solve kGLMSs in their forward pass initialisation. We empirically show that this initialisation scheme improves training stability and performance over random initialisation.
INTRODUCTION
Implicit layers (Pineda 1987 Almeida 1990) have recently been subject renewed atten- tion (Kolter et al. 20200]. In contrast with explicitly defined layers, implicit layers define mapping terms of a solution to some problem depending on the input and problem parameters. For ex- ample, deep equilibrium models (DEQs) consist of layers that output fixed points of parameterised functions (Bai et al., (2019). Deep declarative networks (DDNs) use declarative nodes which output solutions to optimisation problems (Gould et al. 2016 Amos & Kolter 2017). Neural ordinary differential equations (NODEs) output solutions to ODEs (Chen et al. 2018 Dupont et al. 2019). Traditional explicit layers always be represented implicit layers (for example, see Proposition 4.10 4.10 of Gould et al. (202T). Also, solutions to certain convex optimisation problems may be ob- tained via iterative optimisation procedure such as Newton's method gradient descent, and as such, may be represented as fixed points of an iterative scheme. correspondence between DDNs and DEQs is expected (but undiscovered), given the fundamental connection between fixed points of iterative maps and critical points of optimisation problems (Ryu & Boyd 2016). This leads to two natural questions: (1) For given optimisation problem, what is the corresponding DEQ archi- tecture? (2) Can this correspondence be exploited for theoretical, conceptual, or practical benefit?
Contributions. (1) We prove an equivalence between DEQ and a DDN with classical statistical model - kernelised generalised linear model (kGLM) as the declarative node, as illustrated in Figure [ and formally stated in Theorem 3 and Corollary 6 The weights of the DEQ layer have closed-form expressions in terms of the kernel. The surprise in our result is that the feature mapping involved in this correspondence is exactly the class of hidden layers that most commonly used in practice. (2) We empirically demonstrate that initialising a DEQ as a DDN using the derived expression for the weights improves performance and stability over random parameter initialisation.

---

Published as a conference paper at ICLR 2022
X,
Implicit network module
Fr
((F,())
DDN
arg MgninkGLM(axX..1)
((Y) x(,
equivalent to
DEQ
(W12" (2T()) Wap(e))
Implicit network modules such as DDNs and DEQs output solutions to problems de- pending on their inputs and parameters (top). We establish connection between DDNs with an optimisation layer (middle) and DEQs with fixed point layer (bottom). Under mild conditions, DDN that solves kGLM its inner problem over dataser (X, Y) and forms predictions at X (middle) equivalent to fully connected or convolutional DEQ accepting a datapoins Y with un- derlying fixed coordinates X and X (bottom). In an inpainting task, the inner yellow and outer regions represent pixel coordinates X and X. Y and Y represent corresponding image values. The DEQ consists fixed point/linear layer with known fixed parameters Wi, W2, W3, V1, V/ deter- mined by the kernel l and coordinates X, X.X. The activation functions a, p, are determined by the exponential family and kernel regulariser of the kGLM. Red indicates that gradient signals blocked for exact equivalence; equivalence exact under our initialisation scheme.
Figure 1:
Notation. Let C Rd and C R be coordinate and target spaces. Define v-lule stochastic process (v(x,w))ze indexed by E X with outcome from sample space Ω. Let X 1gx be a matrix such that the ith row of X is some element x; E X. Similarly define X Räxd, Take evaluations {w: = {y(2;, wn) }= from a realisation of the stochastic process for every ith row in X, and form corresponding matrix Y. Using the same realisation of the stochastic process, form Y with evaluations (y(7, - for every row in X. Call and the inner coordinate and target data, and X and Y the outer coordinate and target data.
Example implication of result. Consider image inpainting single 32 x 32 colour image. Take [......3]" {1,2,3), 3]. and X E gax to be a matrix consisting of (non- mon-repeated) triples, where n < 32 x 3. Take E z to be the matrix consisting of remaining triples, such that + = -22 x 3. An incomplete image Y E R" together with its missing values Ý E I² are jointly sampled from an image distribution. We may use kernel ridge regression to produce per- pixel prediction Y given X, and X. This model represents a special case of regularised kGLM with closed-form predictor, but more generally algorithm is required to compute the predictor- see Appendix A We now move from single image to a set of images. We wrap the kGLM with an outer minimisation loop over the loss L between neural network F,, output applied to the kGLM
predictor and target Y to obtain DDN, as sketched in Figure [ We view the DDN as producing per-image prediction. We show that such a DDN is equivalent to DEQ with a closed-form expression for the parameters depending on the kernel. When the kGLM has fixed hyperparameters, the DEQ has fixed set of parameters (made precise in Theorem and Corollary 6). Initialising the DEQ with these parameters improves training stability and performance, as shown example using kernel logistic regression for image segmentation is given in Appendix
Another
2

---

Published as a conference paper at ICLR 2022
(b)
[c]
(d)
(e)
Figure 2: (Blue) Layers (1) on the interval [-1, 1] when Y = 0. (Orange) identity. (a) (0.2
has derivative I 0.9 so admits a unique fixed point. (b) tanh(2) 2) has derivative S It satisfies the conditions of Proposition on (-1, 0) and (0, 1) and so admits a unique fixed point. (c) tanh(-32) not a contraction but admits a unique fixed point; contractions are not necessary. (d, e, f) tanh(3z), ReL.U(= + 0.2), Rz) are not contractions and admit 3, O and uncountably many fixed points.
DEEP EQUILIBRIUM MODELS
Given some Y E Fuxd, containing row elements y Y, deep equilibrium models (DEQs) (ai et al. 2019) compute an embedding 2" E 2 C RRadd as a fixed point of some function and
then output an affine transformation (Y) of the fixed point. More concretely, letting go(:; Y)- Raxd, + xnxd denote a parameterised function (e.g. a neural network) with parameters @ E 6
f(Y)= = V2*,
= go Y), x" E
Raxds
(1)
where V E Rd (nxd.) are referred to as readout parameters, and V may be thought of as a d, x xnd matrix acting on a flattened vector with nd, entries. We will find more natural to introduce a linear skip connection between Y and the output. We will also choose dy d2 That is, we consider
( = + V2Y,
x" ===9o(=";>) 2" E E C R"
Typically DEQs are trained in a supervised manner by running some iterative algorithm such as gradient descent on loss that aims to match a neural network involving f") to some target Y with respect to the DEQ and neural network parameters. Given dataset {(Y,, ((),, V.)] this procedure may be realised by running an iterative algorithm over the equality constrained optimisation problem
Σ cf (Y, F, (F
min V..VV.VVV
(YY))= V2YY,, as if the algorithm were to solve the problem, even though it may be highly non-convex. Here C is some loss function and F,, neural network with parameters y. A large class of iterative algorithms requires the derivative with respect to the network parameters 0 and Vi, V2; these may be computed under mild conditions without backpropagating through the fixed point solution via implicit differentiation. We refer the reader to Bai et al. (2019) for details.
subject to 2 go Y.),
5 N
Dealing with existence and uniqueness of fixed points. In order for ( and (2) to specify useful computational rules, they have admit at least one fixed point. To avoid having to choose which fixed point should be returned with additional rules, it might be desirable that they admit exactly one fixed point. We give example configurations of fixed points in Figure 2 The elassical Banach fixed point theorem (BFPT) gives sufficient conditions for the existence and uniqueness of fixed points.
Theorem (BFPT). Let (Z, d) be a complete metric spuce. A function H E + Z said to be contraction if there exists some 0 S q < 1 such that for all 2, E Z, (=)),, H(²))) S qd(z, z'). Every contraction admits unique fixed point.
The contraction property is suggestive of a simple algorithm (Hasselblatt & Katok 2003) for finding the fixed point of contraction // given an initial guess zo: While some termination condition is not met, Update the current estimate z, for the fixed point to be H (1) This algorithm allows one interpret the inner problem of (3) an infinitely deep neural network with weights shared between each layer. More advanced algorithms are available, which we do not discuss here. H is contraction if the induced matrix norm || of the Jacobian of H is strictly less than on Z, providing useful test for checking whether a unique fixed point of H exists. More generally,
Proposition 2. Let be an open strictly convex set, Z its closure, H : Z + Z differentiable on Z and continuous Z. If DH| < X 2, then H is a contraction on Z.
3

---

Published as a conference paper at ICLR 2022
Yg
Y,
Random
kGLM
y
Y,
Random
kGLM
Figure 3: Grouped in sets of four. (Left to right) Uncorrupted target image Ys, noisy image Y.. image output by randomly initialised DEQ, image output by kGLM initialised DEQ. kGLM but not random initialisation preserves some qualitative properties of the input.
We provide proof in Appendix B While elegant, contractions are stronger than necessary and using them limits the set admissible networks. It is therefore desirable to work with tighter conditions, or otherwise sidestep the issue. A consensus on how to deal with existence and uniqueness does not yet appear to have been reached. One may run the algorithm as a unique fixed point exists (Bai cet al. 2019), constrain monitor the parameters during learning to ensure that unique fixed point exists, add a penalisation term on an estimate of the spectral norm of the Jacobian (Roosta- Khorasani & Ascher 2015) to encourage contractive map (Bai et al. 202T), design variants of DEQs (through appropriate restriction) that explicitly ensure that a unique fixed point exists (Winston &
Kolter 2020 Revay et al., 20200 El Ghaoui et al. 2021). We do not address this problem; assume (in precise sense, see Assumption verifiable conditions for the BFPT.
Initialisation. For the vast majority of practical neural network architectures, learning involves applying an optimisation procedure (e.g. stochastic gradient descent or quasi-Newton's method) to an empirical risk minimisation problem the overparameterised network's parameters outside of
conditions that guarantee convergence to a minimum. Debate continues as to why such procedures lead to good generalisation performance (Belkin et al. 2019 Zhang al.] 2021). However, there are intuitive, empirical and theoretical reasons to suggest that appropriate parameter initialisation
plays an important role (Glorot Bengio, 2010 He et al. 2015 Poole et al. 2016 Hu al. 2020). For DEQs, initialisations have not yet been studied in great detail. By interpreting DEQs as unrolled kGLMs, we find parameter initialisations as a corollary of our main theoretical result. See Figure]
EXACT FIXED PARAMETER EQUIVALENCE BETWEEN DDNS AND DEQS
We present main result here and give special case of tractable Ising model in Appendix C.2 Our main result is a derivation of a fully connected or convolutional DEQ architecture as a model that is equivalent DDN that solves kGLM as its inner problem.
3.1 SETTING: KGLM INSIDE A DDN
Inner problem. We work with the regular (Wainwright & Jordan 2008) exponential family in
canonical form (Deisenroth al., 2020, Section 6.6), with log partition function A R. R and sufficient statistic T': Y R. In our setting, A both infinitely differentiable due to regularity, and strictly convex due to minimality (see Appendix A). We choose a prior ps over the predictor
f. which generalises the commonly used Gaussian process prior" (Schölkopf et al. 2001 Canu & Smola 2006). For nog-concave and differentiable q, define
PA (f X) (f(X)) Φx (f),
ox(f) exp (- X|ls \l
(4)
A MAP ("; k(, X)aa with representer coefficients a* satisfies
arg min - KT(Y) + A(Ka) log q (Ka) + Xa Ka/2, RcR=
(5)
where we have used strict convexity of A to ensure at most one minimum exists. For convenience,
we define p = (- lo / o (A')-1, When q is constant, px Gaussian process prior and p =
Thii prior requires delicate treatment which may be avoided if X finite. See Appendix
4

---

Published as a conference paper at ICLR 2022
Deep declarative network. We will use (5) as declarative node (Gould et al. 2021 by wrapping with an outer optimisation task order to learn the parameters of a neural network by empirical risk minimisation. Let L denote loss function (for example, mean squared error), and let F, define a generic neural network with parameters 7. Form set of N quartets {(X,, Y, X., Y.)] for example set of N images. Define K, k(Xx; X,). We consider the optimisation problem
N
Ee(y (s (X.i (x,x)x,))))
min 7:9g
==1
subject
a arg min KYT(Y,) +1 A(K,a) loga (K) + da Ka/2, s I, R 5 k(: X,)
,,
(6)
The outer problem is in general non-convex and highly nonlinear in Y
3.2 MAIN RESULT: DERIVING A HIXED-PARAEEEE DEQ
Under our construction, the equivalence between the embeddings =' of KGLMs and DEQs always holds. Under the additional Assumption I the DEQ and the kGLM are equivalent predictive models.
Assumption 1. The kernel matrix K is strictly positive definite.
We now state our main result, the proof which is given in Appendix D
Theorem 3. Let a be the minimiser of one of the inner optimisation problems 5 inducing a function (* X, k(, x)* Define= == A' (Ka*). Then 2" a fixed point satisfying
z- σ (Wiz* W2T(Y) Wap(=")),
(7)
where W1 W = = and W, = - are parameter matrices, a = A' and == (- log q)o (A')-1 monotone non-decreasing. Furthermore, under Assumption for any test index X Raxds and for least one 2n satisfying 7
(xX: = Vi +(())) VZT(Y),
(8)
where --x--11k(x0 X) and 122 -XX,(XX
Further conditions (Assumption 2) force the fixed point iteration to have a unique solution. Assumption 2. Let 2 be an open strictly convex set and Z its closure. Suppose
||/A|| sup [A" diagp' (z)]l <
=E2
Note that when p zero, that Px Gaussian, Assumption 2 reduces to ||K/\| sup |Aa(2)) 1.
The second derivative of the log partition is equal to for the Gaussian distribution with known variance and is bounded by r/4 for the Binomial distribution with r trials, further simplifying As- sumption 2 Recall that the spectral radius (the largest eigenvalue) of K/X being less than some constant is sufficient to ensure the existence of an operator norm || such that K//j| is less than the same constant. However, this guarantee does not identify the operator norm. In our experiments, we instead fix the operator norm as the spectral norm and check Assumption 2 againsst this norm. Proposition 4. Under Assumption 2 77 admits unique fixed point on Z.
The outer problem depends on the solution at to the inner problem only through f(X;; X,, Ys), which under Assumption in turn only depends on 2 We therefore have following.
Corollary 5. Under Assumptions 7 and 2 the optimisation problem (6) is equivalent to the con- strained optimisation problem
N
min
subject to
2 = + W2.T((Y.) Wssp(z))),
$ s= $=,,...,
,X,;,, Y.) = Vi,(2, + + + V2,
8 s= 1,
5

---

Published as a conference paper at ICLR 2022
W3s - and W2 => where - Vi==->-'A(X,, X,). V22- = -x, W1.
take the role of DEQ parameters and o = A' and p are monotone non- con-decreasing and take the role of DEQ activation functions. The fixed point condition for 2 is met by exactly one element of Z.
The model in Corollary [5 Jallow the parameters W W2,, Vis and V2a vary with whereas does not. An additional assumption ensures these parameters are constant in
Corollary 6. In the same setting as Corollary X, = X and X, = X are constant in 8, the parameters W1, W2, W3. V1, V2 are constant in and we may write (Y,) = (X,; Y,).
Note that in (3), the outer problem is with respect to 7, 9. V1, V/2 whereas in (9) the outer prob- lem only with respect to 7.- The parameters Vi, 1/2 and Wi, W2 (which take the role of 0), are automatically determined according to X, X and the kGLM kernel k.
Corollary S is suggestive of DEQ model that are yet to implement whose weights dynamic kernel function of the coordinate X. One parameterisation of such a model is to have an auxillary network that predicts miiee-dimensional feature mapping of the coordinates X.,
Finally, we note one more special case when X, X.. In this case, since K. k(X,, X.), predictions may be formed as f² (Xxxxxx,, xx: Y,) W3.P(2t), (2f), without the need to invert K2 and therefore without the need for Assumption
Ka = (x") = W + W2, T(Y.) +
3.3 REMARKS ON MATCHING DDNs AND DEQS
Special cases. Choosing PK/A to Gaussian, / = 0. Additionally, if T is the identity and A' tanh, we obtain a fully connected layer with tanh activations, as derived in Ap- pendix Logistic sigmoidal activations are obtained when the kGLM is specialised as kernel logistic regression. When A' and T are the identity, the kGLM becomes kernel ridge regression, with Gaussian process regression as the corresponding Bayesian model. Certain infinitely wide (nonlinear) neural networks are Gaussian processes (Neal 1995). Our result shows that one may also construct Gaussian processes whose posterior predictive mean is infinitely deep neural net- work with linear activations. The role of the coordinates X and X differs between the two models.
Symbol matching. Theorem 3 says that an embedding computed by a DEQ given Y is the same an embedding (7) computed by a kGLM on coordinates X for training set (X,Y) if the hidden parameters Wi, We and W3 are scalar multiples of the kernel matrix xX,
Initialisation via optimisation warm-start. In a stronger setting, Corollary ssooss a connection between the two optimisation tasks (3) and O.. Given a fixed DEQ architecture with a fixed point condition that may be expressed (7) (and noting that this equation also includes convolutional architectures), we may initialise parameter values that ensure that the prediction is equivalent to a trained kGLM and identify the hyperparameters of the kGLM. This initialisation may be naive (i.e. assume a "reasonable" kernel function, coordinates and regularisation parameter for a wide range of tasks) or more informed (i.e. leverage some information about the task suit the kernel and regularisation to the task being performed). Note that even without Assumptions [ and [ we may initialise the DEQ such that the feature embeddings 2' are equivalent for at least one of the fixed points. We demonstrate both naive and informed approaches in $
On augmentation and assumptions. Assumption 2 allows one to compute without concern us- ing (7) since a unique fixed point is guaranteed to exist. DEQs are sometimes implemented without checking that a unique fixed point exists. This assumption may be replaced by any other assumption that is sufficient to ensure unique fixed point. Using the derivative test on the open set Z instead of 2 allows us to handle important edge cases, namely when A' = tanh (with derivative at the origin) or A' is Leaky ReLU with gradients in {0. 1} on both sides of the origin (with undefined derivative at the origin). Assumption [ allows one to map the kGLM embedding to the prediction. The skip connection present in but not [ is not severe limitation from practical perspective. The augmented model considers a coordinate X absent from the original DEQ. Note that any DEQ may be written as an augmented model by simply ignoring the coordinate X. Under our construc- tion but without Assumptions [ or [ the equivalence between the embeddings produced by kGLMs and DEQs is still valid for least one of their respective fixed points.

---

Published as a conference paper at ICLR 2022
Figure 4: A particular choice of kernel induces a sparse matrix K = k(X,X) with repeated entries. Pre-multiplication by this sparse matrix (left) is equivalent to convolution with reshaping (right). (Left) The kernel matrix applied to flattened image. (Right) Each row of the kemel matrix is identical (after zero-padding the image), so that each row's action may be thought of as applying one filter centered at corresponding pixel. See Corollary 1T Appendix E for result on RGB images.
Convolutional layers. The derived network architecture involves only matrix multiplication, how- ever as is well-known, we may represent a convolution through a sparse matrix equation (Figure 4 Conveniently, the local structure expected in images may be encoded by particular informed kernel choice in order to recover a convolutional architecture. We formally discuss how this may be done in 2D RGB images in Corollary II Appendix through a particular choice of kernel k.
Other priors. One may replace the strongly log-concave prior PK/A with, for example, the jugate prior of the exponential family (which is only log-concave). Here we focus on the strongly log-concave prior to recover form more similar DEQs that are implemented in practice.
Spectral normalisation. Supposing || || is the spectral norm, Assumption 2 is suggestive of particular weight normalisation scheme: À is less than the spectral norm of K, then K//|| < 1. The technique of using layers with unit spectral norm is explored by MMyato al. (20T8) in the context of improving training stability of GANs. Our results indicate that such spectral normalisation also leads improved stability in DEQs initialisation, in the sense that guarantees a unique fixed point by Proposition Abusing terminology, we refer to the spectral norm of the linear transformation corresponding with a convolutional layer as the spectral norm of the convolutional layer. An easy to implement method for calculating the spectral norm of convolutional layers is available (Sedghi et al. 2018), which we use in our implementation and experiments.
4 EXPERIMENTS
DEQ parameters may be partitioned into two sets: the parameters of the layer that defines the fixed point iteration (0 (W1, W2, W3, V1, V2)), and the remainder of the parameters. Leveraging our theoretical result, we give DEQs warm-start by initialising 0 such that the DEQ solves a kGLM. We empirically demonstrate that such initialisation superior to random intialisation. We stress that our comparison is between randomly initialised DEQs and kGLM initialised DEQs only. We are not interested in demonstrating that DEQs can achieve results competitive with state-of-the-ar models, as this has already been demonstrated in previous studies (Bai et al.) [019 [021]. Our limited scope allows us to perform a more definitive empirical study with meaningful statistics. We give detailed explanation of two of the tasks in the main text, and refer the reader to Appendix F for more experiments and Appendix G for an empirical demonstration of Theorem 3 For random initialisation, we initialise weights from symmetric uniform distribution (the Pytorch default).
Smooth sequence-to-ssquenee task. Let X = | 2n 2, 2,2xz and define function h(x)) =11010 sin(x) + (2+9))² Let X, = X and X. X be 100 points on uniform grid in 1-2x, 2n] and [-2x 2. 2] respectively. Define sequences Y, and Y, to be joint evaluations of the sth realisation of Gaussian process with covariance function kime (x, x²) 0.1 exp = exp sin? || x')) 2'I)). having means i(X) and h(X) respectively.
7

---

Published as a conference paper at ICLR 2022
Infocmed
Navve
Nandon
Min
Mori
Mix
02
Triinng epoch
(a)
(b)
Figure 5: (a) Test error on a smooth sequence-tO-seqqence task for 100 random seeds for each ini- tialisation scheme. kGLM initialsation offers a better starting point and faster training than random initialisation. (b) Sample model outputs on smooth soquence-to-sequenee task. Black curves show mean h and colours represent different samples. (Top left) Ground-truth test data Y,. (Top right) Random and (Bottom left) Naive GLM initialisation after 20 epochs. (Bottom right) Inf o rmed kGLM initialisation without any training (i.e. epoch 0). kGLM initialisation, particularly informed, preserves some of the qualitative properties of the target sequence.
For informed kGLM initialisation, we pretend that we know the kernel and coordinate space. We choose k = kaue and form the required kernel matrices by taking X, X and X, X. For naive GLM initialisation, pretending we do not know the true underlying kernel or coordinate space, we de-
fault Knaive = exp =I1=-='11 and choose X, X to be uniform grid over the interval [-2T, 2T]. We initialise the hidden parameters W1 and W2 according to Theorem 3 and initialise V1 and V/2 according to the same rule as zandom initialisation. When training using naive GLM, we up- date only the readout parameters for the first 10 epochs. We generate a training and test set of size N = 20, 000 and 2, 000. Each sequence is evaluated on an n 100 dimensional uniform grid. We choose go(=*) tanh (W1²* + WaY + b) and train for 400 epochs using Adam with default hyperparameters. We repeat this for 100 trials using seeds 99, see Figure 5(a) and (b).
Image denoising. We consider a convolutional architecture as described in Appendix E with o ReLU, T the identity. and p = applied to an image denoising task using the CIFARIO dataset. Technically the ReLU is not admissible, but The coordinate space X is the space of all 2D pixel and channel triples (i. (i c) E
interested in examining its empirical properties.
32)2 x
(1, Elements Y, are CIFAR10 images corrupted by i...d. additive A (0, 0.2) noise, clipped to take values between 0 and 1. Elements Y, are the corresponding uncorrupted CIFARIO images.
For random initialisation, we sample the filter weights ..dd AOO,, Var). For kGLM initialisation, let À = K]//C, where || || denotes the spectral norm and C' >> 0 (see Assumption
2 Spectral
norms calculated using the fast and exact method described by [Sedghi et al. (2018) The kernel
is constructed randomly from the squared exponential kernel and described in Appendix
F
We are interested in separating the effects of scaling and initialisation scheme. For random initiali- sation, the scale is chosen through the variance, inducing convolutional layer with random spectral norm. For kGLM initialisation, the scale C is equal the spectral norm. We try all variances in logspace( 10 3 1, 25) and all C in logspace ering roughly the same space for both schemes. We try 100 random seeds for each configuration, resulting in 2 x 100 x 25 5000 models.
10. 25), resulting in grid of spectral norms cov-
In Figure 6 we plot individually after training for O...., , epochs the test MSE against the spectral norm for both initialisation schemes and all random seeds. kGLM initialisation offers improved test error, training stability and reduced variance in test error. The curves for kGLM initialised models adhere to the shape predicted by classical generalisation theory, where the spectral norm measures model complexity. For kGLM initialisation, spectral norms of 10 appear to represent a critical point; smaller values lead to stable training and larger values lead to unstable training. This contrasts with randomly initialised models, most of which have increasing test error with increasing spectral norm in their later epochs. This means it is easy select appropriate scale for kGLM
8

---

Published as a conference paper at ICLR 2022
10
Tx 11
Spokk
Test MSE
MSE
Text MSE
0.0 10
18k-0
7
02x 1m
1
Average sgpeciral barm
Average specizal DOVT
Average spediral DOTT
63
53
6.x 10"
6.3% 10"
Test MSG
633x
Ted. MSF
63x 10"
6.2 to
8.7 10"3
Test
6.1
ki 1073
6 10
59x 10
16
16 10
10
30 139
10
10
Average spectral morm
Average spectral
Average spectial norm
Figure 6: Test MSE against the average spectral norm each layer for image denoising task using kGLM initialisation (blue, ours) and random initialisation (red). The vertical axes change between plots. Markers at the edge of the top border indicate that a value greater than the axis limit or NaN was observed. Our initialisation scheme shows superior performance at all epochs.
initialisation, but not for random initialisation. In Figure we plot sample targets, inputs and outputs for random and kGLM initialised DEQS without any training, showing that samples using kGLM initialisation are visually more similar to the expected output than random initialisation. Figure and epoch 0 of
sanity check of Theorem 3 More plots are given Appendix
DISCUSSION AND CONCLUSION
Related work. review on connections between other optimisation iterative procedures and neural networks generally is given by Monga et al. (2021). Repeated applications of weight-tied layers can sometimes be seen as solving model-based problems, the weights are chosen appropri- ately. Since the derived network implicitly minimises conceptually tractable and principled model, it possesses a certain degree of interpretability. However, only the minimisation problems and not the forward pass computations of the network interpretable, and such the network does not satisfy the requirements of interpretability in many settings (Rudin) (019). MMnga et al. (2021) also discuss how disabling weight-tying and allowing parameters to be fine-tunedd thereby escaping the optimisation basedd iterative procedure, can sometimes lead to improved performance, perhaps at the cost of interpretability, generalisation performance and theoretical guarantees.
Notable models analysed under this framework include ISTA (Beck & Teboulle, 2009) for solving LASSO, which when unrolled and fine-tuned yields LISTA (Gregor LeCun 2010). and ADMM for compressive sensing (Boyd et al. (20TT) with an unrolled version called ADMM-CSNet (Yang al. 2018). Our work considers different class of iterative models to those surveyed by Monga et al. (202T), and recovers exactly the DEQ model. In these works, the architectures, tasks, model classes and activations are specific to particular setting. More recently, Ramsauer et al. (2020) introduce class of networks whose predictions minimise continuous analogue of Hopfield energy. This can be used to justify transformer architectures.
Conclusion. DDNs solve optimisation problems in their forward pass. We considered the problem of regularised maximum likelihood in an RKHS. Using this DDN layer, we derived a DEQ with convolutional or fully connected implicit layer and a fixed closed-form expression for the weights. Such result gives intuitive justification for computing with DEQ models: DEQs can solve clas- sical statistical problems in their forward pass. Using this theoretical connection also allowed us to initialise DEQS as DDNs. Such initialisation scheme offered performance benefits over random initialisation both at initialisation and during training. Future extensions of our work include con- sidering other statistical estimators, learning the kernel, and obtaining Bayesian rather than point estimates of the canonical parameter.

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
Our work is mostly theoretical in nature and is unlikely to directly cause harm, discrimination or privacy violations. However, our work may be used in future in applications, we encourage users of our work to adhere to ICLR's general ethical principles. We welcome open enquiry and scrutiny of the theoretical results presented in this paper.
REPRODUCIBILITY STATEMENT
We have included code and the instructions required reproduce our results. The code is publically available at https: / //ggttttth..gggg/ggg cow.////eeeeeeeiicccaaa/a//eeee
ACKNOWLEDGEMENTS
Russell, Suk Yee, Lars and Cheng Soon gratefully acknowledge the support of CSIRO's Machine Learning and Artificial Intelligence Future Science Platform.
10

---

Published as a conference paper at ICLR 2022
REFERENCES
Luis B Almeida. A learning rule for asynchronous perceptrons with feedback in a combinatorial environment. In Artificial neural networks: concept learning, pp. 102-111, 1990.
Brandon Amos and Zico Kolter. Optnet: Diffcrentiable optimization as a layer in neural networks. In International Conference on Machine Learning, pp. 136-145. PMLR, 2017.
Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances in Neural Information Processing Systems, 32:690-701. 2019.
Shaojie Bai, Vladlen Koltun, and Zico Kolter. Stabilizing equilibrium models by jacobian regular- ization. In International Conference on Machine Learning, pp. 554-565, PMLR, 2021.
Amir Beck and Mare Teboulle. A fast iterative shrinkage-threehooldnng algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183 202, 2009.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias- variance trade-off. Proceedings of the National Academy of Sciences, 116(32): 15843))):589-111) 15849-15844,4 2019.
Stephen Boyd, Neal Parikh, and Eric Chu. Distributed optimization and statistical learning via the alternating direction method of multipliers. Now Publishers Inc, 2011.
Stéphane Canu and Alex Smola. Kernel methods and the exponential family. Neurocomputing, 69 (7-9):714-720, 2006.
Gavin C Cawley, Gareth J Janacek, and Nicola LC Talbot. Generalised kereel machines. 2007 International Joint Conference on Neural Networks, pp. 1720-1725. IEEF, 2007.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary dif- ferential equations. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 5572-6583, 2018.
Mare Peter Deisenroth, Aldo Faisal, and Cheng Soon Ong. Mathematics for Machine Learning. Cambridge University Press, 2020.
Emilien Dupont, Amaud Doucet, and Yee Whye Teh. Augmented neural odes. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 3140-3150, 2019.
Laurent El Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, and Alicia Tsai. Implicit deep learning. SIAM Journal on Mathematics of Data Science, 3(3):930-958, 2021.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256 JMLR Workshop and Conference Proceedings, 2010.
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application to bi-level optimization. XrXiv preprint 1601v:1607.054477 2016.
Stephen Gould, Richard Hartley, and Dylan John Campbell. Deep declarative networks. 1EEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Peter Green and Brian Yandell. Semi-paramctric generalized lincar models. In Generalized linear models, pp. 44-55. Springer, 1985.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th international conference on international conference on machine learning, pp. 496-406, 2010.
Boris Hasselblatt and Anatole Katok. first course in dynamics: with a panorama of recent devel- opments. Cambridge University Press, 2003.

---

Published as a conference paper at ICLR 2022
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015. 2015.
Nicholas Higham. Computing a nearest symmetric positive semidefinite matrix. Linear algebra and its applications, 103: 100--18,,, 1988.
Wei Hu, Lechao Xiao, and Jeffrey Pennington. Provable benefit of orthogonal initialization in opti- mizing deep linear networks. In International Conference Learning Representations, 2020.
Z Kolter, D Duvenaud, and M Johnson. Deep implicit layers neural odes, deep equilibirum models, and beyond. Neural information processing systems tutorial, 2020. URL http:
limplicite waw--llyyrrraa lyters-tttoriallll orr//
Jiarou Lu, Huafeng Liu, Yazhou Yao, Shuyin Tao, Zhenmin Tang, and Jianfeng Lu. Hsi road:
A hyper spectral image dataset for road segmentation. In IEEE International Conference on Mullimedia and Expo (ICME), 2020.
P. McCullagh and J.A. Nelder. Generalized Linear Models, Second Edition. Chapman & Hall/CRC Monographs on Statistics & Applied Probability, Taylor & Francis, 1989. ISBN 9780412317606.
URL https: http:httt////oot// //bokks..ooooooo googleoooooo.oooooooooooooooooo. com. au/books ?i hid=hhkehhh_heee1 FFBkC
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018.
Vishal Monga, Yuelong Li, and Yonina C Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Processing Magazine, 38(2):18-44, 2021.
Radford M Neal. Bayesian learning for neural networks. PhD thesis, University of Toronto, 1995.
H Chau Nguyen, Riccardo Zecchina, and Johannes Berg. Inverse statistical problems: from the inverse ising problem to data science. Advances in Physics, 66(3):197-261, 2017.
Finbarr O'sullivan Brian S Yandell, and William J Raynor Jr. Automatic smoothing of regression functions in generalized linear models. Journal of the American Statistical Association, 81(393): 96-103, 1986.
Fernando Pineda. Generalization of back propagation to recurrent and higher order neural networks. In Neural information processing systems, pp. 611, 1987.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponen- tial expressivity in deep neural networks through transient chaos. Advances in neural information processing systems, 29:3360-3366 2016.
Hubert Ramsauer, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Lukas Gru- ber, Markus Holzleimerr, Thomas Adler, David Kreil, Michael K Kopp. et al. Hopfield networks is all you need. In International Conference on Learning Representations, 2020.
Max Revay, Ruigang Wang, and Ian R Manchester. Lipschitz bounded equilibrium networks. arXiv preprint 1000::20000017333 2020.
Farbod Glosta-KKorasse and Uri Ascher. Improved bounds on sample size for implicit matrix trace estimators. Foundations of Computational Mathematics, 15(5): 122-1 2015.
Mark Rudelson and Roman Vershynin. Non-asymptotic theory of random matrices: extreme singu- lar values. In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II-IV: Invited Lectures, pp. 1576-1602. World Scientific, 2010.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, (55):26-215,, 2019.
Emesst K Ryu and Stephen Boyd. Primer on monotone operator methods. Appl. Comput. Math, 15 (1):3 43. 2016.
12

---

Published as a conference paper at ICLR 2022
Craig Saunders, Alexander Gammerman, and Volodya Vovk. Ridge regression learning algorithm in dual variables. In Proceedings of the Fifteenth International Conference on Machine Learning, pp. 515-521, 1998.
Bernhard Schölkopf. Ralf Herbrich, and Alex Smola. A generalized representer theorem. In International conference on computational learning theory, pp. 416-426. Springer, 2001.
Bernhard Schölkopf, Alexander J Smola, et al. Learning with kernels: support vector machines, regularization. Optimization, and Beyond. MIT press, 1(2), 2002.
Hanie Sedghi, Vineet Gupta, and Philip M Long. The singular values convolutional layers. In International Conference Learning Representations, 2018.
M.J. Wainwright and M.I. Jordan. Graphical Models, Exponential Families, and Variational Infer- ence. Foundations and Trends in Machine Learning. 1(1-2):1-305, 2008.
Ezra Winston and J Zico Kolter. Monotone operator equilibrium networks. Advances in Neural Information Processing Systems, 33:10718- 2020.
Yan Yang, Jian Sun, Huibin Li, and Zongben Xu. Admm-csnet: A deep learning approach for image compressive sensing. IEEE transactions on pattern analysis and machine intelligence, 42 (3):521-538, 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
Ji Zhu and Trevor Hastie. Kernel logistic regression and the import vector machine. Journal of Computational and Graphical Statistics, 14(1):185-205, 2005.
13

---

Published as a conference paper at ICLR 2022
A KERNELISED GENERALISED LINEAR MODELS
A.1 KERNEL TRICK AND REPRESENTER THEOREM
The predictions of some classical algorithms depend on the training input data X Raxd, only through the matrix product X A widely exploited technique in machine learning, the kernel trick, replaces X with (X) IR Rxxd, where de may be large in fact infinite. Here db Rd= - Rd and with abuse of notation, when applied to matrix it is understood to apply individually to each row so that (x)) E Ruxdd It is easy to change the resulting predictor since the type of v (x))xb(X) (X)T E RR'" matches that of X and scales with n and not dg. One example is in kernel ridge regression (Saunders et al., 1998). Following our abuse of notation, we will use XX E R= denote the matrix with ejth entry 2z) == (xx,) (x2)). Any function of the form & together with the matrix X characterises the matrix 1 (X))())
Such a function is called a kernel function, and is a valid choice if and only if it corresponds with an inner product in feature space or equivalently, if it is positive semi-definite (PSD). The space of functions H2 that the kernel k characterises is called a reproducing kernel Hilbert space (RKHS).
Let k be a positive semi-definite (PSD) function inducing a reproducing kernel Hilbert space (RKHS) Ha. We will use K" = XX E TR=x to denote the matrix with ijth entry k(z,, 22). We will make use of the representer theorem, which for appropriately regularised empirical risk minimisation problems, allows one to solve optimisation problems in nonparametric function space.
Theorem 7 (Representer Theorem (Schölkopf al. 2002)). Denote by R (0) - R strictly monotonic increasing function, by X set and by L (x x IR2)" - R Ufoo} an arbitrary loss function. Let Hg be an RKHS with kernel k. Then
n
f E arg min L (1( SEHr
+ (((()))))
f - Σ auk(z.
A.2 KERNELISED GENERALISED LINEAR MODELS
We work with special case of the exponential family in canonical form (Deisenroth et al. 2020 Section 6.6), as shown in (10). As has also been noted by others (0 (O'sullivan et al. 1986. Canu & Smola 2006 Cawley et al. 2007), the representer theorem allows one to extend appropriately regularised GLMs (McCullagh & Nelder 1989) to kGLMs by replacing the linear predictor with an arbitrary element of an RKHS. Here we demonstrate this fact.
Furnish Y with a o-algebra B, forming a measurable space (Y, Let T be a measurable function T: W + RR, called the sufficient statistic. Let be some reference measure and h : Y R2o be any function such that fy (y) < co, where (y) = lv(y)dv(v) We call H the base measure and the base density. H absolutely continuous with respect to v, which may be the Lebesgue measure or the counting measure. Define IF to be the set of all 17 E R such that exx((T(y))) (y) < xo.
Define the log- aagr-parition functioon A : F + R by A(r) = log fg exp(nT(y))dHH()))
We may define a probability measure P(dy | 1) = ply ()) where
p(y n) h(y) exp (v) A(7)
(10)
is with an abuse of terminology called a probability density function for both discrete and continuous cases. Finally, form a joint probability density function product of marginals via p(Y | mn)
I[=1 17)).
We will assume that F is an open set, so that following the terminology of Wainwright & Jordan (2088. (TO) is called member of the regular exponential family. Regularity ensures that the log- partition function is infinitely differentiable, and that àA E[T(y)) Wainwright & Jordan 2008 8h
Proposition 3. Since T(y) and 7) are scalars, 110) satisfies a technical definition of a minimal exponential family. Convexity of A is guaranteed for members of any regular exponential family, but minimality ensures that A is strictly convex (Wainwright & Jordan 2008, Proposition 3.1).
Generalised linear models use an exponential family for the likelihood of observing response yi- We work exclusively with univariate responses y; and canonical parameters 7) but GLMs are con- structed more generally. For GLMs with a canonical link function, one chooses T): x B = S (I,,) to be linear function of the predictor variables x; with parameters / RRd..
14

---

Published as a conference paper at ICLR 2022
It is possible extend GLMs to accommodate non-linear predictor f in RKHS Hr with a small modification. This modification can be motivated by either a Bayesian or frequentist perspective by placing Gaussian prior over the function values regularising respectively, and then solving the resulting functional optimisation problem over an RKHS using the representer theorem. Following the former philosophy, week seek the maximum posteriori (MAP) estimate f of p(f X,Y)
with prior density (Schölkopf et al. 2001 Canu & Smola 2006)
Φx (f) = Z exp fl
(11)
where parameter and Z is a normalisation constant. If f is an infinite dimensional func- tion, such density is not defined (recall that Gaussian processes are defined in terms of their finite marginal distributions, which are jointly Gaussian). However, if we restrict the underlying coordi- nate space X to be finite, then f is simply vector evaluated over all coordinates and such notation for the prior may be employed without concern. The restriction of X to a finite space without prac- tical restriction in machine learning, since only ever condition and predict at finite number of data points. Using (IT) as the prior and (10) as the likelihood, the MAP satisfies
arg min + - 21101134 JEHA
(())
so that by the representer theorem,
-T KT(Y)++++ X 2 where a² arg min 1 (TA(Ka) a.
(*()) ((; X)a*
Ka, K=
a
As example, in binary kernel logistic regression, using the representer theorem seek to min- imise
- -logp(f(X) X,Y) = -Y Ka" + Ioo (1 (1+ ek*aaaa + 2 a Ka + const.
where K = K(X, X) E Raxn is the kernel matrix with pyth entry Kpn = kr Hig). The solution can be found by applying Newton's 's method, resulting in an iterative fixed-point numerical scheme for a". Details of this method can be found in number of references (Zhu & Hastie, 2005). A detailed example of the Ising model given in Appendix C
15

---

Published as a conference paper at ICLR 2022
B DERIVATIVE TEST
We will require the mean value theorem.
Theorem (Mean value theorem). Let S [a, 6] - R" continuous on [a, b) and differentiable on (a, b). Then there exists some (a, b) such that
[S(b) - S(a)ll <
s(t) dt
d
(6 ()-a).
We now restate the result to be proven. We follow the approach in theorem 2.2.16 of Hasselblatt & Katok (2003).
Proposition 2. Let 2 be an open stricily convex set, Z its closure, H Z + z disserentiable Z and continuous on Z. If |D s X < on 2, then H is a contraction on Z.
Proof. Let 21, 22 E 2 and define c(I) + ((22 - 21) for / E [0, and S(I) == H (S(()). Then S : (0, + Z by strict convexity. By the mean value theorem, there exists some E (0, 1) such
that
d
d S(t)
(x2) H(ai)l = (1) S(O)) <
S(t) dt
(1 (1-0)- 0-=
dt
DH (5(1)) d
dt c(t)
DH (S(()) (22 - [1)]
|DH (S(()) ||
S x a|l2 21ll
< || 21ll
and therefore H is a contraction mapping.
16

---

Published as a conference paper at ICLR 2022
C WARM-UP: A TRACTABLE ISING MODEL
We demonstrate our main result for special Ising model case. The general case is given
C.I A
Let and x' be two dimensional indices the finite lattice, E al. (l,...,0) b) for integers a. b E Z. The Ising model prescribes that
P f(x))= exp t- E
( Epwiiiphi Ean Pq
where is the partition function, some normalising constant ensuring that p | ((X) valid probability mass function. Here the parameters Jpg determine interactions between the spin states Vip and Yeg. fee controls an interaction between the spin state Yip and an external magnetic field lattice position Tip and / is a temperature parameter. We let fa f(x) belong to an RKHS HA with PSD) kernel k. With standard Gaussian prior over f, we have that
log (f(X) Y) = t Σ Jpabipliq + Σ (arsp)ii -log Z - X/2
Supposing interactions, pg 0 and Z 2 cosh (t- (f(s))) Nguyen al. 2017). By Theo- rem letting K t- x-X, X) denote the matrix with pęth entry t "ippppp Ligh.
tA
a arg min Ka + 1 log (2 cosh (Ka)) + 2 a
T Ka.
The problem is strictly convex so we may find the solution by applying Newton's 's method. Using that the derivative of log (2 cosh(-)) is tanh(-), stationarity of the solution implies that
- KY + K tanh (Ka") + IXKa" = F(a").
(12)
The Jacobian aF aa given by
0F
J(a") da
TTKKK DK tAK,
where D diag (sech² (oaa)((Ka))
so that the eth Newton iteration requires solving a linear system,
JaTo-n) (oie) - -(o-)) K (y tanh (Ko(e-1) (Datc-1))
We employ the shorthand M (ate)) = M(a) for any matrix function of a'ey- The Newton update is typically rearranged as Iteratively Re- Reighteh Least Squares (IRWLS) form by substituting yielding
a(-1) = =J
((--1)a()) = (D(c-1))(--1),
where = Ka + D- p)) and μ tanh (Ka*). Once a has been approximated to some tolerance using this numerical scheme, the predictor f. may be evaluated at points X E Rxd, using the representer theorem,
f(x)= = = E R", K ==xxx((
(13)
C.2 As A DEQ
Rearranging 12 and applying tanh to both sides of the equation, we obtain
1 K (Y- - tanh (Ka*)))
tanh (Ka*) ) = tanh
t1
Choosing 2' = tanh (Ka*), W1 = -(t -1 K, W₂ = (tA)-1,, we have
オ" = tanh (W12" + W2Y).
(14)
17

---

Published as a conference paper at ICLR 2022
Note that a" being unique fixed point of (12) implies that 2" is fixed point of (14). but not that the fixed point of (14) is necessarily unique. One condition that guarantees the uniqueness of the fixed point of (14) is that the induced matrix norm of K is less than equal to 1. Without this assumption, (14) is still true but when used as computational model, the output will general depend the fxed-point solver and initial conditions passed that solver (and even still, might never return unstable fixed points). Finally by assuming that K is invertible and using 13 we
obtain
f(Y) = tKa tKK tanh --- 1 RY 2¹) Vi=² + V2Y,
where V -A)- and V/2 (A)
18

---

Published as a conference paper at ICLR 2022
D PROOF OF MAIN RESULT
Theorem 3. Let a² be the minimiser of one of the inner optimisation problems D inducing
function (x k(,,))o' Define = A' (Ka"). Then 2" a fixed point satisfying
o W2I(Y) Wap(z")).
A' and p == (- log q)o (A')-1 are monotone non non-decreasing. Furthermore, under Assumption for any test index X E Raxd, for at least one z" satisfying 77.
where W W = - and W3 = K are parameter matrices, 0
(X;;X,Y) Vi (z" + p(=))) V2T(Y),
where V1 = X) and 1/2 = xxxxxx
Proof. Since is strictly convex, A' a strietly increasing and invertible. Q == log q()) is convex function, and its derivative Q' is monotone nondecreasing. Also note that Q' a (A') 1')-11 is monotone nondecreasing. Let K = ,(X,X) X). From (5. stationarity at the minimum, differentiabil- ity of A and Q, and the representer theorem implies
0 -KT()) + Ka + (Q'(Ka") + XKa
Ka 1 -K(K)) KQ'(Ka"))
A'(Ka') = A' (H (KT(Y)
KA((Ka)) -K(KK)) - (Q'(Ka")) -KQ(K')))
A'(Ko")= = A (1 (KT(Y) KA(KK")) - KQ' o (1') A'(Ka)))
(15)
o (W1z" + W2T() + Wap(z"))
(16)
Note that 2" is only a (not necessarily unique) fixed point 16
Suppose Assumption D Since K is invertible, and a is invertible (since A is strictly convex), then again using the representer theorem, new predictions may be formed as
Ka KK-l -''- (T(Y) p(=))) V1 (2" + VVT((),
where K = x),
Proposition 4. Under Assumption 2 admits a unique fixed point on Z.
Proof. Let H be the mapping defined by iteration (16)
((=") o + W2T(() + Wap(z")).
H is a contraction since the induced matrix norm of the Jacobian of H satisfies
|D = (W1 + Wydiagp' (2 dia))daag''' (Wis" + WYT(Y))
< K/A|| sup ||T + diago' (z))l (A)(
=E2
The result follows from Theorem
19

---

Published as a conference paper at ICLR 2022
DEQ for empirical risk minimisation
N
min V...V.
S.L.
2 =0(0;;
(' Vi2, + V2Y +b
Dataset {(E,, {e) Loss function C
1==1
Neural network Fyy
Special go
DDN for empirical risk minimisation
DEQ, fully connected or conv hidden layer
Ee(En
min 7,,,0'
min W.W.W. V3.VL.V
s.L.
ag E arg min Co(a,
s.t.
= o (Wiz) + W2T(Y.) - Wsp(2:))
AcAo.
(YY)) Vi +
kGLM inner problem
Fixed W1, W2. W3 V1, V2,
DDN, kGLM regularised negative log likelihood as inner problem
DEQ, fixed hidden parameters
Ec Fr (J X., Y.))
min
Σ (.
min
1=1
s.t.
0 = argmin kGLM((a, Y.)
= =o W2T((,) +op(x:))
(' = V1 + VoY.
(,) = k.,
Corollary Assumptions and
Fixed X., X. =
Wi = W3 = xXX,, We -W
Theorem 3 (Ka,
Vi = X)/x V/2 -V
Feature embedding
2 (W WyT(Y.) + Wap(=,))
Figure 7: Connections between implicit layer architectures.
20

---

Published as a conference paper at ICLR 2022
E CONVOLUTION AS MATRIX MULTIPLICATION
Let w, h E Z denote the pixel width and height of space of images with e channels. Let
Nwh {l....... h x {O...., w) Awuhe Yuh {I,...,c)
(17)
denote the corresponding pixel and pixel-channel spaces. Let X ((whe) xe denote matrix, where every row one of the pixel coordinates ji,j,c) Xwhe. Choose X, for some set of N images [Y,]==1- The images Y, are of size whoc and contain pixel intensities for the corresponding pixel coordinates X.
Let 22 and Py denote the first, second and third coordinates of an element Karhe Let
hn (1, 1 (|21 211 ri),
h2 1 ([ 2/21 S r2).
where the indicator function for some truncating parameters T1. 12 >> 0. Let Ko Xwhe X
Xa -> IR denote any stationary PSD kernel, for example (o) x) = e Ia-='113, Note that these
functions each define PSD kernel. Using the fact that kernels closed under multiplication, define
<(2, == (1 x' h22 x' 22) (oo
(18)
Here hi and h22 ensure that only close pixels have non-zero kernel values.
Note that the matrix x(,, is sparse when r1 or 12 are small and has an off-diagonal structure. More concretely choosing k(2,, x²) = e =2) ailll 1 the supremum norm, we obtain who who matrix. Each block of size wh is repeated horizontally.
- 2'Il I 5) where || I| denotes
This matrix represents e convolutional filters of filter length 5 x 2 = 11 in both directions. We plot the induced 32 x 32 kernel matrix when w h 32 and c 1 in Figure 4 as well the corresponding operation as a convolution. When e > 1, this matrix is simply repeated vertically and horizontally с times. For rows in the middle of the matrix, there are 11 non-zero entries, corresponding to the indices included in the convolution operation when centered on the pixel of the corresponding row.
The proof is tedious and mostly centres around the notation of appropriate reshaping of arrays and zero-padding. order to state our result, we first need to define the neural network convolution operation.
Definition 9 (Single-channe convolution). Fix X = Yuu (in the sense of (T7 and let the rows of X be equal the elements of X. Let #1 denote the single-channel image convolution operation (in the sense of convolutional networks).
More concretely, C #1 Y applies a filter C. E TR (2) to a flattened image Y E Ruch as follows. First flatten C to be an element Č of IR. 1122m and zero-pad Y to be an element Ý Then define for each j E {1, wh} vector C₁ with the same dimensionality
of (g22r+=)) as Yi, such that (265s+(22++12222112
C and all other elements of C₁ are zero. Then for each
j E {1, wh), define
(C (C+ x) Ō
so that C 11 Y Ranh, where Cmaat +2))+) is matrix with jth row equal Č₁- Definition 10 (Multi-channel convolution). Let denote the muti-channel image convolution oper- ation (in the sense of convolutional networks).
More concretely, C Y applies of filters C Xoxxoox(2 E Runhez as
flattened image
(C* Y), Caras #1 Y, E uh
so that C x Y E Be where Y, E w represents the rth channel of
Generally, have the following corollary of Theorem 3
21

---

Published as a conference paper at ICLR 2022
Corollary 11. In the same setting Theorem under Definition 9 let k = R. (in the sense of 18 and let (X) = n(., )o= be a global minimiser of (5). Then x" is a fixed point satisfying
z' = + -
+22 C3 p(z)),
(19)
where x¹ X'(m(X,)aa") C1 = Cs and C2 are convolutional filters with poth entry Xilaaa) and (x", Xx(p.o)) respectively. A' and = (- (-logg) q) (A')-) are monotone non-decreasing. Furthermore,
-X
1. Under Assumption 2 7 admits unique fixed point on Z.
2. Under Assumption for any test index E Raxds and for at least one x" satisfying
fx(X, x) Vi (=" +(=))) + V2T(Y),
(20)
where V1 = -x--xxXxx-- X) and 2/2 = X x( (X, X).
Proof. We begin with the case By Definition 9 we have that
C * z² Cm 2 1R
where 8, (22222)) is zero-padded z" and Cmat (a) The jth row of Cmat is equal to Čj. where (2 C and all other elements of Cj zero. Here Ò' flattened version Cj.
By removing the zero entries from ā. and the corresponding columns from Cmat. we may write
Cmat z W =
for some Wimat Runtxwhh The same holds for W2 and W3. We may therefore write
(C1 x C2 7(Y) + Cs * p(=)) ( 1 + W2mat T(Y) + W3mut (3mm)(2²"))
On the other hand, Theorem 3 says that
o (W12 + W2T(Y) + Wsp(z")) = =²"
Choosing Wimat = W1 - - - and similarly for W2, W3. we obtain 19 This implies that the filter C₁ has pęth entry -xx / from 3
The rest of the corollary follows
22

---

Published as a conference paper at ICLR 2022
Random initaalittion Kernel initialiasiio
Tanden intiidiiation Kemell initalisaiion
Time (secronds)
Time (spconnds)
10
10
10-3
400
000
800
Width
# Channels
Figure 8: Empirically measured cost (in seconds) for initialisation schemes measured on DELL Laptop (16GB RAM, Intel@Core i7-8665U CPU), averaged over 100 runs. (Left) Fully con- nected DEQ layer. (Right) Convolutional DEQ layer. In all cases, initialisation represents small cost compared with training.
F DETAILED EXPERIMENTS
Our experiments may be reproduced using the code provided in the supplementary material by following the README.md file.
Choice of kernel for initialisation. To intialise a convolutional network, we need to choose T2 and Ki according to (8) We choose 71 T2 3 and x3) Ede+ 1)/2 Dr (2 agee z2ς 11 where gr (u, b) = 1 = a, and = by or a == by and b a, and otherwise. We sample the squared lengthscales from uniform distribution between 0 and 4.
The cost of kGLM initialisation minuscule, and often even faster than random initialisation.
For fully connected layer with hidden and readout weight matrices W and V of size x and n respectively, we require n² + ni evaluations of the kernel function and then a normalisation by the spectral norm (the default option for this calculation for Python library such as Numpy will be the LAPACK divide and conquer algorithm, which will have a worst case (n²), but in practice the computation will be very fast). In contrast, random numbers (the usual method for initialising neural networks) requires n² + nn random number generations, which depending on software platform, is usually done through calls the inverse transform sampling method, perhaps using a stochastic collocation Monte Carlo sampler. Either way, empirically we find that kGLM initialisation actually much faster than random Gaussian initialisation for fully connected layers.
See Figure g
For convolutional layers, which are basically just extremely sparse large fully connected layers, the kernel method induces an additional overhead associated with the various reshaping operations required put the elements of the kernel matrix in the correct position layer. The calculation of the spectral norm is done through the method of Sedghi et al. (2018) at cost of (w + logw)), where is the number of channels and w is the maximum of the pixel width/height of the image. Our implementation is far from optimised, but we find that even with this overhead, the initialisation costs less than 1 second on a laptop PC. This is a tiny fraction of the cost typically associated with training the network, which depends on the problem but will usually be much less than 1%. See Figure g
the convolutional filter
Scaling up parameter counts. The number of rows of the square kernel matrix equal to the number of rows in X. This means, for example, in the setting of CIFARIO where X 3232332333 there are roughly 9.4 * 10t elements in the kernel matrix. Using a convolutional representation, the sparse kernel matrix may be represented as convolutional layer of size (3, 3, 32, 32). Crucially, the parameter count scales quadratically with the number input channels, which in this case is 3.
One way to experiment larger models is scale up the size of the input data. To this effect, take a dataset containing 3799 hyperspectral (25 channel) images (HSI) of roads (Lu et al., 2020) of total size (3799, 25, 192, 384). We consider sequence of denoising tasks when the input data is
23

---

Published as a conference paper at ICLR 2022
611 BUABFORTTOR
Spechw44
Spoth
Figure 9: First 4 channels of HSI dataset. Test MSE against the average spectral norm of each layer for image denoising task using kGLM initialisation (blue, ours) and random initialisation (red). The vertical axes change between plots. Markers the edge of the top border indicate that value greater than the axis limit or NaN was observed. Our initialisation scheme shows superior performance at all epochs.
subset of the 25 hyperspectral channels. The resulting plots are given in Figures 9 results are summarised in Table
10
12
The
Table I: Summary of experimental results. Shown are average log test losses + one "sample stan- dard deviation" the logarithm taken the best performing spectral norm. The spectral norm grid was described in the main text. If NaNs Infs were observed, these were replaced by the maxi- mum before the average and variance were recorded. failed indicates the number of NaNs and Infs observed over the full grid. Due to training instability causing NaN and Infs data points, especially in randomly initialised models, the average and "sample standard deviation" " are not true unbiased estimators. kGLM initialisation shows superior performance, both in terms of average performance and number of failed runs.
Model
Parameter (i))
Runs (l)
Epochs (I)
kGLM init
Random inil
Mean + std (MSE)
Failed (8)
Mean 1: std (MSE)
Failed (8)
channel
1600
70
0
4.80 + 0.55
33.37 + 0.17
220
6.611 = 0.03
-6.51 + 0.01
222
66.64 0.00
-6.57
222
channel
6400
100
-4.87 + 0.37
33.3 4: 0.15
450
6.76 0.01
42
6.73 1: 0.01
485
5
0..0
46
6.79
486
channel
10,000
-4.95
3.63 0.12
256
-6.84
-.800 0.02
268
6.90
35
-6.87 + 0.02
268
13 channel
16,900
65
4.60
3.23 +: 0.15
185
6.22
28
6.42 1 0.40
206
6.22
0.42
208
24

---

Published as a conference paper at ICLR 2022
g 1..0
1
6..0
1poch
Figure 10: First & channels of HSI dataset. Test MSE against the average spectral norm of each layer for image denoising task using kGLM initialisation (blue, ours) and random initialisation (red). The vertical axes change between plots. Markers at the edge of the top border indicate that value greater than the axis limit or NaN was observed. Our initialisation scheme shows superior performance at all epochs.
SH
Figure 1I: First 10 channels of HSI dataset. Test MSE against the average spectral norm of each layer for image denoising task using kGLM initialisation (blue, ours) and random initialisation (red). The vertical axes change between plots. Markers at the edge of the top border indicate that value greater than the axis limit or NaN was observed. Our initialisation scheme shows superior perfor- mance at all epochs.
25

---

Published as a conference paper at ICLR 2022
12
13232
1101111
First 11 channels of HSI dataset. Test MSE against the average spectral norm of each layer for image denoising task using kGLM initialisation (blue, ours) and random initialisation (red). The vertical axes change between plots. Markers at the edge of the top border indicate that value greater than the axis limit or NaN was observed. Our initialisation scheme shows superior perfor- mance at all epochs.
Figure 12:
26

---

Published as a conference paper at ICLR 2022
G EXAMPLE EMPIRICAL INSTANTIATION OF EQUIVALENCE
We take binarised MNIST and for each image, independently corrupt 30% of bits by randomly flipping them. We are interested in obtaining predictive model that can segment the original bi- narised image Yg from its noisy corrupt input y, together with the constant coordinate locations
X. = X. = X that may be represented as 784 x 2 coordinate indices. The index 1 S S 60, 000 runs over different images in the training dataset. We evaluate model performance on independent testing dataset of size 10, 000. We empirically compare five related models.
1. Kernel logistic regression (KLR). Since each element of Y. E R274 is binary, a natural kGLM model to use is kernel logistic regression (KLR) (Green & Yandell 1985 Zhu & Hastic 2005). With respect to the exponential family, such model preseribes that the derivative of the log partition function A'(+) a-) (1 + e-)- is the logistic sigmoid and the sufficient statistic T is the identity. As is common in the literature, we employ a zero-mean Gaussian prior so that p = 0.
The only remaining choices are the kernel function k and the regularisation parameter X. In order to ensure that Assumption iis satisfied, we choose to the sum of a squared exponential kernel with lengthscale and a white noise kernel with variance 10-$, This forces the resulting kernel matrix K to be strictly positive definite. In order to satisfy Assumption [ we need to ensure that |/A|| s (assumption A3.1 is automatically satisfied due to the setting of AA in KLR). Accordingly, we set 2 K-| Note that we do not actually need to ensure that Assumptions and Assumptions [ satisfied for Theorem 3o to hold, but we do need these assumptions that all of our theoretical results hold.
=
The KLR model is trained individually using every datapoint in (Y.)).2.00
datasef and man- ually implemented iterated reweighted least squares algorithm consisting of updates according to (exact) Newton's method. We allow Newton's 's method to run for steps, which point the norm of the difference between subsequent values of a is typically on the order of 10 14, The output of the KLR model a kernelised predictor f that has been trained using data X, and y, evaluated on X, and converted to the maximum posteriori of the Bernoulli distribution through 1 {(a((f) > 0.5).
10-14,
DEQ with kernel initial parameters (DEQ-kernel). Theorem implies an equivalent DEQ model with fixed parameters. We use this model, namely
x" = o + W2Y.), (* = V/2² + 11Y,
where W1 = V1 -X- and W2- = 1/2 = -- are parameter matrices and or is the logistic sig- moid function. To convert the kernelised predictor f (Y() to the mean of the Bernoulli distribution, we must pass it again through the inverse link function,
of = <Vi2" + 1/2)
(Greyscale prediction)
and the resulting maximum a posteriori prediction is determined by examining whether the mean of the Bernoulli distribution is greater than 0.5,
1fa(f( > 0.5}.
(Binarised prediction)
3. DEQ with kernel initialisation and fine-tuned parameters (DEQ-kerrel--raaine)) We interpret the DEQ with initial parameters model as a neural network, and update the parameters Wi, W2, Vi and 1/2 using Adam to minimise the squared loss between the greyscale prediction and binarised ground truth. We also allow biases in both the hidden and readout layers. We train for 5 epochs using a batch size of 100, leading to 5 x (60000 (00000/0000--0 = 3000 gradient updates.
4. DEQ with random initialisation (DEQ-random). We take the same neural network architecture as with kernel initialisation, but randomly initialse the parameters from a Gaussian distribution using the Pytorch default.
5. DEQ with random initialisation and fine-tuned parameters DEQ-randommtrainee take the same neural network architecture as with kerne initialisation, but randomly initialse the parameters from a Gaussian distribution using the Pytorch default. We also allow biases and train using the same optimiser and loss.
We
27

---

Published as a conference paper at ICLR 2022
Observations. Remarkably (but not surprisingly, due to Theorem the binarised prediction agrees exactly with KLR (an entirely independent piece of software, that uses an entirely different solver) over all but 11 of 60, 000 MNIST datapoints each containing 784 pixels. For those 11 where dis- agreements were observed, only of 784 pixels were different. The very small differences arise due the tolerance of the solvers and the way tied predictions (i.e. those whose logistic sigmoid output is 0.5) are handled. In all 11 cases, the DEQ output value of 0.5 and KLR output some value less than but very close to 0.5, See Table 2 for posterior probabilities, and Figure [3 for the corresponding binarised predictions. Figure 14 shows the test error as a function of training epoch for DEQ-kernel-trai
and DEQ DEO-random-trainee
Example index
DEQ posterior probability
KLR posterior probability
3678
0.5
0,499999999005522866
13774
0.5
0.49999999622255599
18222
0.5
0.499999996663143295
19554
0.5
0.499999994445511099
19857
0.5
0,4999999985129994497
22298
0.5
0.49999999984556633
23396
0.5
0,499999974214244477
38328
0.5
0.49999999119991173
43401
0.5
0.499999998905555522
48119 19
0.5
0,499999998392229995
58961
0.5
0.49999997439339999
Table 2: KLR and the equivalent DEQ agreed on all 784 pixels of 60000 examples in the training set except for the 11 examples above. In these cases, the predicted posterior probabilities were very close to borderline.
Figure 13: Visualisation of the 11 datapoints where KLR and DEQ-kernel predictions did not agree exactly. KLR predictions (top), DEO-kernel predictions (middle), and DEQ-randon pre- dictions (bottom). The top and middle rows very close, in contrast with the bottom row. The red pixel in the middle row shows where disagrees with the top. On all other 59989 examples, the top and middle agree exactly.
28

---

Published as a conference paper at ICLR 2022
Kernel initialication
Kermi intiinlaation Raodioo Initidisation
Random Initiallsation
Tost Error
3xx 10
Test Error
20-3
166 WoM M M In: "0/" paa
20
my Mory Mry
10-1
6xx 10
Training iteration
Training iteration
Kornel initialiention
Kormi Intrinlaation
1
Random Enttinlaation
Random Initiaisttion
Train Eror
Train Eror
10-1
10-1
Training Iteration
Troining iteration
Testing and training DEQ-random-trail
for DEO-kernel-trained (green) and (blue) models. The left column shows the first 100 iterations only, and the right column shows the entire training process. The initial models DEQ-kernel and DEG-random are correspondingly represented by iteration O. KLR is equivalent to DEQ kereel (up to tie predictions). The top plots show mean squared error of the binarised images the test set. The bottom two curves show mean squared eтгоr of the greyscale images on the training Kernel initialisation out- performs random initialisation. Note that the initial test error of kernel initialisaton is smaller than after training until about 30 training iterations have passed.
Figure 14:
29

---

Published as a conference paper at ICLR 2022
H EXTENSION TO NONCENTERED CANONICAL PARAMETERS
is straightforward to extend Theorem (and related corrolaries) to the case where the canonical parameters 7) are the sum of evaluations of some deterministic function m and evaluations of the predictor f. We sketch this now and leave details to the reader to suit their application. Starting from 10P and using prior 4..
we obtain new MAP objective
f arg min
log h(v)) + A (f(x.) + m((;)) + (Q((2) + m(x;))
SEHl
2 11
so that by the representer theorem, f*()) = k(,, X)a" is given by
a' arg min 1 (A(Ka+ M) + (Ka - a (TT(Y + 22a Ta, OER"
where M = (X). The same reasoning in the proof of Theorem then still follows if we define
2- ('a + M). That is, the equilibrium condition implies that
0 =-KT(M (Ka( + M) + (K' + +) - >Ka"
1 Ka* = X (KT(Y) -A'(K'' - M) - KQ'KKa' KQQKK""''" +
A'KKa' M) = A' (1 (KT(()--A(KK)) KA'KK' + M) - (Ka + M)) + M)
A'KKa' + M) A' ( - KA'(Ka' + MM) KQ' o (A') o A'(Ka + M) + M)
2' = o (W12" + W2T(Y) + W
and so on. A similar result holds when an additional linear scaling of f(X) is introduced.
30

---

Published as a conference paper at ICLR 2022
I SENSITIVITY OF FIXED POINT EQUATIONS TO NON-PSD MATRIX PERTURBATIONS
The DEQ layers of the models we studied in the main text have parameter matrices that symmet- ric PSD kernel matrices. This departs from the established practice, where one randomly initialises the parameter matrices (say from a zero-mean Gaussian distribution with small variance), and then trains the parameters using gradient descent. Here we investigate connections between our restricted parameter setting and more general parameters.
We begin by bounding the difference between fixed points of DEQ layers with the same activation and input Y, but different parameter matrices.
Proposition 12. Let 2 be an open strictly convex set and Z its closure. Denote by || || norm 2 and its induced matrix norm. Let 91 2 2 and g2 : E + 2 be defined by
some vector
91 (=) -A((Y 2)), A
g2(2) (B(( - -)), B E Rax
for some Y R", function with Lipschitz constant La S (with respect to || on Z) and
matrices A, B with matrix norms LA ||||| < 1 and LB |B| < 1. Define L1 Lo LA and
L Lo LB. Then for fixed points 21 = 91 (11) and 22 92(22) (each guaranteed to exist and be unique),
Lg Y (0)l
|| 2211 S
(1 L1) - L2) [(A B)ll-
Proof. Existence and uniqueness of fixed points follows directly from Theorem the triangle inequality and Lipschitz properties, we have
Exploiting only
|| - 22 || = (1))(11) - 92(22)l
(191(21) 91 (22) (1 (2)))
I (1))(zz) - 91 (32) + (2)) - 92 (2()))
s L1||21 =2ll + (2)) 92(2))l
(1 11)l(a1 - 22 I (19) - -22(22)
L
2| 22 -
(( BY 22]1
L
Using g2( o00), and again the triangle inequality and Lipschitz properties, note that
||22 Y| = (192(22) - 92( + (0) Y| 3 (112(22) - g2(() |) + ||o(0) YI
s L2ll22 Y| + ||Y (
1
|| - YI1 S - L2
I| の (0)).
so that
Lg L L (0)1
||21 2211 5
(1 L1)(1 L2) [I(A B)Il
We will now use this result to bound the difference between fixed points found by arbitrary parameter matrices and fixed points found by PSD kernel matrices, which exactly solve kGLMs as in the main text.
It helps to think of real-valued PSD matrices being different from general matrices in two respects. Firstly, real-valued PSD matrices are always symmetric (so their eigenvalues are real). Secondly, the eigenvalues of PSD matrices are always nonnegative reals. The matrix norm of the difference
31

---

Published as a conference paper at ICLR 2022
between any matrix and its "closest" PSD counterpart can be decomposed into these two distinct effects when the matrix norm is the Frobenius norm (Higham 1988 Theorem 2.1). However, the Frobenius norm is difficult to work with as it is not induced by norm over the vector space Z, and only provides loose bounds to the spectral norm. We instead operate on || directly, and obtain a bound that contains similar decomposition of two effects.
Proposition 13. In the same setting as Proposition 12 choose ||- || to be the Euclidean and spectral norms || 1l2- Let be any n. X n matrix. A admils a decomposition into symmetric and skew symmetric parts A A + A2 where A = 1 (A + A and A2 { A.). Let BB 0}
denote the space of PSD matrices. Then
Lo (Lo (1- 11)² ( 000)1l2)
( A2
||=1 -2112 S (B20)
min
where X2 be the largest absolute value of the negative eigenvalues of A1.
Proof. From the symmetric, skew-symmetric decomposition, A QQAQT + A22, where is (real) orthogonal and A is a real diagonal matrix. Choose =QA maximum of A and zero. Then
where A+ the elementwise
| Bll2 ||A2 + - - AQ
$ ||all12 + 2 $11A- A+112-
The first term is the operator norm of Ag. The second term the largest absolute value of the negative eigenvalues of A,. Finally note that LB I |Aill2 ||A||2, so that T-L. S T-L. and apply Proposition
12
This result helps us understand what happens when parameter matrices that are almost PSD kernel matrices are used. We note that if A is PSD, the bound evaluates to zero. If A is symmetric and real, then the bound is a linear scale of the most negative eigenvalue of A. If A is any matrix, we have to additionally account for the operator norm of the akew-symmetrie part of A, which contains purely imaginary eigenvalues.
more blunt observation can be made when we not know anything about the norm of the skew symmetric part or the most negative eigenvalue of the symmetric part of A, by relating both of these quantities to the norm of Here rather than using relative spectral properties of A, we can just use the scale of A to conclude that if A contains small entries, there is PSD matrix B that obtains close fixed point, and we can quantify this closeness. This makes use the coarse inequality that + || S A|12
A natural question ask is when such blunt device might be applied in practical scenarios. It is noted in the tutorial material (Kolter et al. 2020) that DEQs parameters are typically initialised with smaller weight variance than standard feedforward networks. Recall that Xavier Glorot initialisation for standard feedforward networks chooses parameter standard deviation of VTA" If we slightly alter
this initialisation scheme to achieve a smaller weight variance (that is still O( -1/3)), we can apply the conclusion of the rough reasoning above by applying results from random matrix theory.
Proposition 14. In the same setting Proposition 13 let A be random matrix with Gaussian C/
entries having zero mean and standard deviation 2//4t Then with probability 1 2 exp expp=t
-t2/2
for 2 the smallest sum of squared errors is bounded by
CIIY -ily-o(0)))) CI-
min (B20)
|| 2213
In particular i - (0) < Dn for some D 2 0, the smallest mean squared error is bounded by
|=] - -
C2
min (B20)
< 4D
(1
(1-
32

---

Published as a conference paper at ICLR 2022
Proof. À is bounded by the largest absolute value of all of the eigenvalues of the symmetric part of A, which is the operator norm of the symmetric part of Thus
1 [14 A| LA-
+ ||/2|2
A 1/2 + 1 A A
By Proposition 13 we therefore have
|| - 1-2122 S 11 L - 00)]l2 (B=0}
min
(1 -1- L
Choosing C' such that < C/Lo and letting v/ C/Lo Theorem 15 2
below, we have that
||A||2 = LA < Lo with probability exceeding - 2 exp 1912.
Theorem 15 (Corollary of Theorem 2.6 in Rudelson & Vershynin 2010 Let A be an no X m2 matrix with independent zero-mean Gaussian random entries each having standard deviation v. Then for all t 2 0,
P(IAI12 < u(Vn, + Vnz + +1) 2 2c 2212
When C is small, we expect there exist kernel matrices that perform roughly the same (as poorly) as random Gaussian initialisation. This result is consistent with our empirical results in the figures in Appendix I where we observe that randomly initialised parameter matrices with spectral norm of around 10 or less obtain roughly the same performance as kernel initialised models with the same norm, and both outperform randomly initialised parameter matrices with large spectral norms. However, this experimental setup is slightly complicated by the use of convolutional layers, which when converted to parameter matrices, are very large, sparse and contained shared elements.
33


Reviews:
[{"review_id": "y2wP7urTIrv", "reviewer": "Reviewer_Ldsv", "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 (+) & Weaknesses (–)\n\n(+) The paper is extremely well-written and is pleasant to read. The material is mostly self-contained and the Appendix provides useful elaboration.\n\n(+) The authors provide a useful and simple framework to study and bridge the connection between iterative root-finding models, such as the DEQ, and solving optimization problems in the forward pass. Their assumptions are well-justified, e.g., ensuring a fixed point. The exponential family also naturally lends to the implementation of modern, simple DEQs. For example, taking the sufficient statistic to be identity acts nicely as a residual/skip connection. \n\n(+) Studying DEQs is also worthwhile in the sense that the 'infinite depth' model and its training dynamics may provide further insights on understanding neural networks more broadly.\n\n(+) The initialization scheme, which is motivated by the result, indeed seems to work well. As is stated in the paper, initialization plays a major role in the training of a neural network, and its importance is often understated.\n\n(–) I was expecting to see a result comparing the performance of a simple DEQ (e.g., with a fully connected implicit layer) vs the performance of a DDN that solves the optimization problem related to minimizing the associated risk of a kGLM. If the DDN and DEQ are equivalent (as claimed), then we may expect to see similar performance here (and if not, there should be some further analysis/emphasis of the limitations of the theorem). That is, we should see corresponding empirical evidence to corroborate the claimed equivalence (or a lack thereof).\n\n(–) The importance of the choice of a kernel and the other functions in the exponential family is understated. In some sense, because we have many choices for our functions we are able to manipulate the algebra into the form of a fixed point.\n\nother:\n- In Appendix E, there is an extraneous curly bracket on the line after Equation (16).", "summary_of_the_paper": "The authors draw a resemblance between two classes of models, namely deep declarative networks (DDNs) and deep equilibrium models (DEQs), under mild assumptions. In particular, they show that solving an empirical risk minimization problem of a kernelized generalized linear model (kGLM) over a RKHS in a DDN admits a fixed point that, when viewed with an outer minimization, resembles the optimization of a simple DEQ with a fully connected implicit layer. They use their result to motivate an initialization scheme for DEQs that matches the solution of a trained kGLM.", "summary_of_the_review": "The paper is well-written, and provides a useful result that gives insight into a rich class of models. One set of experiments, namely the comparison of a simple DEQ with a DDN solving empirical risk minimization with a kGLM, should be added to corroborate the theoretical claims. ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "tJxMV5KJ3K6", "reviewer": "Reviewer_zqw8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n  - A good initialization for DEQs is interesting.\n\nCons:\n  - While satisfying nice properties, it's not clear how expressive the kGLM-based DEQ is.\n  - Experiments are on tasks where a kernel-based approach \"makes sense\". But evaluations of using kGLM-based DEQs on other tasks, regardless of \"SOTA\", is missing.\n\nComments / Questions:\n\n1. What is the computational cost of solving for the kGLM initialization? Empirically, how many iterations of training would be equivalent to the time used for solving for this initialization?\n\n2. I'm a bit confused about Corollary 6, which seems to be used for determining the kGLM-based initialization for DEQs. Is it assuming that all data points are the same value? When the data set does not satisfy this property, how are the weights computed? Perhaps writing out the expression for the non-data dependent W's and V's may be helpful here.\n\n3. If I understand correctly, the kGLM approach seems to require restricting the architecture for g. This is useful for proving uniqueness and existence.\n\n(i) Does this restricted architecture negatively impact performance? The paper mentions that it does not contain \"SOTA\" experimental results because DEQ has shown good performance already, but there seems to be a disconnect between the DEQ architecture that shows good performance and a kGLM-based DEQ.\n\n(ii) Would a kGLM-based initialization still be applicable for more general DEQs?\n\n4. What is the explanation for the difference in performance between a \"trained kGLM\" initialization and the fully trained DEQ?\n\n\nTypos / Clarifications:\n\nEq 3: The explanation/definition for F_γ might be missing.\n\nBottom of pg3: Should \"Update the current estimate zr for the fixed point to be <f(z_{r-1})>\" be H(z_{r-1}) instead?\n\nIMO, a clearer separation between the notation and motivating example in \"Notation and example implication of result\" would be good. From what I understood, this section is defining two sets of data (clean vs noisy, train vs test?), a network F_gamma, and the loss function. But having this notation definitions coupled with discussions about modeling with Gaussian processes was a bit confusing.", "summary_of_the_paper": "This paper describes a particular DEQ formulation that is motivated by a kGLM-based deep declarative network (DDN). The MAP of a kGLM admits a closed form solution and is guaranteed to exist due to the convexity of a kGLM's log probability. The paper further discusses making the solution unique through a Lipschitz constraint. While strongly convexity and Lipschitz conditions for making fixed points unique is known, the main advantage of this kGLM approach seems to be being able to have a closed form expression for the solution, which is useful as an initialization for training DEQs. Experimental results validate that careful initialization can benefit training compared to random initialization, and a kGLM approach is useful in cases where the kernel can include domain knowledge.", "summary_of_the_review": "While the paper showcases that adding these extra constraints (kGLM and Lipschitz) is useful for initialization, it's not clear if how useful the kGLM-based DEQ is for real tasks. ", "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": {}}, {"review_id": "aY7YkhnByL", "reviewer": "Reviewer_JoBL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "[Strength] The paper has the following strength.\n- The paper studies the very interesting problem of connecting DEMs with existing models, namely DDNs in this paper. The study opens up new aspect to look at DEMs and more generally implicit models which have shown to have a few desirable properties over feedforward networks.\n- The paper gives solid theoretical analysis of the equivalance and initialization for DEMs from the equivalence is discussed. Numerical experiements shows that the carefully initialized DEMs give higher performance empirically under the same training procedures. \n\n[Weekness] The paper is well written but has a few glitches.\n- The empirical experiment is a bit on the week side. Although the paper discusses the experiements on a synthetic dataset and a real dataset, the presentation of the performance on the real dataset is a bit unclear. The experiments are only shown to epoch 5 which I suppose is not to convergence yet. A similar plot to Fig. 5(a) could help. A time analysis on the initialization stage could also strongly help showcase the efficiency of the method.\n- I have seen another discussion on existance of solution in (El Ghaoui, 2019) for DEMs (refered as well-posedness for implicit model in the paper) where the condition can be further relaxed to something not necessarily contractive. I think this is worth mentioning but should not undermine the contribution of this paper.\n\nRef:\nEl Ghaoui, L., Gu, F., Travacca, B., Askari, A., & Tsai, A. Y. (2019). Implicit deep learning. arXiv preprint arXiv:1908.06315, 2. https://arxiv.org/abs/1908.06315", "summary_of_the_paper": "The paper discusses the relationship between deep declarative networks(DDNs) and deep equilibrium models(DEMs). The paper starts with a specific set of DDNs with a kernelized generalize linear model and shows that some DEMs are equivalent to the DDNs. The paper discusses the insight from such observation and potential usage of DDN inspired initialization for weights for implicit models.", "summary_of_the_review": "Overall a good paper on the theoretical connection between DEMs and DDNs that brings insight into the initialization of DEMs. The theoretical justification is well written and the empirical experiment is a bit on the week side.", "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": "AdZFW_oTObH", "reviewer": "Reviewer_4xxf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I think this is a solid work (in terms of theory, preliminary experimental results, and the strength of the insights), but has limited scope in terms of model novelty and practicality. Specifically:\n\nStrengths:\n1. Well-stated assumptions (though strong), clear theory and sensible proof (though I didn't carefully check everything). The discussions are thorough and establish a clear optimization-based interpretation of the DEQ models.\n2. Understanding the DEQ modeling via kGLM is novel, and the idea of using an informed initialization scheme makes a lot of sense. I especially like the discussion and experiments on how the initialization alone could impact the stability of these equilibrium networks, which is a known challenging problems.\n\nWeaknesses (I'll expand on this part a bit so that the authors can address the issues):\n1. Although the analysis via kGLM is novel, the perspective of considering DEQ iterations from the angle of classical optimization problems is **not**. For instance, the monotone DEQ paper (sort of) already implies this connection; i.e., the **existence and uniqueness of the fixed-point representation** is guaranteed by **the existence and uniqueness of a global optimum in the underlying convex optimization problem**. Moreover, both works start from the optimization problem itself, and eventually propose specialized DEQ layer parameterizations (of the form $\\sigma(W_1 z^* + W_2 T(Y))$, where monDEQ uses $T(Y)=Y$) to reflect this underlying optimization procedure. Representationally, I wonder if the DEQ inspired by kGLM inner optimization has a weaker capacity than the monotone DEQ model.\n2. As mentioned above, the discussion on initialization is interesting and something that I don't see implicit model papers discuss a lot. In particular, **if we can derive what the \"underlying optimization problem\" a DEQ layer might be computing**, then we can use this information to initialize the DEQ network and make it train in a more stable fashion. This is good, but generally impractical for DEQ models outside the scope of this paper. It is much easier to deduce what the weight-tied layer might look like from the optimization, than the other way around (E.g., if $g_\\theta$ is a residual block with normalization). That said, this paper actually **has not answered the question** it asks at the end of the first paragraph in Sec. 1: \"Do commonly implemented DEQs correspond with any optimization problem?\"\n3. While the paper addresses the problem of convolution by considering the circulant matrix form of the filters, with the formulation in Appendix E, wouldn't the convolutional kernel a) have symmetric weights; and b) be prohibited from performing striding or dilation? Do the authors have a sense of how this constrained convolution affect model performance? Can the authors also confirm that spectral normalization is only used at initialization, and not training?\n", "summary_of_the_paper": "The paper discusses a new perspective that establishes the connection between optimization-based layers (i.e., DDNs) and the fixed-point forward computations of the deep equilibrium networks (DEQs). In particular, the paper shows that a kGLM optimization layer, under certain regularity and contractivity assumptions, can be written as an (arguably) simpler form of deep equilibrium model layer. The paper provides solid proof and a thorough discussion of the implication of this connection, such as 1) how we might want to parameterize the matrices; and 2) how this may induce a good initialization scheme for (this particular kind of) DEQ models which improves training stability and convergence.", "summary_of_the_review": "As mentioned in the main review, I think this paper provides a good and solid theoretic perspective to understanding the deep equilibrium networks, which is a form of implicit network that has drawn growing attention these days. While the model is simple and constrained, the idea that the plausibility of DEQ models may be provided by some underlying optimization problems is an interesting and profound property. This also reminds me of the Hopefield network paper [1], which suggests that the self-attention layer is (sort of) minimizing an energy state, which somewhat implies why a Transformer-based DEQ layer would work. In addition, the authors have shown that establishing such connection between DDNs and DEQs allows us to make informed initialization, which provides appealing stability properties to the DEQ model training. Despite the limited scope and practicality, I believe this paper is still a good theoretical addition to the current set of works on implicit modeling (and how to make sense of it).\n\n[1] https://arxiv.org/pdf/2008.02217.pdf", "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": "2: The contributions are only marginally significant or novel.", "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: Thank you for your submission to ICLR.  All the reviewers are in agreement that this paper presents a nice contribution to the field, highlighting a class of DEQ models that correspond to optimization problems.  This provides a nice perspective on what kinds of computations DEQ models may perform, and I think provides a valuable contribution to the field.  The comments provided by the authors in their responses were satisfactory, and all reviewers were ultimately in agreement  that the paper should be accepted.

One comment: the authors mention that monDEQ models are restricted by requiring that the activation be a prox function, but actually [Revay et al., 2021] (https://arxiv.org/abs/2010.01732) showed that any monotone Lipchitz <= 1 function can be used there.  I believe this captures the settings the authors consider here, so it's not clear to me that the formulation indeed provides greater expressivity that monDEQs, and this point should be considered in the paper.  More broadly, however, it is true that the perspective of the monDEQ techniques are different, but I would try to be as precise in this point as possible.
Decision: Accept (Poster)