Stochastic gradient updates yield deep equilibrium kernels
Authors: Russell Tsuchida
Cheng Soon Ong
Venue: Accepted by TMLR ()

Abstract: Implicit deep learning allows one to compute with implicitly defined features, for example features that solve optimisation problems. We consider the problem of computing with implicitly defined features in a kernel regime. We call such a kernel a deep equilibrium kernel (DEKer). Specialising on a stochastic gradient descent (SGD) update rule applied to features (not weights) in a latent variable model, we find an exact deterministic update rule for the (DEKer) in a high dimensional limit. This derived update rule resembles previously introduced infinitely wide neural network kernels. To perform our analysis, we describe an alternative parameterisation of the link function of exponential families, a result that may be of independent interest. This new parameterisation allows us to draw new connections between a statistician's inverse link function and a machine learner's activation function. We describe an interesting property of SGD in this high dimensional limit: even though individual iterates are random vectors, inner products of any two iterates are deterministic, and can converge to a unique fixed point as the number of iterates increases. We find that the (DEKer) empirically outperforms related neural network kernels on a series of benchmarks.

Published in Transactions on Machine Learning Research (07/2023)
Stochastic gradient updates yield deep equilibrium kernels
Russell Tsuchida Data61, CSIRO
Cheng Soon Ong
chengsoon.
Datab1, CSIRO
Australion National University
Reviewed on OpenReview: https: // openreview. net/ forum? id=p7UTu2hig
Abstract
Implicit deep learning allows one to compute with implicitly defined features, for exam- ple features that solve optimisation problems. We consider the problem of computing with implicitly defined features kernel regime. We call such kernel a doep equilib- rium kernel (DEKER). Specialising a stochastic gradient descent (SGD) update rule applicd to features (not weights) in a latent variable model, we find an exact determin- istic update rule for the DEKER in high dimensional limit. This derived update rule resembles previously introduced infinitely wide neural network kernels. To perform our analysis, we describe an alternative parameterisation of the link function of exponen- tial families, result that may be of independent interest. This new parameterisation allows us to draw new connections between a statistician's 's inverse link function and a machine learner's activation function. We describe an interesting property of SGD this high dimensional limit: even though individual iterates are random vectors, inner products of any two iterates are deterrmnnistic, and can converge to a unique fixed point the number of iterates increases. We find that the DEKER empirically outperforms related neural network kernels a series of benchmarks. H
1 Kernel methods, deep learning and implicit deep learning
Kornel methods are a classical paradigm for analysing representational capacity, bias, generalisation performance and practical algorithms for nonparametric prediction (Schōlkopf al.] 22002.. Many classical nopparametric models can be seen as extensions of parametric models (Saunders] 1998; Ras- mussen & Williams, 2006, $ 2.2) that allow for increased representational capacity while retaining some statistical model-based properties. Examples of model-based qualities may include the smoothness, stationarity or periodicity of the predictor (Duvenaud] 2014 $ 2) or the statistical interpretation of the learning procedure (Sollich) 2002; RRasmussen & Williams|& 3), which may be understood by examining the kernel the loss function [Banerjec et al. 20055, Thcorem 4).
Despite carly successes of kernel methods, when data is plentiful and/or modelling is hard, over- parameterised and under-regularised deep learning is now seen the dominant paradigm for practical nomparametric-style prediction (OpenAI et al.] 2019 Adiwardana et al. 2020 Rombach et al. 2022). Unlike parametric and classical uonpaaametric approaches, the architecture and loss lunctions iaany explicit neural networks are driven purely from the perspective of representational power predictive
performance (either empirical /Vaswani et al. 2017 or mathematical (Raghu et al. 2017 rather than model-basee based qualitics.
A fruitful direction is to analyse deep learning predictors through the reductionist lens of kernel methods through sufficiently well- well-behaved neural networks in certain large parameter count regimes (Neal 1995).
Code available at httpp::/ sttpp://gitthbe httpe///ggiuub...///eeeeeeeeee ccm//BuseelTeecchcccbkkk.k.

---

Published in Transactions on Machine Learning Research (07/2023)
Kernel methods
Neal (1995]
al. (2018)
This paper
Jacot et al. (2018)
Deep learning
Implicit functions
Chen et al. (0018
Bai al. 20199
Gould et al. (2021
Figure 1: We establish links between kernel methods and implicit functions to design kernel with corresponding statistical assumptions about a latent variable model.
However, to the best of our knowledge, no current theory describes architectural properties of neural networks the kernel regime such choice of activation function, depth and skip connoctions, terms of model-based properties. It is desirable to motivate predictive deep learning architectures from a more fundamental, statistical model-based perspective (Rudin 2019 Efron 2020 in a kernel regime.
Implicit neural networks are emerging approach model-based deep learning. We describe such net- works as model-basee because the layers are defined and guaranteed to implicitly satisfy the solution to a problem arising from a model that not only purely prodictive, but also couceptually elegant. Implicit networks use solutions to problems as feature representations. For example, deep declarative networks (DDNs) (Gould et al. 2021) solve optimisation problems, deep equilibrium models (DEQs) (Bai et al. 2019 solve fixed point (algebraic) problems and neural ODEs solve differential equations (Chen al., 2018). Example applications of implicit neural network layers include layers that model optimal trans- port layers |Campbell et al., 2020 Eisenberger et al. 2022) and layers that perform point estimation of specific statistical models (Tsuchida al. 2022: Tsuchida & Ong) 2023). Such problems are usu- ally computed numerically via the (approximate) fixed point of an iterative procedure. This leads to the view that implicit layers are themselves a composition of infinitely many functions. Owing to the complexity of deep learning algorithms, theory falls short of explaining the empirically demonstrated successes of both implicit and explicit models. To the best of our knowledge, no general notion of an implicit kernel is currently described in the literature.
We define new type of kernel called a deep equilibrium kernel. This kernel is defined as the inner product of leatures, where features are taken using a given algorithm, at given iteration of the algorithm. We focus the special case where the problem is an optimisation problem for point estimates of a particular latent variable model and the algorithm is stochastic gradient descont. We find that the limit as the dimensionality of the features goes to infinity, the deep equilibrium kernel at any iterate can be represented equilibrium kernel at the previous iterate. We describe our contributions in more detail in 1.1 Our analysis brings together elements of implicit functions, kernel methods, and deep learning (F (Figure)
solutions to a given problem depending on inputs,
function of the deep
1.1 Our contributions: an implicit kernel and an update rule in kernel space
Updates in feature space Solutions to optimisation, fixed point or differential equation problems are practice most often obtained via possiblly stochastic iterative update procedure. Let X1 C R be an input to the problem and úx, E & C R be the solution to the problem. Note that thx, is the evaluation of an implicit function of X1. The function is implicit because the mapping is delined through the solution to a problem, rather than an explicit closed-form expression. Let (0) be an initial guess for solution at iterate 0. Suppose there exists some possibly stochastic function g (.: X): - & that maps solutions at iterate to solutions at iterate t + 1, so that
(+1) (0) xx)
(1)
2

---

Published in Transactions on Machine Learning Research (07/2023)
We call 2 features and g()) the update rule in feature space. We emphasise that consider the problem where features are updated, not weight parameters as in some other settings. This is unlike typical settings for the ncural langent kernel (Jacol al. 2018), where weight and paramoter updates are performed for a fixed depth.
Deep equilibrium kernels We find helpful the notion of an implicitly defined kernel, which we call deep equilibrium kernel (DEKER). This allows
draw parailels between infinitely wide implicit neural networks and implicitly defined kernel machines. Let ''x, ((+1) and 4 (++1) be two features corresponding to imputs X1 and X2. Recall that is the dimension of the feature mapping and is the iteration of the solver. We consider three kernel evaluations in terms of the implicit updates in feature space,
(++1) Enite feature DEKER (IDEKER)
1++
12
((+1)
1 12
& plim V ()+1)
12
and
1/ lim v
(2)
m-000
DEKNI
limiting DEKER (IDKKB))
where defined, where plim denotes convergence in probability. Note the order the limits. We will simi- larly write V1 and 22 to represent. evaluations of such DEKERS (X1, X1) and (X2, X2) respectively. We write
(++1)
v ((+1)
((++1)
12
(++1)
w (++1)
22
for the corresponding 2 x 2 PSD matrices (and likewise for the #DEKER and (DEKER). The dimen- sionality of features are allowed to grow to infinity, but only after laking the inner product, resulting in scalar value for examination. The mathematical construction of 2 x matrices suffices for purposes to analyse algorithms that utilise N examples XI,..., since every element of an N x N matrix. Defining such kernel allows one to build
kernel matrix an element corresponding predictive algorithms that operate on kernel matrices instead of feature space, avoiding the necessity of describing, analysing and building algorithms involving infinite dimensional feature spaces.
Updates in kernel space Let s {K R2x2 K KT,K K = 0) denote the space of 2 x 2 PSD matrices. Our central questions are as follows. Firstly, as m + oo, does there exist an update that may performed on
PSD) DEKER matrices instead of 2m-diimnnsional write closed form for the update? Finally, do repeated
feature space? Secondly, iterations of the update converge? That is, does there exist closed-form update rule in kernel space X2) 22 + S7 such that
(r((+1) X1,
(3)
And does
- G(V)
lim Go Go... GG X1. ~00
(4)
+ compositions
For convenience, we notationally decompose G into components via function G satisfying for each kj (11,22, 12)
Gn
G12
where
G12
Gza
Giy A (DD a b3 Byy X,) & (G)
Here 83 is a local dummy variable whose sole purpose is define and G.
Contributions We study important special case of DEKER where answer equation 3 and equation f positively, one in which the features are iteratively updated using SGD applied to latent variable model. The model peemeerreetee (the number of parameters grows much faster than the amount of data), but shallow (the motivation for the model more closely resembles exponential
3

---

Published in Transactions on Machine Learning Research (07/2023)
family PCA than deep neural network). The objective to which apply SGD is an under-regularist variant of an expected negative log posterior for point estimates of latent variables. Our main result. (stated precisely in 3 is a constructive proof of the existence of closed form update rule kernel space G.
Surprisingly, despite the feature space of the DEKER having scemingly no direct relation with doep learning predictors, deep learning structures emerge as part of our analysis. Our DEKER is a kernel which satisfies a fixed point equation, constructed via a latent variable model optimisation problem solved using SGD, Our DEKER may be understood (but is not constructed) as an infinitely wide DEQ whose iterates are computed with stochastic mapping that is resampled at every iterate rather than as a deterministic fixed point iteration. Further, the kernel iterates of our DEKER resemble previously introduced NNKs and NTKs and may be computed with deterministic fixed point solvers.
Informally, main result (Theorem 4 states that when the features Vx and Uxx are point estimates obtained by SGID, we can construct. deterministic update rule, G, for the DEKER, vr(t+1), Further, Corollary 5 says that repeated applications of G converge to a fixed point, the dDEKER. We further quantify the degree to which the dDEKER is an invariant of SGD (i.e. does not change as iterates of SGD incrcase) when treated as IDEEEER (Thoorcm 7
2
Background
Our analysis requires combining fixed point theory (optimisation), the exponential family (statisties), and neural network kernels (machine learning). We briefly describe elements of these topics here.
2.1 Notation
Numerical subscripts are used to extract (groups of) indices of vector or matrix. Parenthesised superseripts indicate a layer iteration of a naive fixed point solver, both of which turn out to be the same in our constructions, as is consistent with other DEQ works. We index objects by iteration by superscript (L), that gs(t) represents a feature in the Ith iteration. Sans serif fonts used to denote matrices, and serif fonts are used to denote vectors (so W is a matrix and W is vector). We use ø and & for arbitrary vectors and inner products that are not necessarily obtained by iterations SGD. We will use & and Ye for feature mappings and inner products of feature mappings that are obtained by iterations of SGD.
We assume that we are given access datasel X Rxxl of N examples of datapoints X, E X C R We denote by X, and X2 any two elements of this dataset.
There are two types of function signatures we associate with PSD kernels. The first is for usual PSD kernel h : X x X - R, so that an evaluation is written k(X.X') for any two X, E X. We call this form a k-form kernel. The second for a PSD kernel whose evaluation depends on 01,00 E & only through evaluations 411 (Φ1, (1), (2), 422 = (02, Φ2) of some suitably defined inner product (.-)) 16 x of + W. We represent such a kernel through x : a + R with evaluations x((01, Φ1), (d22, Φ2) (11, (22)). An example of this second form the NNK (equation 11 We call this form a k-form kernel.
Our notation summarised Table 3 in Appendix
2.2 Fixed points and infinite compositions
Let f F + F for some set F equipped with norm ||- and norm-induced metric. A fixed point of f is any Z" E satisfying z' -== =(=)). Banach's fixed point. theorem (BFPT) (Goebel & Kirk 1990
Theorem 2.1) gives sufficient conditions for the existence and uniqueness of such fixed point.
Theorem 1 (BFPT). Let [I, II) be non-empty complete normed space. A mapping f F + is called contraction mapping if there crists some q E [0, 1) such that [[() s(z')] & 9ll 2 2'|l for
4

---

Published in Transactions on Machine Learning Research (07/2023)
every EF. Every contraction mapping f admits unique fized point Z F. Furthermore, for any initial element Z() E 18, the sequence 2(+1) = = for 1 2 converyes to z as L - oc.
It is worth noling that BFPT not only provides a mat hernttial condition for well-posedness, but also describes an algorithm for approximating fixed points of contraction mappings. We call this algorithm the naice fized point solver, which simply involves applying 7-fold composition of f to some starting value (4), with a linear rate convergence immediate from the definition of contraction mapping, i.e. | I=" - z I - --111 - 1( Other solvers for lixed point problems are available, many of which are approximate Newton mothods for root finding Kelley 1995..
Deep equilibrium models (DEQs) (Bai al. 2019 neural network predictors constructed of pa- rameterised layers that output the solution to fixed point equations Z = fu(Z"), where U is general parameler object. These layers draw upon carlier works on recurrent backpropagation (Pinoda 1987 Almeida 1990), leveraging the modern machinery of deep learning architectures, optimisers and heuris- tics, The unsupervised learning problem for a DEQ, an example of which is considered by [Tsuchida &
Ong
2023 is
N min LX,, U)
subject to
=u X:),
Empirical risk minimisation for parameters U
Fixed point solution for DEQ predictions 2;
where Is is some loss function, U is parameter object, and [X;] is collection of inpul examples (a supervised setting might also involve set of output examples). Derivatives oz: layers with respect to their parameters U can be computed without backpropagating through the iterates of the fixed point solver using the implicit function theorem (Bai et al., 2019). This allows finst-order stochastic gradient methods that are popular with explicit deep learning architectures to be applied to DEQs.
"8O" of outputs of these
In general, it is not guaranteed that function necessarily admits unique fixed point; various works discuss dealing with multiple fixed points or ensuring or encouraging that exactly or at least one fixed point. exists (Winston & Kolter 2020: Revay et al. 2020; El Ghaoui al. 2021). Interestingly, if a single DEQ layer involves finding the fixed point of a contraction mapping, by Theorem the output computed by a DEQ has the interpretation of an infinitely deep neural net work with shared parameters in each layer. More generally, mappings computed by the naive fixed point solver have interpretations as very deep neural networks with shared paramcters in each layer. Since zeros of the gradient of sufficiently well behaved objectives are stationary points of the objectives, DEQ layers share a connection with optimisation-basee implicit layers (Gould et al. 2021), a8 explored in various works (Revay et al. 2020 Xie et al.] 2021 Tsuchida et al.) 2022] Riccio et al. 2022 Tsuchida & Ong. 2023). Our current investigation concerns a connection more specilic than optimisation, since it considers the special case of applying SGD.
2.3 Exponential families
Exponential families The feature mappings that we use to build our kernel are estimates obtained using SGI) applied to certain variants of exponential family likelihoods and Gaussian priors. We now deline minimal and regular exponential families in canonical form. Let h be a probability density (mass) function supported on data space Y R. Let T Y + be function called the sufficient statistic. Given some canonical purameler 1) belonging to an open set H C R, we may construct probability density (mass) function by normalising the nonnegative function h(-)) exp (T()))) The normalising constant is called the partition function, and its strictly convex and infinitely differentiable logarithm A is called the log pertition function WWinwwight et al.) 2008 Proposition 3.1). We write
ply m) = h(y) exp (T(y)n - AG1), A(r) = log J h(()) exp (T())n) dy
5

