# Equilibration and Typicality in Quantum Processes

Pedro Figueroa Romero

partempty subsection  I certify that I have made all reasonable efforts to
secure copyright permissions for third-party content included in this thesis
and have not knowingly added copyright content to my work without the owner’s
permission.

© Pedro Figueroa Romero (2020)

##  Chapter 0 Abstract

Forgetfulness is a common occurrence in natural processes. After all, if each
carbon atom remembered its detailed past, then each of these would have a
unique behaviour and there would be no sense in classifying atoms and
molecules. Moreover, without forgetfulness, repeatability would be impossible.
Despite this, small systems constantly leak information about their state to
their surroundings, and quantum mechanics tells us that this information can
never be deleted, so that it invariably returns to influence their future
behaviour.

How can physical nature be forgetful if it is not allowed to forget?
Precisely, in the theory of open quantum systems, memory is the rule and
forgetfulness the exception. This conundrum is not dissimilar from that of the
emergence of the laws of thermodynamics purely from underlying quantum
mechanical laws, which dates from the inception of quantum mechanics itself,
and is still fertile ground for important foundational and practical
questions.

In this thesis, we address the emergence of forgetfulness—more precisely
called _Markovianity_ —through a generalization of the concepts of
equilibration on average and typicality, previously employed to study the
emergence of statistical mechanics from quantum mechanics: the first shows how
time-dependent quantities of quantum systems evolve towards fixed values and
stay close to them for most times, while the second one argues that small
subsystems of a composite are in equilibrium for almost all states of the
whole. Using the process tensor framework for quantum stochastic processes, we
introduce an extended notion of equilibration, characterizing the conditions
under which a multitime quantum process can be approximately described by an
equilibrium one. Furthermore, without resorting to the Born-Markov assumption
of weak coupling, we show that Markovian processes are typical, and prove that
there are physical non-Markovian processes that with high probability look
almost Markovian for all orders of correlations, in a phenomenon that we call
_Markovianization_.

The results within this thesis bridge the aforementioned gap between what we
see in the real world and what idealised physical theories say. The main
implications of these findings are twofold: foundationally, they give birth to
almost Markovian processes from closed quantum dynamics, while for
applications and experiments, they pave the way to predict and quantify the
rate at which memory effects become relevant.

##  Chapter 1 Declaration

This thesis contains no material which has been accepted for the award of any
other degree or diploma at any university or equivalent institution and, to
the best of my knowledge and belief, contains no material previously published
or written by another person, except where due reference is made in the text
of the thesis.

Melbourne, September 2020

##  Chapter 2 Acknowledgements

I have grown incommensurately in the last three and a half years, and despite
reaching this point in such dire times (amidst the covid-19 pandemic), I can
only be grateful for all the people who supported me in one way or another.

I am deeply thankful to both Kavan Modi and Felix Pollock for giving me the
chance to do this research, for their patience, enthusiasm, kindness and
guidance; they are two of the brightest minds that I have been fortunate to
learn from and I hold both in the highest regard as scientists and as human
beings. I was also very fortunate to have been part of the unique Monash
Quantum Information Science ($\allowdisplaybreaks[4]\mathsf{MonQIS}$) group, I
am grateful for the support and insightful conversations with all its members,
as well as for the memes and the shenanigans. My special thanks to Francesco
Campaioli, Mathias Jørgensen, Roberto Muñoz and Magdalini Zonnios for their
support, friendship and good times. Thanks as well to Cody Duncan, honorary
classical $\allowdisplaybreaks[4]\mathsf{MonQIS}$ member, for helping me
proofreading my early drafts.

I specially thank Cristian Sierra, who showed up when I was in the middle of
my PhD and is now a dearest friend and brother for life, he was there to help
me get through the darkest days as well as to have fun on the sunny ones, I
thank him for sharing both the mundane and the outstanding with me.

I am sincerely grateful to the whole School of Physics & Astronomy for the
accommodating and amicable atmosphere, together with all the academic and
administrative facilities and support. Financially, this work would not have
been possible without the Monash Graduate Scholarship (MGS) and the Monash
International Postgraduate Research Scholarship (MIPRS).

At this stage of my life, I am now fairly convinced that luck plays a higher
role in life than most talents one could put forth, and in this sense, I am
incredibly lucky for having my family, _mamá, papá y mi hermana Ale_ , and
their support from so far away for all this time. To be writing these lines
was literally unbelievable ten years ago as a _high-school_ dropout, but I
never lacked their unconditional support and this is only possible due to
them.

Finally, in this same spirit, I am grateful to Felicia Grant for filling my
life with light and colour, bringing warmth and safety in these uncertain
times, and being my constant reminder of what really matters in life.

##  Chapter 3 Publications

The main results in this thesis have been presented in the following
publications:

  * [FigueroaRomero2020equilibration] _Equilibration on average in quantum processes with finite temporal resolution_
Pedro Figueroa-Romero, Felix A. Pollock and Kavan Modi
Phys. Rev. E 102, 032144.

  * [FigueroaRomero2019almostmarkovian] _Almost Markovian processes from closed dynamics_
Pedro Figueroa-Romero, Kavan Modi, and Felix A. Pollock
Quantum 3, 136 (2019).

  * [FigueroaRomero2020makovianization] _Markovianization by design_
Pedro Figueroa-Romero, Felix A. Pollock and Kavan Modi
Preprint: arXiv:2004.07620 [quant-ph].

By date of writing and publication, these are ordered as
[FigueroaRomero2019almostmarkovian], [FigueroaRomero2020equilibration],
[FigueroaRomero2020makovianization], but for sake of presentation we follow
the order cited above in the corresponding Chapters LABEL:sec:equilibration,
LABEL:sec:typicality and LABEL:sec:_Markovianization_by_design.

_No hay nada más vertiginoso que mirar atrás._

###### Contents

  1. 0 Abstract
  2. 1 Declaration
  3. 2 Acknowledgements
  4. 3 Publications
  5. 4 Introduction
    1. 1 Outline

*

*

## Acronyms

##  Chapter 4 Introduction

Thermodynamics is without a doubt the most resilient, universal and, in a
sense, _strange_ theory of physics. It was originally devised as a
phenomenological theory, surviving all major revolutions in science and
serving as the highest authority for most technological developments.
Similarly, the concept of energy pervades the social imaginarium (albeit often
in pseudo-scientific ways) and there’s arguably no more popular physical law
than the first law of thermodynamics, which, together with the remaining three
laws (or two, depending who one asks), no one has yet been able to contradict
in a real laboratory.

On the other hand, quantum mechanics is one of the fundamental pillars on
which any physical theory must stand. By circa 1930, the mathematical
formalism of quantum mechanics was established thoroughly by John von Neumann
in Ref. [vonNeumann], and given that statistical mechanics—the mathematical
spinal cord of thermodynamics—was already a mature field of research, it is no
surprise that he would quickly approach a quantum theory of statistical
mechanics and raise foundational questions that remained largely unsolved
until very recently.

A characteristic feature of quantum mechanics is that of generating a distinct
type of correlations which is non-local in nature, and this was just recently
seen to be key in explaining the quantum emergence of statistical mechanics.
Correlations, however, can also be temporal, and it turns out that many
foundational questions regarding these correlations in quantum mechanics can
be posed in an analogous way to those regarding the foundations of statistical
mechanics. Namely, how do quantum systems become _forgetful_ , i.e. behaving
independently of their detailed past? Or how resilient is a system in thermal
equilibrium when temporal correlations are present and when the act of
observing the system itself disturbs it?

The overarching goal of this thesis is to provide an in-depth and novel
account of the relationship between the phenomenon of equilibration, which is
a pillar in the foundations of statistical mechanics, and general quantum
processes that incorporate a full account of correlations and memory effects;
namely, under what conditions do quantum processes with seemingly negligible
temporal correlations arise, given that processes with non-vanishing
correlations are the norm? And furthermore, how do we account for the
pervasiveness of these in nature? In investigating these questions, we find a
non-trivial interplay between complexity and randomness, further
characterizing how equilibration comes about in quantum processes.

###  1 Outline

The rest of text is organised as follows: Part I consists of Chapters
LABEL:sec:qm101 to LABEL:sec:processes, containing an overview and explanation
of existing literature and no original results, followed by Part II, which
consists of Chapters LABEL:sec:equilibration to
LABEL:sec:_Markovianization_by_design and discusses the original results
obtained during this PhD.

LABEL:sec:qm101

We briefly introduce the concepts and the mathematical framework of quantum
mechanics such as quantum states, observables, measurements, closed system
evolution and distinguishability of quantum states.

LABEL:sec:statmech

We first motivate this chapter with a brief discussion of the second law of
thermodynamics and why a derivation purely from quantum mechanics is needed.
This is followed by a discussion of the main results in the literature showing
how quantum systems dynamically fulfil the second law given solely the quantum
mechanical framework, in a concept known as equilibration on average. Finally,
we discuss how the backbone of the second law, namely the fundamental
postulate of statistical mechanics, emerges naturally through entanglement in
quantum mechanics without any a-priori assumptions by appealing to a notion of
typicality.

LABEL:sec:processes

We begin by describing more general quantum operations with the concept of
quantum channels and three of their main representations, namely dilations,
the operator sum representation and the Choi Jamiołkowski isomorphism. We then
describe open quantum dynamics and the problem of initial correlations,
together with a resolution known as the superchannel. Following this, we
motivate the generalization encoding the initial correlations problem via
multiple interventions, whereby temporal correlations between more than two
points become relevant, in turn leading to the generalization of the
superchannel known as the process tensor. We describe how the process tensor
framework generalizes the concept of classical stochastic processes and the
concept of Markovianity, contrasting with several different approaches in the
literature which have proved to be problematic. We finally discuss how the
process tensor framework naturally provides an unambiguous measure of non-
Markovianity.

LABEL:sec:equilibration

In this chapter we blend the concepts in the first chapters to study the
conditions under which a process with a finite temporal resolution can be
approximately described by an equilibrium one, which is equivalent to having
operations being implemented with a fuzzy clock or to having a system with
uniformly fluctuating energies. We first define what we mean by an equilibrium
process and by a fuzzy clock, and we then derive a generalization of the
concept of equilibration on average to one which can be operationally assessed
at multiple times, placing an upper-bound on a new observable
distinguishability measure comparing a multitime process with a fuzzy clock
against a fixed equilibrium one. We will see that the conditions for
equilibration to occur can be extended, with genuine multitime contributions
depending on the fuzzy process and the amount of disturbance of the observer’s
operations on it. We finally motivate a parallel between the concepts of
subsystem equilibration, thermalization and the emergence of statistical
mechanics, and process equilibration, _Markovianization_ and the emergence of
memorylessness in nature. This chapter is based on Ref.
[FigueroaRomero2020equilibration]

