# An Information-Theoretic Analysis of
Compute-Optimal Neural Scaling Laws

Hong Jun Jeon
Department of Computer Science
Stanford University
Stanford, CA 94305, USA
<EMAIL_ADDRESS>
&Benjamin Van Roy
Stanford University

###### Abstract

We study the compute-optimal trade-off between model and training data set
sizes for large neural networks. Our result suggests a linear relation similar
to that supported by the empirical analysis of Hoffmann et al. (2022). While
that work studies transformer-based large language models trained on the
MassiveText corpus (Rae et al., 2021), as a starting point for development of
a mathematical theory, we focus on a simpler learning model and data
generating process, each based on a neural network with a sigmoidal output
unit and single hidden layer of ReLU activation units. We establish an upper
bound on the minimal information-theoretically achievable expected error as a
function of model and data set sizes. We then derive allocations of
computation that minimize this bound. We present empirical results which
suggest that this approximation correctly identifies an asymptotic linear
compute-optimal scaling. This approximation can also generate new insights.
Among other things, it suggests that, as the input space dimension or latent
space complexity grows, as might be the case for example if a longer history
of tokens is taken as input to a language model, a larger fraction of the
compute budget should be allocated to growing the learning model rather than
training data set.

##  1 introduction

In recent years, state-of-the-art neural network models have grown immensely.
GPT-3 (Brown et al., 2020), for example, includes 175 billion learned
parameters. While larger models have in general produced better results, they
also require much more compute to train. It is has become impractical to
perform hyperparameter sweeps at the scale of these modern models. This is
concerning since deep learning has previously been heavily reliant on tuning
of hyperparameters via extensive trial and error.

When fitting a large language model, two important hyperparameters control
$1)$ the size, measured in terms of the parameter count $p$, of the neural
network model and $2)$ the number $t$ of training tokens. The compute budget
$C$ scales with the product of these two quantities since each training token
produces a gradient that is used to adjust each parameter of the neural
network. For any compute budget $C$, one should carefully balance between $p$
and $t$. Too few training tokens leads to model estimation error, while too
few parameters gives rise to mispecification error. As evaluating performance
across multiple choices of $p$ and $t$ becomes computationally prohibitive at
scale, alternative kinds of analysis are required to guide how to allocate
computational resources.

Recently, Kaplan et al. (2020) and Hoffmann et al. (2022) have proposed the
following procedure for allocating a large compute budget:

  1. 1.

Evaluate test errors of models produced using various small compute budgets
$C$ with many different allocations to parameters $n$ versus training tokens
$t$.

  2. 2.

Based on these results, estimate the optimal relation between $p$ and $t$,
which minimizes error for each compute budget $C$.

  3. 3.

Extrapolate to estimate the relation between $p$ and $t$ for large $C$.

To give a sense of scales involved here, Hoffmann et al. (2022) evaluate test
errors across “small” models for which $p\times t$ ranges from around
$10^{18}$ to $10^{22}$ and extrapolates out to “large” models at around
$10^{24}$. Kaplan et al. (2020) and Hoffmann et al. (2022) each extrapolate
based on a hypothesized _scaffolding function_. Kaplan et al. (2020) guess a
scaffolding function based on results observed in small scale experiments.
Hoffmann et al. (2022) carry out an informal and somewhat speculative
mathematical analysis to guide their choice (see their Appendix D).

The analysis of Hoffmann et al. (2022) is somewhat generic rather than
specialized to the particular neural network architecture used in that paper.
In this paper, we develop a more rigorous and formal mathematical analysis,
bringing to bear information-theoretic tools that build on the framework and
results of Jeon & Van Roy (2022a; b). To keep things simple and concrete, we
carry out the analysis with a particular data generating process for which
neural networks are well-suited. The sorts of arguments developed by Hoffmann
et al. (2022) are just as relevant to this context as they are to language
models.

Hoffmann et al. (2022) suggest that the compute optimal trade-off between
parameter count and number of training tokens is linear, though the authors
expressed some doubt and considered other possibilities that are near-linear
as well. We establish an upper bound on the minimal information-theoretically
achievable expected error as a function of $p$ and $t$ and derive the relation
required to minimize this bound for each compute budget. For large compute
budgets, this relation is linear, as suggested by Hoffmann et al. (2022).
Given that our data generating process differs from that considered by
Hoffmann et al. (2022), we also carry out a computational study that
corroborates this linear relation in our context.

Our main contributions include a first rigorous mathematical characterization
of the compute-optimal efficient frontier for a neural network model and
development of information-theoretic tools which enable that. A limitation of
our analysis is in its simplified treatment of computational complexity as the
product of the model and data set sizes; we do not assume any constraints on
computation beyond those imposed by choices of $p$ and $t$. In particular, in
our framework, a learning algorithm carries out perfect Bayesian inference,
though with a a model that is misspecificified due to its restricted size.
While this abstracts away the details of practical training algorithms that
apply stochastic gradient descent, empirical evidence suggests that our
idealized framework leads to useful approximations (Zhu et al., 2022). In
spite of this limitation, we hope our results set the stage for further
mathematical work to guide hyperparameter selection when training large neural
networks. Furthermore, our approach can give rise to new insights not captured
by previous analyses. For example, we consider implications of our bound on
how computation ought to be apportioned as the input space dimension or the
latent space complexity of the data generating process grows, as may be the
case, for example, when taking a longer history of tokens as input to a
language model. We next summarize our formulation and insights.

##  2 Formulation and Insights

Our analysis is inspired by the empirical study of Hoffmann et al. (2022),
which uses a simple formula to approximate flops of computation: $C=p\times
t$. In other words, the number $C$ of flops is taken to be the product of the
number $p$ of model parameters and the number $t$ of training data samples. We
will similarly use this formula, which is motivated by the fact that, when
training a large language model, each training data sample is processed only
once and the computation required by each scales roughly with the number of
model parameters. Sample are not processed more than once because there is
insufficient computation time to work through vast text data corpi.

Hoffmann et al. (2022) train transformer models on the MassiveText corpus (Rae
et al., 2021). However, in order to simplify our analysis, we restrict
attention to a particular synthetic data generating process and learning
model, each based on a neural network architecture. Our data generating
process samples inputs $X_{t}$ iid from a standard multivariate Gaussian and
produces binary labels $Y_{t+1}$ via a neural network with a sigmoidal output
unit and a single infinitely wide hidden layer of ReLu activation units. We
denote by $F$ the associated mapping from input $X_{t}$ to the sigmoid output.
A prior distribution over output weights characterizes initial uncertainty
about $F$. This distribution depends on a scalar hyperparameter $K$, which
controls the expected complexity of $F$. In particular, output weights are
sampled such that the number of hidden units required to attain any particular
level of loss scales with $K$.

As a learning model, we consider a similar neural network architecture, again
with a linear output node and single hidden layer of ReLu activation units.
However, while the data generating process architecture includes an infinite
number of hidden units, we limit the number in our learning model based to
$C/p$. We aim to learn an approximation $\tilde{F}$ to $F$ within the
constrained learning model class. Note that $\tilde{F}$ depends on $F$, and
therefore, uncertainty about $F$ induces uncertainty about $\tilde{F}$. It is
this uncertainty about $\tilde{F}$ that is reduced as the learning model is
trained.

In order to model uncertainty, that we treat the data generating process $F$,
the learning model $\tilde{F}$, and observed data as random variables. These
and all other random variables we introduce are defined with respect to a
common probability space $(\Omega,\mathbb{F},\mathbb{P})$. We consider an
idealized training algorithm, which carries out exact Bayesian inference to
the derive the posterior distribution
$\tilde{Q}_{t}=\mathbb{P}(\tilde{F}\in\cdot|H_{t})$ of the learning model
conditioned on training data pairs $H_{t}=(X_{0},Y_{1},\ldots,X_{t-1},Y_{t})$.
While this abstracts away the details of practical training algorithms that
apply stochastic gradient descent, empirical evidence suggests that they can
approximately attain the performance of our idealized counterpart (Zhu et al.,
2022). To assess performance, we characterize out-of-sample cross-entropy loss
of the prediction $\mathbb{P}(Y_{t+1}=1|\tilde{Q}_{t},X_{t})$, which is
conditioned on $\tilde{Q}_{t}$ and $X_{t}$. Our results inform how a compute
budget $C$ should be apportioned to a number $p$ of model parameters versus a
number $t$ of training samples in order to minimize out-of-sample cross-
entropy loss.

Figure 1 plots estimates of compute-optimal allocations between model size and
training samples across different compute budgets. Due to limitations in our
computational resources, we ran experiments with only up to around one hundred
and fifty thousand training samples. The ticks on horizontal axis indicate the
range spanned by our experiments. Each point on the blue curve is produced by
a linear model fit to a subset of our experimental results; further detail is
provided in Section 4.2. If the compute-optimal model size grows linearly in
the compute-optimal number of training samples, that would be reflected
through unit slope. The dotted black line has unit slope and is plotted for
reference. The blue curve represents empirical estimates produced using
synthetic data and stochastic gradient descent, as explained in further detail
in Section 4. The shaded blue region represents a standard error confidence
interval. The orange curve is our theoretical approximation. As the compute
budget grows, the slopes of both curves become statistically indistinguishable
from one. Furthermore, the curves appear to merge. Overall, these results are
consistent with empirical observations of Hoffmann et al. (2022) and suggest
that our theory captures the right qualitative behavior as the compute budget
grows.

Figure 1: Estimates of compute-optimal allocations between parameter count and
training samples.

Figure 2 is based on theoretical approximation. Assuming that the
approximation is accurate, it plots the optimal fraction of the compute budget
allocated to the parameter count $p$ as a function of the complexity of the
data generating process which is determined by $K$ and $d$. The trend suggests
that, as complexity grows, an increasing fraction of computation should be
allocated to scaling models as opposed to increasing the number of training
data samples. Furthermore, this relationship is concave. With large language
models, it is natural to expect that complexity of the data will grow when a
longer history of tokens is taken as input. As such, this figure offers
insight into how the optimal allocation of computation ought to change as
models are designed to ingest longer histories.

Figure 2: The parameter count as a fraction of compute budget increases with
complexity of the data generating process. Note that the vertical axis is
identical across both plots. Interestingly, parameter allocations are
_identical_ whether we vary $d$ or $K$. The shape of the curves seems to be
independent of $C$. These plots were generated with $C=2^{50}$.

##  3 Models and Error

Let us now present the data generating process and learning model we study and
establish an error bound that captures dependence on the learning model size
$p$ and number of number $t$ of training samples.

###  3.1 Data generating process

Figure 3: This diagram depicts our data generating process. Each basis
function is parameterized by some $w\in\mathcal{W}$. After passing through a
ReLU, the output is multiplied by $\theta$ sampled from the Dirichlet process
outlined in the text. Despite the fact that $\theta$ has dimension $\infty$,
the scale parameter $K$ ensures that only $\approx K$ dimensions have
significant magnitude. A sigmoidal function is applied to the output to
designate the probability that $Y_{t+1}$ is $1$.

Our data generating process is represented by a neural network with $d$
inputs, a single asymptotically wide hidden layer of ReLU activation units,
and a sigmoidal output unit. We denote by $F$ the associated mapping from
input to sigmoidal output. In particular, inputs and binary labels are
generated according to $X_{t}\overset{iid}{\sim}\mathcal{N}(0,I_{d})$ and
$\mathbb{P}(Y_{t+1}=1|\theta,\delta,X_{t})=F(X_{t})$.

Let $S^{d-1}$ denote the $d$-dimensional unit sphere. We index hidden units by
a vector $w\in S^{d-1}$. The corresponding output is given by ${\rm
ReLU}(w^{\top}X_{t})$. We sample hidden unit weights $\theta$, also indexed by
$w\in S^{d-1}$, in a manner such that, with probability one, $\theta_{w}$ is
nonzero for only a countable set of indices. Let $\mathcal{W}=\\{w\in
S^{d-1}:|\theta_{w}|>0\\}$ denote this set. Then,

$F(X_{t})=\frac{1}{1+\exp\left(-\sqrt{K}\sum_{w\in\mathcal{W}}\theta_{w}{\rm
ReLU}(w^{\top}X_{t})\right)}.$

We now described how $\theta$ is generated. First, $\overline{\theta}$ is
sampled from a Dirichlet process with base distribution
$\mathrm{uniform}(S^{d-1})$ and scale parameter $K$. That this almost surely
results in countable support $\mathcal{W}$ is a well-known property of
Dirichlet processes. For each $w\in\mathcal{W}$, we randomly flip the sign of
the weight according to