---

Published in Transactions on Machine Learning Research (07/2023)
for the evaluation of a probability density (mass) function of an exponential family. The log partition function A acts as a cumulant generating function for the conditional distribution of the sufficient statistic T. In particular the expected value of the sufficient statistic (often called the expectation porameter Nielsen & Garcia 20091) is the gradient of the log partition function A. That is,
(T((()) mg ('
(6)
We consider factorised exponential families the following sense. Let vi.... Ve be cisttributed according to the same exponential family and define data vector Y = (Ji...., , and canonical parameter vector = (m......Th ma). Then the joint distribution of data Y conditioned on canonical parameters H is the product of the individual clements
p(Y H) = IP( I 1n)== = (II h(w.)) exp (
==1
where we write T(Y) = (T(w)....,,
, A(II) = A(m))...,,AAn)))) and 1 = (I,...,1)² 1)T.
Link functions and canonical link functions Exponential families are used in generalised linear models (GLMs) (McCullagh & Nekder 1989). In GLMMs the conditional expectation equation 6 of an exponential family is set be the result of applying an (invertible) inverse link function s to the
result of a linear transformation of features e E Rt (classically called parameters). That is, for some linear basis V e Raxo (classically called covariates).
A'(H) NE (T)) I H = === ((Vo).
(8)
The conditional expectation is then mapped to the canonical parameter H through H = (4')-1 (Vo)). noting that A' is invertible because A is strictly convex. In the case where --1 is chosen to be A', s = (A)-1 is called the canonical link function, and we observe from equation R that the canonical parameter and conditional expectation satisfy
== Vo, B(T(Y) Vø] = A'(VØ) = -Voo).
There are two main and sometimes conflicting reasons why one might. be interested in using a non- canonical link function. The first is computational; the link function were canonical, for some dis- tributions such Gamma exponential one would need constrained optimisation method over the open set H. instead of R. If 3- were allowed to be non-canonical - that is, we are free to choose s-1 different from A' we could map the conditional expectation to the appropriate constraint set and unconstrained optimisation procedures could be applied. In a Bayesian context, sampling from the posterior over & can be made easier by convenient choices of 8. For example, the probit model admits an efficient Gibb's sampler for the posterior (Albert Chib 1993). The second, and arguably more important consideration is modelling; we might have reason to suspect. that the conditional expectation is constrained. For example, the observations should have a positive expectation, the power family of link functions might be used (McCullagh & Nelder 1989 equation 2.9a). Alternative link functions can lead to exploiting particular propertics of interest; for example, Wiemann et al. (2021) use the softplus function for positive conditional expectations to exploit its identity-like behaviour at large pos- itive values. In weighing up the possibly conflicting aims of computational convenience and modelling suitability, we highlight. the view of Efron & Hastie (2021] page 68); while classical exponential families and link functions may lead to closed-form expressions, modern computer technology allows us more flexible models.
When using canonical inverse link function s = A', the negative logarithm of the likelihood (equation 7 is strictly convex in H, since A is strictly convex and linear functions are convex. If H is chosen to be H = Vo, this translates to convexity in o, and maximum likelihood estimates can be computed using first or (more typically, in a classical setting) second order optimisation methods. When s-1 is not canonical inverse link function, convexity does not necessarily hold. Nevertheless,
Point estimation
6

---