LABEL:sec:typicality

By bridging the ideas from the discussion of the emergence of statistical
mechanics and the postulate of equal a-priori probabilities to the realm of
quantum processes, we argue that this naturally leads to the question of the
emergence of memoryless processes, known as Markovian, purely from the rules
of quantum mechanics. Motivated by the results on typicality for quantum
states, we are able to formally prove that a quantum process drawn uniformly
at random will be almost memoryless with high probability whenever it is
undergone within a large-dimensional environment. We argue that our results
have a parallel interpretation to the case of the emergence of statistical
mechanics in the sense of replacing ad-hoc assumptions and approximations to
render quantum processes memoryless. We finally discuss the limitations of the
typicality approach, the most contentious of which is further discussed in the
following chapter. This chapter is based on Ref.
[FigueroaRomero2019almostmarkovian]

LABEL:sec:_Markovianization_by_design

Almost all quantum processes drawn at random within a large environment will
be almost Markovian. However, nature seldom behaves randomly. In this chapter
we identify a class of physically motivated quantum processes –known as
unitary designs– that satisfy a statement known as a large deviations bound,
quantifying the probability that these differ greatly from their Markovian
counterparts. We show that, similar to the way that quantum systems
thermalize, quantum processes _Markovianize_ in the sense that they can
converge towards Markovian processes in the correct limits, and in particular
as the overall complexity of the interactions in the whole system increases.
We further exemplify our result making use of an efficient construction of an
approximate unitary design with an $\allowdisplaybreaks[4]n$-qubit quantum
circuit mediated by two-qubit interactions only, showing how seemingly simple
systems can speedily become forgetful. We finally discuss potential
applications as well as further open questions related to the forgetfulness of
nature. This chapter is based on Ref. [FigueroaRomero2020makovianization].


$\widehat{\Sigma}_{h}^{\text{cov}}$ are close. Recall the definition of the
latter:

$\displaystyle\widehat{\Sigma}_{h}^{\text{cov}}=\frac{1}{M_{0}}I+\frac{1}{M_{0}N_{0}}\sum_{m=1}^{M_{0}}\sum_{t=(m-1)N_{0}+1}^{mN_{0}}\phi(x_{t,h},a_{t,h})\phi(x_{t,h},a_{t,h})^{\top}.$

We now apply Lemma A.3 with $n=N_{0}$ and

$\displaystyle
X_{k}=\frac{1}{M_{0}}\sum_{m=1}^{M_{0}}\phi(x_{\tau(m,k),h},a_{\tau(m,k),h})\phi(x_{\tau(m,k),h},a_{\tau(m,k),h})^{\top}-\frac{1}{M_{0}}\sum_{m=1}^{M_{0}}\mathbb{E}_{(x_{h},a)\sim\pi_{m}}\left[\phi(x_{h},a)\phi(x_{h},a)^{\top}\right],$

for $k=1,\ldots,N_{0}$, where $\tau(m,k)\triangleq(m-1)N_{0}+k$. Note that
$X_{k}^{2}\preceq I$. Therefore, we can pick $A_{k}=I$ and $\sigma=1$. By
Lemma A.3, we have with probability at least $1-\delta$,

$\displaystyle\left\|{\widehat{\Sigma}^{\text{cov}}_{h}-\frac{1}{M_{0}}I-\Sigma_{h}^{\text{cov}}}\right\|_{\text{op}}\leq\sqrt{\frac{8\log(d/\delta)}{N_{0}}}.$

Following the same proof as [Meng and Zheng, 2010, Theorem 2.1], we have

$\displaystyle\left\|{\left(\frac{1}{M_{0}}I+\Sigma_{h}^{\text{cov}}\right)^{-1}-\left(\widehat{\Sigma}_{h}^{\text{cov}}\right)^{-1}}\right\|_{\text{op}}\leq
M_{0}^{2}\left\|{\widehat{\Sigma}^{\text{cov}}_{h}-\frac{1}{M_{0}}I-\Sigma_{h}^{\text{cov}}}\right\|_{\text{op}}\leq
M_{0}^{2}\sqrt{\frac{8\log(d/\delta)}{N_{0}}}\leq\frac{\alpha}{2}.$ (by our
choice of $N_{0}$ and $M_{0}$)

Consequently, for any vector $\phi$ with $\|\phi\|\leq 1$, we have

$\left|\left\|{\phi}\right\|_{\left(\frac{1}{M_{0}}I+\Sigma_{h}^{\text{cov}}\right)^{-1}}^{2}-\left\|{\phi}\right\|_{\left(\widehat{\Sigma}_{h}^{\text{cov}}\right)^{-1}}^{2}\right|\leq\left\|{\left(\frac{1}{M_{0}}I+\Sigma_{h}^{\text{cov}}\right)^{-1}-\left(\widehat{\Sigma}_{h}^{\text{cov}}\right)^{-1}}\right\|_{\text{op}}\leq\frac{\alpha}{2}.$

Therefore, combining everything we have

$\beta\|\phi(x,a)\|_{\widehat{\Sigma}^{+}_{k,h}}^{2}\leq\frac{\beta}{\delta_{e}}\left(\|\phi(x,a)\|_{\left(\widehat{\Sigma}_{h}^{\text{cov}}\right)^{-1}}^{2}+\frac{\alpha}{2}\right)+\frac{1}{4}\leq\frac{3\beta\alpha}{2\delta_{e}}+\frac{1}{4}\leq\frac{1}{2},$

where the last two steps use the fact $x\in{\mathcal{K}}$ and the value of
$\alpha$. This finishes the proof. ∎

Next, we define the following notations for convenience due to the epoch
schedule of our algorithm, and then proceed to prove the main theorem.

######  Definition 2.

$\displaystyle\overline{\ell}_{k}(x,a)$
$\displaystyle=\frac{1}{W}\sum_{t=T_{0}+(k-1)W+1}^{T_{0}+kW}\ell_{t}(x,a)$
$\displaystyle\overline{Q}_{k}^{\pi}(x,a)$
$\displaystyle=Q^{\pi}(x,a;\overline{\ell}_{k})$
$\displaystyle\overline{\theta}_{k,h}^{\pi}$ $\displaystyle~{}~{}\text{is such
that}~{}~{}\overline{Q}_{k}^{\pi}(x,a)=\phi(x,a)^{\top}\overline{\theta}_{k,h}^{\pi}$
$\displaystyle B_{k}(x,a)$
$\displaystyle=b_{k}(x,a)+\left(1+\frac{1}{H}\right)\mathbb{E}_{x^{\prime}\sim
P(\cdot|x,a)}\mathbb{E}_{a^{\prime}\sim\pi_{k}(\cdot|x^{\prime})}[B_{k}(x^{\prime},a^{\prime})]$
$\displaystyle\widehat{B}_{k}(x,a)$
$\displaystyle=b_{k}(x,a)+\phi(x,a)^{\top}\widehat{\Lambda}_{k,h}\qquad\qquad\text{{(for
$x\in X_{h}$)}}$

###### Proof of Theorem 6.1.

We first analyze the regret of policy optimization after the first $T_{0}$
rounds. Our goal is again to prove Eq. (21) which in this case bounds

$\sum_{k=1}^{(T-T_{0})/W}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\sum_{a}\Big{(}\pi_{k}(a|x)-{\pi^{\star}}(a|x)\Big{)}\left(\overline{Q}^{\pi_{k}}_{k}(x,a)-B_{k}(x,a)\right)\right].$

The first step is to separate known states and unknown states. For unknown
states, we have

$\displaystyle\sum_{k=1}^{(T-T_{0})/W}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\notin{\mathcal{K}}]\sum_{a}\Big{(}\pi_{k}(a|x)-{\pi^{\star}}(a|x)\Big{)}\left(\overline{Q}^{\pi_{k}}_{k}(x,a)-B_{k}(x,a)\right)\right]$
$\displaystyle\leq\frac{(T-T_{0})He}{W}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\notin{\mathcal{K}}]\right]=\widetilde{\mathcal{O}}\left(\frac{dH^{3}T}{\alpha
W}\right),$

where the first step is by the facts $0\leq\overline{Q}^{\pi_{k}}_{k}(x,a)\leq
H$ and $0\leq B_{k}(x,a)\leq(1+\frac{1}{H})^{H}\times H\leq He$ (Lemma F.1),
and the second step applies Lemma D.4. For known states, we apply a similar
decomposition as previous analysis, but since we also use function
approximation for bonus $B_{t}(x,a)$, we need to account for its estimation
error, which results in two extra bias terms:

$\displaystyle\sum_{k=1}^{(T-T_{0})/W}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}\Big{(}\pi_{k}(a|x)-{\pi^{\star}}(a|x)\Big{)}\left(\overline{Q}^{\pi_{k}}_{k}(x,a)-B_{k}(x,a)\right)\right]$
$\displaystyle=\underbrace{\sum_{k=1}^{(T-T_{0})/W}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}\pi_{k}(a|x)\Big{(}\overline{Q}_{k}^{\pi_{k}}(x,a)-\widehat{Q}_{k}(x,a)\Big{)}\right]}_{\textsc{Bias-1}}$
$\displaystyle\quad+\underbrace{\sum_{k=1}^{(T-T_{0})/W}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}{\pi^{\star}}(a|x)\Big{(}\widehat{Q}_{k}(x,a)-\overline{Q}_{k}^{\pi_{k}}(x,a)\Big{)}\right]}_{\textsc{Bias-2}}$
$\displaystyle\quad+\underbrace{\sum_{k=1}^{(T-T_{0})/W}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}\pi_{k}(a|x)\Big{(}\widehat{B}_{k}(x,\cdot)-B_{k}(x,\cdot)\Big{)}\right]}_{\textsc{Bias-3}}$
$\displaystyle\quad+\underbrace{\sum_{k=1}^{(T-T_{0})/W}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}{\pi^{\star}}(a|x)\Big{(}B_{k}(x,a)-\widehat{B}_{k}(x,a)\Big{)}\right]}_{\textsc{Bias-4}}$
$\displaystyle\quad+\underbrace{\sum_{k=1}^{(T-T_{0})/W}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}\Big{(}\pi_{k}(\cdot|x)-{\pi^{\star}}(\cdot|x)\Big{)}\Big{(}\widehat{Q}_{k}(x,\cdot)-\widehat{B}_{k}(x,\cdot)\Big{)}\right]}_{\textsc{Reg-
Term}}.$