$\theta_{w}=\left\\{\begin{array}[]{ll}\overline{\theta}_{w}&\text{with
probability }1/2,\\\
-\overline{\theta}_{w}&\text{otherwise.}\end{array}\right.$

Note that the distribution of $\theta$ depends on the scalar hyperparameter
$K$, which controls the expected complexity of $F$. In particular, the number
of hidden units required to attain any particular level of loss scales with
$K$.

A few observations may help with interpreting our data generating process.
While our description has framed the neural network as one with an uncountably
infinite number of hidden units, each indexed by an element of $w\in S^{d-1}$,
for all but a countable subset, the output is weight $\theta_{w}$ sis zero.
Hence, we could alternatively interpret the neural network as having a
countable number of hidden units, each with random weights drawn from
$S^{d-1}$. Let us denote the input to the sigmoidal output unit by
$f(x)=\sqrt{K}\sum_{w\in\mathcal{W}}\theta_{w}{\rm ReLU}(w^{\top}x)$. Its mean
and covariance structure satisfy

$\mathbb{E}[f(x)]=0,\qquad\mathbb{E}[f(x)^{2}]=\frac{1}{2},\qquad\text{and}\qquad\mathbb{E}[f(x)f(x^{\prime})]=\frac{1}{2\pi},$

where $x,x^{\prime}$ are independently sampled from $\mathcal{N}(0,I_{d})$.
This model remains nontrivial as $d$ and $K$ grow as all of the above
quantities are invariant in $d$ and $K$.

###  3.2 Learning model

Our data generating process is too complex for exact Bayesian inference to be
computationally viable. As such, we consider what can be inferred about a
smaller neural network which serves as a learning model.

A learning model is a random variable $\tilde{F}$ for which
$\tilde{F}\perp(X,Y)|F$. In other words, a learning model provides information
about $F$ but no additional information pertaining to input-label pairs.
Intuitively, $\tilde{F}$ represents what we aim to learn about given limited
computational resources, instead of $F$, which is too complex.

We take our learning model to be a random neural network with $d$ inputs, a
single hidden layer of $n$ ReLU activation units, and a sigmoidal output unit.
Let $\tilde{F}$ be the random function that maps the input to the sigmoidal
output. This represents a natural neural network architecture for learning
from data generated by $F$. In particular, $\tilde{F}$ shares the same
architecture but restricted to a finite number $n$ of hidden units. We let
$\mathcal{F}_{n}$ denote the set of all such learning models. By this, we mean
that each element of $\mathcal{F}_{n}$ is a random variable that induces a
distribution over single hidden layer neural networks of input dimension $d$
and width $n$. Note that this learning model has $(d+1)\cdot n$ parameters.
Since $d$ is fixed, the parameter count is allowed to vary only via altering
the width $n$.

In the sections to come, we will upper bound the performance of a learning
model that is _optimal_ with respect to a notion of error we define next.

###  3.3 Error

We evaluate performance via cross-entropy error. Given an input $X_{t}$ and a
prediction $P_{t}$, which takes the form of a probability in $[0,1]$, of the
label $Y_{t+1}$, the cross-entropy error is defined by

$L_{t}(P_{t})=-Y_{t+1}\ln P_{t}-(1-Y_{t+1})\ln(1-P_{t}).$

In this paper, we focus on predictions of the form
$P_{t}=\mathbb{P}(Y_{t+1}=1|\tilde{Q}_{t},X_{t})$ where
$\tilde{Q}_{t}=\mathbb{P}(\tilde{F}\in\cdot|H_{t})$ is the posterior
distribution of the learning model. This represents the best prediction
possible given what can be inferred about the learning model $\tilde{F}$ from
the data $H_{t}$.

As shorthand, we denote by $L_{t}(Z)$ the error
$L_{t}(\mathbb{P}(Y_{t+1}=1|Z,X_{t}))$ of a prediction made based on a random
variable $Z$. Hence, $L_{t}(\mathbb{P}(Y_{t+1}=1|\tilde{Q}_{t},X_{t}))\equiv
L_{t}(\tilde{Q}_{t})$. The following result facilitates analysis of this
quantity.

######  Lemma 1.

(cross-entropy error decomposition) For all $t\in\mathbb{Z}_{+}$, and learning
models $\tilde{F}$,

$\mathbb{E}\left[L_{t}(\tilde{Q}_{t})\right]=\underbrace{L^{*}}_{\rm
IrreducibleError}+\underbrace{\mathbb{I}(Y_{t+1};F|\tilde{F},X_{t})}_{\rm
MisspecificationError}+\underbrace{\mathbb{I}(Y_{t+1};\tilde{F}|\tilde{Q}_{t},X_{t})}_{\rm
EstimationError}.$

where $L^{*}=\mathbb{E}\left[L_{t}(F)\right]$.

Lemma 1, which we prove in Appendix A.1, decomposes cross-entropy error into
$3$ intuitive terms. $L^{*}$ is the baseline error, which is the cross-entropy
error incurred by a _prescient_ predictor. As $L^{*}$ does not depend on
$\tilde{Q}_{t}$, it is the latter two terms that we wish to minimize. The
second term $\mathbb{I}(Y_{t+1};F|\tilde{F},X_{t})$ represents
_misspecification error_. It is the error incurred due to approximating the
data generating process $F$ using a learning model $\tilde{F}$. The final term
$\mathbb{I}(Y_{t+1};\tilde{F}|\tilde{Q}_{t},X_{t})$ represents _estimation
error_. It is the error incurred from estimating $\tilde{F}$ based on a finite
data set $H_{t}$.

For fixed $n,t\in\mathbb{Z}_{++}$, an optimal learning model
$\tilde{F}^{*}_{n,t}$ is one in which

$\tilde{F}^{*}_{n,t}\in\operatorname*{arg\,min}_{\tilde{F}\in\mathcal{F}_{n}}\
\mathbb{E}\left[L_{t}(\tilde{Q}_{t})\right].$

We refer to $\mathbb{P}(\tilde{F}^{*}_{n,t}\in\cdot|H_{t})$ as
$\tilde{Q}^{*}_{n,t}$.

###  3.4 Error bound

We now present an upper bound on the cross-entropy error of an optimal neural
network learning model of width $n$ and $t$ training samples.

######  Theorem 2.

(optimal cross-entropy error upper bound) For all $n,t,d,K\in\mathbb{Z}_{++}$,
if $n,K\geq 2$, then

$\mathbb{E}\left[L_{t}\left(\tilde{Q}^{*}_{n,t}\right)\right]\leq
L^{*}+\underbrace{\frac{3K}{n}}_{\rm
MisspecificationError}+\underbrace{\frac{K\ln\left(1+\frac{n}{K}\right)\left(\ln(2n)+\frac{d}{2}\ln(et)\right)}{t}}_{\rm
EstimationError}.$

The second term represent the misspecification error incurred from using
finite width $n$ to approximate a data generating process of countably
infinite width. Intuitively, this error increases with the environment
complexity $K$ and decreases with the learning model complexity $n$. The third
term represents the approximation error incurred from estimating output layer
weights from $t$ training samples. This quantity intuitively decreases as the
sample size $t$ increases and increases with the learning model complexity
$n$. Notably, this increase is only logarithmic in $n$. The final term
represents the misspecification and estimation error that arrise from learning
the basis functions (1st layer of the neural network). Again unsurprisingly
the error increases the input dimension $d$ and environment complexity $K$
increase and decrease with the number of training samples $t$. In section 5,
we derive the intermediate results that culminate in Theorem 2. However, we
first present an analysis of how the parameters and training samples ought to
be allocated to minimize the upper bound presented in Theorem 2.

##  4 Compute-Optimal Allocations

In this section, we provide a bound on the width of the learning model that
minimizes the upper bound presented in Theorem 2 subject to compute
constraints. Recall that $C\in\mathbb{Z}_{++}$ denotes our _compute budget_
which is the product of the _parameter count_ and _number of training
samples_.

###  4.1 Theoretical Approximation

The following result provides an upper bound on the optimal width of the
learning model that minimizes the error upper bound from Theorem 2 subject to
compute constraint $n\cdot d\cdot t\leq C$. Note that in reality the parameter
count is $n\cdot(d+1)$ but we use $n\cdot d$ as it reduces clutter without
significantly impacting the result.

######  Theorem 3.

(compute-optimal width approximation) For all $d,K,C\in\mathbb{Z}_{++}$, if
$K\geq 2,d\geq 3$, and

$\displaystyle n^{*}$ $\displaystyle=\operatorname*{arg\,min}_{n\leq
C/td}\left(\frac{3K}{n}+\frac{K\ln\left(1+\frac{n}{K}\right)\cdot\ln\left(2n\right)}{t}+\frac{dK\ln\left(1+\frac{n}{K}\right)\left(\frac{1}{2}+\frac{1}{2}\ln\left(4t\right)\right)}{t}\right),$

then

$n^{*}\leq\min\left\\{\frac{\sqrt{\frac{6C}{d^{2}\ln(\ln(d))}}}{W_{0}\left(\sqrt{\frac{6C}{d^{2}K^{2}\ln(\ln(d))}}\right)},\sqrt{\frac{6C}{d^{2}\ln(\ln(d))}}+\sqrt{\frac{6C}{d^{2}\ln(\ln(d))}+4\sqrt{\frac{6CK^{2}}{d^{2}\ln(\ln(d))}}}\right\\},$

where $W_{0}$ is the Lambert $W$ function on branch $0$.

While Theorem 3 is stated only as an upper bound due to cumbersome terms that
preclude a closed-form solution, we believe that it is a close approximation
that captures the appropriate scaling in $d,K,$ and $C$.

Note that this is not necessarily an upper bound on the compute-optimal width,
but rather an upper bound on the width that minimizes the error upper bound of
Theorem 2.

Recall that the parameter count is $n\cdot d$ so ignoring $\ln\ln$ factors,
Theorem 3 suggests that the optimal parameter count for minimizing our error
upper bound scales in the following way:

$n^{*}\cdot
d\leq\min\left\\{\frac{\sqrt{6C}}{W_{0}\left(\sqrt{\frac{6C}{d^{2}K^{2}}}\right)},\sqrt{6C}+\sqrt{6C+4\sqrt{6Cd^{2}K^{2}}}\right\\}$

Note that $W_{0}(x)\approx\ln(x)-\ln(\ln(x))$ so we can establish that both of
these bounds are $\tilde{O}\left(\sqrt{C}\right)$. Another interesting
property is that in of these quantities the role of $d$ and $K$ is equivalent
(up to the $\ln\ln$ factors we ignored). Therefore, irrespective of which of
$d$ or $K$ are perturbed, the implications on the optimal parameter count
upper bound is equivalent. This is not just a result of Theorem 3 being loose
as experimentally we verified that the value of $n\cdot d$ which minimizes the
upper bound in Theorem 2 truly behaves identically for perturbations in $d$
and $K$ as apparent in Figure 2.

If we further analyze the bound, we see that for extrapolation i.e. large $C$,
the first term will be the lesser of the two quantities. As a result, we will
focus attention on this quantity. Since $W_{0}(x)\sim\ln(x)-\ln(\ln(x))$, so
$n^{*}\cdot d=\mathcal{O}(\sqrt{C}/\ln(\sqrt{C/(d^{2}K^{2})}))$. The optimal
dataset size would therefore be
$\mathcal{O}(\sqrt{C}\ln(\sqrt{C/(d^{2}K^{2})}))$ This is consistent with the
compute-optimal scaling laws of (Hoffmann et al., 2022) up to logarithmic
factors in $C$. However, our analysis additionally provides insight into how
these scaling laws ought to vary with changes in the complexity $(d,K)$ of the
data generating process.

###  4.2 Empirical Estimates

While our theoretical approximation is consistent with the linear scaling
observed in (Hoffmann et al., 2022), we study a much simpler data generating
process. To corroborate our theoretical approximation, we performed a set of
experiments under our data generating process and compared the empirical
compute-optimal trade-off with our theoretical approximation. While we leave
the full details to Appendix E, we will provide a high-level overview of the
experiments in this section.

To generate Figure 1, we first specified an increasing sequence of compute
budgets. For each compute budget $C$, we performed a line search over various
pairs of network width and number of training samples $(n,t)$ which satisfied
the constraint $nt(d+1)=C$. For each configuration $(n,t)$, we conducted
several runs of Adam optimizer for a fixed number of epochs. We performed this
procedure over many realizations of $F$ and $H_{t}$, both sampled according to
our data generating process. Note that each run was influenced by both the
randomness in the optimization and the data. We smooth out this randomness by
averaging over our many runs of optimization and realizations of $F,H_{t}$.

As in (Hoffmann et al., 2022), we are interested in the behavior of this
procedure for compute scales that are computationally burdensome so we require
a method of extrapolating our results from affordable compute scales to much
larger ones. We performed extrapolation via two linear fits in _logarithmic
space_ in which the regressors are the log-optimal training set sizes and the
targets are the log-optimal parameter counts. Since the regression takes place
in log space, a solution with _slope_ $1$ demonstrates a linear relation
between optimal parameter count and training samples. As apparent by the
noticeable change in slope in Figure 1, it seems unwise to extrapolate with
just a single linear fit of the data in log scale. Therefore, we extrapolate
to higher compute scales via a linear fit of only the data from _larger_
compute budgets that we tested. Likewise, we extrapolate to lower compute
scales via linear fits of only the data from _smaller_ compute budgets that we
tested. We observed that for large compute budgets, a line of slope $1$ is
well within the confidence bounds produced by statistical bootstrapping. This
result both lends credence to our theoretical analysis (depicted in orange)
and qualitatively matches what was observed by Hoffmann et al. (2022).

##  5 Understanding Sources of Error

Recall that Theorem 2 bounds the expected cross-entropy error of an _optimal_
single hidden-layer relu neural networks of width $n$. We arrive at this bound
by analyzing a _particular_ learning model with this architecture. In this
section, we introduce this learning model and discuss key steps in the
analysis. Though it is unclear even to us why the efficient frontier of this
particular learning model reflects what is achieved via stochastic gradient
descent, as discussed in Section 4, some prior work suggests that this ought
to be the case.

$\tilde{F}^{*}_{n,t}$, the learning model addressed by Theorem 2, is the
single hidden-layer ReLU neural network with input dimension $d$ and width $n$
that minimizes out-of-sample cross-entropy error when conditioned on $t$
training data samples. Since $\tilde{F}^{*}_{n,t}$ is difficult to analyze
directly, we instead study a surrogate learning model. This surrogage model
shares the same architecture as our primary learning model but differs in its
prior parameter distribution. Our analysis yields an upper bound, as error
incurred by the surrogate exceeds that of our primary learning model.
Relations between these the aforementioned models are illustrated in Figure 4.
We now describe our surrogate learning model in more detail.

Figure 4: The data generating process applies $F$ to inputs sampled from a
$d$-dimensional standard normal to produce labels. In our framework, learning
amounts to conditioning a learning model on the resulting training data
$H_{t}$. Our primary learning model $\tilde{F}_{n,t}^{*}$ is the single-
hidden-layer relu network which produces the best prediction when conditioned
on history. Our surrogate learning model $\tilde{F}_{n,t}$ shares the same
architecture but has a different prior distribution.

###  5.1 Our Surrogate Learning Model

Like our primary learning model, our surrogate $\tilde{F}_{n,t}$ is a neural
network with input dimension $d$ and width $n$. Each $i$th hidden unit is
parameterized by weights $w_{i}\in S^{d-1}$. Recall that $\overline{\theta}$
is a discrete distribution over $S^{d-1}$ sampled from a Dirichlet process to
produce output weights $\theta$ for our data generating process. Our learning
model weights are sampled according to
$w_{i}\overset{iid}{\sim}\overline{\theta}$ _with replacement_. In our
surrogate learning model, the weight assigned to the output of the $i$th
hidden unit is taken to be ${\rm sign}(\theta_{w_{i}})\sqrt{K}/n$, so that

$\tilde{F}_{n,t}(X_{t})=\frac{1}{1+\exp\left(-\frac{\sqrt{K}}{n}\sum_{i=1}^{n}{\rm
sign}(\theta_{w_{i}}){\rm
ReLU}(\left(w_{i}+Z_{w_{i}}\right)^{\top}X_{t})\right)},$

where $Z_{w}\overset{iid}{\sim}\mathcal{N}(0,\delta^{2}I_{d})$. Intuitively,
this function is constructed by sampling $n$ hidden units from the data
generating process, possibly with repeated samples of each, perturbing the
input weights of each of these hidden units with Gaussian noise, and averaging
their outputs. As such, misspecification error stems from two sources of
imprecision: $1)$ the input weight perturbations $Z_{w}$ and $2)$ use of a
random sample of $n$ hidden units to approximate the data generating process.
Approximations of this sort date back to the work of Barron (1993), who
established that neural networks can provide accurate approximations even for
some data generating process with infinitely many parameters.