Published in Transactions on Machine Learning Research (07/2023)
local estimates are practically useful, so pre-implemented link functions and the option to implement custom link functions is available in a number of soft ware frameworks including R (R Core Team 2021 family) and Stata (Hardin & Hilbe 2018 glm).
2.4 Kernels arising from neural networks
Our main result describes the DEKER update rule as composite function involving evaluations of kernels of particular form. These are kernels that are constructed from neural network models. In this section, we describe such kernels.
The neural network kernel was first investigated as the covariance function certain neural network with random parameters and a single hidden fully connected layer (Neal
1995 Under mild conditions,
as the width of the hidden layer goes to infinity the neural network converges to a Gaussian process.
This analysis has since been extended to handle multiple layers (Matthews al. 2018 Lec et al.
2018), other layer types inchuding convolutional layers (Mairal et al. 2014 Garriga-Alone Alonso et al. 2018
Novak et al. 2019 Yang, 2019a by, and training under gradient flow via the neural tangent kernel
(NTK) (Jacot et al. 2018) Since our motivation is better described in terms of inner products of the fealures, we lavour the view of the neural network kernel as an inner product in an infinitely wide hidden layer rather than covariance function Gaussian process. We note that connections between Bayesian Gaussian processes and kernel methods exist (Kanagawa et al. 2018) and apply to some but not all infinitely wide neural networks.
Neural network kernel, single hidden layer Let W()) E [Rdxa be the weights of a fully connected hidden layer with activation function Ç defined over the reals. Suppose each entry of w(!) is ii.d. with distribution M(0 1 Given an input feature Φ1 Rax1 (we take the convention that vectors are column voctors), the signal in the hidden layer is A(1) A ((W()) Here and throughout the paper the symbol A means that the object on the left hand side defined to be the expression on the right hand side. By strong law of large numbers, suitably normalised inner product in the hidden layer converges almost surely as d + oo to an expectation,
hn f((WW))) ((WW)) (2) 0 Ew Ew To)c( d2)]:
assumnnng the right hand side is finite, since the inner product is a sum of iid. random variables. Here WT Rixx xm is a vector with ii.d. entries drawn from NN(,,) 1). We define
ke( 02) A Ew [c(WTo dn) [e)]].
(10)
and call ky a single hidden layer neural network kernel (NNK) with activation function Ç. The PSD kernel kg uniquely defines an RKHS by the
Aronszaju theorem. Closed-form expressions of kz
for different ( are available (Williams 1997 Le Roux & Bengio 2007 Cho & Saul 2009 Tsuchida et al.
2018 Pearce et al. 2019 Tsuchida 2020 Meronen et al. 2020 Tsuchida et al. 2021 Han al. 2022
(T,, which is a zero mcan bivariate Gaussian with a covariance matrix I(, Note that kg(d1. d2) depends on the input features Φ1 and d2 only through the covariance matrix (()) It helpful to explicate this dependence structure through a special notation. We have that equation 10 is equal to
Define T2)
TT oz o2
( Nic (211))
> A (2(01,02) 222
((x))))))) I e
(1I)
With an abuse of terminology, we refer to both kg and Kcç as PSD single hidden layer NNKs. For a more detailed description of the NNK, see Appendix C
The effect non-unit weight variance may be obtained by scaling all inputs Φ1 by a hyperparameter. arbitrary covariance structures inside of W(l) can be reflected linear transformations all inputs
Similarly,
'The effect of magnitude of this coordinate is equivalent the quotient of the standard deviation of the weights to the biases.
Gaussian biases may be obtained by augmenting inputs with additional coordinate. The
7

---