Now we combine the bounds in Lemma F.2, Lemma F.3, and Lemma F.4 (included
after this proof). Suppose that the conditions on the parameters specified in
Lemma F.4 hold. We get

$\displaystyle\mathbb{E}[\textsc{Bias-1}+\textsc{Bias-2}+\textsc{Bias-3}+\textsc{Bias-4}+\textsc{Reg-
Term}]$
$\displaystyle=\widetilde{\mathcal{O}}\left(\frac{H}{\eta}+\frac{\eta\epsilon
H^{4}T}{W}+\frac{\eta H^{4}}{\gamma^{2}T^{2}W}+\frac{\gamma dH^{3}T}{\beta
W}+\frac{\epsilon H^{3}T}{W}\right)$
$\displaystyle\qquad\qquad+\left(\frac{\beta}{2}+2\eta
H^{3}\right)\sum_{k}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}({\pi^{\star}}(a|x)+\pi_{k}(a|x))\|\phi(x,a)\|_{\widehat{\Sigma}^{+}_{k,h}}^{2}\right]$
$\displaystyle\qquad\qquad+\frac{1}{H}\sum_{k}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\sum_{a}\pi_{k}(a|x)B_{k}(x,a)\right]$
$\displaystyle\leq\widetilde{\mathcal{O}}\left(\frac{H}{\eta}+\frac{\eta\epsilon
H^{4}T}{W}+\frac{\eta H^{4}}{\gamma^{2}T^{2}W}+\frac{\gamma dH^{3}T}{\beta
W}+\frac{\epsilon H^{3}T}{W}\right)$
$\displaystyle\qquad\qquad+\sum_{k}V^{\pi^{\star}}(x_{0};b_{k})+\frac{1}{H}\sum_{k}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\sum_{a}\pi_{k}(a|x)B_{k}(x,a)\right]$

where the last inequality is because $\frac{\beta}{2}+2\eta H^{3}\leq\beta$
(implied by $\frac{\eta}{\beta}\leq\frac{1}{20H^{4}}$, a condition specified
in Lemma F.4).

Combining two cases and applying Lemma B.2, we thus have

$\displaystyle\mathbb{E}\left[\sum_{k=1}^{(T-T_{0})/W}V^{\pi_{k}}(x_{0};\overline{\ell}_{k})\right]-\sum_{k=1}^{(T-T_{0})/W}V^{{\pi^{\star}}}(x_{0};\overline{\ell}_{k})$
$\displaystyle\leq\widetilde{\mathcal{O}}\left(\frac{H}{\eta}+\frac{\eta\epsilon
H^{4}T}{W}+\frac{\eta H^{4}}{\gamma^{2}T^{2}W}+\frac{\gamma dH^{3}T}{\beta
W}+\frac{\epsilon
H^{3}T}{W}+\beta\mathbb{E}\left[\sum_{k=1}^{(T-T_{0})/W}\sum_{h}\mathbb{E}_{(x_{h},a)\sim\pi_{k}}\left[\|\phi(x_{h},a)\|_{\widehat{\Sigma}^{+}_{k,h}}^{2}\right]\right]+\frac{dH^{3}T}{\alpha
W}\right)$
$\displaystyle=\widetilde{\mathcal{O}}\left(\frac{H}{\eta}+\frac{\eta\epsilon
H^{4}T}{W}+\frac{\eta H^{4}}{\gamma^{2}T^{2}W}+\frac{\gamma dH^{3}T}{\beta
W}+\frac{\epsilon H^{3}T}{W}+\frac{\beta dHT}{W}+\frac{dH^{3}T}{\alpha
W}\right).$ (by similar calculation as Eq. (40))

Finally, to get the overall regret, it remains to multiply the bound above by
$W$, add the trivial bound
$HT_{0}=2HM_{0}N_{0}=\mathcal{O}\left(\frac{\delta_{e}^{8}d^{10}H^{11}}{\beta^{8}}\right)$
for the initial $T_{0}$ rounds, and consider the exploration probability
$\delta_{e}$, which leads to

$\displaystyle\mathbb{E}[\text{\rm Reg}]$
$\displaystyle=\widetilde{\mathcal{O}}\left(\frac{HW}{\eta}+\eta\epsilon
H^{4}T+\frac{\eta H^{4}}{\gamma^{2}T^{2}}+\frac{\gamma
dH^{3}T}{\beta}+\epsilon H^{3}T+\beta
dHT+\frac{dH^{3}T}{\alpha}+\frac{d^{10}H^{11}\delta_{e}^{8}}{\beta^{8}}+\delta_{e}HT\right)$
$\displaystyle=\widetilde{\mathcal{O}}\left(\frac{H}{\eta\epsilon^{2}\gamma^{3}}+\frac{\eta
H^{4}}{\gamma^{2}T^{2}}+\frac{\gamma dH^{3}T}{\beta}+\epsilon H^{3}T+\beta
dHT+\frac{dH^{3}T\beta}{\delta_{e}}+\frac{d^{10}H^{11}\delta_{e}^{8}}{\beta^{8}}+\delta_{e}HT\right)$

where we use the specified value of $M$, $N$, $W=2MN$, $\alpha$, and that
$\eta H\leq 1$ (so that the second term $\eta\epsilon H^{4}T$ is absorbed by
the fifth term $\epsilon H^{3}T$).

Considering the constraints in Lemma F.4 and Lemma F.1, we choose
$\gamma=\max\left\\{16\eta H^{4},\frac{4\beta^{2}}{\delta_{e}}\right\\}$. This
gives the following simplified regret

$\displaystyle\widetilde{\mathcal{O}}\left(\frac{1}{\epsilon^{2}\eta^{4}H^{11}}+\frac{1}{\eta
H^{4}T^{2}}+\frac{\eta dH^{7}T}{\beta}+\epsilon H^{3}T+\beta
dHT+\frac{dH^{3}T\beta}{\delta_{e}}+\frac{d^{10}H^{11}\delta_{e}^{8}}{\beta^{8}}+\delta_{e}HT\right).$

Choosing $\delta_{e}$ optimally, and supposing $\eta\geq\frac{1}{T}$, the
above is simplified to

$\displaystyle\widetilde{\mathcal{O}}\left(\frac{1}{\epsilon^{2}\eta^{4}H^{11}}+\frac{\eta
dH^{7}T}{\beta}+\epsilon H^{3}T+\beta
dHT+H^{2}\sqrt{d\beta}T+d^{2}H^{\nicefrac{{35}}{{9}}}T^{\nicefrac{{8}}{{9}}}\right)$
$\displaystyle=\widetilde{\mathcal{O}}\left(\frac{1}{\epsilon^{2}\eta^{4}H^{11}}+\frac{\eta
dH^{7}T}{\beta}+\epsilon
H^{3}T+H^{2}\sqrt{d\beta}T+d^{2}H^{\nicefrac{{35}}{{9}}}T^{\nicefrac{{8}}{{9}}}\right).$
(choosing $\beta\leq\frac{H^{2}}{d}$)

Picking optimal parameters in the last expression, we get
$\widetilde{\mathcal{O}}\left(d^{2}H^{4}T^{\nicefrac{{14}}{{15}}}\right)$. ∎

######  Lemma F.2.

$\displaystyle\mathbb{E}[\textsc{Bias-1}+\textsc{Bias-2}]$
$\displaystyle\leq\frac{\beta}{4}\mathbb{E}\left[\sum_{k=1}^{(T-T_{0})/W}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}\Big{(}{\pi^{\star}}(a|x)+\pi_{k}(a|x)\Big{)}\left\|{\phi(x,a)}\right\|_{\widehat{\Sigma}^{+}_{k,h}}^{2}\right]\right]+\mathcal{O}\left(\frac{\gamma
dH^{3}T}{\beta W}+\frac{\epsilon H^{3}T}{W}\right).$

###### Proof.

The proof of this lemma is similar to that of Lemma E.1, except that we
replace $T$ by $(T-T_{0})/W$, and consider the averaged loss
$\overline{\ell}_{k}$ in an epoch instead of the single episode loss
$\ell_{t}$:

$\displaystyle\mathbb{E}_{k}\left[\overline{Q}^{\pi_{k}}_{k}(x,a)-\widehat{Q}_{k}(x,a)\right]$
$\displaystyle=\phi(x,a)^{\top}\left(\overline{\theta}_{k,h}^{\pi_{k}}-\mathbb{E}_{k}\left[\widehat{\theta}_{k,h}\right]\right)$
$\displaystyle=\phi(x,a)^{\top}\left(\overline{\theta}_{k,h}^{\pi_{k}}-\mathbb{E}_{k}\left[\widehat{\Sigma}^{+}_{k,h}\right]\mathbb{E}_{k}\left[\frac{1}{|S_{k}^{\prime}|}\sum_{t\in
S_{k}^{\prime}}((1-Y_{t})+Y_{t}H\mathbbm{1}[h=h_{t}^{*}])\phi(x_{t,h},a_{t,h})L_{t,h}\right]\right)$
($S_{k}^{\prime}$ is the $S^{\prime}$ in Algorithm 5 within epoch $k$)
$\displaystyle=\phi(x,a)^{\top}\left(\overline{\theta}_{k,h}^{\pi_{k}}-\left(\gamma
I+\Sigma_{k,h}^{\text{mix}}\right)^{-1}\mathbb{E}_{k}\left[\frac{1}{|S_{k}^{\prime}|}\sum_{t\in
S_{k}^{\prime}}((1-Y_{t})+Y_{t}H\mathbbm{1}[h=h_{t}^{*}])\phi(x_{t,h},a_{t,h})L_{t,h}\right]\right)+\mathcal{O}(\epsilon
H^{2})$ (by Lemma D.1 and that $\|\phi(x,a)\|\leq 1$ for all $x,a$ and
$L_{t,h}\leq H$; $\Sigma_{k,h}^{\text{mix}}$ is defined in Eq. (41))
$\displaystyle=\phi(x,a)^{\top}\left(\overline{\theta}_{k,h}^{\pi_{k}}-\left(\gamma
I+\Sigma_{k,h}^{\text{mix}}\right)^{-1}\mathbb{E}_{k}\left[\frac{1}{|S_{k}^{\prime}|}\sum_{t\in
S_{k}^{\prime}}\Sigma_{k,h}^{\text{mix}}\theta^{\pi_{k}}_{t,h}\right]\right)+\mathcal{O}(\epsilon
H^{2})$
$\displaystyle=\phi(x,a)^{\top}\left(\overline{\theta}_{k,h}^{\pi_{k}}-\left(\gamma
I+\Sigma_{k,h}^{\text{mix}}\right)^{-1}\mathbb{E}_{k}\left[\frac{1}{W}\sum_{t=(k-1)W+1}^{kW}\Sigma_{k,h}^{\text{mix}}\theta^{\pi_{k}}_{t,h}\right]\right)+\mathcal{O}(\epsilon
H^{2})$ ($S_{k}^{\prime}$ is randomly chosen from epoch $k$)
$\displaystyle=\phi(x,a)^{\top}\left(\overline{\theta}_{k,h}^{\pi_{k}}-\left(\gamma
I+\Sigma_{k,h}^{\text{mix}}\right)^{-1}\Sigma_{k,h}^{\text{mix}}\overline{\theta}_{k,h}^{\pi_{k}}\right)+\mathcal{O}(\epsilon
H^{2})$ $\displaystyle=\gamma\phi(x,a)^{\top}\left(\gamma
I+\Sigma^{\text{mix}}_{k,h}\right)^{-1}\overline{\theta}^{\pi_{k}}_{k,h}+\mathcal{O}\left(\epsilon
H^{2}\right)$ $\displaystyle\leq\frac{\beta}{4}\|\phi(x,a)\|_{(\gamma
I+\Sigma_{t,h}^{\text{mix}})^{-1}}^{2}+\frac{\gamma^{2}}{\beta}\left\|{\overline{\theta}_{k,h}^{\pi_{k}}}\right\|_{(\gamma
I+\Sigma_{k,h}^{\text{mix}})^{-1}}^{2}+\mathcal{O}(\epsilon H^{2})$ (AM-GM
inequality)
$\displaystyle\leq\frac{\beta}{4}\mathbb{E}_{k}\left[\left\|{\phi(x,a)}\right\|_{\widehat{\Sigma}^{+}_{k,h}}^{2}\right]+\frac{\gamma
dH^{2}}{\beta}+\mathcal{O}\left(\epsilon H^{2}\right).$

The same bound also holds for
$\mathbb{E}_{k}\left[\widehat{Q}_{k}(x,a)-\overline{Q}^{\pi_{k}}_{k}(x,a)\right]$
by the same reasoning. Taking expectation over $x$, summing over $k,h$ and $a$
(with weights $\pi_{k}(a|x)$ and ${\pi^{\star}}(a|x)$ respectively) finishes
the proof. ∎

######  Lemma F.3.

$\displaystyle\mathbb{E}[\textsc{Bias-3}+\textsc{Bias-4}]$
$\displaystyle\leq\frac{\beta}{4}\mathbb{E}\left[\sum_{k=1}^{(T-T_{0})/W}\sum_{h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}\Big{(}{\pi^{\star}}(a|x)+\pi_{k}(a|x)\Big{)}\left\|{\phi(x,a)}\right\|_{\widehat{\Sigma}^{+}_{k,h}}^{2}\right]\right]+\mathcal{O}\left(\frac{\gamma
dH^{3}T}{\beta W}+\frac{\epsilon H^{3}T}{W}\right).$

###### Proof.

The proof is almost identical to that of the previous lemma. The only
difference is that $L_{t,h}$ is replaced by $D_{t,h}$ and
$\overline{\theta}^{\pi_{k}}_{t,h}$ is replaced by $\Lambda^{\pi_{k}}_{k,h}$
(recall the definition of $\Lambda_{k,h}^{\pi_{k}}$ in Section 6). Note that
$b_{t}(x,a)\in[0,1]$ (Lemma F.1), so $D_{t,h}\in[0,He]$, which is also the
same order for $L_{t,h}$. Therefore, we get the same bound as in the previous
lemma. ∎

######  Lemma F.4.

Let $\frac{\eta}{\gamma}\leq\frac{1}{16H^{4}}$ and
$\frac{\eta}{\beta}\leq\frac{1}{40H^{4}}$. Then

$\displaystyle\mathbb{E}[\textsc{Reg-
Term}]=\widetilde{\mathcal{O}}\left(\frac{H}{\eta}+\frac{\eta\epsilon
H^{4}T}{W}+\frac{\eta H^{4}}{\gamma^{2}T^{2}W}\right)$ $\displaystyle+2\eta
H^{3}\mathbb{E}\left[\sum_{k,h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}\pi_{k}(x,a)\|\phi(x,a)\|_{\widehat{\Sigma}^{+}_{k,h}}^{2}\right]\right]+\frac{1}{H}\mathbb{E}\left[\sum_{k,h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\sum_{a}\pi_{k}(x,a)B_{k}(x,a)\right]\right].$

###### Proof.

We first check the condition for Lemma A.4:
$\eta\left|\widehat{Q}_{k}(x,a)-\widehat{B}_{t}(x,a)\right|\leq 1$. In our
case,

$\displaystyle\eta\left|\widehat{Q}_{k}(x,a)\right|$
$\displaystyle=\eta\left|\phi(x,a)^{\top}\widehat{\Sigma}^{+}_{k,h}\left(\frac{1}{|S^{\prime}|}\sum_{t\in
S^{\prime}}((1-Y_{t})+Y_{t}H\mathbbm{1}[h=h_{t}^{*}])\phi(x_{t,h},a_{t,h})L_{t,h}\right)\right|$
$\displaystyle\leq\eta\times\|\widehat{\Sigma}^{+}_{k,h}\|_{\text{op}}\times
H\times\sup_{t\in S^{\prime}}L_{t,h}$
$\displaystyle\leq\eta\times\frac{1}{\gamma}\times H^{2}$ (by Lemma D.1)
$\displaystyle\leq\frac{1}{2}$ (by the condition specified in the lemma)

and

$\displaystyle\eta\left|\widehat{B}_{k}(x,a)\right|$
$\displaystyle\leq\eta\left|b_{k}(x,a)\right|+\eta\left|\phi(x,a)^{\top}\widehat{\Sigma}^{+}_{k,h}\left(\frac{1}{|S^{\prime}|}\sum_{t\in
S^{\prime}}((1-Y_{t})+Y_{t}H\mathbbm{1}[h=h_{t}^{*}])\phi(x_{t,h},a_{t,h})D_{t,h}\right)\right|$
$\displaystyle\leq\eta+\eta\times\|\widehat{\Sigma}^{+}_{k,h}\|_{\text{op}}\times
H\times\sup_{t\in S^{\prime}}D_{t,h}$
$\displaystyle\leq\eta+\eta\times\|\widehat{\Sigma}^{+}_{k,h}\|_{\text{op}}\times
H\times(H-1)\left(1+\frac{1}{H}\right)^{H}$ (Lemma F.1)
$\displaystyle\leq\eta+\frac{3\eta H^{2}}{\gamma}\leq\frac{4\eta
H^{2}}{\gamma}$ $\displaystyle\leq\frac{1}{2H}.$ (by the condition specified
in the lemma)

Now we derive an upper bound for
$\mathbb{E}_{k}\left[\widehat{Q}_{k}(x,a)^{2}\right]$:

$\displaystyle\mathbb{E}_{k}\left[\widehat{Q}_{k}(x,a)^{2}\right]$
$\displaystyle\leq\mathbb{E}_{k}\left[\frac{1}{|S_{k}^{\prime}|}\sum_{t\in
S_{k}^{\prime}}H^{2}\phi(x,a)^{\top}\widehat{\Sigma}^{+}_{k,h}\Big{(}((1-Y_{t})+Y_{t}H\mathbbm{1}[h=h_{t}^{*}])^{2}\phi(x_{t,h},a_{t,h})\phi(x_{t,h},a_{t,h})^{\top}\Big{)}\widehat{\Sigma}^{+}_{k,h}\phi(x,a)\right]$
($*$)
$\displaystyle=\mathbb{E}_{k}\left[H^{2}\phi(x,a)^{\top}\widehat{\Sigma}^{+}_{k,h}\Big{(}(1-\delta_{e})\Sigma_{k,h}+\delta_{e}H\Sigma_{h}^{\text{cov}}\Big{)}\widehat{\Sigma}^{+}_{k,h}\phi(x,a)\right]$
$\displaystyle\leq
H^{3}\mathbb{E}_{k}\left[\phi(x,a)^{\top}\widehat{\Sigma}^{+}_{k,h}\Sigma_{k,h}^{\text{mix}}\widehat{\Sigma}^{+}_{k,h}\phi(x,a)\right]$
$\displaystyle\leq
H^{3}\mathbb{E}_{k}\left[\phi(x,a)^{\top}\widehat{\Sigma}^{+}_{k,h}\Sigma_{k,h}^{\text{mix}}(\gamma
I+\Sigma_{k,h}^{\text{mix}})^{-1}\phi(x,a)\right]+\widetilde{\mathcal{O}}\left(\epsilon
H^{3}+\frac{H^{3}}{\gamma^{2}T^{3}}\right)$ (Lemma D.1) $\displaystyle\leq
H^{3}\phi(x,a)^{\top}(\gamma
I+\Sigma_{k,h}^{\text{mix}})^{-1}\Sigma_{k,h}^{\text{mix}}(\gamma
I+\Sigma_{k,h}^{\text{mix}})^{-1}\phi(x,a)+\widetilde{\mathcal{O}}\left(\epsilon
H^{3}+\frac{H^{3}}{\gamma^{2}T^{3}}\right)$ (Lemma D.1) $\displaystyle\leq
H^{3}\phi(x,a)^{\top}(\gamma
I+\Sigma_{k,h}^{\text{mix}})^{-1}\phi(x,a)+\widetilde{\mathcal{O}}\left(\epsilon
H^{3}+\frac{H^{3}}{\gamma^{2}T^{3}}\right)$
$\displaystyle=H^{3}\mathbb{E}_{k}\left[\|\phi(x,a)\|_{\widehat{\Sigma}^{+}_{k,h}}^{2}\right]+\widetilde{\mathcal{O}}\left(\epsilon
H^{3}+\frac{H^{3}}{\gamma^{2}T^{3}}\right),$ (42)