Note that we constrain the width $n$ of our surrogate learning model to be the
same as that of our primary learning model. This is so that the surrogate is
constrained to the same architecture and thus is subject to error at least as
large as that of our primary learning model, which is optimal among those
sharing this architecture. Note that $\delta^{2}$, the perturbation variance,
is a free parameter that we can optimize for any pair $(n,t)$ to produce a
tight bound. This perturbation is introduced to keep the mutual information
between the surrogate learning model and the data generating process finite.

In the remainder of this section, we present upper bounds on the
misspecification error, estimation error, and cross-entropy error of this
surrogate learning model $\tilde{F}_{n,t}$ with respect to our data generating
process $F$. We will denote $\mathbb{P}(\tilde{F}_{n,t}\in\cdot|H_{t})$ by
$\tilde{Q}_{n,t}$.

###  5.2 Error Bounds for Our Learning Model

We begin by providing an upper bound on the misspecification error of our
learning model.

######  Theorem 4.

(misspecification error upper bound) For all $n,t,d,K\in\mathbb{Z}_{++}$ and
$\delta>0$,

$\mathbb{I}(Y_{t+1};F|\tilde{F}_{n,t},X_{t})\leq\frac{3K}{n}+2d\delta^{2}.$

This result is intuitive and matches the error bound derived in (Barron, 1993)
when we set $\delta^{2}=1/dn$. The first term contains the error incurred from
our learning model having at most width $n$. The second term contains the
error from fitting with basis functions that are perturbed by variance
$\delta^{2}$ noise. The error increases as the complexity of the environment
$d,K$ increases, and decreases as the number of parameters in our learning
model $n$ increases and the magnitude of perturbations $\delta^{2}$ to our
basis function decrease.

We next derive an upper bound for the estimation error incurred by our
learning model.

######  Theorem 5.

(estimation error upper bound) For all $n,t,d,K\in\mathbb{Z}_{++}$ and
$\delta>0$, if $K\geq 2$, then

$\mathbb{I}(Y_{t+1};\tilde{F}_{n,t}|\tilde{Q}_{n,t},X_{t})\leq\frac{K\ln\left(1+\frac{n}{K}\right)\cdot\left(\ln\left(2n\right)+\frac{d}{2}\ln\left(1+\frac{1}{d\delta^{2}}\right)\right)}{t}.$

Just as in (Barron, 1994), as the number of training samples grows, the
estimation error decays at a rate of $\mathcal{O}\left(\frac{1}{t}\right)$.
However, the interesting distinction is that Theorem 5 suggests that while the
estimation error increases as the parameter count of our learning model grows,
the dependence on $n$ is only _logarithmic_ as opposed to _linear_.

With Theorems 4 and 5, an upper bound on the full cross-entropy error directly
follows:

######  Corollary 6.

(cross-entropy error upper bound) For all $n,t,d,K\in\mathbb{Z}_{++}$, and
$\delta>0$, if $K\geq 2$, then

$\mathbb{E}\left[L_{t}\left(\tilde{Q}_{n,t}\right)\right]\leq
L^{*}+\frac{3K}{n}+2d\delta^{2}+\frac{K\ln\left(1+\frac{n}{K}\right)\cdot\left(\ln(2n)+\frac{d}{2}\ln\left(1+\frac{1}{d\delta^{2}}\right)\right)}{t}.$

Corollary 6 still has a dependence on the free parameter $\delta^{2}$ i.e. the
noise in our approximation of the basis functions. One way to eliminate the
$\delta^{2}$ dependence is select the value of $\delta^{2}$ which minimizes
the upper bound in Corollary 6. The following result computes an upper bound
on the expression that results after we perform this minimization.

######  Theorem 7.

(optimal noise) For all $n,d,K\in\mathbb{Z}_{++}$ and $\epsilon>0$, if
$n,K\geq 2$, then

$\inf_{\delta^{2}>0}2d\delta^{2}+\frac{dK\ln\left(1+\frac{n}{K}\right)\ln\left(1+\frac{1}{\delta^{2}}\right)}{2t}\leq\frac{dK\ln\left(1+\frac{n}{K}\right)\left(1+\ln\left(4t\right)\right)}{2t}.$

Theorem 2 follows as a direct consequence of Corollary 6 and Theorem 7.

###  5.3 Relation to Barron’s Bounds

It is well known that a learning model of this form can achieve
misspecification error that decays at rate $\mathcal{O}(K/n)$ (Barron, 1993)
when measured in _squared error_. Barron (1993) derived a results which
bounded the misspecification error incurred by approximating any function with
a particular Fourier representation via a single hidden layer neural network
with $n$ hidden units. Their followup analysis in (Barron, 1994) studies both
the misspecification error and the _estimation error_. They upper bound the
estimation error by analyzing the number of samples required by a width $n$
neural network that minimizes a regularized least-squares objective. Notably,
the techniques used to bound the misspecification error are almost entirely
divorced from those used to bound the estimation error. If these bounds were
tight, one could derive a scaling law for which the optimal number of training
samples is $\tilde{\mathcal{O}}(C^{2/3})$ while the optimal parameter count is
$\tilde{\mathcal{O}}(C^{1/3})$, which unfortunately does not match empirical
results highlighted in Figure 1. We hypothesize that our analysis is able to
recover the appropriate scaling law because our framework allows us to
coherently reason about the misspecification and estimation error of a
learning model in tandem as opposed to independently.

The scaling law of Barron (1994) indicates? that the number of training
samples grows _faster_ than what is optimal for a neural network learning via
stochastic gradient descent. This suggests that either the estimation error
bounds of Barron (1994) are loose, or neural networks trained via stochastic
gradient descent do not require as many samples to avoid overfitting as their
regularized least-squares solution does. Since these bounds are loose and
analyzing the performance of stochastic gradient descent directly is
cumbersome, we instead analyzed the performance of an optimal Bayesian
learner. Inspired by the observation that stochastic gradient descent seems to
match the performance of an optimal Bayesian learner (Zhu et al., 2022), we
attempted to understand the performance of stochastic gradient descent applied
to a single-hidden layer neural network of width $n$ by analyzing the
performance of an _optimal Bayesian learner_ that tries to learn $\tilde{F}$
from observed training samples.

##  6 Closing Remarks

State-of-the-art neural networks have grown tremendously over the past decade.
As this trend continues and these neural networks are deployed in production
systems it is becoming increasingly important to optimize use of the enormous
resources – computation, energy, data, and human interaction – that they
consume. The traditional approach to neural network modeling, entailing
experimentation with many architectures and hyperparameter sweeps before
settling on a favorite is no longer viable. This gives rise to demand for a
theory that predicts what will work well. This theory might be developed
through a combination of mathematical analysis and experimentation with
smaller scale models that are much less expensive to train.

Our results represent a first step in developing rigorous mathematics for this
purpose. We hope that this will inspire further theoretical research on the
subject. Our analysis is based on an error upper bound. While our empirical
analysis raises the possibility that this guides reasonable allocations of
large compute budgets, further research is required to determine whether this
is really the case. Furthermore, our analysis restricts attention to single-
hidden-layer feedforward neural networks. Generalizing the results to treat
state-of-the-art architectures remains an open issue.

We have only considered allocation of pretraining compute. State-of-the-art
performance in modern application domains relies on subsequent fine-tuning
(see, e.g., (Ziegler et al., 2019)) through reinforcement learning from human
feedback, and, after that, resources are required in production to support
application of the learned model as well as further learning from real-world
interactions. How best to allocate resources between pretraining, fine-tuning,
and production is another area that deserves attention. An information-
theoretic framework that treats pretraining, fine-tuning, and decision making
in a unified and coherent manner, perhaps in the vein of (Lu et al., 2021),
might facilitate theoretical developments on this front.

#### Acknowledgments

We thank Yifan Zhu and Shi Dong for helpful pointers to a couple mathematical
arguments used in our analysis. This research was supported by Army Research
Office (ARO) grant W911NF2010055.

## References

  * Barron (1993) Andrew R. Barron.  Universal approximation bounds for superpositions of a sigmoidal function.  _IEEE Transactions on Information theory_ , 39(3):930–945, 1993.
  * Barron (1994) Andrew R. Barron.  Approximation and estimation bounds for artificial neural networks.  _Machine learning_ , 14(1):115–133, 1994.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners, 2020.  URL https://arxiv.org/abs/2005.14165.
  * Hoffmann et al. (2022) Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent Sifre.  Training compute-optimal large language models, 2022.  URL https://arxiv.org/abs/2203.15556.
  * Jeon & Van Roy (2022a) Hong Jun Jeon and Benjamin Van Roy.  An information-theoretic framework for deep learning.  In _Advances in Neural Information Processing Systems_ , volume 35, 2022a.
  * Jeon & Van Roy (2022b) Hong Jun Jeon and Benjamin Van Roy.  An information-theoretic framework for supervised learning, 2022b.  URL https://arxiv.org/abs/2203.00246.
  * Kaplan et al. (2020) Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models, 2020.  URL https://arxiv.org/abs/2001.08361.
  * Lu et al. (2021) Xiuyuan Lu, Benjamin Van Roy, Vikranth Dwaracherla, Morteza Ibrahimi, Ian Osband, and Zheng Wen.  Reinforcement learning, bit by bit, 2021.  URL https://arxiv.org/abs/2103.04047.
  * Rae et al. (2021) Jack W. Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po-Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John Mellor, Irina Higgins, Antonia Creswell, Nat McAleese, Amy Wu, Erich Elsen, Siddhant Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, Laurent Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean-Baptiste Lespiau, Maria Tsimpoukelli, Nikolai Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Toby Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson d’Autume, Yujia Li, Tayfun Terzi, Vladimir Mikulik, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy, Chris Jones, James Bradbury, Matthew Johnson, Blake Hechtman, Laura Weidinger, Iason Gabriel, William Isaac, Ed Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem Ayoub, Jeff Stanway, Lorrayne Bennett, Demis Hassabis, Koray Kavukcuoglu, and Geoffrey Irving.  Scaling language models: Methods, analysis & insights from training gopher, 2021.  URL https://arxiv.org/abs/2112.11446.
  * Zhu et al. (2022) Yifan Zhu, Hong Jun Jeon, and Benjamin Van Roy.  Is stochastic gradient descent near optimal?, 2022.  URL https://arxiv.org/abs/2209.08627.
  * Ziegler et al. (2019) Daniel M. Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B. Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving.  Fine-tuning language models from human preferences, 2019.  URL https://arxiv.org/abs/1909.08593.

##  Appendix A Appendix

###  A.1 Proofs of General Information-Theoretic Results

See 1

###### Proof.