Published in Transactions on Machine Learning Research (07/2023)
Neural network kernel, hidden layers One may compose equation 11 multiple times by applying a sequence of kernels to a 3-dimensional state represented by a 2 x 2 PSD matrix I in place the infinitely wide signals. This 3-dimensional state represents the squared norms and inner product in each hidden layer. For / = I.....T and ij E [11,2 12),
(((x)) kc ER E.))
(12)
where >14 denotes the ijth element of [() This iteration appears in deep infinitely wide NNKs (Matthews et al., 2018 Lee et al., 2018). We will refer to this kernel as the t layer NNK. Eval- uations "12+11 of the PSD kernel are determined entirely by the activation function ç, and uniquely define an RKHS.
Neural tangent kernel, hidden layers This kernel describes the limiting behaviour of randomly initialised neural networks that are trained under gradient flow (Jacol et al. 2018). The kernel iterations are similar equation 12 but also contain components involving the derivative Ç of Ç. Let @ denote clementwise product. In addition to the iteration equation 12
let @11) ( and define
( Oit) 15(++)) >)(+)))
where
(13)
= = n2 x2
to obtain the evaluation of the PSD NTK in the last iteration 0 Once again, the kernel is determined entircly by the Ç, and uniquely defines an RKHS. The notion of an NTK for DEQ models has been explored (Feng & Kolter )02T), which results in kernel that is in some sense composition many layers of kernels. In contrast, our current investigation is about building a compositional kernel from a latent variable model, rather than neural network model.
While the DEKER we will derive shares only superficial similarities with the NTK, special cases the DEKER can recover NNKs. We further discuss this at the end of
3 Main results
Our results are most clearly described in terms of an alternative parameterisation of exponential fam- ilies and link functions, which are perhaps of independent interest. We first describe this alternative parameterisation [3. before moving onto the setup for our main analysis in $ $..2
then $3.3
provide special case (Corollary 3 of our main and most general result (Theorem 4 in 3.44 Finally, quantification of error between the DEKER and fDDEKER is described in 3.5 We give examples of our resulting updates Appendix G.2
3.1 An alternative view of link functions in exponential families
Instead of computing via the conditional expectation resulting from the application of an inverse link function equation we follow Tsuchida & Ong (002) and learn the canonical parameter via a non- linearity H R(Vo) for some onco-differcntiable R R + H called the aononccal nonlincority, This means that the conditional likelihood equation is now
p(Y V. = I1 p(u mp) = (II ((.)) exp (T(Y) R(V)) A(H(Vo)) 1).
(14)
Such parameterisation is rich enough to recover the (non-canonical) inverse link function view of the statistician (sce Proposition 2). It can therefore be considered be a change of notation, placing emphasis on the canonical nonlinearity Rt instead of the inverse link function =1, In our setting, one advantage of such a notation is that it avoids more complicated function compositions involving inverses and derivatives. For example, instead of writing A (A')-1 o s s'(o)) we may write A R(Vo). The value of these simple compositions become more evident in Proposition 2

---

Published in Transactions on Machine Learning Research (07/2023)
Exponential family
A(r)
e- (a)
R(a)
pla)
a(a)
Gaussian
1//2
(a)
sa)
((a
(a)
[(a]
Gaussian
1f/2
Gaussian
1f' /2 1f /2
erfla/v2)
cri(a/v2)
2p(a)
crf(a/VZjpp(aa
Gaussian
ReLt((a) (a)
ReLUU())
u(a)
ReLU(())
Poisson
exp(n)
logs~((a)
[s (s"
(sa))(a)
Poisson
exp(1)
exp(a)
exp(e)
Poisson
exp(1)
log(1 + expo)
log log(1 + expa)
impplo
expla) (xp(a))
[Teesp-- Hespa)
Berncull
exp(6)))
(a)
(e)
((o)
Bernoull
(eg([+)x((n))
expl exp(a)/(L (pp(a)/LL+ exp(()))
a Plu) P
exp(a)/(1++ exp(a))
Bernoulli
+xp(1))
P(a)
log
2003 Plo
P(
plu)
Table 1: These examples are obtained by plugging the desired log partition function and inverse link function s-1 into expressions equation 24 equation 25 and equation 26 Canonical link functions are shown in blue. General inverse link function scttings are shown in red. Here P and respectively denote the edf and pdf of the univariate standard Gaussian and erf denotes the crror function.
Nonlinearities and activation functions The derivatives of the log likelihood equation (a score function) play central role in numerical procedures associated with estimation. In our setting, such derivatives involve terms derived from A and R. These terms are expressed in terms of functions we call factor activations p(a) _ (a) and chain activations (aa) & (A Ra)a). The following identities show how one may map between choices of (A, a) and choices of (A, RR), and additionally how these induce activation functions a and which appear in gradient- based optimisers and our later derivations. Note that may choose the inverse link function s to be non-canonical (not. A').
Proposition 2. Consider regular and minimal exponential family with log partition function A + R. Suppose the conditional expectation belongs to a set A', that is, A'(r) E A' for all canonical porameters 7 H. Let s-1
A' be an inverse link: function, for some B C R. That is, for every n E H there erists some E B such that A'(n) (a). Then equivalently, R(a), where R: B H defined by R(a) & ((A') os (a). Furthermore,
(8 (aa) p(a) A RR) A" ( a as (a)
8 (a) (s (Y(a)
and o(d) a (yo A (44)-1os-110
The proof given in Appendix In practice will take B = R. We observe that R is the identity if and only if s is a canonical link function (which is to say that sa) = d')a). For the special case Gaussian with known variance, is the identity and R is the inverse link function -1, Further cases are listed in Table
Nonlinear parameterisation framed in terms of R instead of s- are often used (MCCullagh & Nelder 1989 Chapter 11.4 and references therein), but their general relationship to -1 does not appear be discussed. As our setting is equivalent to using arbitrary link function, inherit the motivation using a non-identity from the motivation for using a non-canonical link function. We also inherit the usual difficulties in estimation and sample complexity due to using not necessarily canonical link functions.
Recall that the choice of s) should be informed by both modelling and numerical convenience (sampling, optimisation) considerations. Motivated by neural network kernels, we find a different set of (A,s) pairs convenient work with compared with the generalised linear model setting. Convenience here translates to being able to compute certain Gaussian integrals of the form equation 11 in closed form. For example, we find it easy to work with a Gaussian with non-negative conditional expectation, parameterised by A(r) 1/2/2 and s' (a) = ReLU(a), where ReLU is the popular rectified linear unit (Erron& & Hastie, 2021 page 362). Another convenient setting is Gaussian likelihood and probit inverse link function (in contrast. with the often seen Bernoulli and probit. inverse link function). Our theory holds for general (A, pairs, but its practical efficiency is contingent upon the existence of efficient numerical routines for computing the integral equation 11 Such numerical routines in the

---

Published in Transactions on Machine Learning Research (07/2023)
absence of closed-forme are available in other works Zandich et al. 2021 Han et al. 2022 but we do not study their application here.
3.2 Setup
Stochastic gradient descent We apply SGD (Robbins & Monro 1951 Wright & Rechi 2022 Chapter 5) to minimisation objective [(d; X) EyL(or X, V) with docision variable &, input and random linear transformation V. The exact minimisation objective relates to a continuous latent variable model, and is described shortly. Given two inputs X1 and X2, the t + 1th iterates are
(+1)) Xx, ex (1)
a 2
v(1) and ( a (0) Ou
LV X2, v(t) (15)
with initial features 2 and ux2 a sequence {a step sizes, and a sequence of [V of iid samples of V. We the features Vx, and 4x, in equation 15 to define the I'EEEE,, DEKER and (EKER via equation 2
We stress that we are updating features, not weight parameters.
Continuous latent variable model We work with data generating process which is slight nonlinear generalisation (Tsuchida & Ong. 2023) of exponential family PCA (Collins et al. 2001). allowing for nonlinear R (or equivalently, non-canonical link functions as in Proposition (2). This model describes data Y as being drawn from an exponential family distribution with a canonical parameter that is a function of a latent 6. The number of conditionally independent observations exponential lamily distributed random variables is d, and the dimensionality of the latent is
More concretely, let X E X C IR be an imput and suppose that data Y = T(X) follows a factorised exponential family equation 7 for some realisation of random mapping T - yd Let R: H be a once-differentiabll function. Choose the canonical parameter H R(V)) to be the composition R and a linear transformation V of a latent input variable & E - Rm. The linear transformation V form the model parameters. Place ii.d. A/ 1) prior over each entry of V gdxm, independent of r. Place an i..dd A-00A-//m prior over 6. This results in a pre-nonlinearity parameter Vó having components with variance which stays constant in d and m. For some constant C not depending on Φ, we have
( = -o-1oog [og [((v))
m 11 +
Log likelibood
LLg prior
As discussed in Proposition 2 the derivative of the negative log-posterior with log-partition function A, which appears in our later optimisation procedure, induces two functions p(a) R'(a) and a(a)
(A o (a) which we call factor activations and chain activations respectively.
Objective function
The expected negative log postcrior
X C(o; X) A (ox where X.): & H (ogg(T(X) R(Ve)) + m m (00p))
(16)
is a commonly used minimisation objective to find point estimates of d. Seo Appendix H.] for a discussion on this objective. The division by is introduced to account for the natural numerical
scaling of the likelihood term, which is a sum of d parts. Following recent deep learning trends, we consider an nuer-porumeterreee and under-regularised variant.
C(o; X) A (d; where 1(x e ( (ooggg(((()) R(VØ)) + Vmd mlll)
(17)
where < m. We call the setting over-parameteriseed because there are more parameters than datapoints (m > d) and muder-regularisee because the regularisation strength Vmd is less than what it would be under typical Gaussian prior, m² This expected negative log posterior may be obtained by choosing an overly broad i.idd prior (0, (00AA-//vmi /-1//md) over Φ. We will take d to be rell-behaved function of such that d + oo as m + (sce Assumption
10

---

Published in Transactions on Machine Learning Research (07/2023)
Assumptions We now describe two assumptions common to both settings. Our first assumption says that the dimensionality m of the feature space should become larger much faster than the dimensionality d of the number of conditionally independent observations in the exponential family. Assumption 1. Consider any limit path (m, d) + (oo, 2o) such that lim d 0. mi
Our second assumption describes how the step size should depend on m, d, and the SGD iteration t. Recall the nomenclature "fixed" and "decreasing" as qualifiers for step-size, which describe a dependency on & (but not d). Recall that À is the regularisation parameter. Assumption (a). lim ( // ==
vd Assumption 2 (a) allows for fixed or decreasing step sizes, such as ()++r(t for increasing but finite
r. Assumption 2 [a) suffices for our limiting result to hold. If we want to additionally quantify the
distance between the limit and finiteddimensional kernels, we use the stronger Assumption (2 (b) which
in particular requires a fixed step-size. Both variants 2 (a) and
2 (b) result in a limiting step size of O,
under Assumption [
Assumption (b). We have a fixed step ( m
We will find that in setup, the DEKER is composite function involving NNK building blocks.
3.3 Error function inverse link and Gaussian likelihood to match a random mapping
We will find that the update rule G of the DEKER. is composite function involving NNK building blocks. In order to clearly highlight the role of these NNK building blocks, we first present a special case before presenting our more general Theorem 4 This provides a clear link between the statistical likelihood model and closed form expressions for the DEKER update rule.
We choose an exponential family, canonical nonlinearity and random mapping r. This particular setup leads to closed-form expressions for the NNKs involved in the update rule. As activation function, we choose the error function erf(()) = 2/ [-- -u² du (closely related to the Probit function), and rely
on a closed-form NNK derived in Williams 1997).
2 sin ((1 E + E2))
E12
Bar(( (En,, E2e, E1²)
(18)
π
We show here the statistical modelling choices and their corresponding effect on the DEKER update rule.
In this special case, main result (Theorem 4 implies Corollary 3 as proven in Appendix G.I Recall
from $ [2.3] that the designer needs to choose a log partition function A, and a canonical nonlinearity R. We map input X E IR! to data Y R2 through random mapping Y err((WX/22) Q, where W E Baxd and Q E Rdd contain i.i.d. standard Gaussian elements. The distribution of Y given er. (WX//()))))))e conditionally Gaussian, with conditional expectation crf(WX/ having elements between -1 and 1. We therefore choose matching inverse link function, represent the conditional expectation as a function of features vix- The inverse link function is 8 (a) = erf(a/v2). The log partition function
A(1) = /2 and the sufficient statistic T(y) y. Since the likelihood is Gaussian, the canonical nonlinearity R and inverse link function s are the same, as shown in the first row of Table D In this particular case, the activations P and a are shown in the third row of Table [ Corollary 3. Suppose input X is mapped to data Y by Y erf( v2) + Q, where erf is the error function and W E IRax! and Q E IRd contain iid. slandard Gaussian elements. Choose the log partition function A(n) = 72/2. Choose the cononical nonlinearity R(a) = erf(a/ v2), or equivalently, choose the inverse link function to be (-) crf(a/ 22). This implies that p(a) 2p(a) and o(a) 20(a) crf(a/v2), where p is the pdf of the standard Gaussion. Then Ho and ni are given by
K2 P2z, 112) =
TI / + & 111)(1 122) D22
(o 10:10000 422, 112) = (pp(111 422, 4 112) ( /22) (FI1, F22, Fiz), where F= (0-1 + +1) +1)-

---

Published in Transactions on Machine Learning Research (07/2023)
Let Cij = F /vrlt//Vj (X;
X X, Suppose Assumptions 1 and 2 (a hold. Then applying SGD the update rale equation cxists and car be decomposed inlo G equalion 5
to objective equation 17 satisfying
1 x2 G Py Pesi X X,)
(C (:n. Pys, 0is) + Ko ( Pyg. P3g. 0.))
Note that in this case the component G of the update rule G can be computed entirely in closed
form. The 2 x 2 matrix F == (Ø-1 + +1)=1 has simple flosed-form in terms of + (see Appendix G. Recall that the decompasition of G into says that, by plugging equation into equation for each {11, 22, 12),
w = G(V 1 (T X,, X²). That is, w(++1) ; X2,
3.4
General case
We now consider the general setting, allowing for arbitrary (A,s) pairs and random mappings P. In order to analyse this generalised setting, we require one additional definition equation 19 and two additional assumptions and I
In the most general setting, the DEKER includes some non-symmetric (hence not PSD and not a kernel) cross terms. Given two activations C and Cz.
Recico (E11, Ege, E1s) e (ro
(19)
The third assumption says that if the inner products empirical estimates of expectation, the resulting expectation is real valued and finite. Recall that T is the sufficient statistic of the exponential family, I is the random mapping from imput space to data space, and o(a) R)((a)
Assumption 3. The expectation ((a)= = lx (T(T(X)) @ p(az) - alaz) { is finite for all X X and a E R, where Z is stendard Gaussion random variable.
The fourth assumption describes the properties of the random mapping I' x yd d co. In order to understand what happens to the solutions found by SGD as d becomes large, need the inputs which are passed through to be well-behaved. It suffices that a kernel and average defined by converges. We call the limiting kernel the explicit kernel, which contrasts with our implicitly defined DEKER. We give examples in Appendix F
Assumption 4. The PSD kernel defined by X2) ET(T(X)) T(T(X2)) is finâte. Similarly, the mean function defined by p(X)) & lim (T((()))) 1 (T((())) 1 is finite.
lim (T(((X)) T(T(X)))
m mo
We are now ready to state our main result..
Theorem Suppose Assumptions |
a and hold. Let C.yy X,),, and μi = x(X,) be the updute rule G equation 3
defined in Assumplion 4 Then applying S
D to objective equation 17
exists and can decomposed into G equation satisfying
Gl 1s X,)
1 x2
Cijmi
O33 4iy) Ka,p (Dir, D3. Dig) Kip. (#n Pzj. Di))py + mo Pzg 0ey)
Here Ko; Bip Ka,p and kp are as defined by equation equation 15 and Proposition
"The matrix F arises because the activation functions o and involve the pdf of standard normal distribution with covariance matrix I. When p multiplied with the pdf of the bivariate normal distribution with covariance this has effect of computing harmonic means of covariances & and I, resulting F.
12

---

Published in Transactions on Machine Learning Research (07/2023)
Our main result is a constructive proof for the existence of an update rule G, as posed in equation 3 In order to prove our main result, we will need to prove a series of lemmas, as detailed in Appendix The intuition behind these lemmas as follows. The stochastic gradient d6 [o; X, V) evaluated at an arbitrary point & EΦ for input X and random V is the sum of the gradient of the negative log prior and the stochastic gradient of the negative log likelihood,
Proof sketch
0 06 1.
m T
v y (T(T(X)) o
=
AD
(20)
Gradient of negative log prior
Stochastic gradient of log, likelihood
Assumption 2 (a) means that if the limit were allowed to be applied, the gradient of the negative log prior term in equation 20 multiplied by the step size would look like d. This means that the update of SGI) would reduce to the stochastic gradient of the log likelihood. To derive the kernel update rule, we then examine the inner product of the stochastic gradient of the log likelihood. We first convert the inner product of the stochastic gradient of the log likelihood an approximate form that is easier to deal with (Lemma 15). We then confirm that the kernel update only involves the inner product of the stochastic gradients of the log likelihood (Lemma [6]. Finally, we show that the inner products of the approximate form converges
closed form update rule G (Lemma 17 Assembling these lemmas
together yields Theorem 4 The detailed proof is given in Appendix E
Recall again that the decomposition of into G says that, by plugging equation into equation for each ij E (11,22, 12}.
v = = ( X, X,). That is, v((+1) = G(vr(r) X1, X2).
Note the cross terms involving Ko, and j in Theorem g which were not present in the special case of Corollary 3. These cross-terms arise from random mappings I' with average element that is non-zero. In the case of Corollary 3 these cross- terms cancel out.
Theorem implies fixed point condition by Theorem providing positive answer for equation Corollary 5. Suppose the same setting as Theorem 4 G is a contraction mapping, then the DEKER converges to a unique fized point as 00. That is, for each ij E {11, 12),
CumppVine Ui. Vi)) Ka,p (Va, Dos. Wig) Kp (Va, Doi, Vig)as + Ki (Vii Mis Wiy) Vi X²
(21)
Whether G is a contraction can be determined by a derivative test and an identity given in Theorem 19 we demonstrate in & G.2 Note that even if a unique fixed point does not exist (which may be the case if G is not contraction), one may still compute with finite-f iterates of SGD via Theorem 4
We may compute iterates of SGD in the limit via the update rule for any to obtain v/7), which is the naive fixed point algorithu applied to equation 21 Alternatively, we may compute the (DEKER by solving equation 21 for each ij E {11, 22, 12] using any other fixed point solver.
Notable special cases and relation to NNK and NTK Some further examples arising from special choices of A, 1t and I' (inducing corresponding P; a, e and p)) are discussed in Appendix G.2 We find that the linear Gaussian (A(r) = 7² /2, R(a)= = a) results in a DEKER that is a scale multiple of e (Appendix G.2.Ip. We can recover an NNK with activation a when and are allowed to be general and C and μ set to zero (Appeudix G.2.2 This means that any NNK with activaiton a may be expressed as a special case of EE. The setting we found useful for our experiments ($ 4 is a nonlincarly parameterised Gaussian (A(1) /2 and R(a) ReLU(a)) with a first-order arc-cosine kernel for and corresponding mean function μ. This setting admits closed-form update rule for G. While this setting is distinct from the NTK with ReLU activations, it shares superficial similarities in that both updates involve repeated iterations of kernels Kp, and Ko. See Appendices G.2.4 and G.2.5 for details.
13

---

Published in Transactions on Machine Learning Research (07/2023)
3.5 Sensitivity
In order to quantify the rate at which the infiittedimmesionnal, infinite-iteration DEKER converges with respect the dimension, we need the feature mapping to well-behaved. Lipschitzness and boundedness allows concentration inequalities to be applied.
Assumption 5. Suppose p is bounded lipschitz. Suppose. a is bounded Lápschitz.
We may quantify the degrce to which the infinite-dimmnsionne infinite- inteatiottttation DEKER is invariant of SGD, We define specific values of finite dimensional & and &' using the infinite dimensional kernel lixed point W1 W22 and 12 This definition will serve as a good approximation of an invariant. Definition 6. Define
n=vin M VL.,, (1.0....00 .)" E R
n=
12 v 2r cos w, sinw, O,....)) 0) e R""
where cosw
12 Van V22
Then r|r2 122 rIn I1, and rfr2 1z2.
bound the residual of the finite dimensional kernel evaluated an initial guess that solution of the infinite (m,d) d) system. When this bound is small, intuitively speaking, the limiting solution V is "almost" an invariant of the finite-dimensional system. By invariant of SGD, we mean that V does not change iterates of SGD increase. In other words, if we intitialise SGD close to the solution V, future iterates of kernels will stay close to the initialisation with high probability.
Theorem 7. Suppose Assumptions
(b and hold. Let initial guesses be vix rı and
<x; 12 in Definition and E2,
Then there cxist conslants Q2, Q2 02 0g such that for all 62 0
P(V12 12 (1) 122 S SEI +52) 21 21-62 81 -22
where
K + X²
(2e1 + +i).
81 = 2exp (-c2ddM) + expp (-mo?/2) and 82 = 2xx (-dey.Mg
and 61
V d 8 M2 min
and M3 = min
and cg > 0 is some absolute constant. Q3
52
2 02
Q3
The proof is given in Appendix E The probability decays to I exponentially the minimum m and d, where recall that d is the number of conditionally independent observations in the exponential lamily and m is the dimensionality of the latent variable. The closeness é + 82 may be configured to be close to zero by choosing 52, and e2 to be small, thereby trading off against constants resulting a slower exponential decay of probabilitics.
4 Experiments
Recall that the fDEKER is defined for finite SGD iteration an inner product of finite m-dimensional features. The DEKER is defined for finite SGD iteration т as a limit as m - oo of an inner product of m-dimensional features. The &DEKER is defined as limit as SGD iteration 7 Although the DEKER and (DEKER are defined in terms of infinite dimensional features, evaluations the DEKER and &DEKER are scalar values and can be used to form matrices with a finite number of and columns. These matrices be used in kernel methods to build predictive algorithms.
of the DEKER.
In our analysis in the previous section, we considered x 2 kernel matrices. Such analysis exlends to N xXN kernel matrices, where each element of the N N kernel matrices may be related an element of a 2 x 2 kernel matrix. All our implementations are vectorised, so that they operate on N N matrices.
14

---

Published in Transactions on Machine Learning Research (07/2023)
4.1 Measuring finite-width effects
We empirically mensure the similarity of (finile-r, finito-d) ITDEKER matrices and (infinito-r, infinite- d) ÆDEKER matrices using the centered variant (Cortes et al. 2012) of kernel aligument (Cristianini ot al. 2001 abbreviated CKA, as d incrcases. We vary between 5 and 500 steps of and choose For control, we also measure the CKA between the (finite-T, finite-d) #DEKEE and the squared exponential kernel (SEK). See Figure 2 and Appendix [.1 for full details on the experimental setup. As expected (Theorem [ the CKA between the DEKER matrices becomes larger as and increase, but not between the SEK and finite DEKER.
Ganssian
Bernoulli
Gaussian (rectified parameter)
1.30
1.00
#DFK SEK CKA=]
0.75
0.25
0.50
0.20
0:30
0.25
0:25
0.00
310
200
100
Figure 2: CKA between kernel matrices consisting of entries V.s and 4& Xx) (Blue) and squared
exponential ial kernel for control and (x,, (Orange) for three choices and R. (Left) Gaussian exponential family, A(n) n/²/ /2 and R(n) n. (Middle) Bernoulli exponential family, A(n) = log(1 + exp.)) and R(n) = n- (Right) Gaussian exponential family with rectified parameter, A(r) = 1/² and R(n) ReLU(y). The dashed rod horizontal line at represents the maximun value of CKA.
4.2 Inference using the DEKer
(KRR) (ef Gaussian process regres- suite of benchmarks. For each dataset, we first partition the data into an 80 - 20 train-test split. Using the training set, we perform 5-fold cross-validation for hyperparameter selection using the default settings of sci-kit learn's GridSearchCt which performs model selection based on the coefficient of determination. The hyperparameter grid we search over is described in Table g Appendix J.2 We then compute the RMSE on the held out test set using all training data. We repeat this procedure for 100 different random shuflles of dataset, and find the sample average and standard deviation RMSE over the random shuffles. The results are reported in Table 2 The input X is preprocessed by subtracting the sample average and dividing by the sample standard deviation of cach feature. Additionally, the target data is mean-centered and scaled by the sample standard deviation. The reported RMSE is after conversion of back to original units.
We use the DEKER for kernel ridge regression (Saunders) 1998)
sion (Rasmussen & Williams, 2006))
Since the DEKER is strict generalisation of the NNK, we expect the DEKER to strictly out-perform the NNK. Any empirical performance result that may be obtained by previous investigations into the NNK with activations a (Lee el al., 2020) can be reproduced by a DEKER with the correct hyperparameler choice. We do not empirically explore uncertainty properties of corresponding Gaussian process models as others do (Adlam et al. 2020). but note that the same principle applies. We find that GridSearchCV somctimes picks out settings that correspond with an NNK, but often does not. The number of times Grid GridSearchCV collapses the DEKER to the NNK is indicated in the last column of Table 2] Our results are consistent with the previously established observation that "NNKs frequently outperform " (eee et al.] 2020). More interestingly, we find that for each dataset, the DEKER performs well or better than every other kernel, including the NNK.
15

---

Published in Transactions on Machine Learning Research (07/2023)
Data
DEKER or &DEKER
NNK
NTK
SEK
yacht
0.65 + 0.21
2.13 + 0.57
2.75 + 0.58
3.62 0.67
0
diabetes
54.51 + 3.29
54.58 + 3.30
55.05 + 3.38
54.75 - 3.32
70
energyl
1.00 + 0.11
1.01 0.11
1.67 + 0.14
1.08 + 0.13
78
energy2
1.58 + 0.15
1.58 0.15
2.10 0.18
1.58 - 0.16
68
concrete
4.94 + 0.47
4.97 0.47
5.05
0.48
5.65 0.39
60
wine
0.57 = 0.02
0.61 = 0.02
0.54 + 0.02
0.62 + 0.02
1
Table 2: RMSE of KRR models (# one standard deviation over 100 random seeds). We use the DEKER described in $ G.2.5 which performs other kernels according to the sample average the RMSE. Often the difference in performance is small compared with the standard deviation. The final column is the number of times the best DEKER found using GridSearchCy was an NNK. The datasets are UCI benchmarks- yacht (Gerritsma et al.) 2013). diabetes (Kahnj. energy (first and second value independently) (Tsaas & Xifara 2012. concrete (Yeh) 2007) and wine (Cortez et al. 2009
5 Conclusion
We introducod the DEKER, a kernel analogue of implicit noural network models. The DEKER is defined as the limiting inner product between two features computed using feature update procedure as the dimensionality of the features goes to infinity.
We considered the problem of whether deterministic update procedure for the DEKER cxists (equa- tion 3), and whether this update rule converges (equation 4) We focused on the special case where the features are latent variables an exponential family PCA model (with not necessarily canonical link function) learnt using SGD. Leveraging the connection between infinitely wide explicit neural networks and kernel methods, we showed how in such a sctting an explicit update rule can be computed. The update rule is a composition of functions involving NNK building blocks. While this type of update rulc is not the one that is typically encountered in deep learning, which usually updates weights using SGD, it results in an interesting limiting model that shares connections to the NNK.
The DEKER has a number of interesting properties. The DEKER is able to recover instances of the NNK, and also resembles the NTK. Importantly, unlike the NNK and NTK, the deep layer utructure of the DEKER is motivated entirely from an optimisation perspective. The activation functions (and thus kernels) involved in the computation of the DEKER can be related back to statistical modelling assumptions on the data through the exponential family. particular, the activation functions share a conncction to the log partition function and inverse link function of the exponential family. On a scries of benchmarks, the DEKER performs as well as or outperforms the NNK, NTK and SEK.
Our work admits several natural extensions. The matrix V which represents linear transformation fully connected layer may be constrained to resemble convolutional layer, and expect a convolutional variant of the DEKER to be tractable (Novak et al. 2019). Since our construction probabilistic, the Laplace approximation may yield tractable mcans of obtaining principled uncertainty estimates for kernel methods beyond the regular Gaussian process framework. Since the DEKER satisfies a fixed point equation, implicit differentiation may be used to compute derivatives of the DEKER with respect to its hyperparameters, mirroring the neural network counterpart (Bai et al. 2019
We considered the special case where the DEKER equation 2 is defined using features that are solu- tions to (latent variable model) optimisation problems using SGD. The resulting DEKER satisfies a fixed point equation. In future, other work might consider other types of problems and algorithmss, resulting in DEKERS which satisfy other types of conditions. Concurrent work (Cirone et al. 2023) considers solving neural controlled differential equations using Fuler discretisations. Their resulting kernel satisfies a certain lype of partial differential equation. We believe these two results, along with classical descriptions of Gaussian processes as solutions stochastic differential equations (Rasmussen & Williams 2006 Appendix B), might represent special instances of a more general framework.
16

---

Published in Transactions on Machine Learning Research (07/2023)
We hope that our optimisation view and deterministic kernel update rule stimulates research in both deep learning and kernel methods.
Acknowledgments
Both authors would like to acknowledge the support of CSIRO's Machine Learning and Artificial Intel- ligence Future Science Platform.
References
Daniel Adiwardana, Minh-Thang Luong, David R So, Jamic Hall, Noah Fiedel, Romal Thoppilan, Yang, Apoorv Kulshreshtha, Gaurav Nemade, Yifeng Lu, et al. Towards a human-like open- domain chatbot. Xiv preprint orXie:2001.099 2020.
Ben Adlam, Jachoon Lee, Lechao Xiao, Jeffrey Pennington, and Jasper Snock. Exploring the un- certainty properties of neural networks' implicit priors in the infinite-wddth limit. ar preprint arXiv:2010.0703 07355, 2020.
James H Albert and Siddhartha Chib. Bayesian analysis of binary and polychotomous response data. Journal of the American stafistionl Association, 88(422):669 0090,677900 1993.
Luis B. Almeida. A learning rule for asynchronous perceptrons with feedback in combinatorial envi- ronment. 1990.
Sanjeev Arora, Simon S Du, Zhiyuan Li, Ruslan Salakhutdinor, Ruosong Wang, and Dingli Yu. Harness- ing the power of infinitely wide deep nets small-data tasks. nntenaaional Conference Learning Representations, 2020.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances in Neural Infor- mation Processing Systems, 32, 2019.
Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, Joydeep Ghosh, and John Lafferty. Clustering with Bregman divergences. Journal of machine learning research, 6(10), 2005.
Dylan Campbell, Liu Liu, and Stephen Gould. Solving the blind perspective-n-point problem end-to-end with robust diffcrentiable geometric optimization. In Computer Vision-ECCV 2020: 16th Europeon Conference, pp. 244 261. Springer, 2020.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differ- ential equations. Advances in Neural Information Processing Systems, 31, 2018.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming, Advances in Neural Information Processing Systems, 32, 2019.
Younganin Cho and Lawrence K. Saul. Kernel methods for deep learning. In Advances in Newrul Information Processing Systems, pp. 342 350. 2009.
Nicola Muca Cirone, Mand Lemercier, and Cristopher Salvi. Neural signature kernels as infinitewwitth- depth-limits controlled ResNets. International Conference on Machine Learning, 2023.
Michael Collins, Sanjoy Dasgupta, and Robert E Schapire. A generalization of principal components
analysis to the exponential family. Advances in Newral Information Processing Systems, 14, 2001.
Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. Algorithms for learning kernels based on centered alignment. The Journal of Machine Learning Research, 13:795-828 2012.
P Cortez, A Cerdeira, F Almeida, T Matos, and J Reis. Wine Quality. UCI Machine Learning Repository, 2009. DOI: https://oi..or/// www.oo//g....2422C5555..5
17

---

Published in Transactions on Machine Learning Research (07/2023)
Nello Cristianini, John Shawe- Taylor, Andre Elisseeff, and Jaz Kandola. On kernel-target alignment. Adoances in Nearal Information Processing Systems, 14, 2001.
Ricky Der and Daniel Lee. Beyond Gaussian processes: On the distributions of infinite networks. In Advances in Nearal Information Processing Systems, volume 18. MIT Press, 2005.
David Duvenaud. Automatic model construction with Gaussian processes. PhD thesis, University of Cambridge, 2014.
Bradley Efron. Prediction, estimation, and attribution. International Statistical Review, 88:S28 $59, 2020.
Bradley Efron and Trevor Hastic. Computer Age Statistical Inference: Algorithms, Evidence, and Data Science, volume 6. Cambridge University Press, 2021.
Marvin Eisenberger, Aysim Toker, Laura Leal-Taixé, Florian Bernard, and Daniel Cremers. A unified framework for implicit sinkhorn differentiation. In IEEE/CVF Conference on Computer Vision and Pallern Recogriition, pp. (199-18,770 2022.
Laurent Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, and Alicia Tsai. Implicit doep learning. STAM Journal on Mothematics of Data Science, 3(3):930 958, 2021.
Stefano Favaro, Sandra Fortini, and Stefano Peluchetti. Deep stable neural networks: largo-width asymptotics and convergence rates. arXiv preprint arXiv:2108. 02316, 2021.
Stefano Favaro, Sandra Fortini, and Stefano Peluchetti. Neural tangent kernel analysis of shallow alpha-stable ReLU neural networks. arXiv preprint arXiv:2206.n 08065, 2022.
Zhili Feng and J Zico Kolter. On the neural tangent kernel of equilibrium models. preprint, 2021.
Adrià Garriga-Alonso, Carl Edward Rasmussen, and Laurence Aitchison. Deep convolutional networks shallow Gaussian processes, In International Conference Learwing Representations, 2018.
J Gerritsma, R Onnink, and A Versluis. Yacht Hydrodynamics. UCI Machine Learning Repository, 2013. DOL:
Kazimierz Goebel and William A Kirk. Topics in metric fixed point theory. Number 28. Cambridge university press, 1990.
Stephen Gould, Richard Hartley, and Dylan Campbell. Deep declarative networks. IEEE Transactions on Pottern Analysis and Machine Intelligence, 44(8):3988-4000 2021.
Insu Han, Amir Zandieh, Jachoon Lee, Roman Novak, Lechao Xiao, and Amin Karbasi. Fast neural kernel embeddings for general activations. Advances in Neural Information Processing Systems, 2022.
James W Hardin and Joseph W M Hilbe, Generalized Lineor Models and Eztensions. College Station
Tex: StataCorp Press, 4th edition, 2018.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural langent kernel: Convergence and general- ization in neural networks. In Advances in Neural Information Processing Systems, pp. 8571 8580, 2018.
Kahn. Diabetes. UCI Machine Learning Repository. DOL:
Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K Sriperumbudur. Gaus- sian processes and kernel hods: review on connections and equivalences. arXio preprint arXiv:1807.02582 2018.
C. Kelley. Iterative Methods for Linear and Nonlinear Equations. Society for Industrial and Applied Mathematics, 1995. doi: 10.1137/1.7711111999
18

---

Published in Transactions on Machine Learning Research (07/2023)
Diederik P Kingma and Max Welling. Auto-encoding variational Bayes. 2014.
Nicolas Le Roux and Yoshua Bengio. Contimuous neural networks. In Artificial Intelligncce and Statis- lics, pp. 404-414 104-411,20 2007.
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as Gaussian processes. International Conference on Leurning Representations, 2018.
Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. Advances in Neural Information Processing Systems, 33:15156-15172, 2020.
David JC MacKay. Introduction Gaussian processes. 1998.
Julien Mairal, Piotr Koniusz, Zaid Harchaoui, and Cordelia Schmid. Convolutional kernel networks.
Advances in Newral Information Processing Systems, 27, 2014.
Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard E Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks. In The International Conference on Learning Representations, 2018.
McCullagh and J.A. Nelder. Generalized Linear Models, Second Edition. Monographs on Statistics and Applied Probability Series. Chapman & Hall, 1989.
Lassi Meronen, Christabella Irwanto, and Arno Solin. Stationary activations for uncertainty calibration in deep learning. Advonces in Neural Information Processing Systems, 33:2338-283 22500,2300--2 2020.
Shakir Mohaned, Zoubin Ghahramani, and Katherine A Heller. Bayesian exponential family PCA. Advances in Neural Information Processing Systems, 21, 2008.
Radford M Neal. Bayesion learning for neural networks. PhD thesis, University Toronto, 1995.
Frank Nielsen and Vincent. Garcia. Statistical exponential families: A digest with flash cards. arXiv preprint 48X4:30911.4863, 2009.
Roman Novak, Lechao Xiao, Jachoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels are Gaussian processes. In The International Conference on Learning Representations, 2019.
OpenAI, Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, Rafal Jozefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Ponde de Oliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, Ilya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang. Dota 2 with large scale deep reinforcement learning. 2019.
Tim Pearce, Russell Tsuchida, Mohamed Zaki, Alexandra Brintrup, and Andy Necly. Exprcssive priors in Bayesian neural networks: Kernel combinations and periodic functions. In Uncertointy in Artificial Intelligence, 2019.
Stefano Peluchetti, Stefano Favaro, and Sandra Fortini. Stable behaviour of infinitely wide deep neural networks. In International Conference on Artificial Intelligence and Statistics, pp. 1187-1146. PMLR, 2020.
Fernando Pineda. Generalization of back propagation to recurrent and higher order neural networks. In Neural information processing systems, 1987.
R Core Team. R: A Language and Ensironment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2021. URL http:///wwwwwwojjtttooorr..o
19

---

Published in Transactions on Machine Learning Research (07/2023)
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power deep neural networks. In International Conference on Machine Learning, pp. 2847-2854 PMLR, 2017.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems, 20, 2007.
Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian processes for machine learning. Adaptive computation and machine learning. MIT Press, 2006.
Max Revay, Ruigang Wang, and Ian R Manchester. Lipschitz bounded equilibrium networks. arXiv preprint or Xin::2000.01 01.0000..1132.. 0172, 2020.
Danilo Riccio, Matthias J Ehrhardt, and Martin Benning, Regularization of inverse problems: Deep equilibrim models versus bilevel learning, arXie preprint orXiv:2206. 131998 2022.
Herbert Robbins and Sutton Monro. stochastic approximation method. The Annals of Mathemationl Stafisties, pp. 400-407, 1951.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High- resolution image synthesis with latent diffusion models. In IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 10684-10695, 2022.
Cynthia Rudin. Stop explaining black box machine learning madels for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-215, 2019.
C Saunders. Ridge regression learning algorithm in dual variables. In International Conference on Machine Learning, 1998.
Bernhard Schölkopf, Alexander Smola, Francis Bach, et al. Learning with kernels: support vector machines, regulorization, optimization, and beyond. MIT press, 2002.
William Fleetwood Sheppard. On the application of the theory of error to cases of normal distribu- tion and normal correlation. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of Mathematical Physical Character, (192):140, 1899.
Jascha Sohl-Dickstein, Roman Novak, Samuel S Schocnholz, and Jachoon Lec. On the infinite width limit of neural networks with standard parameterization. arXív preprint or Xiv:2000 .07301, 2020.
Poter Sollich. Bayosian methods for support vector machines: Evidence and predictive class probabili- ties. Machine learnóng, 46(1):21 52, 2002.
Athanasios Tsanas and Augeliki Xifara. Energy efficiency. UCI Machine Learning Repository, 2012.
DOI: https://doi.orr/10.225532 CC51307
Russell Tsuchida. Results on infinitely wide multi-layer perceptrons. PhD thesis, The University of Qucensland, 2020.
Russell Tsuchida and Cheng Soon Ong. Deep equilibrium models as estimators for continuous latent variables. In International Conference Artificial Inteliigncee and Stalistics, 2023.
Russell Tsuchida, Fred Roosta, and Marcus Gallagher. Invariance of weight distributions in rectified MLPs. In International Conference on Machine Learning, pp. 5002 5002-5011, 2018.
Russell Tsuchida, Tim Pearce, Chris van der Heide, Fred Roosta, and Marcus Gallagher. Avoiding kernel fixed points: Computing with ELU and GELU infinite networks. In AAAI Conference Artificial Intellignnce, volume 35, pp. 9967-9977, 2021.
Russell Tsuchida, Suk Yee Yong, Mohammad Ali Armin, Lars Petersson, and Cheng Soon Ong. Declar- ative nets that are equilibrium models. In International Conference Learning Representations, 2022.
20

---

Published in Transactions on Machine Learning Research (07/2023)
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Adoances in Neural Information Processing Systems, 30, 2017.
Roman Vershyuin. figh-dimensional probability; An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Martin J. Wainwright. High-Dimense Dimensionnll Statistics: A Non-Asymptotic Viewpoint. Cambridge Se- ries in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10.1017/
108627777
Martin J Wainwright, Michael I Jordan, et al. Graphical models, exponential families, and variational inference. Foundations and Trendsm in Machine Learnóng, 1(1 2):1 305, 2008.
Paul FV Wiemann, Thomas Kneib, and Julien Hambuckers. Using the softplus function to construct alternative link functions in generalized linear models and beyond. arXiv preprint arXiv:2111.14207, 2021.
Christopher KI Williams. Computing with infinite networks. In Advances in Neural Information Processing Systems, pp. 295 301, 1997.
Ezra Winston and J Zico Kolter. Monotone operator equilibrium networks. Advances in Neural Infor- mation Processing Systems, 33:10716 10728, 2020.
Blake Woodworth, Suriya Gunasekar, Jason D) Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes overparametrized models. In Confer ence Learning Theory, pp. 3635-3677 3673. PMLR, 2020.
Stephen J. Wright and Benjamin Recht. Optimization for Dato Analysis. Cambridge University Press, 2022. doi: 10.1017/9781000004222
Xingyu Xie, Qiuhao Wang, Zeman Ling, Xia Li, Yisen Wang, Guangcan Liu, and Zhouchen Lin. Opti- mization induced equilibrium networks, arXiu preprint arxi::1005. 192228 2021.
Greg Yang. Wide feedforward or recurrent neural networks of any architecture are Gaussian processes. In Advances in Neural Information Processing Systems, pp. 9947-9996 19600 2019a.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. In arXiv preprint arXiv:1902 fto:1990.04700 2019b.
I-Cheng Ych. Concrete Compressive Strength. https://doi.orr/10 2wwp//..4432////// C5PK67.
UCI Machine Learning Repository, 2007. DOL:
Amir Zandich, Insu Han, Haim Avron, Neta Shoham, Chaewon Kim, and Jinwoo Shin. Scaling neural tangent kernels via sketching and random features. Advances in Neural Information Processing Systems, 34:1062-1073, 2021.
21


Reviews:
[{"review_id": "cnZK2ThCQp", "reviewer": "Reviewer_NhqZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Pros**\n* The paper addresses an interesting topic, considering infinite-width, infinite-depth models (e.g., Deep Equilibrium Models with infinite feature dimensionality).\n* The theory appears sound, although I did not check the proofs in detail.\n* The mathematical exposition is mostly well-written, except for some notational issues mentioned below.\n* Following Tsuchida & Ong (2022), they discuss some interesting connections between DEQ architectures and statistical concepts (e.g., the relationship between inverse link functions in statistics and activation functions in ML).\n\n**Cons**\n* In the 4th paragraph of the Introduction, what does \"model-based deep learning\" mean?\n* I think it would be important to state the high-level contributions and takeaways before the start of Section 1.1, which already starts introducing fairly heavy mathematical notation.\n\n* The exposition in the \"Updates in feature space\" paragraph of Section 1.1 is not clear.\n* In Section 1.1, \"$\\psi_{X_1}$ is the evaluation of an implicit function of $X_1$\" --> why not just \"a function of\"?\n* \"Let $\\psi_{X_1}^{(t)}$ be a representation of the solution at iterate $t$.\" -> Iterate $t$ of what? The wording here seems backwards, because it defines the function $g^{(t)}$ _after_ $\\psi_{X_1}^{(t)}$ when it should be defined before.\n* It is confusing to introduce $X_1$ and $X_2$ in Eq. 1 as though they are central to the definition of $\\psi_X^{(t)}$.\n* Regarding Eq. 2, the paper should re-state that $m$ is the feature dimensionality, otherwise it is quite unclear, as $m$ does not appear in the right-hand side of any of the equations. The feature dimension is only briefly implied in the previous paragraph as $\\psi_{X_1} \\in \\boldsymbol{\\psi} \\subseteq \\mathbb{R}^m$.\n* The writing in the \"Deep equilibrium kernels\" paragraph in Section 1.1 is unclear: it does not state why we would want to construct the matrix $\\Psi^{(t+1)}$ or how it would be useful. Also, it would be clearer to write out the full matrix as\n$$\n\\Psi^{(t+1)} =\n\\begin{bmatrix}\n\\Psi_{11}^{(t+1)} & \\Psi_{12}^{(t+1)} \\\\\n\\Psi_{21}^{(t+1)} & \\Psi_{22}^{(t+1)}\n\\end{bmatrix}\n$$\n  rather than writing \"a PSD matrix containing $\\Psi_{11}^{(t+1)}$, $\\Psi_{12}^{(t+1)}$, $\\Psi_{22}^{(t+1)}$.\n* In the \"Updates in kernel space\" box: 1) clarify what the updates correspond to; 2) the writing is confusing, as $G$ is not described when it is first used.\n* There is new notation $\\Phi$ used without sufficient explanation.\n* In the Contributions paragraph in Section 1.1, there is far too much referencing of future sections, equations, and theorems that have not been introduced yet, and this makes it hard for the reader to follow.\n- \"The objective (17) to which we apply SGD\" --> This references an equation that is first defined 6 pages away, which the reader should not be expected to flip back-and-forth through the whole paper to find.\n- The statement \"Theorem 4 and Corollary 5 (informal)\" is a bit jarring and out of place, as it is stated before any of the other theorems; if anything, I think that this writing can be simply stated in a paragraph without the Theorem block. The Theorem 4 statement again references Eq. 17, so this would need to be introduced in Section 1.1.\n- The last sentence of Section 1.1, \"We further quantify the degree to which the $\\ell$DEK is an invariant of SGD when treated as an ffDEK.\" is not clear without context, and does not currently fit well in the introduction.\n- \"DEQ whose iterates are computed with stochastic approximation rather than as a deterministic fixed point iteration.\" --> This needs further explanation: what is mean by \"stochastic approximation\" here?\n- In Section 2.1, the \"unsupervised learning problem for a DEQ\" is introduced, but the vast majority of work on DEQs considers the supervised setting. The work by Tsuchida & Ong 2022 should be cited here as one of the few that considers the unsupervised setting.\n- I think that Section 2.4 on notation sould be moved earlier, near the introduction.\n- In Section 2.4, it states that \"superscripts indicate a layer or iteration of a naive fixed point solver, both of which turn out to be the same in our constructions\" --> this makes it sound like it is unique to this paper's construction, while it is a general property of DEQs.\n- \"$V \\phi$ having components with variance which stays in $d$ and $m$\" --> what does it mean that the variance styas in $d$ and $m$?\n- In Section 3.2, it is not clearly stated what \"the dimension of the exponential family\" means.\n- In Section 3.2, it should be clarified whether the \"random object $V$\" refers to the model parameters?\n- The presentation in Section 3.2 is unclear because it is not stated clearly enough that $m$ is the feature space dimensionality and $d$ is the dimensionality of the exponential family.\n- In Section 3.3, it is unclear to mention corollaries and theorems that have not been stated yet, e.g., \"In this special case, our main result (Theorem 4) implies Corollary 3.\"\n- Structurally, it is _very_ confusing that Assumption 2(a) is stated in Section 3.2, while Assumption 2(b) is stated in Section 3.5---Assumptions 3 and 4 are listed in between them! What is the justification for this?\n- In Corollary 3, where does $F$ come from? Why is the identity matrix added in $F$? Also, it is probably worth re-iterating that $\\Phi$ is a matrix of kernel evaluations.\n- There needs to be more discussion about the takeaways and implications of Theorem 8.\n* It would be important to clearly define what is meant by \"an invariant of SGD.\"\n* The right-hand side of Eq. 20 is identical to that in Theorem 4, but is hard to parse and compare. It may be better to write $\\Psi_{ij} = G(...)$  and then optionally write out the RHS.\n* In Section 3.5, it is unclear what the sensitivity refers to, e.g., sensitivity to what?\n* The subplots in Figure 2 are too small, and don't have legends (the legend information should not be just in the caption). In addition, each subplot should have a title to differentiate them, e.g., \"Gaussian Exponential Family,\" \"Bernoulli Exponential Family\" and \"Rectified Gaussian Exponential Family.\" Also, it is never stated what the dashed red line at $y=1$ corresponds to.\n\n* This paper does not cite other work on neural tangent kernels for DEQ models, such as [1].\n\n[1] Feng & Kolter. \"On the Neural Tangent Kernel of Equilibrium Models\" 2021.\n\n**Minor**\n* The abbreviation for Deep Equilibrium Kernel (DEK) would be pronounced identically to DEQ, which is the standard terminology for deep equilibrium models; the authors might want to consider an alternative abbreviation.\n* Why are the equations in Eq. 2 expressed in terms of $t+1$ rather than $t$?\n* A reference should be provided for Banach's fixed point theorem (Theorem 1).\n* A great deal of space in the paper is devoted to background, comprising 4 pages (page 2.5 to page 6.5).\n* Throughout the paper, it would be better to use the notation \"Eq. 10\" rather than just \"(10).\" This is especially confusing in Corollary 3, where it states \"$G$ (3) exists and can be decomposed into $G$ (5) satisfying,\" because it is not obvious whether these parentheses are equation references or function applications.\n* $U$ needs to be defined when it is first used, in $f_U(Z^*) = Z^*$.\n* Extra space after \"(NTK) (Jacot et al., 2018) .\" on page 6.\n* In Section 3.2, the reference for SGD is weird (Wright & Recht, 2022). Shouldn't this be Robbins & Monro, \"A Stochastic Approximation Method\" 1951?\n* In Eq. 15, it is slightly confusing to write the same SGD update twice for $X_1$ and $X_2$.\n* The first sentence of Section 3.3 is almost identical to the last sentence of Section 3.2.\n* I don't know why Remark 6 is delineated as a Remark rather than just being part of the text.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper analyzes deep equilibrium models in the kernel regime, taking the dimensionality of the implicit representations to infinity. They define kernels in terms of the features of an implicit architecture, that are the approximate fixpoints resulting from  $t$ iterations of naive forward iteration. They consider three variants of the Deep Equilibrium Kernel (DEK): 1) a kernel for finite-dimensional features (with a finite number of fixpoint solver iterations); 2) a kernel for infinite-dimensional features (with a finite number of fixpoint solver iterations); and 3) a kernel for infinite-dimensional features and infinite iterations of the fixpoint solver.\n\nThey provide four pages of background on fixed point theory, exponential families, and kernels for neural networks (e.g., NTK). Their main contribution is theoretical: they show that there exists a closed-form update rule in kernel space (e.g., operating on a $2 \\times 2$ matrix of kernel evaluations) and that under certain conditions, this update converges to a fixpoint.\n\nThe authors perform a couple small-scale experiments, using the proposed DEK for kernel ridge regression. They show that, because DEQ is a generalization of the neural network kernel (NNK), it performs at least as well in all cases.\n\nUnfortunately, there are several issues with the exposition. The writing could use another pass to improve clarity, as there are many places where the structure is disorganized and confusing to the reader, discussed in the Cons section below.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I'd mostly request changes around writing, presentation, and positioning of contributions as stated in detail in my review above.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KBdlVMOJPk", "reviewer": "Reviewer_xp66", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe most interesting result of the paper is that it finds the close-form expression for the DEK update, for several special settings of deep implicit neural network. For more general cases, it also provide an relation of $G$ with some quantities, which I believe can be numerically computed.\n\nThe proving techniques looks novel and contains new insights. It may be helpful for solving similar problems in other settings.\n\n**weakness**\n\nThe current results are limited to the cases where the inference is done via SGD-like operation. I think it will be more interesting if it can apply to more standard settings. \n\nI don't quite see the connection between the DEK with the kernels arising from neural networks, such as NNK, NTK. The paper spends a large space to describe those kernels, however, none of them seems to be DEK.\n\nThe paper is potentially misleading when talking about SGD, especially in the title, abstract and introduction. Because SGD often referes to the training of a neural network; however, in this paper SGD referes to the inference through a layer. The paper should clarify this difference early on in the paper.\n\nThe problem is not clearly setup until very late in the context. For example, in section 1.1 when talking about feature space, it is not clear what the feature should be, and what the dimension m means. Still in section 1.1, it is not clearly explained why one should consider the 2x2 matrix, instead of a nxn matrix. In addition, in section 3.2, it is not clear what the random object V is. I think the problem should be setup clearly early on, and physical meaning of each quantity should also be clarified. \n\nIt is confusing to me that, in section 2.4, the inner product of two features is a feature \"$\\psi \\times \\psi \\to \\psi$\". Is that a typo?  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers a special case of implicit neural networks, where the inference(feedforward) through a layer is equivalent to a SGD update step of a certain optimization problem. In the infinite feature dimension limit, it tries to find a closed-form update rule $G$ of the DEK kernel, which corresponds to the SGD update step in the feature space. The theory shows that, under certain assumptions, an update rule $G$ exists and in certain speical cases $G$ has closed form expression.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The problem should be setup clearly early on, and physical meaning of each quantity should also be clarified. It is better to give an illustrating example.\n\n2. Clarify the connection between DEK and NNK, NTK.\n\n3. Clarify the different meaning of SGD of this paper in the abstract and early in introduction.\n\n4. Talk about the limitation (or extenstion) to general cases where the features are not obtained by SGD-like inference.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "80DC4diPTs", "reviewer": "Reviewer_RRbN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This works introduces a kernel for the deep equilibrium models. Empirically, the kernel is shown to outperform the NTK kernel\n\n\nWeakness:\nThe motivation and the promise of the paper is to propose a DEQ kernel to understand deep equilibrium models. However, I am not sure the question is answered throughout the paper: can the DEK understand deep equilibrium models? This should deserve extensive discussion and empirical validation. For example, I would like to see that a standard deep equilibrium model, as we increase its width, approaches the theoretical predictions of the DEK theory. This part is distinctively lacking in the current draft", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a new kernel method called deep equilibrium kernel, the kernel is shown to be a generalization of common kernels in deep learning", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "\nSee weakness. I think extensive discussion and empirical validation of how DEK explains deep equilibrium models is needed", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NZ8GnzJ9rf", "reviewer": "Reviewer_1C9V", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strength \n\n1. The family of kernels studied are quite interesting as well as their connection to stochastic exponential family, though I have some concern about this setup. \n\n2. The paper covers a variety topics in ML, e.g. Neural networks kernels, deep equilibrium models, exponential family, etc. \n\n# Weaknesses. \n\n1. The paper is hard to follow. The paper requires some major changes to improve readability. See details comments in the next section.  \n\n2. Several settings in the paper seem unnatural, e.g., SGD updates on features (vs. parameters), optimization objective is stochastic from step to step, etc. \n\n3. Connection to deep equilibrium models (Bai) is unclear. Is it the infinite-width limit of DEQs (this is what I expect from the name DEK)? There is a key difference regarding weight-tying, please clarify. In addition, what is special about `equilibrium` part of the DEK other than being a fixed point of certain iteration? E.g., one can also iterate the NNKs (Lee) to obtain a fixed point. \n\n4. Experiments need some clarification. What is the dataset's name, UCI? Can you also compare it with existing works, e.g. table 2 in [1]. In addition, it will be good to have some comparison vs Lee (and potentially follow-up paper) on other dataset, e.g. CIFAR-10. \n\n5. The math/notations are difficult to follow. Many of them are left unexplained; see next section. \n\n[1] EXPLORING THE UNCERTAINTY PROPERTIES OF NEURAL NETWORKS’ IMPLICIT PRIORS IN THE INFINITEWIDTH LIMIT", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a family of recursively defined kernels (called DEK, deep equilibrium kernels) that are associated with specific stochastic updates on the features. More precisely, the authors defined a sequence of features $\\phi^t$, where $\\phi^{t+1}$ is obtained from $\\phi_t$ via an SGD update which maximizes the log-likelihood associated with a certain stochastic exponential family. Under several assumptions and in certain scaling limits, the authors prove convergences of the kernel $\\phi_t^T \\phi_t \\to K_t$ and obtain the recursive formula  $K_{t+1} = G(K_t)$ for some $G$. If $G$ is a contraction, then $K_t\\to K^*$ for some fixed point. \n\nThe authors point out that the DEK is different from the NNK (Lee 2018) and compare performance between them on some benchmarks (UCI datasets?) and see some benefits from DEK. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Streamlining the presentation. Exponential family/link functions, NNK, are splashed around the paper. I am trying to figure out what are the main results of the paper, and it is only evident after reading the first part of section E in the appendix. What you need is just a stochastic update to the features, while the (stochastic) exponential family is one approach to generate such an update. As such, this seems to be a particular setting in the Tensor Program (Yang, [2])\n\n2. Two major points regarding the update rules. 1. SGD update is to the features (vs. variables) with random objectives $\\Gamma(X)$. 2. $V^t$ are freshly resampled (vs. sharing) during each update. Is there an explanation behind doing so? Or is it just a technical consideration to make sure the arguments can go through? Please motivate the update rule (15). \n\n3. There is a large knowledge gap between update (15) and Theorem 4. I only understand the connection and main result of the paper after reading its proof in Section 4. Please fill in the gap and move some parts of the content in Section E to the main text. The idea is not difficult, but the presentation makes it hard to follow. \n\n\n4. Too many notations without proper explanation. Several examples are in order. (1) I think average readers will have a hard time to understand the notations in section 1.1, which are not clearly defined. (2) What is $U$ in the second paragraph of page 4, which is later defined. (3) What is $L$ in section 3.2? which is defined much later in eq (13). (4) The inner product $\\psi \\times \\psi \\to \\psi$ above Section 3 is problematic, the same as the definition of $\\kappa$ (the domain is incorrect). $\\psi$ a subset in $\\mathbb R^m$. (5) I don't understand what \"over-parameterised\" and \"under-regularised\" mean on page 9. (6) $W$ is used for both vectors in matrices\n\n\n\nothers. \n- NTK is not very relevant to the paper, or am I missing something?  \n- In the appendix E, why the norm of $\\|\\psi_X\\| $ is bounded, isn't it the size is of $m$, which goes to $\\infty$ by the assumption you made. \n\n\n[2] Tensor Programs I: Wide Feedforward or Recurrent Neural Networks of Any Architecture are Gaussian Processes\n https://arxiv.org/abs/1910.12478", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Various concerns were raised regarding presentation and positioning.  While the authors have addressed many of them, some of the reviewers feel that more profound changes are required.  The authors are asked to take this feedback into account and appropriately update the text towards publication.
Decision: Accept (poster)