where in $(*)$ we use $\left(\frac{1}{|S_{k}^{\prime}|}\sum_{t\in
S_{k}^{\prime}}v_{t}\right)^{2}\leq\frac{1}{|S_{k}^{\prime}|}\sum_{t\in
S_{k}^{\prime}}v_{t}^{2}$ with
$v_{t}=\phi(x,a)^{\top}\widehat{\Sigma}^{+}_{k,h}\left((1-Y_{t})+Y_{t}H\mathbbm{1}[h=h_{t}^{*}]\right)\phi(x_{t,h},a_{t,h})L_{t,h}$.

Next, we bound $\mathbb{E}_{t}\left[\widehat{B}_{t}(x,a)^{2}\right]$:

$\displaystyle\mathbb{E}_{k}\left[\widehat{B}_{k}(x,a)^{2}\right]$
$\displaystyle\leq
2\mathbb{E}_{k}\left[b_{k}(x,a)^{2}\right]+2\mathbb{E}_{k}\left[(\phi(x,a)^{\top}\widehat{\Lambda}_{k,h})^{2}\right]$
$\displaystyle\leq
2\mathbb{E}_{k}[b_{k}(x,a)]+18H^{3}\mathbb{E}_{k}\left[\|\phi(x,a)\|_{\widehat{\Sigma}^{+}_{k,h}}^{2}\right]+\widetilde{\mathcal{O}}\left(\epsilon
H^{3}+\frac{H^{3}}{\gamma^{2}T^{3}}\right)$
$\displaystyle\leq\frac{20H^{3}}{\beta}b_{k}(x,a)+\widetilde{\mathcal{O}}\left(\epsilon
H^{3}+\frac{H^{3}}{\gamma^{2}T^{3}}\right),$

where in the second inequality we bound
$\mathbb{E}_{k}\left[(\phi(x,a)^{\top}\widehat{\Lambda}_{k,h})^{2}\right]$
similarly as we bound $\mathbb{E}_{k}\left[\widehat{Q}_{k}(x,a)^{2}\right]$ in
Eq. (42), except that we replace the upper bound $H$ for $L_{t,h}$ by the
upper bound for $D_{t,h}$:
$H\left(1+\frac{1}{H}\right)^{H}\sup_{t,x,a}b_{t}(x,a)\leq 3H$ (since
$b_{t}(x,a)\leq 1$ by Lemma F.1).

Thus, by Lemma A.4, we have

$\displaystyle\mathbb{E}[\textsc{Reg-Term}]$
$\displaystyle\leq\widetilde{\mathcal{O}}\left(\frac{H}{\eta}\right)+2\eta\sum_{k,h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}\pi_{k}(a|x)(\widehat{Q}_{k}(x,a)^{2}+\widehat{B}_{k}(x,a)^{2})\right]$
$\displaystyle\leq\widetilde{\mathcal{O}}\left(\frac{H}{\eta}+\frac{\eta\epsilon
H^{4}T}{W}+\frac{\eta H^{4}}{\gamma^{2}T^{2}W}\right)$ $\displaystyle+2\eta
H^{3}\mathbb{E}\left[\sum_{k,h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}\pi_{k}(x,a)\|\phi(x,a)\|_{\widehat{\Sigma}^{+}_{k,h}}^{2}\right]\right]+\frac{40\eta
H^{3}}{\beta}\mathbb{E}\left[\sum_{k,h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\sum_{a}\pi_{k}(a|x)b_{k}(x,a)\right]\right]$
$\displaystyle\leq\widetilde{\mathcal{O}}\left(\frac{H}{\eta}+\frac{\eta\epsilon
H^{4}T}{W}+\frac{\eta H^{4}}{\gamma^{2}T^{2}W}\right)$ $\displaystyle+2\eta
H^{3}\mathbb{E}\left[\sum_{k,h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\bm{1}[x\in{\mathcal{K}}]\sum_{a}\pi_{k}(x,a)\|\phi(x,a)\|_{\widehat{\Sigma}^{+}_{k,h}}^{2}\right]\right]+\frac{1}{H}\mathbb{E}\left[\sum_{k,h}\mathbb{E}_{X_{h}\ni
x\sim{\pi^{\star}}}\left[\sum_{a}\pi_{k}(a|x)\textsc{Bonus}_{k}(x,a)\right]\right]$

where in the last inequality we use the conditions specified in the lemma and
that $B_{k}(x,a)\geq b_{k}(x,a)$. ∎


# Learning from Randomly Initialized Neural Network Features

Ehsan Amid†
<EMAIL_ADDRESS>Rohan Anil†
<EMAIL_ADDRESS>Wojciech Kotłowski⋆
<EMAIL_ADDRESS>Manfred K. Warmuth†
<EMAIL_ADDRESS>
(†Google Research, Brain Team
⋆Poznan University of Technology, Poznan, Poland)

###### Abstract

We present the surprising result that randomly initialized neural networks are
good feature extractors in expectation. These random features correspond to
finite-sample realizations of what we call Neural Network Prior Kernel (NNPK),
which is inherently infinite-dimensional. We conduct ablations across multiple
architectures of varying sizes as well as initializations and activation
functions. Our analysis suggests that certain structures that manifest in a
trained model are already present at initialization. Therefore, NNPK may
provide further insight into why neural networks are so effective in learning
such structures.

##  1 Introduction: Neural Kernels

There has been tremendous progress in recent years in connecting deep neural
networks with kernel machines. The main example of such efforts is NTK (Jacot
et al., 2018) which introduces a kernel in terms of the gradient of the
network with respect to the inputs. NTK has provided significant insight into
the training dynamics (Canziani et al., 2016; Novak et al., 2018a; Li & Liang,
2018; Du et al., 2019; Allen-Zhu et al., 2019) and generalization properties
(Arora et al., 2019a; Cao & Gu, 2019) of neural networks. The properties of
NTK are well studied in the infinite-width regime and under a squared loss
assumption (Lee et al., 2019; Arora et al., 2019b). Recent progress has
generalized these results to hinge loss and support vector machines (Chen et
al., 2021). Also recently, it was shown that the training dynamics of any
network trained with gradient descent induces a path kernel that depends on
the NTK (Domingos, 2020).

Another class of neural models involves constructing limit cases of infinitely
wide Bayesian neural networks, resulting in a Gaussian process (NNGP) (Lee et
al., 2017; Matthews et al., 2018; Novak et al., 2018b; Garriga-Alonso et al.,
2018; Borovykh, 2018). NNGP describes the distribution of the output
predictions of a randomly initialized infinitely-wide network. Adopting a
sequential view of neural networks casts the uncertainty in the output of a
layer as a conditional distribution on the previous layer’s output. NNGP is
closely related to NTK (Jacot et al., 2018; Hron et al., 2020) and has been
used to characterize the trainability of different architectures (Schoenholz
et al., 2016).

Neural networks have been shown to have great expressive power even when the
weights are randomly initialized (Frankle & Carbin, 2018; Evci et al., 2020;
Ramanujan et al., 2020). For instance, only training the BatchNorm (Ioffe &
Szegedy, 2015) variables in a randomly initialized ResNet model provide a
reasonable test performance on CIFAR and ImageNet-1k datasets (Frankle et al.,
2020). Our work constructs random features from the outputs of repeatedly
(randomly) re-initialized neural networks. We show that these features are in
fact related to a kernel.

Figure 1: TriMap (Amid & Warmuth, 2019) visualization of the CIFAR-10 training
examples: (a) output probabilities of a fully trained ResNet-18 model, (b)
output probabilities of a (linear) logistic classifier trained on a
$10240$-dimensional NRF representation, extracted from identical _randomly
initialized_ ResNet-18 architectures. Note that the cluster in (a) already
appear in (b) and the closeness of pairs of clusters is roughly preserved.

This paper introduces a new kernel construction induced from infinitely many
randomly initialized neural networks. Our new kernel, called Neural Network
Prior Kernel (NNPK), corresponds to the expected value of the inner-product of
the logits of the network for two input examples. This expectation involves
calculating an integral over all possible realizations of a prior distribution
on the network’s weights. Thus, NNPK inherently corresponds to an infinite-
dimensional representation in a Hilbert space. Our finite-sample approximation
of NNPK, called Neural Random Features (NRF), corresponds to embedding the
input examples in the logits space using random networks, for which the
weights are sampled from the prior (i.e., initial) distribution. Our extensive
experiments with NRF across different architectures, initializations,
activation functions, and dimensions suggest that NNPK is a useful tool to
analyze the trainability of neural networks. Also, our experiments with NRF
reveal that certain structures in the data that manifest in a fully trained
neural network are already present at initialization. Thus, NNPK may also
provide further insights into the expressive power of neural networks.

Figure 1 shows a TriMap (Amid & Warmuth, 2019) visualization of the output
probabilities of the training examples obtained from a ResNet-18 model,
trained on the CIFAR-10 dataset along with the output probabilities of a
linear classifier, trained on $10240$ sampled features from _randomly
initialized_ ResNet-18 models. The visualizations reveal a fair amount of
similarity between the structure of the data and the placement of the clusters
induced by the fully trained network and randomly initialized networks. In
summary:

  * •

We formally define the Neural Network Prior Kernel (NNPK) and present its
finite sample approximation as Neural Random Features (NRF).

  * •

We analyze NRF across a span of model architectures, initialization, and
activation functions.

  * •

We report several intriguing observations that suggest that NNPK may reflect
some properties about the trainability and generalization of the network at
initialization before observing any data samples.

  * •

We also show that certain structures in the data that manifest in a fully-
trained network are already observable at initialization using NRF. These
findings hint that NNPK may provide further insights into understanding the
expressivity of deep neural network architectures.

##  2 Neural Prior Kernel

We now formally define the Neural Network Prior Kernel (NNPK) of a neural
network. Let $f^{k}_{\theta}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k}$ denote a
neural network function parameterized by the weights
$\theta\in\mathbb{R}^{m}$. The network transforms an input
$x\in\mathbb{R}^{d}$ to the $k$-dimensional output
$f^{k}_{\theta}\in\mathbb{R}^{k}$, called _logits_. The logits are the output
of a linear fully-connected layer and are fed into a softmax function to
produce a $k$-dimensional probability vector over classes. The weights
$\theta$ at the initialization follow a _prior_ distribution111The term
_prior_ is commonly used in Bayesian statistics to describe the uncertainly of
a distribution before observing some evidence. Here, we loosely use the term
prior to denote the initial distribution of the model weights, although the
connection to Bayesian statistics is yet to be established in future work.
$\pi(\theta)$. For deep neural network, this distribution usually amounts to a
scaled (truncated) normal or a uniform distribution. The NNPK of the network
between two inputs $x,x^{\prime}\in\mathbb{R}^{d}$ is then defined in terms of
an expectation with respect to the initial weight distribution $\pi$,