$\displaystyle L_{t}(\tilde{Q}_{t})$
$\displaystyle=\mathbb{E}\left[-\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\ln\mathbb{P}(Y_{t+1}\in\cdot|\tilde{Q}_{t},X_{t})\right]$
$\displaystyle=\mathbb{E}[\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\ln\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})]-\mathbb{E}[\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\ln\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})]$
$\displaystyle\quad+\mathbb{E}[\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\ln\mathbb{P}(Y_{t+1}\in\cdot|H_{t})]-\mathbb{E}[\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\ln\mathbb{P}(Y_{t+1}\in\cdot|H_{t})]$
$\displaystyle\quad-\mathbb{E}\left[\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\ln\mathbb{P}(Y_{t+1}\in\cdot|\tilde{Q}_{t},X_{t})\right]$
$\displaystyle=-\mathbb{E}[\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\ln\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})]$
$\displaystyle\quad+\mathbb{E}[\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\ln\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})]-\mathbb{E}[\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\ln\mathbb{P}(Y_{t+1}\in\cdot|H_{t})]$
$\displaystyle\quad+\mathbb{E}[\mathbb{P}(Y_{t+1}\in\cdot|F,H_{t})\ln\mathbb{P}(Y_{t+1}\in\cdot|H_{t})]-\mathbb{E}\left[\mathbb{P}(Y_{t+1}\in\cdot|F,H_{t})\ln\mathbb{P}(Y_{t+1}\in\cdot|\tilde{Q}_{t},X_{t})\right]$
$\displaystyle=L^{*}+\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\
\|\ \mathbb{P}(Y_{t+1}\in\cdot|H_{t}))\right]$
$\displaystyle\quad+\mathbb{E}\left[\mathbb{E}\left[\mathbb{P}(Y_{t+1}\in\cdot|F,H_{t})\ln\frac{\mathbb{P}(Y_{t+1}\in\cdot|H_{t})}{\mathbb{P}(Y_{t+1}\in\cdot|\tilde{Q}_{t})}\Big{|}H_{t}\right]\right]$
$\displaystyle\overset{(a)}{=}L^{*}+\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\
\|\ \mathbb{P}(Y_{t+1}\in\cdot|H_{t}))\right]$
$\displaystyle\quad+\mathbb{E}\left[\mathbb{P}(Y_{t+1}\in\cdot|H_{t})\ln\frac{\mathbb{P}(Y_{t+1}\in\cdot|H_{t})}{\mathbb{P}(Y_{t+1}\in\cdot|\tilde{Q}_{t})}\right]$
$\displaystyle=L^{*}+\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\
\|\ \mathbb{P}(Y_{t+1}\in\cdot|H_{t}))\right]$
$\displaystyle\quad+\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y_{t+1}\in\cdot|H_{t})\
\|\ \mathbb{P}(Y_{t+1}\in\cdot|\tilde{Q}_{t}))\right]$
$\displaystyle\overset{(b)}{=}L^{*}+\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t})\
\|\ \mathbb{P}(Y_{t+1}\in\cdot|H_{t}))\right]$
$\displaystyle\quad+\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y_{t+1}\in\cdot|H_{t},\tilde{Q}_{t})\
\|\ \mathbb{P}(Y_{t+1}\in\cdot|\tilde{Q}_{t}))\right]$
$\displaystyle\overset{(c)}{=}L^{*}+\mathbb{I}(Y_{t+1};F|H_{t})+\mathbb{I}(Y_{t+1};H_{t}|\tilde{Q}_{t})$
$\displaystyle=L^{*}+\mathbb{I}(Y_{t+1};F|H_{t})+\mathbb{I}(Y_{t+1};F|\tilde{F},X_{t})-\mathbb{I}(Y_{t+1};F|\tilde{F},X_{t})+\mathbb{I}(Y_{t+1};H_{t}|\tilde{Q}_{t},X_{t})$
$\displaystyle=L^{*}+\mathbb{I}(Y_{t+1};F|H_{t})+\mathbb{I}(Y_{t+1};F|\tilde{F},X_{t})$
$\displaystyle\quad-\mathbf{h}(Y_{t+1}|\tilde{F},X_{t})+\mathbf{h}(Y_{t+1}|F,X_{t})+\mathbf{h}(Y_{t+1}|\tilde{Q}_{t},X_{t})-\mathbf{h}(Y_{t+1}|H_{t})$
$\displaystyle\overset{(d)}{=}L^{*}+\mathbb{I}(Y_{t+1};F|H_{t})+\mathbb{I}(Y_{t+1};F|\tilde{F},X_{t})+\mathbb{I}(Y_{t+1};\tilde{F}|\tilde{Q}_{t},X_{t})-\mathbb{I}(Y_{t+1};F|H_{t})$
$\displaystyle=L^{*}+\mathbb{I}(Y_{t+1};F|\tilde{F},X_{t})+\mathbb{I}(Y_{t+1};\tilde{F}|\tilde{Q}_{t},X_{t}),$

where $(a)$ follows from the tower property, $(b)$ follows from the fact that
$Y_{t+1}\perp\tilde{Q}_{t}|H_{t}$, $(c)$ follows from the KL-divergence
expression of mutual information, and $(d)$ follows from the fact that
$\mathbf{h}(Y_{t+1}|F,X_{t})=\mathbf{h}(Y_{t+1}|F,H_{t})$ and that
$\mathbf{h}(Y_{t+1}|\tilde{F},X_{t})=\mathbf{h}(Y_{t+1}|\tilde{F},\tilde{Q}_{t},X_{t})$
because $Y_{t+1}\perp\tilde{Q}_{t}|\tilde{F}$. The result follows. ∎

We first derive a general information-theoretic upper bound on the estimation
error. To arrive at this result, we first present 2 supporting lemmas.

######  Lemma 8.

(monotonicity of error) For all $t\in\mathbb{Z}_{+}$ and learning models
$\tilde{F}$,

$\mathbb{I}(Y_{t+1};\tilde{F}|\tilde{Q}_{t},X_{t})\geq\mathbb{I}(Y_{t+2};\tilde{F}|\tilde{Q}_{t+1},X_{t+1}).$

###### Proof.

$\displaystyle\mathbb{I}(Y_{t+1};\tilde{F}|\tilde{Q}_{t},X_{t})$
$\displaystyle=\mathbf{h}(Y_{t+1}|\tilde{Q}_{t},X_{t})-\mathbf{h}(Y_{t+1}|\tilde{Q}_{t},X_{t},\tilde{F})$
$\displaystyle=\mathbf{h}(Y_{t+1}|\tilde{Q}_{t},X_{t})-\mathbf{h}(Y_{t+1}|\tilde{F},X_{t})$
$\displaystyle=\mathbf{h}(Y_{t+1}|\tilde{Q}_{t},X_{t})-\mathbf{h}(Y_{t+2}|\tilde{F},X_{t+1})$
$\displaystyle=\mathbf{h}(Y_{t+2}|\tilde{Q}_{t},X_{t+1})-\mathbf{h}(Y_{t+2}|\tilde{F},X_{t+1})$
$\displaystyle\overset{(a)}{\geq}\mathbf{h}(Y_{t+2}|\tilde{Q}_{t},\tilde{Q}_{t+1},X_{t+1})-\mathbf{h}(Y_{t+2}|\tilde{F},X_{t+1})$
$\displaystyle\overset{(b)}{=}\mathbf{h}(Y_{t+2}|\tilde{Q}_{t+1},X_{t+1})-\mathbf{h}(Y_{t+2}|\tilde{F},X_{t+1})$
$\displaystyle=\mathbb{I}(Y_{t+2};\tilde{F}|\tilde{Q}_{t+1},X_{t+1}),$

where $(a)$ follows from the fact that conditioning reduces entropy and $(b)$
follows from the fact that
$\mathbb{I}(Y_{t+2};\tilde{P}_{t}|Q_{t+1},X_{t+1})=0$. ∎

This result is rather intuitive as it suggests that more data leads to smaller
estimation error. The following result provides another way to write the
estimation error which will make it more amenable to summation in $t$.

######  Lemma 9.

For all $t\in\mathbb{Z}_{+}$ and learning models $\tilde{F}$,

$\mathbb{I}(Y_{t+1};\tilde{F}|\tilde{Q}_{t},X_{t})=\mathbb{I}(\tilde{Q}_{t+1};\tilde{\mathcal{E}}|\tilde{Q}_{t}).$

###### Proof.

$\displaystyle\mathbb{I}(Y_{t+1};\tilde{F}|\tilde{Q}_{t},X_{t})$
$\displaystyle=\mathbf{h}(\tilde{F}|\tilde{Q}_{t},X_{t})-\mathbf{h}(\tilde{F}|\tilde{Q}_{t},X_{t},Y_{t+1})$
$\displaystyle=\mathbf{h}(\tilde{F}|\tilde{Q}_{t})-\mathbf{h}(\tilde{F}|\tilde{Q}_{t},X_{t},Y_{t+1})$
$\displaystyle=\mathbf{h}(\tilde{F}|\tilde{Q}_{t})-\mathbf{h}(\tilde{F}|\tilde{Q}_{t+1})$
$\displaystyle=\mathbb{I}(\tilde{Q}_{t+1};\tilde{F}|\tilde{Q}_{t}).$

∎

With Lemmas 8 and 9, we can establish the following upper bound on the
estimation error.

######  Theorem 10.

(estimation error upper bound) For all $t\in\mathbb{Z}_{++}$, learning models
$\tilde{F}$,

$\mathbb{I}(Y_{t+1};\tilde{F}|\tilde{Q}_{t},X_{t})\leq\frac{\mathbb{I}(F;\tilde{F})}{t}.$

###### Proof.

$\displaystyle\mathbb{I}(Y_{t+1};\tilde{F}|\tilde{Q}_{t},X_{t})$
$\displaystyle\overset{(b)}{\leq}\frac{1}{t}\sum_{s=0}^{t-1}\mathbb{I}(Y_{s+1};\tilde{F}|\tilde{Q}_{s},X_{s})$
$\displaystyle\overset{(c)}{=}\frac{1}{t}\sum_{s=0}^{t-1}\mathbb{I}(Q_{s+1};\tilde{F}|\tilde{Q}_{s})$
$\displaystyle\overset{(d)}{=}\frac{\mathbb{I}(\tilde{F};\tilde{Q}_{t})}{t}$
$\displaystyle=\frac{\mathbb{I}(\tilde{F};H_{t})}{t}$
$\displaystyle\overset{(e)}{\leq}\frac{\mathbb{I}(F;\tilde{F})}{t},$

where $(a)$ follows from Lemma 1, $(b)$ follows from Lemma 8, $(c)$ follows
from Lemma 9, $(d)$ follows from the chain rule of mutual information, and
$(e)$ follows from the data processing inequality. ∎

The estimation error is decreasing in $t$ as expected. However, the estimation
error grows as the learning model $\tilde{F}$ contains more information about
$F$. This is intuitive as in practice $F$ may be incredibly complex. The more
information that $\tilde{F}$ attempts to capture about $F$, the more it must
error before arriving at a good estimate.

##  Appendix B Proofs of Misspecification Error Bounds

###  B.1 General Lemmas

We begin this section with two very general lemmas that facilitate analysis.
We first introduce some notation that is necessary to parse the results of
this section. Consider a function $f(z)=\mathbb{P}(G|Z=z)$ where $G$ is an
event. Given another random variable $Y$ with the same range as $Z$, we use
the assignment operator $\leftarrow$ to denote $f(Y)$ by
$\mathbb{P}(G|Z\leftarrow Y)$. Note that in general $\mathbb{P}(G|Z\leftarrow
Y)$ differs from $\mathbb{P}(G|Z=Y)$ as the latter conditions on the event
$Z=Y$ while the former represents a change of measure for the variable $Z$.

The first result provides an upper bound on the error of the predictor
$\mathbb{P}(Y_{t+1}\in\cdot|\tilde{F},X_{t})$ via the error of the predictor
that takes $\tilde{F}$ to be $F$:
$\mathbb{P}(Y_{t+1}\in\cdot|F\leftarrow\tilde{F},X_{t})$.

######  Lemma 11.

(upper bounds via plug-in estimator) For all $d,K,M\in\mathbb{Z}_{++}$, and
any learning model $\tilde{F}$,

$\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(P_{t}^{*}\|\tilde{P}_{t})\right]\leq\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(P^{*}_{t}\|\bar{P}_{t})\right],$

where $P_{t}^{*}=\mathbb{P}(Y_{t+1}\in\cdot|F,X_{t}),\
\tilde{P}_{t}=\mathbb{P}(Y_{t+1}\in\cdot|\tilde{F},X_{t}),$ and
$\bar{P}_{t}=\mathbb{P}(Y_{t+1}\in\cdot|F\leftarrow\tilde{F},X_{t})$.

###### Proof.

$\displaystyle\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(P^{*}_{t},\|\bar{P}_{t}\right)\right]$
$\displaystyle=\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\mathbb{P}(Y_{t+1}\in\cdot|F,\tilde{F},X_{t})\|\bar{P}_{t}\right)\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\ln\frac{d\tilde{P}_{t}}{dP^{*}_{t}}\bigg{|}F,\tilde{F},X_{t}\right]\right]+\mathbb{E}\left[\mathbb{E}\left[\ln\frac{d\bar{P}_{t}}{d\tilde{P}_{t}}\bigg{|}F,\tilde{F},X_{t}\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\ln\frac{d\tilde{P}_{t}}{dP^{*}_{t}}\bigg{|}F,\tilde{F},X_{t}\right]\right]+\mathbb{E}\left[\mathbb{E}\left[\mathbb{E}\left[\ln\frac{d\bar{P}_{t}}{d\tilde{P}_{t}}\bigg{|}F,\tilde{F},X_{t}\right]\bigg{|}\tilde{F},X_{t}\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(P^{*}_{t}\|\tilde{P}_{t}\right)\right]+\mathbb{E}\left[\mathbb{E}\left[\ln\frac{d\bar{P}_{t}}{d\tilde{P}_{t}}\bigg{|}\tilde{F},X_{t}\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(P^{*}_{t}\|\tilde{P}_{t}\right)\right]+\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\tilde{P}_{t}\|\bar{P}_{t})\right]$
$\displaystyle\geq\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(P^{*}_{t}\|\tilde{P}_{t}\right)\right].$

∎

This lemma states that if we have a learning model $\tilde{F}$, then the
performance of a predictor that interprets $\tilde{F}$ as the _true_ function
$F$ upper bounds the performance of an optimal predictor reasons about the
conditional distributions $\mathbb{P}(F\in\cdot|\tilde{F})$ and
$\mathbb{P}(Y\in\cdots|F,X)$. This result is helpful in situations in which
the conditional distribution $\mathbb{P}(F\in\cdot|\tilde{F})$ is difficult to
analyze.

######  Lemma 12.

(squared error upper bounds KL) For all random variables $X$ and real-valued
functions $G$ and $\tilde{G}$, if $Y$ is a binary random variable for which
$\mathbb{P}(Y=1|G,X)=\frac{1}{1+e^{-G(X)}}$, then

$\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y\in\cdot|G,X)\|\mathbb{P}(Y\in\cdot|G\leftarrow\tilde{G},X))\right]\leq\mathbb{E}\left[\left(G(X)-\tilde{G}(X)\right)^{2}\right].$

###### Proof.

$\displaystyle\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y\in\cdot|G,X)\|\mathbb{P}(Y\in\cdot|G\leftarrow\tilde{G},X))\right]$
$\displaystyle=\mathbb{E}\left[\frac{1}{1+e^{G(X)}}\ln\left(\frac{1+e^{\tilde{G}(X)}}{1+e^{G(X)}}\right)\right]$
$\displaystyle\quad+\mathbb{E}\left[\frac{1}{1+e^{-G(X)}}\ln\left(\frac{1+e^{-\tilde{G}(X)}}{1+e^{-G(X)}}\right)\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\left(G(X)-\tilde{G}(X)\right)^{2}\right]$

where $(a)$ follows from the fact that for all $x,y\in\Re$,
$\frac{1}{1+e^{x}}\ln\left(\frac{1+e^{y}}{1+e^{x}}\right)+\frac{1}{1+e^{-x}}\ln\left(\frac{1+e^{-y}}{1+e^{-x}}\right)\leq(x-y)^{2}$.
∎

###  B.2 Lemmas Pertaining to Dirichlet Multinomial Random Variables

In this section, we study a finite-dimensional analogue of the Dirichlet
Process. Let $d,K,N\in\mathbb{Z}_{++}$ where $\theta^{\prime}\in\Re^{N}$ are
the hidden unit weights and $A\in\Re^{N\times d}$ where each row $A_{i}$ is
distributed uniformly on $\mathbb{S}^{d-1}$. Then,

$F_{N}(X)=\frac{1}{1+\exp\left(-\sqrt{K}\theta^{\prime\top}{\rm
ReLU}(AX)\right)}.$

We now describe how $\theta^{\prime}$ is generated. First,
$\bar{\theta}^{\prime}$ is sampled from ${\rm Dirichlet}([K/N,\ldots,K/N])$.
For each $i\in[N]$, we randomly flip the sign of the weight according to

$\theta_{i}^{\prime}=\left\\{\begin{array}[]{ll}\overline{\theta}_{i}^{\prime}&\text{with
probability }1/2,\\\
-\overline{\theta}_{i}^{\prime}&\text{otherwise.}\end{array}\right.$

We let $Y^{\prime}$ be a binary random variable for which
$\mathbb{P}(Y^{\prime}=1|F_{N},X)=F_{N}(X).$

We now describe the learning model. For all $n\in\mathbb{Z}_{++}$ and
$\delta>0$, our learning model weights $w_{1},\ldots,w_{n}$ are sampled iid
from a categorical distribution with probabilities specified by
$\bar{\theta}^{\prime}$.

$\tilde{F}_{n,t}^{\prime}(X)=\frac{1}{1+\exp\left(-\frac{\sqrt{K}}{n}\sum_{i=1}^{n}{\rm
sign}(\theta_{w_{i}}){\rm ReLU}(\tilde{A}_{w_{i}}^{\top}X)\right)},$

where $\tilde{A}_{w_{i}}=A_{w_{i}}+Z_{w_{i}}$ for
$Z_{w_{i}}\overset{iid}{\sim}\mathcal{N}(0,\delta^{2}I_{d})$ . For notational
simplicity in the results to follow, we will choose the following
reparameterization:

$\tilde{F}_{n,t}^{\prime}(X)=\frac{1}{1+\exp\left(-\sqrt{K}\tilde{\theta}^{\prime\top}{\rm
ReLU}(\tilde{A}X)\right)}$

where $\tilde{\theta}^{\prime}_{i}=\frac{{\rm
sign}(\theta_{i})\sum_{j=1}^{n}\mathbbm{1}_{[w_{j}=i]}}{n}$ and
$\tilde{A}\in\Re^{N\times d}$ is the matrix for which row $i$ is
$\tilde{A}_{i}$.

We first derive the mean squared error between the logits of $F_{N}$ and
$\tilde{F}_{n,t}^{\prime}$.

######  Lemma 13.

For all $d,n,N\in\mathbb{Z}_{++}$, if $X\sim\mathcal{N}(0,I_{d})$, then

$\mathbb{E}\left[\left(\left(\theta^{\prime}-\tilde{\theta}^{\prime}\right){\rm
ReLU}(AX)\right)^{2}\right]\leq\frac{1}{n}.$

###### Proof.

$\displaystyle\mathbb{E}\left[\left(\left(\theta^{\prime}-\frac{1}{n}{\rm
sign}(\theta^{\prime})\odot\tilde{\theta}^{\prime}\right){\rm
ReLU}(AX)\right)^{2}\right]$ $\displaystyle=\mathbb{E}\left[{\rm
ReLU}(AX)^{\top}\left(\tilde{\theta}^{\prime}\tilde{\theta}^{\prime\top}-\theta^{\prime}\theta^{\prime\top}\right){\rm
ReLU}(AX)\right]$ $\displaystyle\leq\mathbb{E}\left[{\rm
ReLU}(AX)^{\top}\left(\tilde{\theta}^{\prime}\tilde{\theta}^{\prime\top}\right){\rm
ReLU}(AX)\right]$ $\displaystyle=\mathbb{E}\left[{\rm
ReLU}(AX)^{\top}\left(\frac{{\rm diag}(\bar{\theta}^{\prime})}{n}\right){\rm
ReLU}(AX)\right]$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{N}|\theta_{i}^{\prime}|(A_{i}^{\top}X)^{2}\right]$
$\displaystyle=\frac{1}{n}$

∎

With this result, we are able to derive the following two upper bounds on
misspecification error.

######  Lemma 14.

For all $d,n,K,N\in\mathbb{Z}_{++}$ and $\delta>0$, if
$X\sim\mathcal{N}(0,I_{d})$, then

$\mathbb{I}(Y^{\prime};A|\theta^{\prime},\tilde{\theta}^{\prime},\tilde{A},X)\leq\frac{2K}{n}+2d\delta^{2}\quad\text{and}\quad\mathbb{I}(Y^{\prime};\theta^{\prime}|\tilde{\theta}^{\prime},A,X)\leq\frac{K}{n}.$

###### Proof.

$\displaystyle\mathbb{I}(Y^{\prime};A|\theta^{\prime},\tilde{\theta}^{\prime},\tilde{A},X)$
$\displaystyle=\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y^{\prime}\in\cdot|\theta^{\prime},A,X)\|\mathbb{P}(Y^{\prime}\in\cdot|\theta^{\prime},\tilde{\theta}^{\prime},\tilde{A},X))\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y^{\prime}\in\cdot|\theta^{\prime},A,X)\|\mathbb{P}(Y^{\prime}\in\cdot|\theta^{\prime},\tilde{\theta}^{\prime},A\leftarrow\tilde{A},X))\right]$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[K\left(\theta^{\prime\top}{\rm
ReLU}(A^{\top}X)-\theta^{\prime\top}{\rm
ReLU}(\tilde{A}^{\top}X)\right)^{2}\right]$
$\displaystyle\overset{(c)}{=}\mathbb{E}\left[K\left(\theta^{\prime\top}{\rm
ReLU}(A^{\top}X)-\hat{\theta}^{\prime\top}{\rm
ReLU}(A^{\top}X)+\hat{\theta}^{\prime\top}{\rm
ReLU}(A^{\top}X)-\theta^{\prime\top}{\rm
ReLU}(\tilde{A}^{\top}X)\right)^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[2K\left(\left(\theta^{\prime\top}{\rm
ReLU}(A^{\top}X)-\hat{\theta}^{\prime\top}{\rm
ReLU}(A^{\top}X)\right)^{2}+\left(\hat{\theta}^{\prime\top}{\rm
ReLU}(AX)-\theta^{\prime\top}{\rm ReLU}(\tilde{A}X)\right)^{2}\right)\right]$
$\displaystyle\overset{(d)}{\leq}\mathbb{E}\left[2K\left(\frac{1}{n}+\left(\hat{\theta}^{\prime\top}{\rm
ReLU}(\hat{A}X)-\hat{\theta}^{\prime\top}{\rm
ReLU}(\tilde{A}X)\right)^{2}\right)\right]$
$\displaystyle\leq\mathbb{E}\left[2K\left(\frac{1}{n}+\left(\theta^{\prime\top}{\rm
ReLU}(\hat{A}X)-\theta^{\prime\top}{\rm
ReLU}(\tilde{A}X)\right)^{2}\right)\right]$
$\displaystyle=\mathbb{E}\left[2K\left(\frac{1}{n}+\left({\rm
ReLU}(\hat{A}X)-{\rm
ReLU}(\tilde{A}X)\right)^{\top}\theta^{\prime}\theta^{\prime\top}\left({\rm
ReLU}(\hat{A}X)-{\rm ReLU}(\tilde{A}X)\right)\right)\right]$
$\displaystyle=\frac{2K}{n}+2K\mathbb{E}\left[\left({\rm ReLU}(\hat{A}X)-{\rm
ReLU}(\tilde{A}X)\right)^{\top}\theta^{\prime}\theta^{\prime\top}\left({\rm
ReLU}(\hat{A}X)-{\rm ReLU}(\tilde{A}X)\right)\right]$
$\displaystyle=\frac{2K}{n}+2K\mathbb{E}\left[\sum_{i=1}^{N}\mathbb{E}[(\theta^{\prime}_{i})^{2}|\hat{A},\tilde{A},X]\cdot({\rm
ReLU}(\hat{A}_{i}^{\top}X)-{\rm ReLU}(\tilde{A}_{i}^{\top}X))^{2}\right]$
$\displaystyle\leq\frac{2K}{n}+2K\mathbb{E}\left[\sum_{i=1}^{N}\mathbb{E}[(\theta^{\prime}_{i})^{2}|\hat{A},\tilde{A},X]\cdot(\hat{A}_{i}^{\top}X-\tilde{A}_{i}^{\top}X)^{2}\right]$
$\displaystyle=\frac{2K}{n}+2K\mathbb{E}\left[\sum_{i=1}^{N}\mathbb{E}[(\theta^{\prime}_{i})^{2}|\hat{A}]\cdot(W_{i}^{\top}X)^{2}\right]$
$\displaystyle\leq\frac{2K}{n}+2K\mathbb{E}\left[\sum_{i=1}^{N}\frac{1-\frac{1}{N}}{N(K+1)}\cdot
d\delta^{2}\right]$ $\displaystyle\leq\frac{2K}{n}+2d\delta^{2}$

where $(a)$ follows from Lemma 11, $(b)$ follows from Lemma 12,
$\frac{1}{1+e^{x}}\ln\left(\frac{1+e^{y}}{1+e^{x}}\right)+\frac{1}{1+e^{-x}}\ln\left(\frac{1+e^{-y}}{1+e^{-x}}\right)\leq(x-y)^{2}$,
where in $(c)$,

$\hat{\theta}_{i}^{\prime}=\begin{cases}\theta_{i}^{\prime}&\text{ if
}\tilde{\theta}_{i}^{\prime}>0\\\ 0&\text{ otherwise}\end{cases},$

and $(d)$ follows from Lemma 13 and

$\hat{A}_{i}=\begin{cases}A_{i}&\text{ if }\tilde{\theta}_{i}^{\prime}>0\\\
0&\text{ otherwise}\end{cases}.$
$\displaystyle\mathbb{I}(Y^{\prime};\theta^{\prime}|\tilde{\theta}^{\prime},A,X)$
$\displaystyle=\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y^{\prime}\in\cdot|\theta^{\prime},A,X)\|\mathbb{P}(Y^{\prime}\in\cdot|\tilde{\theta}^{\prime},A,X))\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y^{\prime}\in\cdot|\theta^{\prime},A,X)\|\mathbb{P}(Y^{\prime}\in\cdot|\theta^{\prime}\leftarrow\tilde{\theta}^{\prime},A,X))\right]$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[K\left(\theta^{\prime\top}{\rm
ReLU}(A^{\top}X)-\tilde{\theta}^{\prime\top}{\rm
ReLU}(A^{\top}X)\right)^{2}\right]$
$\displaystyle\overset{(c)}{\leq}\frac{K}{n},$

where $(a)$ follows from Lemma 11, $(b)$ follows from Lemma 12, and $(c)$
follows from Lemma 13. ∎

Notably, all of these results are _independent_ of $N$. Therefore, with an
appropriate application of dominated convegence, these results will hold as
$N\rightarrow\infty$ and $F_{N}\overset{d}{\rightarrow}F$.

###  B.3 From Dirichlet Random Variable to Dirichlet Process

In this section, we will extend the results of the previous section to our
Dirichlet process. We will define a few new variables for our learning model
up front. Recall that our learning model $\tilde{F}$ samples
$w_{1},\ldots,w_{n}$ iid according to $\bar{\theta}$. Then,

$\tilde{F}_{n,t}(X)=\frac{1}{1+\exp\left(-\frac{\sqrt{K}}{n}\sum_{i=1}^{n}{\rm
sign}(\theta_{\tilde{w}_{i}}){\rm ReLU}(w_{i}^{\top}X)\right)},$

where $\tilde{w}_{i}=w_{i}+Z_{w_{i}}$ for
$Z_{w_{i}}\overset{iid}{\sim}\mathcal{N}(0,\delta^{2}I_{d})$. We will express
$\tilde{F}$ in the following alternate way:

$\tilde{F}_{n,t}(X)=\frac{1}{1+\exp\left(-\sqrt{K}\sum_{w\in\mathcal{W}}\tilde{\theta}_{w}{\rm
ReLU}(\tilde{w}^{\top}X)\right)},$