$\begin{split}\kappa_{\text{\tiny
NNPK}}(x,x^{\prime})&=\mathbb{E}_{\theta\sim\pi}[\langle\,f^{k}_{\theta}(x),f^{k}_{\theta}(x^{\prime})\rangle]\,.\\\
\end{split}$ (NNPK)

That is, NNPK is simply the expected value of the inner-product of the output
logits for the given two inputs. Clearly, NNPK is a valid kernel since it
corresponds to a convex combination of symmetric and positive semi-definitive
functions. NNPK is also deterministic for a given distribution $\pi$, as the
expectation is over all realizations of $\theta\sim\pi$.

Figure 2: NRF of different model architectures on CIFAR-10/100 datasets: Train
and test accuracy of linear classifiers trained on randomly sampled $n=3072$
NRF using different standard architectures. The accuracy of the trained
networks (without data augmentation) is also shown for each network. The
models are sorted roughly in the order of their capacity. We also plot the
train and test accuracy of a linear classifier on the original CIFAR-10/100
inputs using dashed and solid horizontal lines, respectively. Note that the
train and test curves for learning with NRF present very rough approximations
of the corresponding curves for the fully trained models.

We can calculate a finite sample approximation of NNPK as

$\begin{split}\hat{\kappa}_{\text{\tiny
NNPK}}(x,x^{\prime})&=\frac{1}{n}\,\sum_{i}\langle
f^{k}_{\theta_{i}}(x),f^{k}_{\theta_{i}}(x^{\prime})\rangle\,,\end{split}$ (1)

using $n$ iid samples $\\{\theta_{i}\\}_{i=1}^{n}$ drawn from $\pi$. For a
given neural network architecture, this corresponds to randomly re-
initializing the networks $n$ times and calculating the average inner-product
between the logits for the given two inputs.

For a randomly initialized network, the output logits of an example are
correlated. In order to obtain uncorrelated output samples, in our
construction, we set $k=1$ while keeping the rest of network architecture
unchanged. In this case, each randomly initialized network maps each input
example to a single scalar value. Thus, Eq. (1) can be written as

$\begin{split}\hat{\kappa}_{\text{\tiny
NNPK}}(x,x^{\prime})&=\langle\phi_{n}(x),\phi_{n}(x^{\prime})\rangle\,,\end{split}$
(2)

where the embedding map $\phi_{n}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{n}$ is
defined as

$\phi_{n}(x)=\nicefrac{{1}}{{\sqrt{n}}}\,[f^{1}_{\theta_{1}}(x),\ldots,f^{1}_{\theta_{n}}(x)]^{\top}\,.$
(NRF)

These randomly generated features are then treated as new representations for
the training examples and are used to train a classifier. In our experiments,
we mainly focus on training a linear classifier with a softmax output to
predict the class probabilities. At inference, the same randomly initialized
networks are used to construct the random features for a test example.

In the following sections, we show that NNPK is a non-trivial kernel which
allows separating the data significantly better than the original input space.
We analyze the dependency of NNPK (via its finite-sample approximation NRF) on
different elements and properties of the models. Interestingly, NNPK is a
fixed kernel for a given architecture and therefore, the same randomly
initialized networks to realize NRF can be used across different datasets.
This is in contrast to the _data-dependent_ path kernel (Domingos, 2020) which
relies on the training trajectory of the model.

##  3 Experiments

We conduct several ablations to understand the effect of different elements,
such as architecture, width, depth, activation function, etc., on the NNPK.
For the first set of experiments, we conduct ablations on CIFAR-10/100
datasets of images (Krizhevsky, 2009). To show the generality of the NRF
extracted from the NNPK, we also perform an experiment on the ImageNet-1K
dataset (Deng et al., 2009).

###  3.1 Effect of Architecture

We first show the dependency of NRF on different model architectures. For
this, we consider a number of different models of varying sizes. These models
include a two-layer fully-connected network (MLP), a small (CNN-S) and a
medium (CNN-M) convolutional network, variants of LeNet (LeCun et al., 1989),
AlexNet (Krizhevsky et al., 2012), and VGG19 (Simonyan & Zisserman, 2014) as
well as several ResNets (He et al., 2016) (ResNet-18, ResNet-50, ResNet-101,
ResNet-152, and ResNet-200). The details of all models are described in the
appendix. We also consider a linear projection of the input data using a
random matrix. The Linear baseline corresponds to a random projection of the
input data which is used for applications such k-neareast neighbor search
(Kleinberg, 1997) and random projection trees (Dasgupta & Freund, 2008). We
use a He normal initialization (He et al., 2015) for the ResNet models and use
Glorot normal (Glorot & Bengio, 2010) for the rest.

We set the NRF dimension $n$ equal to the original dimensionality of the input
data, which is $32\times 32\times 3=3072$. This way, any improvement in
separability over the original input data is solely due to a better
representation by NRF. To classify the data, we train a logistic regression
classifier on NRF using the L-BFGS (Liu & Nocedal, 1989) optimizer for which
we tune the $\mathrm{L}_{2}$-regularizer value. We repeat each experiment over
5 random trials.

Figure 3: Effect of initialization and activation function on NRF on CIFAR-10:
Train (unfilled) and test (filled markers) accuracy of linear classifiers on
$n=3072$ NRF sampled from CNN-S, LeNet, and ResNet-18 architectures using
different (a) initializations and (b) activation functions. The train and test
accuracy of a linear classifier on the original CIFAR-10 inputs are shown
using dashed and solid horizontal lines, respectively. Note that for fully
trained ResNet networks, He normal initialization and ELU activations are
known to achieve good performance (He et al., 2015; Shah et al., 2016).
Surprisingly our NRF methods picks out these choices in (a) and (b).

In Figure 2, we plot the train and test accuracy of NRF along with the
baseline linear classifier trained on the original input data (dashed and
solid horizontal lines, respectively). We also plot the train and test
accuracy of the trained network. To train each model on the training examples,
we use a SGD with Nesterov momentum optimizer (Nesterov, 1983) with a batch
size of 128 for 100k iterations. We use a linear warmup followed by a linear
decay schedule for the learning rate and tune the maximum learning rate value,
momentum constant, and the weight decay parameter for 128 trials using a
Bayesian parameter search package. One important detail to notice is that we
train the networks  _without data augmentation_. Data augmentation is a
standard practice for training such networks and is a strong form of
regularization that allows larger networks provide better generalization when
the number of train examples is limited. With data augmentation, we expect the
performance of the models to increase with size, which is evident in several
existing benchmarking efforts on CIFAR-10/100 datasets.222For instance, see
https://github.com/kuangliu/pytorch-cifar and
https://paperswithcode.com/sota/image-classification-on-cifar-10 for some
benchmarking results. However, our goal here is to understand how much a
trained network can improve on the initial representation of the data,
reflected in NNPK, _after_ seeing the (original) training examples.

Several interesting observations can be made from Figure 2. First, the NRF
extracted from all architectures perform better than the baseline classifier
trained on the original input image representations. The performance of Linear
random projection is about the same as the original data, as we expect such
projections to be at best as good as the original data (Dasgupta & Gupta,
2003). Next, the performance of NRF is not monotonic with the architecture
size. Among the models, the shallow CNN-S model provides the best performance
while performance drops by expanding the model to CNN-M or LeNet. A similar
phenomenon happens when we increase the ResNet sizes. More interestingly, the
performance of the trained model also follows a similar pattern to NRF on both
datasets. This suggests that a trained network (without data augmentation)
improves on the initial representation of the input that is reflected via NNPK
at initialization. Thus, the performance after observing the inputs is
proportional to the initial NNPK representation. We test this hypothesis
further in our later experiments.

###  3.2 Effect of Initialization

The expectation in the definition of NNPK is with respect to the prior
distribution (i.e., initialization) of the model weights. In order to analyze
the effect of the prior distribution $\pi$, we evaluate the NRF for CNN-S,
LeNet, and ResNet-18 models using different standard weight initializations.
As before, we set the embedding dimension $n=3072$. Figure 3(a) shows the
train (unfilled) and test (filled markers) accuracy of the linear classifiers
trained on NRF. Similarly, we show the baseline train and test accuracy
(dashed and solid lines, respectively) on the original inputs.

From 3(a), we observe that the NRF of some networks, e.g. CNN-S are more
robust to the choice of initialization than the others. The NRF of ResNet-18
architecture, in particular, seem to vary significantly and are degraded,
especially when using (Glorot) uniform or Glorot normal initializations. In
addition, the NRF induced by the ResNet-18 model seems to perform the best
when using He normal (which is usually the default initialization for ResNets
(He et al., 2015)).

(a) (b)

Figure 4: Effect of depth and width on NRF on CIFAR-10: Train and test
accuracy of linear classifiers on $n=3072$ NRF extracted from an MLP model
with varying (a) depth and (b) width. We also plot the train and test accuracy
of the trained networks (without data augmentation). We also show the train
and test accuracy of a linear classifier on the original CIFAR-10 inputs using
dashed and solid horizontal lines, respectively. Note again that the NRF
curves are rough approximations of the curves for the fully trained models.

###  3.3 Effect of Activation Function

Apart from the prior distribution on the weights (i.e., initialization), NRF
is also dependant on the activation functions of the network. To study their
effect, we conduct an experiment by varying the activation functions of CNN-S,
LeNet, and ResNet-18 models. Again, we set the embedding dimension $n=3072$
and use the default initializations for each model.

From Figure 3(b), we can see that certain activation functions such as leaky
ReLU ($\text{slope}=0.1$) seem to consistently produce better NRF across
architectures (although ELU seems to perform the best on ResNet-18, which is
known to also perform well for a trained ResNet (Shah et al., 2016)). On the
other hand, the NRF induced by the sigmoid activation function is consistently
worse for all architectures. This suggests that the choice of a good
activation function has a significant effect on the initial representation of
the model, thus it may as well affect the generalization performance of the
model after training.

In summary, based on our experiments on different initializations and
activation functions and our findings on ResNet-18, NNPK seems to hint at the
choices that are known to work also well for fully trained models (Gotmare et
al., 2018; Shah et al., 2016; Martens et al., 2021).

###  3.4 Effect of Depth and Width