where $\tilde{\theta}_{w}=\frac{{\rm
sign}(\theta_{w})\cdot\sum_{i=1}^{n}\mathbbm{1}_{[w_{i}=w]}}{n}$ and
$\tilde{w}=w+Z_{w}$. We let
$\tilde{\mathcal{W}}=\\{w\in\mathcal{W}:|\tilde{\theta}|>0\\}$ and
$\bar{\mathcal{W}}=\\{\tilde{w}:w\in\tilde{\mathcal{W}}\\}$.

We begin by extending Lemma 14 to our Dirichlet process and learning model.

######  Corollary 15.

For all $d,n,K\in\mathbb{Z}_{++}$,

$\mathbb{I}(Y;\theta|\tilde{\theta},\mathcal{W},X)\leq\frac{K}{n}.$

###### Proof.

$\displaystyle\mathbb{I}(Y;\theta|\tilde{\theta},\mathcal{W},X)$
$\displaystyle=\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y\in\cdot|\theta,\mathcal{W},X)\|\mathbb{P}(Y\in\cdot|\tilde{\theta},\mathcal{W},X))\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y\in\cdot|\theta,\mathcal{W},X)\|\mathbb{P}(Y\in\cdot|\theta\leftarrow\tilde{\theta},\mathcal{W},X))\right]$
$\displaystyle\overset{(b)}{\leq}K\mathbb{E}\left[\left(\sum_{w\in\mathcal{W}}\theta_{w}{\rm
ReLU}(w^{\top}X)-\sum_{w\in\mathcal{W}}\tilde{\theta}_{w}{\rm
ReLU}(w^{\top}X)\right)^{2}\right]$
$\displaystyle\overset{(c)}{=}K\mathbb{E}\left[\left(\lim_{N\rightarrow\infty}\sum_{i=1}^{N}\theta_{i}^{\prime}{\rm
ReLU}(A_{i}^{\top}X)-\sum_{i=1}^{N}\tilde{\theta}_{i}^{\prime}{\rm
ReLU}(A_{i}^{\top}X)\right)^{2}\right]$
$\displaystyle\overset{(d)}{=}\lim_{N\rightarrow\infty}K\mathbb{E}\left[\left(\sum_{i=1}^{N}\theta_{i}^{\prime}{\rm
ReLU}(A_{i}^{\top}X)-\sum_{i=1}^{N}\tilde{\theta}_{i}^{\prime}{\rm
ReLU}(A_{i}^{\top}X)\right)^{2}\right]$
$\displaystyle\overset{(e)}{\leq}\lim_{N\rightarrow\infty}\frac{K}{n}$
$\displaystyle=\frac{K}{n},$

where $(a)$ follows from Lemma 11, $(b)$ follows from Lemma 12, $(c)$ follows
from the fact that the distribution of $\theta$ is the limiting distribution
$\lim_{N\rightarrow\infty}$ of a Dirichlet $[K/N,\ldots,K/N]$ random variable,
$(d)$ follows from the dominated convergence theorem, and $(e)$ follows from
Lemma 13. ∎

This result is intuitive as the results shown for the Dirichlet distribution
and multinomial learning model in the previous section were independent of the
dimension $N$. The following corollary bounds the remaining term from Lemma 14
for our data generating process and learning model.

######  Corollary 16.

For all $d,n,K\in\mathbb{Z}_{++}$, and $\delta>0$, if
$\tilde{\mathcal{W}}=\\{w\in\mathcal{W}:|\tilde{\theta}_{w}|>0\\}$, and
$\bar{\mathcal{W}}=\\{w+Z_{w}:w\in\tilde{\mathcal{W}}\\}$ where
$Z_{w}\overset{iid}{\sim}\mathcal{N}(0,\delta^{2}I_{d})$, then

$\mathbb{I}(Y;\mathcal{W}|\theta,\tilde{\theta},\bar{\mathcal{W}},X)\leq\frac{2K}{n}+2d\delta^{2}.$

###### Proof.

$\displaystyle\mathbb{I}(Y;\mathcal{W}|\theta,\tilde{\theta},\bar{\mathcal{W}},X)$
$\displaystyle=\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y\in\cdot|\theta,\mathcal{W},X)\|\mathbb{P}(Y\in\cdot|\theta,\tilde{\theta},\bar{\mathcal{W}},X))\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y\in\cdot|\theta,\mathcal{W},X)\|\mathbb{P}(Y\in\cdot|\theta,\tilde{\theta},\mathcal{W}\leftarrow\bar{\mathcal{W}},X))\right]$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[K\left(\sum_{w\in\mathcal{W}}\theta_{w}{\rm
ReLU}(w^{\top}X_{t})-\sum_{w\in\tilde{\mathcal{W}}}\theta_{w}{\rm
ReLU}((w+Z_{w})^{\top}X_{t})\right)^{2}\right]$
$\displaystyle\overset{(c)}{=}\mathbb{E}\left[K\left(\lim_{N\rightarrow\infty}\sum_{i=1}^{N}\theta_{i}^{\prime}{\rm
ReLU}(A_{i}^{\top}X_{t})-\sum_{i=1}^{N}\theta^{\prime}_{i}{\rm
ReLU}(\tilde{A}_{i}^{\top}X_{t})\right)^{2}\right]$
$\displaystyle\overset{(d)}{=}\lim_{N\rightarrow\infty}\mathbb{E}\left[K\left(\sum_{i=1}^{N}\theta_{i}^{\prime}{\rm
ReLU}(A_{i}^{\top}X_{t})-\sum_{i=1}^{N}\theta^{\prime}_{i}{\rm
ReLU}(\tilde{A}_{i}^{\top}X_{t})\right)^{2}\right]$
$\displaystyle\overset{(e)}{\leq}\lim_{N\rightarrow\infty}\frac{2K}{n}+2d\delta^{2}$
$\displaystyle=\frac{2K}{n}+2d\delta^{2},$

where $(a)$ follows from Lemma 11, $(b)$ follows from Lemma 12, $(c)$ follows
from the fact that the distribution of $\theta$ is the limiting distribution
$\lim_{N\rightarrow\infty}$ of a Dirichlet $[K/N,\ldots,K/N]$ random variable,
$(d)$ follows from the dominated convergence theorem, and $(e)$ follows from
Lemma 14. ∎

The final step before proving Theorem 4 is to show that the mutual information
between $Y$ and $\theta$ is _higher_ when we condition on the true basis
functions $\tilde{W}$ as opposed to the noisy ones $\bar{\mathcal{W}}$.

######  Lemma 17.

(more is learned with the true input) For all $n,d,K\in\mathbb{Z}_{++}$,

$\mathbb{I}(Y;\theta|\tilde{\theta},\bar{\mathcal{W}},X)\leq\mathbb{I}(Y;\theta|\tilde{\theta},\mathcal{W},X).$

###### Proof.

$\displaystyle\mathbb{I}(Y;\theta|\tilde{\theta},\bar{\mathcal{W}},X)$
$\displaystyle=\mathbb{I}(Y,X,\bar{\mathcal{W}};\theta|\tilde{\theta})-\mathbb{I}(X,\bar{\mathcal{W}};\theta|\tilde{\theta})$
$\displaystyle=\mathbb{I}(Y,X,\bar{\mathcal{W}};\theta|\tilde{\theta})$
$\displaystyle=\mathbb{I}(Y;\theta|\tilde{\theta})+\mathbb{I}(X,\bar{\mathcal{W}};\theta|\tilde{\theta},Y)$
$\displaystyle\overset{(a)}{\leq}\mathbb{I}(Y;\theta|\tilde{\theta})+\mathbb{I}(X,\mathcal{W};\theta|\tilde{\theta},Y)$
$\displaystyle=\mathbb{I}(Y,X,\mathcal{W};\theta|\tilde{\theta})$
$\displaystyle=\mathbb{I}(Y;\theta|\tilde{\theta},\mathcal{W},X)+\mathbb{I}(\mathcal{W},X;\theta|\tilde{\theta})$
$\displaystyle=\mathbb{I}(Y;\theta|\tilde{\theta},\mathcal{W},X),$

where $(a)$ follows from the fact that
$\theta\perp\bar{\mathcal{W}}|(X,Y,\tilde{\theta})$ and the data processing
inequality. ∎

With this result in place, we provide a proof for Theorem 4. See 4

###### Proof.

$\displaystyle\mathbb{I}(Y_{t+1};F|\tilde{F}_{n,t},X_{t})$
$\displaystyle\overset{(a)}{=}\mathbb{I}(Y_{t+1};\theta,\mathcal{W}|\tilde{\theta},\tilde{\mathcal{W}},X_{t})$
$\displaystyle\overset{(b)}{=}\mathbb{I}(Y_{t+1};\theta|\tilde{\theta},\tilde{\mathcal{W}},X_{t})+\mathbb{I}(Y_{t+1};\mathcal{W}|\theta,\tilde{\theta},\tilde{\mathcal{W}},X_{t})$
$\displaystyle\overset{(c)}{\leq}\mathbb{I}(Y_{t+1};\theta|\tilde{\theta},\mathcal{W},X_{t})+\mathbb{I}(Y_{t+1};\mathcal{W}|\theta,\tilde{\theta},\tilde{\mathcal{W}},X_{t})$
$\displaystyle\overset{(d)}{\leq}\frac{K}{n}+\frac{2K}{n}+2d\delta^{2}$
$\displaystyle=\frac{3K}{n}+2d\delta^{2}$

where in $(a)$, $w_{1},\ldots,w_{n}\overset{iid}{\sim}\bar{\theta}$ and
$\tilde{\theta}=\frac{1}{n}\sum_{i=1}^{n}{\rm sign}(\theta_{w_{i}})$ and
$\tilde{\mathcal{W}}=\\{w\in\mathcal{W}:|\tilde{\theta}_{w}|>0\\}$, $(b)$
follows from the chain rule of mutual information, $(c)$ follows from Lemma
17, and $(d)$ follows from Corollaries 15 and 16. ∎

##  Appendix C Proofs of Estimation Error Bounds

In this section, we will provide proofs for the estimation error bound shown
in Theorem 10. The roadmap will match that of the previous section. We will
first prove results for the Dirichlet-Multinomial process with finite
dimension $N$ and then appropriately apply dominated convergence as
$N\rightarrow\infty$ to derive the results for our Dirichlet process and
learning model.

###  C.1 General Lemmas

The following lemmas are general combinatorics results that we will eventually
apply to bound the estimation error of the finite $N$ Dirichlet-Multinomial
process.

######  Lemma 18.

For all $m,j,n,K,N\in\mathbb{Z}_{++}$ s.t. $j<n$, if

$C_{m}(j)=\underbrace{\sum_{i=j}^{n-1}\frac{\frac{K}{N}}{K+i}\cdot\sum_{i=j+1}^{n-1}\frac{\frac{K}{N}}{K+i}\cdot\ldots\cdot\sum_{i>j+m-1}^{n-1}\frac{\frac{K}{N}}{K+i}}_{m},$

then

$\frac{1}{m!}\frac{K^{m}}{N^{m}}\ln^{m}\left(\frac{K+n}{K+m-1+j}\right)\leq
C_{m}(j)\leq\frac{1}{m!}\frac{K^{m}}{N^{m}}\ln^{m}\left(\frac{K+n}{K-1+j}\right).$

###### Proof.

We first prove the upper bound via induction. Base Case: $n=1$

$\displaystyle C_{1}(j)$
$\displaystyle=\sum_{i=j}^{n-1}\frac{\frac{K}{N}}{K+i}$
$\displaystyle\leq\frac{K}{N}\int_{j-1}^{n}\frac{1}{K+x}dx$
$\displaystyle=\frac{K}{N}\ln\left(\frac{K+n}{K-1+j}\right)$

Assume inductive hypothesis is true for $m=k$.

$\displaystyle C_{k+1}(j)$
$\displaystyle=\sum_{i=j}^{n-1}\frac{\frac{K}{N}}{K+i}\cdot C_{k}(i+1)$
$\displaystyle\leq\frac{K}{N}\int_{j-1}^{n}\frac{1}{K+x}\cdot C_{k}(x+1)$
$\displaystyle\leq\frac{K^{k+1}}{N^{k+1}}\frac{1}{k!}\int_{j-1}^{n}\frac{1}{K+x}\cdot\ln^{k}\left(\frac{K+n}{K+x}\right)dx$
$\displaystyle\leq-\frac{K^{k+1}}{N^{k+1}}\frac{1}{(k+1)!}\cdot\ln^{k+1}\left(\frac{K+n}{K+x}\right)\bigg{|}^{n}_{j-1}$
$\displaystyle=\frac{K^{k+1}}{N^{k+1}}\frac{1}{(k+1)!}\ln^{k+1}\left(\frac{K+n}{K-1+j}\right).$

We now prove the lower bound also via induction. Base Case: $m=1$

$\displaystyle C_{1}(j)$
$\displaystyle=\sum_{i=j}^{n-1}\frac{\frac{K}{N}}{K+i}$
$\displaystyle\geq\frac{K}{N}\int_{j}^{n}\frac{1}{K+x}dx$
$\displaystyle=\frac{K}{N}\ln\left(\frac{K+n}{K+j}\right)$

Assume inductive hypothesis is true for $m=k$.

$\displaystyle C_{k+1}(j)$
$\displaystyle=\sum_{i=j}^{n-1}\frac{\frac{K}{N}}{K+i}\cdot C_{k}(i+1)$
$\displaystyle\geq\frac{K}{N}\int_{j}^{n}\frac{1}{K+x}\cdot C_{k}(x+1)$
$\displaystyle\geq\frac{K^{k+1}}{N^{k+1}}\frac{1}{k!}\int_{j}^{n}\frac{1}{K+x}\cdot\ln^{k}\left(\frac{K+n}{K+k+x}\right)dx$
$\displaystyle\geq-\frac{K^{k+1}}{N^{k+1}}\frac{1}{(k+1)!}\cdot\ln^{k+1}\left(\frac{K+n}{K+k+x}\right)\bigg{|}^{n}_{j}$
$\displaystyle=\frac{K^{k+1}}{N^{k+1}}\frac{1}{(k+1)!}\ln^{k+1}\left(\frac{K+k+n}{K+k+j}\right)$
$\displaystyle\geq\frac{K^{k+1}}{N^{k+1}}\frac{1}{(k+1)!}\ln^{k+1}\left(\frac{K+n}{K+k+j}\right).$

The result follows. ∎

######  Lemma 19.

For all $i,n,K,N\in\mathbb{Z}_{++}$, if $2\leq K\leq\sqrt{N}$ and $n\leq N$,
then

$\frac{1}{(2i)!}\frac{K^{2i}}{N^{2i}}\ln^{2i}\left(\frac{K+n}{K-1}\right)-\frac{1}{(2i+1)!}\frac{K^{2i+1}}{N^{2i+1}}\ln^{2i+1}\left(\frac{K+n}{K+2i}\right)\geq
0.$

###### Proof.

$\displaystyle 0$
$\displaystyle\overset{(a)}{\leq}1-\frac{1}{2i+1}\frac{K}{N}\ln\left(\frac{K+n}{K-1}\right)$
$\displaystyle=\ln^{2i}\left(\frac{K+n}{K-1}\right)-\frac{1}{2i+1}\frac{K}{N}\ln^{2i+1}\left(\frac{K+n}{K-1}\right)$
$\displaystyle\leq\ln^{2i}\left(\frac{K+n}{K-1}\right)-\frac{1}{2i+1}\frac{K}{N}\ln^{2i+1}\left(\frac{K+n}{K+2i}\right)$
$\displaystyle=\frac{1}{(2i)!}\frac{K^{2i}}{N^{2i}}\ln^{2i}\left(\frac{K+n}{K-1}\right)-\frac{1}{(2i+1)!}\frac{K^{2i+1}}{N^{2i+1}}\ln^{2i+1}\left(\frac{K+n}{K+2i}\right)$

where $(a)$ follows for all $n\leq\left(K-1\right)e^{\frac{3N}{K}}-K$ which is
implied by $n\leq N$ for $K\geq 2$. ∎

######  Lemma 20.

For all $n,K,N\in\mathbb{Z}_{++}$, if $2\leq K\leq\sqrt{N}$ and $n\leq N$,
then

$\prod_{i=0}^{n-1}\left(1-\frac{\frac{K}{N}}{K+i}\right)\geq
1-\frac{K}{N}\ln\left(1+\frac{n}{K}\right).$

###### Proof.

$\displaystyle\prod_{i=0}^{n-1}\left(1-\frac{\frac{K}{N}}{K+i}\right)$
$\displaystyle\overset{(a)}{\geq}1-\sum_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}\frac{1}{(2i+1)!}\frac{K^{2i+1}}{N^{2i+1}}\ln^{2i+1}\left(\frac{K+r}{K+2i}\right)$
$\displaystyle\quad+\sum_{i=1}^{\lceil\frac{n-1}{2}\rceil}\frac{1}{(2i)!}\frac{K^{2i}}{N^{2i}}\ln^{2i}\left(\frac{K+r}{K-1}\right)$
$\displaystyle\overset{(b)}{\geq}1-\frac{K}{N}\ln\left(1+\frac{n}{K}\right)$
$\displaystyle\quad+\sum_{i=1}^{\lfloor\frac{n-1}{2}\rfloor}\frac{1}{(2i)!}\frac{K^{2i}}{N^{2i}}\ln^{2i}\left(\frac{K+n}{K-1}\right)-\frac{1}{(2i+1)!}\frac{K^{2i+1}}{N^{2i+1}}\ln^{2i+1}\left(\frac{K+n}{K+2i}\right)$
$\displaystyle\overset{(c)}{\geq}1-\frac{K}{N}\ln\left(1+\frac{n}{K}\right),$

where $(a)$ follows from Lemma 18, and $(b)$ follows from Lemma 19 ∎

###  C.2 Lemmas pertaining to Dirichlet Multinomial

The following result bounds the expected number of unique classes drawn from a
Dirichlet-Multinomial distribution with $n$ draws and
$\alpha=[K/N,\ldots,K/N]\in\Re^{N}$.

######  Lemma 21.

For all $n,K,N\in\mathbb{Z}_{++}$ s.t. $K\leq\sqrt{N}$ and $r\leq N$, if
$\tilde{\theta}^{\prime}\sim{\rm DirMult}(n,\alpha)$ for
$\alpha=\left[K/N,\ldots,K/N\right]\in\Re^{N}$, then

$\mathbb{E}\left[\sum_{i=1}^{N}\mathbbm{1}_{[\tilde{\theta}^{\prime}>0]}\right]\leq
K\ln\left(1+\frac{r}{K}\right).$

###### Proof.

$\displaystyle\mathbb{E}\left[\sum_{i=1}^{N}\mathbbm{1}_{[\tilde{\theta}^{\prime}_{i}>0]}\right]$
$\displaystyle=N\cdot\mathbb{P}(\tilde{\theta}^{\prime}_{i}>0)$
$\displaystyle\overset{(a)}{=}N\cdot\left(1-\mathbb{P}(\tilde{\theta}^{\prime}_{1}=0,\tilde{\theta}^{\prime}_{2}+\cdots+\tilde{\theta}^{\prime}_{N}=n)\right)$
$\displaystyle=N\cdot\left(1-\frac{\Gamma(K)\Gamma(n+1)}{\Gamma(n+K)}\cdot\frac{\Gamma\left(\frac{K}{N}\right)}{\Gamma\left(\frac{K}{N}\right)\Gamma\left(1\right)}\cdot\frac{\Gamma\left(n+\frac{K}{N}(N-1)\right)}{\Gamma\left(\frac{K}{N}(N-1)\right)\Gamma\left(n+1\right)}\right)$
$\displaystyle=N\cdot\left(1-\frac{\Gamma(K)}{\Gamma(n+K)}\cdot\frac{\Gamma\left(n+K-\frac{K}{N}\right)}{\Gamma\left(K-\frac{K}{N}\right)}\right)$
$\displaystyle=N\cdot\left(1-\frac{\prod_{i=0}^{n-1}\left(K-\frac{K}{N}+i\right)}{\prod_{i=0}^{n-1}K+i}\right)$
$\displaystyle=N\cdot\left(1-\prod_{i=0}^{n-1}\left(1-\frac{\frac{K}{N}}{K+i}\right)\right)$
$\displaystyle\overset{(b)}{\leq}N\cdot\left(1-\left(1-\frac{K}{N}\ln\left(1+\frac{n}{K}\right)\right)\right)$
$\displaystyle=K\ln\left(1+\frac{n}{K}\right).$

where $(a)$ follows from the aggregation property of the Dirichlet-multinomial
distribution and $(b)$ follows from Lemma 20. ∎

Note that this upper bound is _independent_ of $N$. In the next section, we
will apply the dominated convegence theorem to bound the number of unique
basis functions drawn by our learning model.

###  C.3 Extensions to Dirichlet Processes

Recall that our learning model $\tilde{F}_{n,t}$ is identified by approximate
output layer weights $\tilde{\theta}_{w}=\frac{{\rm
sign}(\theta_{w})\cdot\sum_{i=1}^{n}\mathbbm{1}_{w_{i}=w}}{n}$ where
$w_{i}\overset{iid}{\sim}\bar{\theta}$ and approximate basis function weights
$\bar{\mathcal{W}}=\\{\tilde{w}:w\in\tilde{\mathcal{W}}\\}$ where
$\tilde{w}=w+Z_{w}$,
$\tilde{\mathcal{W}}=\\{w\in\mathcal{W}:|\tilde{\theta}|>0\\}$ and
$Z_{w}\overset{iid}{\sim}\mathcal{N}(0,\delta^{2}I_{d})$.

In this section, we will translate the results from the previous section to
the case in which the data generating process is the Dirichlet process that we
study in the main text.

######  Lemma 22.

For all $n,K\in\mathbb{Z}_{++}$,

$\mathbb{E}\left[\sum_{w\in\mathcal{W}}\mathbbm{1}_{[|\tilde{\theta}_{w}|>0]}\right]\leq
K\ln\left(1+\frac{n}{K}\right).$

###### Proof.

$\displaystyle\mathbb{E}\left[\sum_{w\in\mathcal{W}}\mathbbm{1}_{[|\tilde{\theta}_{w}|>0]}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\sum_{w\in\mathcal{W}}\mathbbm{1}_{[|\tilde{\theta}_{w}|>0]}\bigg{|}\mathcal{W}\right]\right]$
$\displaystyle\overset{(a)}{=}\mathbb{E}\left[\mathbb{E}\left[\lim_{N\rightarrow\infty}\sum_{w\in\tilde{\mathcal{W}}}\mathbbm{1}_{[|\tilde{\theta}_{w}^{\prime}|>0]}\bigg{|}\mathcal{W}\right]\right]$
$\displaystyle\overset{(b)}{=}\lim_{N\rightarrow\infty}\mathbb{E}\left[\mathbb{E}\left[\sum_{w\in\tilde{\mathcal{W}}}\mathbbm{1}_{[|\tilde{\theta}_{w}^{\prime}|>0]}\bigg{|}\mathcal{W}\right]\right]$
$\displaystyle\overset{(c)}{\leq}\lim_{N\rightarrow\infty}K\ln\left(1+\frac{n}{K}\right)$
$\displaystyle=K\ln\left(1+\frac{n}{K}\right),$

where in $(a)$, $\mathcal{W}_{N}$ is a subset of the first $N$ elements of
$\mathcal{W}$ and $\tilde{X}_{N}$ is ${\rm DirMult}(n,\alpha_{N})$ where
$\alpha_{N}=[K/N,\ldots,K/N]\in\Re^{N}$ and $\mathcal{W}_{N}$ is the set of
classes, $(b)$ follows from the dominated convergence theorem since
$|\sum_{w\in\tilde{\mathcal{W}}}\mathbbm{1}_{[\tilde{\theta}_{w}^{\prime}>0]}|\leq
n$, and $(c)$ follows from Lemma 21. ∎

######  Theorem 23.

(rate upper bound) For all $d,n,K\in\mathbb{Z}_{++}$ and $\delta>0$,

$\mathbb{I}(F;\tilde{F}_{n,t})\leq
K\ln\left(1+\frac{n}{K}\right)\cdot\left(\ln(2n)+\frac{d}{2}\ln\left(1+\frac{1}{d\delta^{2}}\right)\right).$

###### Proof.

$\displaystyle\mathbb{I}(F;\tilde{F}_{n,t})$
$\displaystyle=\mathbb{I}(\theta,\mathcal{W};\tilde{\theta},\bar{\mathcal{W}})$
$\displaystyle\leq\mathbb{I}(\theta;\tilde{\theta}|\mathcal{W})+\mathbb{I}(\mathcal{W};\bar{\mathcal{W}})$
$\displaystyle\leq\mathbb{H}(\tilde{\theta}|\mathcal{W})+\mathbb{I}(\mathcal{W};\bar{\mathcal{W}})$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\sum_{w\in\mathcal{W}}\mathbbm{1}_{[|\tilde{\theta}_{w}|>0]}\cdot\left(\log\left(2n\right)+\mathbb{I}(w;\tilde{w})\right)\right]$
$\displaystyle\leq\mathbb{E}\left[\sum_{w\in\mathcal{W}}\mathbbm{1}_{[|\tilde{\theta}_{w}|>0]}\cdot\left(\log\left(2n\right)+\frac{d}{2}\ln\left(1+\frac{1}{d\delta^{2}}\right)\right)\right]$
$\displaystyle\overset{(b)}{=}K\ln\left(1+\frac{n}{K}\right)\cdot\left(\ln(2n)+\frac{d}{2}\ln\left(1+\frac{1}{d\delta^{2}}\right)\right),$

where $(a)$ follows from the fact that if $w$ is drawn in $\tilde{F}$, the
output weight can take on at most $2n$ different values
$(-\frac{n\sqrt{K}}{n},-\frac{(n-1)\sqrt{K}}{n},\ldots,-\frac{\sqrt{K}}{n},\frac{\sqrt{K}}{n},\ldots\frac{n\sqrt{K}}{n})$
and $(b)$ follows from Lemma 22. ∎

See 5

###### Proof.

The result follows from Theorems 23 and 10. ∎

##  Appendix D Characterization of the Efficient Frontier

In this section, we provide a proof for Theorem 3. See 3

###### Proof.