A natural question is whether depth or width affects the NNPK of a network. To
study this, we create different variants of our basic MLP model by expanding
its width or depth (i.e. number of layers) by different multiples. Figure 4
illustrates the train and test accuracy of these expanded models as a function
of the multiplier. We use the default Glorot normal initialization for the
networks. We also plot the train and test accuracy of the trained models
(using the same tuning protocol and without data augmentation). Interestingly,
the NNPK does not improve by increasing the depth of the network. Also, the
deeper networks become harder to train without data augmentation and other
regularization techniques. In contrast, both the performance of NNPK and the
trained network improves slightly by increasing the width. This is also
consistent with the empirical findings on wide neural networks (Novak et al.,
2018a; Canziani et al., 2016).

###  3.5 Effect of Dimension

We empirically show that the finite-sample approximation of NNPK using NRF in
Eq. (1) improves for all networks as we increase the number of samples $n$.
This corresponds to increasing the embedding dimension of NRF in $\phi_{n}$.
Figure 5 shows the test accuracy of linear classifiers trained on NRF using
different dimensions $n$ on CIFAR-10/100 datasets. As we expect, the
performance of the random projection of the data (Linear) matches the
performance of the linear classifier trained on the original input features
(solid horizontal lines) and does not improve with dimension. On the contrary,
the performance of NRF increases monotonically with dimension for all
networks. This justifies the definition of the NNPK as a limit case when
$n\rightarrow\infty$. Interestingly, the order of performance for different
models (along the vertical axis) remains roughly the same across different
dimensions. This suggest that the observations about NNPK are relatively
consistent using different dimensionality $n$ to approximate the kernel.

(a) (b)

Figure 5: Effect of dimension $n$ on the finite-sample approximation of NNPK
using NRF: Test accuracy of linear classifiers on (a) CIFAR-10 and (b)
CIFAR-100, trained on NRF with varying dimensionality $n$ extracted from
different model architectures. We also plot the test accuracy of the linear
model trained on the original CIFAR-10/100 input images (solid horizontal
lines). As we expect, the accuracy of the linear random projection of the
input images (Linear) does not exceed the accuracy on original inputs, as we
increase the dimension. On the contrary, the accuracy of the classifiers
trained on NRF improves monotonically with dimension. This justifies the
definition of the NNPK as a limit case when $n\rightarrow\infty$. Also, the
order of the performance using different model architectures remains roughly
the same across dimension.

###  3.6 Does Skip Connection Improve NRF?

The immense success of ResNets is mainly attributed to two elements: the use
of Batch Normalization (BatchNorm) (Ioffe & Szegedy, 2015) and skip
connections (He et al., 2016). There has been a number of efforts to replace
or remove these two elements from ResNets (Zhang et al., 2019; Gaur et al.,
2020; Bachlechner et al., 2021). The more recent adjustments proposed in
(Martens et al., 2021) have shown further promise. This modification includes
replacing the ReLU activation function with a scaled leaky ReLU and the use of
delta orthogonal initialization for the convolutional kernels (and orthogonal
initialization for the final dense layer). Here, we explore the dependence of
NNPK and the trained models (without data augmentation) on skip connections
(and BatchNorm). One important point to notice is that BatchNorm is an affine
transformation on the activations in each layer during inference. Since the
mean and scale values are initially set to $0$ and $1$, respectively,
BatchNorm with default initialization will have no effect on the NNPK, but
affects the performance of the trained model. We also examine whether NRF
varies by removing skip connections and whether the changes proposed in
(Martens et al., 2021) affect the results.

We create variants of the ResNet-18 model by removing BatchNorm and/or skip
connections. In the first approach, we use the default He normal
initialization with ReLU activation while in the second case, we use the delta
orthogonal initialization proposed in (Martens et al., 2021) for the
convolutional filters (and orthogonal initialization for the final dense
layer). We also replace the ReLU activation with the scaled leaky ReLU
proposed in (Martens et al., 2021). We set the slope of the leaky ReLU to
$0.3$. For both variants, we train the models without data augmentation and
tune the learning rate, momentum constant, and the weight decay parameters for
$128$ trials. We generate $n=3072$ dimensional NRF using each variant and
train linear classifiers. The results are shown in Figure 6.

It can be seen from Figure 6 that the performance of the trained base model
(using He normal initialization and ReLU activation) degrades without
BatchNorm (and skip connection). However, the performance remains about the
same without only the skip connections. As we expect, the performance using
the NRF of the base model does not vary by adding/removing BatchNorm. However,
removing skip connections degrades the performance of NRF.