$\displaystyle n^{*}$
$\displaystyle=\operatorname*{arg\,min}_{n\in\left[\frac{C}{d}\right]}\frac{3K}{n}+\frac{K\ln\left(1+\frac{n}{K}\right)\cdot\ln\left(2n\right)}{t}+\frac{dK\ln\left(1+\frac{n}{K}\right)\left(1+\frac{1}{2}\ln\left(4t\right)\right)}{t};\
\text{ s.t. }n\cdot d\cdot t\leq C$
$\displaystyle=\operatorname*{arg\,min}_{n\in\left[\frac{C}{d}\right]}\frac{3}{n}+\frac{\ln\left(1+\frac{n}{K}\right)\cdot\ln\left(2n\right)}{t}+\frac{d\ln\left(1+\frac{n}{K}\right)\left(1+\frac{1}{2}\ln\left(4t\right)\right)}{t};\
\text{ s.t. }n\cdot d\cdot t\leq C$
$\displaystyle=\operatorname*{arg\,min}_{n\in\left[\frac{C}{d}\right]}\frac{3}{n}+\frac{nd\ln\left(1+\frac{n}{K}\right)\cdot\ln\left(2n\right)}{C}+\frac{nd^{2}\ln\left(1+\frac{n}{K}\right)\left(1+\frac{1}{2}\ln\left(\frac{4C}{nd}\right)\right)}{C}$
$\displaystyle\overset{(a)}{=}n\text{ s.t.
}\frac{3}{n^{2}}=\frac{d\left(\ln\left(1+\frac{n}{K}\right)+\ln\left(1+\frac{n}{K}\right)ln(2n)+\frac{n}{K+n}\ln\left(2n\right)\right)}{C}$
$\displaystyle\qquad+\frac{d^{2}\ln\left(1+\frac{n}{K}\right)\ln\left(\frac{4C}{nd}\right)}{2C}+\frac{n}{C(n+K)}+\frac{nd^{2}\ln\left(\frac{4C}{nd}\right)}{2C\left(n+K\right)}$
$\displaystyle\overset{(b)}{\leq}n\text{ s.t.
}C=\frac{n^{2}d^{2}\ln\left(1+\frac{n}{K}\right)\ln\left(\frac{4C}{nd}\right)}{6}$
$\displaystyle=n\text{ s.t.
}C-\frac{n^{2}d^{2}\ln(1+\frac{n}{K})}{6}\ln(C)=\frac{-n^{2}d^{2}\ln\left(1+\frac{n}{K}\right)\ln\left(\frac{nd}{4}\right)}{6}$
$\displaystyle\overset{(c)}{=}n\text{ s.t.
}C=-\frac{n^{2}d^{2}\ln(1+\frac{n}{K})}{6}W_{-1}\left(-\frac{e^{\ln\left(\frac{nd}{4}\right)}}{\frac{n^{2}d^{2}\ln(1+\frac{n}{K})}{6}}\right)$
$\displaystyle=n\text{ s.t.
}C=-\frac{n^{2}d^{2}\ln(1+\frac{n}{K})}{6}W_{-1}\left(-\frac{6nd}{4n^{2}d^{2}\ln(1+\frac{n}{K})}\right)$
$\displaystyle\overset{(d)}{\leq}n\text{ s.t.
}C=-\frac{n^{2}d^{2}\ln(1+\frac{n}{K})}{6}W_{-1}\left(-\frac{3}{2nd\ln(1+\frac{n}{K})}\right)$
$\displaystyle\overset{(e)}{\leq}n\text{ s.t.
}C=\frac{n^{2}d^{2}\ln(1+\frac{n}{K})}{6}\ln\left(\frac{2nd\ln(1+\frac{n}{K})}{3}\right)$
$\displaystyle\overset{(f)}{\leq}n\text{ s.t.
}C=\frac{1}{6}n^{2}d^{2}\ln\left(1+\frac{n}{K}\right)^{2}\cdot\ln(\ln(d))$
$\displaystyle=n\text{ s.t.
}\frac{6C}{d^{2}\ln(\ln(d))}=n^{2}\ln\left(1+\frac{n}{K}\right)^{2}$
$\displaystyle=n\text{ s.t.
}\sqrt{\frac{6C}{d^{2}\ln(\ln(d))}}=n\ln\left(1+\frac{n}{K}\right)$
$\displaystyle\overset{(g)}{\leq}\min\left\\{\frac{\sqrt{\frac{6C}{d^{2}\ln(1+d)}}}{W_{0}\left(\sqrt{\frac{6C}{d^{2}K^{2}\ln(1+d)}}\right)},\sqrt{\frac{6C}{d^{2}\ln(\ln(d))}}+\sqrt{\frac{6C}{d^{2}\ln(\ln(d))}+4\sqrt{\frac{6CK^{2}}{d^{2}\ln(\ln(d))}}}\right\\},$

where $(a)$ follows from $1$st order optimality conditions, $(b)$ follows from
the fact that the rhs is an increasing function in $n$, so the root of a lower
bound is an upper bound for the true root, $(c)$ follows from the fact that
for all $a\in\Re$, the inverse function of $x-a\ln(x)$ is
$-aW_{-1}\left(-\frac{e^{-\frac{x}{a}}}{a}\right)$ where $W_{-1}$ is the $-1$
branch of the Lambert W function, $(d)$ follows from the fact that the rhs is
an increasing function in $n$ and so the root of a lower bound is an upper
bound for the true root, $(e)$ follows from the fact that
$W_{-1}(x)=\ln(-x)-\ln(-\ln(-x))+o(1)$ and monotonicity, $(f)$ follows from
monotonicity and the fact that
$\ln(1+\frac{n}{K})\ln(\frac{4nd\ln(1+\frac{n}{K}}{3})\geq\frac{\ln(n)^{2}\cdot\ln(1+d)\cdot\ln(K)}{2K}$,
and $(g)$ follows from the fact that for small $n/K$, $\ln(1+n/K)$ is well
approximated by $\frac{n/K}{1+n/K}$ and the inverse of $n^{2}/(n+K)$ is
$n+\sqrt{n^{2}+4Kn}$, and for large $n/K$, $\ln(1+n/K)$ is well approximated
by $\ln(n/K)$ and the inverse of $nln(n/K)$ is $\frac{n}{W_{0}(x/K)}$. The
result follows. ∎

###  D.1 Optimizing the Noise

Finally, we provide a proof for Theorem 7 which finds the value of
$\delta^{2}$ in our surrogate model which minimizes the upper bound on
expected cross-entropy error.

See 7

###### Proof.

$\displaystyle\operatorname*{arg\,min}_{\delta^{2}>0}2d\delta^{2}+\frac{dK\ln\left(1+\frac{n}{K}\right)\ln\left(1+\frac{1}{\delta^{2}}\right)}{2t}$
$\displaystyle=\operatorname*{arg\,min}_{\delta^{2}>0}2\delta^{2}+\frac{K\ln\left(1+\frac{n}{K}\right)\ln\left(1+\frac{1}{\delta^{2}}\right)}{2t}$
$\displaystyle\overset{(a)}{=}\delta^{2}\text{ s.t.
}0=2-\frac{K\ln\left(1+\frac{n}{K}\right)}{2t}\cdot\frac{1}{\delta^{4}+\delta^{2}}$
$\displaystyle=\delta^{2}\text{ s.t.
}4=\frac{K\ln\left(1+\frac{n}{K}\right)}{t}\cdot\frac{1}{\delta^{4}+\delta^{2}}$
$\displaystyle=\delta^{2}\text{ s.t.
}t\delta^{4}+t\delta^{2}=\frac{K}{4}\ln\left(1+\frac{n}{K}\right)$
$\displaystyle\overset{(b)}{=}\frac{-t+\sqrt{t^{2}+tK\ln\left(1+\frac{n}{K}\right)}}{2t}$
$\displaystyle=\frac{-1+\sqrt{1+\frac{K\ln\left(1+\frac{n}{K}\right)}{t}}}{2}$

where $(a)$ follows from first order optimality conditions and $(b)$ follows
from solving the quadratic equation. The resulting expression above is rather
messy, so to provide an upper bound, we replace it with

$\delta^{2}=\frac{K\ln\left(1+\frac{n}{K}\right)}{4t},$

which is a good approximation when $K\ln\left(1+\frac{n}{K}\right)/t$ is
small. Plugging in this value of $\delta^{2}$ gives:

$\displaystyle\inf_{\delta^{2}>0}2d\delta^{2}+\frac{dK\ln\left(1+\frac{n}{K}\right)\ln\left(1+\frac{1}{\delta^{2}}\right)}{2t}$
$\displaystyle\leq\frac{dK\ln\left(1+\frac{n}{K}\right)\left(1+\ln\left(1+\frac{4t}{K\ln\left(1+\frac{n}{K}\right)}\right)\right)}{2t}$
$\displaystyle\overset{(a)}{\leq}\frac{dK\ln\left(1+\frac{n}{K}\right)\left(1+\ln\left(4t\right)\right)}{2t},$

where $(a)$ follows from the fact that
$1+\frac{4t}{K\ln\left(1+\frac{n}{K}\right)}\leq 4t$ for $n,K\geq 2$. The
result follows. ∎

##  Appendix E Experimental Details

###  E.1 Data Generating Process

Figure 1 was generated by setting $d=16$ and $K=16$. We implemented the data
generating process in the following way. We let

$F(X)=\sqrt{K}\sum_{i=1}^{N}\theta_{i}\cdot\omega_{i}\cdot{\rm
ReLU}(A_{i}^{\top}X).$

Instead of sampling directly from a Dirichlet process with base distribution
${\rm Uniform}(\mathbb{S}^{d-1})$ and scale parameter $K$, we approximate this
via sampling linear layer weights $\theta$ from an $N$ dimensional dirichlet
random variable with parameter $(K/N,\ldots,K/N)$ and then sampling
$\omega_{i}\overset{iid}{\sim}{\rm Rademacher}$. The the basis functions are
sampled $A_{i}\overset{iid}{\sim}{\rm Uniform}(\mathbb{S}^{d-1})$. It is well
known that as $N\rightarrow\infty$ this process converges to the Dirichet
process that we study theoretically. For our experiments, we choose
$N=2^{12}$.

We let $X_{t}\sim\mathcal{N}(0,I_{d})$ and generate
$Y_{t+1}=1/(1+\exp\\{-F(X_{t})\\})$. Note that in our experiments, we do not
actually sample $Y_{t+1}$ as a binary random variable with probability
$1/(1+\exp\\{-F(X_{t})\\})$ but instead provide the probability itself. This
is done primarily to reduce variance in the experiments as the two data
generating processes result in optimizing the same objective but providing the
probabilities reduces the variance of the empirical risk.

###  E.2 Efficient Frontier Sweep

We construct a geometric sequence of tractable compute budgets for which we
empirically compute the efficient frontier. For these experiments we used the
sequence $\\{2^{18},2^{19},\ldots,2^{26}\\}$. For each value of $C$ in this
sequence, we construct a set of pairs $(n,t)$ for which $nt=C/d$. For each
pair $(n,t)$, we generated a training dataset of size $t$ and a learning
network of input dimension $d$ and width $n$. For each dataset, we performed
$10$ training runs of Adam optimizer and record the final resulting test
error. We perform these $10$ runs to smooth out anomalous cases as neural
networks can be finicky. We detail the training procedure in the following
subsection.

###  E.3 Training

Given $t$ training samples and a training network of width $n$, we endow each
training run with a validation dataset of fixed size $10000$. Note that as the
compute budget grows, this validation set is quickly dwarfed by the size of
the training dataset so we ignore its impacts the flop count. We perform $500$
epochs of minibatch stochastic gradient descent with adam optimizer and
batchsize $1024$. We implemented an early stopping procedure in which we
return the model within the 500 epochs with the lowest validation error. This
returned model is separately evaluated on a test set of size $100000$ and the
out of sample cross-entropy error is recorded.

Figure 5: We plot each of the $78\times 9\times 10$ aforementioned trials.

###  E.4 Bootstrapping and Extrapolation

For $K=16,d=16$, we performed the above procedure for $78$ different
realizations of $F$. For each realization, we perform an efficient frontier
sweep over $9$ different compute values $(\\{2^{18},2^{19},\ldots,2^{26}\\})$.
For each compute value, we perform a sweep over pairs $(n,t)$ which satisfy
$nt=C/d$ and for each, generate a dataset of size $t$ from $F$. With this
training dataset, we initialize $10$ learning models with input dimension $d$
and width $n$ and perform the training procedure outlined above. The results
of this procedure are displayed in Figure 5. We average the test errors of the
model returned by each of these $10$ runs. The result is that for each $(n,t)$
pair, we have $78$ values for the average test error based on different
realizations of the data generating process. We perform a bootstrapping
procedure to generate the confidence intervals in Figure 1.

In our bootstrapping, we subsample $10$ realizations with replacement from the
$79$ and perform 4 linear fits in logarithmic scale. Recall that we evaluated
$9$ different compute values so the first linear fit performs least squares
regression where $X$ is the subsampled log optimal training set sizes for
compute values $\\{2^{18},\ldots,2^{21}\\}$ and $Y$ is the corresponding log
optimal parameter counts. The second linear fit is for compute values
$\\{2^{20},\ldots,2^{23}\\}$, the third for compute values
$\\{2^{22},\ldots,2^{25}\\}$, and the fourth for $\\{2^{23},\ldots,2^{26}\\}$.
To generate Figure 1, we performed this bootstrapping process $10000$ times,
each generating $4$ linear fits to the log optimal dataset size and parameter
count.

To extrapolate to compute values higher than $2^{26}$, we compute a mean of
just the $4$th linear fit of each of the $10000$ subsamples. The confidence
intervals provided in Figure 1 are $1$-standard deviation above and below this
mean value computed from the $10000$ subsamples. Likewise, for extrapolation
to compute values lower than $2^{18}$, we perform the same procedure but with
the $1$st linear fit.

For interpolation within the compute values we evaluated, we performed a
moving average where values at the extremes $(2^{18}\text{ and }2^{26})$ were
evaluated just via averages of linear fits $1$ and $4$ respectively, but
values in the middle were averages of linear fits in which they were a part of
i.e. the value of $2^{20}$ would be an average of linear fits $1$ and $2$
since both of these linear fits used data from compute value $2^{20}$.

For reference, generating the results to produce Figure 1 took over $1$ week
when run in parallel across $2$ machines each with $32$ cpu cores and $8$gb
gpus. In Figure 6, we provide results for $(d=16,K=64)$ and $(d=64,K=16)$
which perform the same procedure as above but only over $20$ realizations of
$F$. They are marginally less convincing than the result of Figure 1 but this
could be due to noise in the data from having fewer runs. It would be
interesting to perform much more comprehensive and higher-scale experiments in
the future, but for the purposes of this work, we found this experimental
evidence compelling enough.

Figure 6: We produce the same plot as in Figure 1 but for $(d=16,K=64)$ and
$(d=64,K=16)$. Note that we only perform averaging over $20$ realizations as
opposed to $78$ and for our bootstrapping procedure we subsample $5$
realizations as opposed to $10$.