Figure 6: Effect of BatchNorm and skip connection on the ResNet-18 model and
the induced NRF on CIFAR-10: we consider the original ResNet-18 model with He
normal initialization and ReLU activations (RN-18 (HN)) along with the variant
proposed in (Martens et al., 2021) with delta orthogonal initialization and
scaled leaky ReLU activations (RN-18 (DO). We also generate $n=3072$ NRF using
each model. We plot the test accuracy of each trained model (without data
augmentation) as well as the performance of linear classifiers trained on NRF
for the base models along with the variants in which BatchNorm and/or skip
connections are removed. As we expect, we observe that BatchNorm with the
default initial values behaves as an identity map, thus has no effect on NRF.
On the other hand, removing skip connections degrades the performance on NRF.

In comparison, the trained model using delta orthogonal initialization and
leaky ReLU activation performs better than the base model in most cases,
especially when both BatchNorm and skip connections are removed. The NRF of
this model also follows a similar pattern: the NRF does not vary by
adding/removing BatchNorm, but degrades without the skip connections. However,
the performance of the NRF of this model is comparatively lower than the NRF
of the base model.

Figure 7: Cosine similarities for different classes of ResNet-18: a linear
classifier trained on the original inputs (left), on NRF sampled from
ResNet-18 (middle), and the softmax layer of a fully trained ResNet-18 network
(right). NRF appear to be an intermediate representation between the original
input data and the representation induced by a fully trained model. Some
classes that are close in the fully trained model are closer in the NRF
representation compared to the original input representation.

These observations are interesting from several aspects. First, the NRF seems
to improve by using skip connections for both initialization and activation
function combinations. However, the performance of the trained model using the
adjustments proposed in (Martens et al., 2021) seems to improve without the
skip connections. This observation shows that there are cases for which NNPK
may not reflect the performance of the final trained model (although the
results may vary when using data augmentation and other types of
regularizations). Additionally, as we expect, the NNPK is not affected by
BatchNorm using the default initialization for the BatchNorm variables.
However, the dependence of NNPK on different types of normalization techniques
such as Layer Normalization (Ba et al., 2016) and Instance Normalization
(Ulyanov et al., 2016) is yet to be examined.

###  3.7 NNPK Reveals Structure

In this section, we show that the structure in the data that appears in a
fully-trained network is somehow reflected in NNPK. In other words, NNPK seems
to be an intermediate representation between the original input space and the
final trained network. For this, we consider the linear classifier trained on
the original input images from the CIFAR-10 dataset. We also consider the
fully trained ResNet-18 model (without data augmentation) as well as the
linear classifier trained on NRF, sampled from the randomly initialized
ResNet-18 models. We set $n=3072$ the same as the original data dimension. We
then calculate the cosine similarities of the class weights for each
classifier (for the fully trained ResNet-18, this corresponds to the weights
of the output softmax layer). We then plot the top and bottom-2 similar
classes for each of the 10 classes of CIFAR-10 in Figure 7.

We can see from Figure 7 that in many cases (such as the class ‘horse’), the
top similar classes are identical for the NRF classifier and the output layer
of the fully trained network. However, in some cases (e.g., ‘automobile’), the
top classes of the classifier trained on the original CIFAR-10 images are
closer to the NRF classifier than the ResNet-18 model. This observation
further hints at the following conjecture.

######  Conjecture 1.

The original representation of the data is first projected via NNPK into an
initial representation which is then enhanced throughout the training into the
final representation of the fully-trained network.

A further theoretical and empirical study of the above conjecture is an
interesting future research direction.

###  3.8 Results on the Larger ImageNet-1K Dataset

In order to demonstrate the applicability of the results using NRF on a larger
scale, we perform an experiment on the ImageNet-1K dataset (Deng et al.,
2009). The dataset contains around 1.2M training images from $1000$ classes. A
linear classifier on the original input images (150K features) achieves a 3.4%
test top-1 accuracy. In contrast, a linear classifier trained on $4096$ NRF,
sampled from randomly initialized ResNet-18 models, achieves a 10.3% test
accuracy. This result is fascinating given that NRF achieves a significantly
higher accuracy with 37$\times$ fewer features than the original input
features. Training a linear classifier and a two-layer MLP on $31568$ NRF
achieves 12.2% and 15.2% top-1 test accuracies, respectively.

##  4 Conclusion

From experiments on a large variety of image classification datasets and
neural network architectures, we found that the representation of a fully
trained network is already “echoed” in a representation induced from random
neural network features. These random features are constructed from multiple
randomly initialized networks, and a simple linear classifier is trained on
top of these features for classifying the input.

This line of work leads to several empirical questions:

  * •

Can the NRF be used to find suitable architectures for a given dataset
rapidly? Figures 2-5 suggest that this is possible; in each case, the
comparative performance on the fully trained network is reflected by NRF.

  * •

Which properties affect (thus, can be measured by) NNPK? What are the key
architectural features that make the NRF reflect the performance of the fully
trained network?

  * •

Are there other feature extraction methods that can achieve the same echoing
of the performance of the fully trained model?

## References

  * Allen-Zhu et al. (2019) Allen-Zhu, Z., Li, Y., and Song, Z.  A convergence theory for deep learning via over-parameterization.  In _International Conference on Machine Learning_ , pp. 242–252. PMLR, 2019.
  * Amid & Warmuth (2019) Amid, E. and Warmuth, M. K.  TriMap: Large-scale Dimensionality Reduction Using Triplets.  _arXiv preprint arXiv:1910.00204_ , 2019.
  * Arora et al. (2019a) Arora, S., Du, S., Hu, W., Li, Z., and Wang, R.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In _International Conference on Machine Learning_ , pp. 322–332. PMLR, 2019a.
  * Arora et al. (2019b) Arora, S., Du, S. S., Hu, W., Li, Z., Salakhutdinov, R., and Wang, R.  On exact computation with an infinitely wide neural net.  _arXiv preprint arXiv:1904.11955_ , 2019b.
  * Ba et al. (2016) Ba, J. L., Kiros, J. R., and Hinton, G. E.  Layer normalization.  _arXiv preprint arXiv:1607.06450_ , 2016.
  * Bachlechner et al. (2021) Bachlechner, T., Majumder, B. P., Mao, H., Cottrell, G., and McAuley, J.  Rezero is all you need: Fast convergence at large depth.  In _Uncertainty in Artificial Intelligence_ , pp. 1352–1361. PMLR, 2021.
  * Borovykh (2018) Borovykh, A.  A gaussian process perspective on convolutional neural networks.  _arXiv preprint arXiv:1810.10798_ , 2018.
  * Canziani et al. (2016) Canziani, A., Paszke, A., and Culurciello, E.  An analysis of deep neural network models for practical applications.  _arXiv preprint arXiv:1605.07678_ , 2016.
  * Cao & Gu (2019) Cao, Y. and Gu, Q.  Generalization bounds of stochastic gradient descent for wide and deep neural networks.  _Advances in Neural Information Processing Systems_ , 32:10836–10846, 2019.
  * Chen et al. (2021) Chen, Y., Huang, W., Nguyen, L., and Weng, T.-W.  On the equivalence between neural network and support vector machine.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Dasgupta & Freund (2008) Dasgupta, S. and Freund, Y.  Random projection trees and low dimensional manifolds.  In _Proceedings of the fortieth annual ACM symposium on Theory of computing_ , pp. 537–546, 2008.
  * Dasgupta & Gupta (2003) Dasgupta, S. and Gupta, A.  An elementary proof of a theorem of johnson and lindenstrauss.  _Random Structures & Algorithms_, 22(1):60–65, 2003.
  * Deng et al. (2009) Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L.  ImageNet: A Large-Scale Hierarchical Image Database.  In _CVPR09_ , 2009.
  * Domingos (2020) Domingos, P.  Every model learned by gradient descent is approximately a kernel machine.  _arXiv preprint arXiv:2012.00152_ , 2020.
  * Du et al. (2019) Du, S., Lee, J., Li, H., Wang, L., and Zhai, X.  Gradient descent finds global minima of deep neural networks.  In _International Conference on Machine Learning_ , pp. 1675–1685. PMLR, 2019.
  * Evci et al. (2020) Evci, U., Gale, T., Menick, J., Castro, P. S., and Elsen, E.  Rigging the lottery: Making all tickets winners.  In _International Conference on Machine Learning_ , pp. 2943–2952. PMLR, 2020.
  * Frankle & Carbin (2018) Frankle, J. and Carbin, M.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  _arXiv preprint arXiv:1803.03635_ , 2018.
  * Frankle et al. (2020) Frankle, J., Schwab, D. J., and Morcos, A. S.  Training batchnorm and only batchnorm: On the expressive power of random features in CNNs.  _arXiv preprint arXiv:2003.00152_ , 2020.
  * Garriga-Alonso et al. (2018) Garriga-Alonso, A., Rasmussen, C. E., and Aitchison, L.  Deep convolutional networks as shallow Gaussian processes.  _arXiv preprint arXiv:1808.05587_ , 2018.
  * Gaur et al. (2020) Gaur, D., Folz, J., and Dengel, A.  Training deep neural networks without batch normalization.  _arXiv preprint arXiv:2008.07970_ , 2020.
  * Glorot & Bengio (2010) Glorot, X. and Bengio, Y.  Understanding the difficulty of training deep feedforward neural networks.  In _Proceedings of the thirteenth international conference on artificial intelligence and statistics_ , pp. 249–256. JMLR Workshop and Conference Proceedings, 2010.
  * Gotmare et al. (2018) Gotmare, A. D., Thomas, V., Brea, J., and Jaggi, M.  Decoupling Backpropagation using constrained optimization methods.  In _ICML Workshop on Efficient Credit Assignment in Deep Learning and Deep Reinforcement Learning_ , 2018.
  * He et al. (2015) He, K., Zhang, X., Ren, S., and Sun, J.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In _Proceedings of the IEEE international conference on computer vision_ , pp. 1026–1034, 2015.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Hron et al. (2020) Hron, J., Bahri, Y., Sohl-Dickstein, J., and Novak, R.  Infinite attention: NNGP and NTK for deep attention networks.  In _International Conference on Machine Learning_ , pp. 4376–4386. PMLR, 2020.
  * Ioffe & Szegedy (2015) Ioffe, S. and Szegedy, C.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _Proceedings of Machine Learning Research_ , pp. 448–456, Lille, France, 07–09 Jul 2015. PMLR.
  * Jacot et al. (2018) Jacot, A., Gabriel, F., and Hongler, C.  Neural tangent kernel: Convergence and generalization in neural networks.  _arXiv preprint arXiv:1806.07572_ , 2018.
  * Kleinberg (1997) Kleinberg, J. M.  Two algorithms for nearest-neighbor search in high dimensions.  In _Proceedings of the twenty-ninth annual ACM symposium on Theory of computing_ , pp. 599–608, 1997.
  * Krizhevsky (2009) Krizhevsky, A.  Learning multiple layers of features from tiny images.  Technical report, Citeseer, 2009.
  * Krizhevsky et al. (2012) Krizhevsky, A., Sutskever, I., and Hinton, G. E.  Imagenet classification with deep convolutional neural networks.  _Advances in neural information processing systems_ , 25:1097–1105, 2012.
  * LeCun et al. (1989) LeCun, Y., Boser, B., Denker, J. S., Henderson, D., Howard, R. E., Hubbard, W., and Jackel, L. D.  Backpropagation applied to handwritten zip code recognition.  _Neural computation_ , 1(4):541–551, 1989.
  * Lee et al. (2017) Lee, J., Bahri, Y., Novak, R., Schoenholz, S. S., Pennington, J., and Sohl-Dickstein, J.  Deep neural networks as gaussian processes.  _arXiv preprint arXiv:1711.00165_ , 2017.
  * Lee et al. (2019) Lee, J., Xiao, L., Schoenholz, S., Bahri, Y., Novak, R., Sohl-Dickstein, J., and Pennington, J.  Wide neural networks of any depth evolve as linear models under gradient descent.  _Advances in neural information processing systems_ , 32:8572–8583, 2019.
  * Li & Liang (2018) Li, Y. and Liang, Y.  Learning overparameterized neural networks via stochastic gradient descent on structured data.  _arXiv preprint arXiv:1808.01204_ , 2018.
  * Liu & Nocedal (1989) Liu, D. C. and Nocedal, J.  On the limited memory BFGS method for large scale optimization.  _Mathematical programming_ , 45(1):503–528, 1989\.
  * Martens et al. (2021) Martens, J., Ballard, A., Desjardins, G., Swirszcz, G., Dalibard, V., Sohl-Dickstein, J., and Schoenholz, S. S.  Rapid training of deep neural networks without skip connections or normalization layers using deep kernel shaping.  _arXiv preprint arXiv:2110.01765_ , 2021.
  * Matthews et al. (2018) Matthews, A. G. d. G., Rowland, M., Hron, J., Turner, R. E., and Ghahramani, Z.  Gaussian process behaviour in wide deep neural networks.  _arXiv preprint arXiv:1804.11271_ , 2018.
  * Nesterov (1983) Nesterov, Y. E.  A method for solving the convex programming problem with convergence rate of ($1/k^{2}$).  _Dokl. akad. nauk Sssr_ , 269:543–547, 1983.
  * Novak et al. (2018a) Novak, R., Bahri, Y., Abolafia, D. A., Pennington, J., and Sohl-Dickstein, J.  Sensitivity and generalization in neural networks: an empirical study.  _arXiv preprint arXiv:1802.08760_ , 2018a.
  * Novak et al. (2018b) Novak, R., Xiao, L., Lee, J., Bahri, Y., Yang, G., Hron, J., Abolafia, D. A., Pennington, J., and Sohl-Dickstein, J.  Bayesian deep convolutional networks with many channels are gaussian processes.  _arXiv preprint arXiv:1810.05148_ , 2018b.
  * Ramanujan et al. (2020) Ramanujan, V., Wortsman, M., Kembhavi, A., Farhadi, A., and Rastegari, M.  What’s hidden in a randomly weighted neural network?  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 11893–11902, 2020.
  * Schoenholz et al. (2016) Schoenholz, S. S., Gilmer, J., Ganguli, S., and Sohl-Dickstein, J.  Deep information propagation.  _arXiv preprint arXiv:1611.01232_ , 2016.
  * Shah et al. (2016) Shah, A., Kadam, E., Shah, H., Shinde, S., and Shingade, S.  Deep residual networks with exponential linear unit.  In _Proceedings of the Third International Symposium on Computer Vision and the Internet_ , pp. 59–65, 2016.
  * Simonyan & Zisserman (2014) Simonyan, K. and Zisserman, A.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Ulyanov et al. (2016) Ulyanov, D., Vedaldi, A., and Lempitsky, V.  Instance normalization: The missing ingredient for fast stylization.  _arXiv preprint arXiv:1607.08022_ , 2016.
  * Zhang et al. (2019) Zhang, H., Dauphin, Y. N., and Ma, T.  Fixup initialization: Residual learning without normalization.  _arXiv preprint arXiv:1901.09321_ , 2019.

##  Appendix A Details of the Model Architectures

####  MLP Model:

contains two fully-connected layers of size $128$ with ReLU activations
followed by the output layer.

CNN-S model: contains two 2-D convolutional layers of size 32 and 64,
respectively, with $5\times 5$ filters. Each convolutional layer is followed
by a max-pooling layer. We then apply a dense layer of size 512 followed by
the final dense layer. All the activation functions are set to ReLU.

CNN-M model: contains four $5\times 5$ convolutional layers, for which the
sizes are 32, 64, 64, and 32, respectively. The first two convolutions are
each followed by a max-pooling layer. We then similarly apply a dense layer of
size 512 followed by the final dense layer. All the activation functions are
set to ReLU.

LeNet model: is a variation of the LeNet model described in
https://www.kaggle.com/blurredmachine/lenet-architecture-a-complete-guide in
which we replace the activation functions with ReLU.

AlexNet model: is a variation of the model desctibed in
https://www.analyticsvidhya.com/blog/2021/03/introduction-to-the-architecture-
of-alexnet/ where we changed the filter sizes in the first and last
convolutional layers to $3\times 3$ and $1\times 1$, respectively.

VGG19 model: we use the VGG-19 implementation available in Keras at
https://www.tensorflow.org/api_docs/python/tf/keras/applications/vgg19/VGG19.

ResNet models: are standard ResNet-v1 models implemented in TensorFlow.