#
Learning Curve Theory

Marcus Hutter
DeepMind
http://www.hutter1.net/

(5 February 2021)

###### Abstract

Recently a number of empirical “universal” scaling law papers have been
published, most notably by OpenAI. ‘Scaling laws’ refers to power-law
decreases of training or test error w.r.t. more data, larger neural networks,
and/or more compute. In this work we focus on scaling w.r.t. data size $n$.
Theoretical understanding of this phenomenon is largely lacking, except in
finite-dimensional models for which error typically decreases with $n^{-1/2}$
or $n^{-1}$, where $n$ is the sample size. We develop and theoretically
analyse the simplest possible (toy) model that can exhibit $n^{-β}$ learning
curves for arbitrary power $β>0$, and determine whether power laws are
universal or depend on the data distribution.

###### Contents

  1. 1 Introduction
  2. 2 Setup
  3. 3 Expected Learning Curves
  4. 4 Learning Curve Variance
  5. 5 Experiments
  6. 6 Extensions
  7. 7 Discussion
  8. References
  9. A Other Loss Functions
  10. B Derivation of Expectation and Variance
  11. C Noisy Labels
  12. D Approximating Sums by Integrals
  13. E List of Notation
  14. F More Figures

Keywords

> Power Law, Scaling, Learning Curve, Theory, Data Size, Error, Loss, Zipf, …

##  1 Introduction

Power laws in large-scale machine learning. The ‘mantra’ of modern machine
learning is ‘bigger is better’. The larger and deeper Neural Networks (NNs)
are, the more data they are fed, the longer they are trained, the better they
perform. Apart from the problem of overfitting [BHM18] and the associated
recent phenomenon of double-descent [BHMM19], this in itself is rather
unsurprising. But recently ‘bigger is better’ has been experimentally
quantified, most notably by Baidu [HNA+17] and OpenAI [HKK+20, KMH+20,
HKHM21]. They observe that the _error_ or _test loss_ decreases as a power
law, with the _data size_ , with the _model size_ (number of NN parameters),
as well as with the _compute budget_ used for training, assuming one factor is
not “bottlenecked” by the other two factors. If all three factors are
increased appropriately in tandem, the loss has power-law scaling over a very
wide range of data/model size and compute budget.

If there is intrinsic noise in the data (or a non-vanishing model mis-
specification), the loss can never reach zero, but at best can converge to the
intrinsic entropy of the data (or the intrinsic representation=approximation
error). When we talk about _error_ , we mean test loss with this potential
offset subtracted, similar to regret in online learning.

Ubiquity/universality of power laws. Power laws have been observed for many
problem types (supervised, unsupervised, transfer learning) and data types
(images, video, text, even math) and many NN architectures (Transformers,
ConvNets, …) [HNA+17, RRBS19, HKK+20, KMH+20]. This has led some to the belief
that power laws might be universal: Whatever the problem, data, model, or
learning algorithm, learning curves follow power laws. To which extent this
conjecture is true, we do not know, since theoretical understanding of this
phenomenon is largely lacking. Below we review some (proto)theory we are aware
of.

Theory: Scaling with model size. Consider a function
$f:[0;1]^{d}\textrightarrow ℝ$ which we wish to approximate. A naive
approximation is to discretize the hyper-cube to an $ε$-grid. This constitutes
a model with $m=(1/ε)^{d}$ parameters, and if $f$ is $L$-Lipschitz, can
approximate $f$ to accuracy $L⋅ε=L⋅m^{-1/d}$, i.e. the (absolute) error scales
with model size $m$ as a power law with exponent $-1/d$. More generally, there
exist (actually linear) models with $m$ parameters that can approximate all
functions $f$ whose first $k$ derivatives are bounded to accuracy
$O(m^{-k/d})$ [Mha96], again a power law, and without further assumptions, no
reasonable model can do better [DHM89]; see [Pin99] for reformulations and
discussions of these results in the context of NNs. Not being aware of this
early theoretical work, this scaling law has very recently been empirically
verified and extended by [SK20]. Instead of naively using the input dimension
$d$, they determine and use the (fractal) dimension of the data distribution
in the penultimate layer of the NN.

Theory: Scaling with compute. Most NNs are trained by some form of stochastic
gradient descent, efficiently implemented in the form of back-propagation.
Hence compute is proportional to number of iterations $i$ times batch-size
times model size. So studying the scaling of error with the number of
iterations tells us how error scales with compute. The loss landscape of NNs
is highly irregular, which makes theoretical analyses cumbersome at best. At
least asymptotically, the loss is locally convex, hence the well-understood
stochastic (and online) convex optimization could be a first (but possibly
misleading) path to search for theoretical understanding of scaling with
compute. The error of most stochastic/online optimization algorithms scales as
a power law $i^{-1/2}$ or $i^{-1}$ for convex functions [Bub15, Haz16].

Theory: Scaling with data size. Even less is theoretically known about scaling
with data size. [Cho20] and [HNA+17] consider a very simple Bernoulli model:
Essentially they observe that the Bernoulli parameter can be estimated to
accuracy $1/\sqrt{n}$ from $n$ i.i.d samples, i.e. the absolute loss (also)
scales with $1/\sqrt{n}$ [HNA+17] and the log-loss or KL-divergence scales
with $1/n$ [Cho20]. Indeed, the latter holds for any loss, locally quadratic
at the minimum, so is not at all due to special properties of KL as [Cho20]
suggests. These observations trivially follow from the central limit theorem
for virtually any finitely-parameterized model in the under-parameterized
regime of more-data-than-parameters. This is of course always the case for
their Bernoulli model, which only has one parameter, but _not_ necessarily for
the over-parameterized regime some modern NNs work in. Anyway, the scaling
laws identified by OpenAI et al. are $n^{-β}$, for various $β<1/2$, which
neither the Bernoulli nor any finite-dimensional model can explain.

Data size vs iterations vs compute. Above we have used the fact that compute
is (usually in deep learning) proportional to number of learning iterations,
provided batch and model size are kept fixed. In addition,

  * (i)

in _online learning_ , every data item is used only once, hence the size of
data used up to iteration $n$ is proportional to $n$.

  * (ii)

This is also true for _stochastic learning algorithms_ for some recent
networks, such as GPT-3, trained on massive data sets, where every data item
is used at most once (with high probability).

  * (iii)

When generating _artificial data_ , it is natural to generate a new data item
for each iteration.

Hence in all of these 3 settings, the _learning curves_ , error-with-data-
size, error-with-iterations, and error-with-compute, are scaled versions of
each other. For this reason, scaling of error with iterations, also tells us
how error scales with data size and even with compute, but scaling with model
size is different.

This work. In this work we focus on scaling with data size $n$. As explained
above, any reasonable finitely-parameterized model and reasonable loss
function leads to a scaling law $n^{-β}$ with $β={\textstyle\frac{1}{2}}$ or
$β=1$, but not the observed $β<{\textstyle\frac{1}{2}}$. We therefore
conjecture that any theoretical explanation of power laws for a variety $β$
(beyond 0-1 and absolute error implying $β={\textstyle\frac{1}{2}}$ and
locally-quadratic loss implying $β=1$) requires real-world data of unbounded
complexity, that is, no finite-dimensional model can “explain” all information
in the data.

Possible modelling choices are (a) scaling up the model with data, or (b)
consider non-parametric models (e.g. kNN or Gaussian processes), or (c) a
model with (countably-)infinitely-many parameters. We choose (c) for
mathematical simplicity compared to (b), and because (c) clearly separates
scaling with data from scaling with model size, unlike (a). In future, (a) and
(b) should definitely also be pursued, in particular, since we have no
indication that our findings transfer.

Within our toy model, we show that for domains of unbounded complexity, a
large variety of learning curves are possible, including _non_ -power-laws. It
is plausible that this remains true for most infinite models. Real data is
often Zipf distributed (e.g. the frequency of words in text), which is itself
a power law. We show that this, in our toy model, implies power law learning
curves with “interesting” $β$, though most (even non-Zipf) distributions
_also_ lead to power laws but with “uninteresting” $β$.

Contents. In Section 2 we introduce our setup: classification with countable
“feature” space and a memorizing algorithm, the simplest model and algorithm
we could come up with that exhibits interesting/relevant scaling behavior. In
Section 3 we derive and discuss general expressions for expected learning
curves and for various specific data distributions: finite, Zipf, exponential,
and beyond, many but not all lead to power laws. In Section 4 we estimate the
uncertainty in empirical learning curves. We show that the signal-to-noise
ratio deteriorates with $n$, which implies that many (costly) runs need to be
averaged in practice to get a smooth learning curve. On the other hand, the
signal-to-noise ratio of the time-averaged learning curves tends to infinity,
hence even a single run suffices for large $n$. In Section 5 we perform some
simple control experiments to confirm and illustrate the theory and claims,
and the accuracy of the theoretical expressions. In Section 6 we discuss
(potential) extensions of our toy model towards a more comprehensive and
realistic theory of scaling laws: noisy labels, other loss functions,
continuous features, models that generalize, and deep learning. Section 7
concludes with limitations and potential applications. Appendix A discusses
losses beyond 0-1 loss. Appendix B contains derivations of the expected error,
and in particular exact and approximate expressions for the time-averaged
variance. Appendix C considers noisy labels. Appendix D derives an
approximation of sums by integrals, tailored to our purpose. Appendix E lists
notation. Appendix F contains some mores plots.

##  2 Setup

We formally introduce our setup, model, algorithm, and loss function in this
section: We consider classification problems with 0-1 loss and countable
feature space. A natural practical example application would be classifying
words w.r.t. some criterion. Our toy model is a deterministic classifier for
features/words sampled i.i.d. w.r.t. to some distribution. Our toy algorithm
predicts/recalls the _class_ for a new _feature_ from a previously observed
(_feature_ ,_class_) pair, or acts randomly on a novel _feature_. The
probability of an erroneous prediction is hence proportional to the
probability of observing a new feature, which formally is equivalent to the
model in [Cha81]. The usage and analyses of the model and resulting
expressions are totally different though. While [Cha81]’s aim is to develop
estimators for the probability of discovering a new species from data whatever
the unknown true underlying probabilities, we are interested in the
relationship between the true probability distribution of the data and the
resulting learning curves, i.e. the scaling of expected (averaged) error with
sample size. In Appendix A we show that, within a for our purpose irrelevant
multiplicative constant, the results also apply to most other loss functions.

The toy model. The goal of this work is to identify and study the simplest
model that is able to exhibit power-law learning curves as empirically
observed by [HNA+17, HKK+20, KMH+20] and others. Consider a classification
problem $h∈{\cal H}:={\cal X}\textrightarrow{\cal Y}$, e.g. ${\cal
Y}=\\{0,1\\}$ for binary classification, where classifier $h$ is to be learnt
from data ${\cal D}_{n}:=\\{(x_{1},y_{1}),...,(x_{n},y_{n})\\}∈({\cal X}×{\cal
Y})^{n}$. For finite ${\cal X}$ and ${\cal Y}$, this is a finite model class
($|{\cal H}|<∞$), which, as discussed above, can only exhibit a restrictive
range of learning curves, typically $n^{-1}/n^{-1/2}/e^{-O(n)}$ for locally-
quadratic/absolute/0-1 error. In practice, ${\cal X}$ is often a (feature)
vector space $ℝ^{d}$, which can support an infinite model class ($|{\cal
H}|=∞$) (e.g. NNs) rich enough to exhibit (at least empirically) $n^{-β}$
scaling for many different $β\not\in\\{{\textstyle\frac{1}{2}},1\\}$,
typically $β\ll 1$. The smallest potentially suitable ${\cal X}$ would be
countable, e.g. $ℕ$, which we henceforth assume. The model class ${\cal
H}:=ℕ\textrightarrow{\cal Y}$ is uncountable and has infinite VC-dimension,
hence is not uniformly PAC learnable, but can be learnt non-
uniformly.Furthermore, for simplicity we assume that data ${\cal
D}_{n}:=\\{(i_{1},y_{1}),...,(i_{n},y_{n})\\}≡(i_{1:n},y_{1:n})$ with
“feature” $i_{t}∈ℕ$ “labelled” $y_{t}$ is noise-free = deterministic, i.e.
$y_{t}=y_{t^{\prime}}$ if $i_{t}=i_{t^{\prime}}$. Let $h_{0}∈{\cal H}$ be the
unknown true labelling function. We discuss relaxations of some of these
assumptions later in Section 6, in particular extension to other loss function
in Appendix A and noisy labels in Appendix C. Let features $i_{t}$ be drawn
i.i.d. with $\mathbb{P}[i_{t}=i]=:θ_{i}≥0$ and (obviously)
$∑_{i=1}^{∞}θ_{i}=1$. The infinite vector ${\bm{θ}}≡(θ_{1},θ_{2},...)$
characterizes the feature distribution. The labels are then determined by
$y_{t}=h_{0}(i_{t})$.

The toy algorithm. We consider a simple tabulation learning algorithm
$A:ℕ×(ℕ×{\cal Y})^{*}\textrightarrow{\cal Y}$ that stores all past labelled
features ${\cal D}_{n}$ and on next feature $i_{n+1}=i$ recalls $y_{t}$ if
$i_{t}=i$, i.e. feature $i$ has appeared in the past, or outputs, in its
simplest instantiation, _undefined_ if $i\not\in i_{1:n}$ i.e. is new.
Formally:

$\displaystyle A(i,{\cal
D}_{n})~{}:=~{}\left\\{{y_{t}~{}~{}~{}~{}~{}~{}\text{if ~{}~{}~{}~{}$i=i_{t}$
for some $t≤n$}\atop\bot~{}~{}~{}~{}~{}\text{else~{}~{}~{}i.e.\ if }i\not\in
i_{1:n}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}}\right.$ (1)

Error. Algorithm $A$ only makes an error predicting label $y_{n+1}$ if
$i\not\in i_{1:n}$. We say $A$ makes 1 unit of error in this case. Formally,
the _(instantaneous) error_ $\text{\sf E}_{n}$ of algorithm $A$ when
predicting $y_{n+1}$ from ${\cal D}_{n}$ is defined as

$\displaystyle\text{\sf E}_{n}~{}:=~{}[\\![i_{n+1}\not\in i_{1:n}]\\!]$

The expectation of this w.r.t. to the random choice of ${\cal D}_{n}$ and
$i_{n+1}$ gives the _expected (instantaneous) error_

$\displaystyle\text{\sf E$\\!\\!\\!\\!\;$E}_{n}~{}:=~{}\mathbb{E}[\text{\sf
E}_{n}]~{}=~{}\mathbb{P}[i_{n+1}\not\in
i_{1:n}]~{}=~{}∑_{i=1}^{∞}θ_{i}(1-θ_{i})^{n}$ (2)

A formal derivation is given in Appendix B, but the result is also intuitive:
If feature $i$ has not been observed so far (which happens with probability
$(1-θ_{i})^{n}$), and then feature $i$ is observed (which happens with
probability $θ_{i}$), the algorithm makes an error. $\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}$ as a function of $n$ constitutes an (expected)
learning curve, which we will henceforth study. In Appendix A we show that
expression (2) remains valid within an irrelevant multiplicative constant for
most other loss functions.

##  3 Expected Learning Curves

We now derive theoretical expected learning curves for various underlying data
distributions. We derive exact and approximate, general and specific
expressions for the scaling of _expected_ error with sample size. Specifically
we consider finite models, which lead to exponential error decay, and infinite
Zipf distributions, which lead to interesting power laws with power $β<1$.
Interestingly even highly skewed data distributions lead to power laws, albeit
with “uninteresting” power $β=1$.

Exponential decay. In the simplest case of $m$ of the $θ_{i}$ being equal and
the rest being $0$, the error $\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}=(1-{\textstyle\frac{1}{m}})^{n}≈e^{-n/m}$ decays
exponentially with $n$. This is not too interesting to us, since (a) this case
corresponds to a finite model (see above), (b) exponential decay is an
“artifact” of the deterministic label and discontinuous 0-1 error, and (c)
will become a power law $1/n$ after time-averaging (Section 4).

Superposition of exponentials. Since (2) is invariant under bijective
renumbering of features $i∈ℕ$, we can w.l.g. assume $θ_{1}≥θ_{2}≥θ_{3}≥...$.
Some $θ$s may be equal. If we group equal $θ$s together into
$\bar{\bar{θ}}_{j}$ with multiplicity $m_{j}>0$ and define
$\bar{\bar{ϑ}}_{j}:=-\ln(1-\bar{\bar{θ}}_{j})$, then

$\displaystyle\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}~{}=~{}∑_{j=1}^{M}m_{j}\bar{\bar{θ}}_{j}e^{-n\bar{\bar{ϑ}}_{j}}$
(3)

where $M∈ℕ∪\\{∞\\}$ is the number of _different_ $θ_{i}>0$. This is a
superposition of exponentials in $n$ (note that
$∑_{j=1}^{M}m_{j}\bar{\bar{θ}}_{j}=1$) with different decay rates
$\bar{\bar{ϑ}}_{j}$. If different $\bar{\bar{θ}}_{j}$ have widely different
magnitudes and/or for suitable multiplicities $m_{j}$, the sum will be
dominated by different terms at different “times” $n$. So there will be
different phases of exponential decay, starting with fast decay
$e^{-n\bar{\bar{ϑ}}_{1}}$ for small $n$, taken over by slower decay
$e^{-n\bar{\bar{ϑ}}_{2}}$ for larger $n$, and $e^{-n\bar{\bar{ϑ}}_{3}}$ for
even larger $n$, etc. though some terms may never (exclusively) dominate, or
phases may be unidentifiably muddled together (see figure above). In any case,
if $M=∞$, the dominant terms shift indefinitely to ever smaller $θ$ for ever
larger $n$. For $M<∞$ eventually $e^{-n\bar{\bar{ϑ}}_{M}}$ for the smallest
$\bar{\bar{ϑ}}$ will dominate $\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$. The same
caveats (a)-(c) apply as for $M=1$ in the previous paragraph.

Approximations. First, in our subsequent analysis we (can) approximate
$(1-θ_{i})^{n}=:e^{-nϑ_{i}}≈e^{-nθ_{i}}$, justified as follows: (i) For
$nθ_{i}\ll 1$ this is an excellent approximation. (ii) For $θ_{i}\ll 1$,
$ϑ_{i}≈θ_{i}$, while numerically $e^{-nϑ_{i}}/e^{-nθ_{i}}\not≈1$ for
$nθ_{i}\gg 1$, but the exponential scaling of $e^{-nϑ_{i}}$ and $e^{-nθ_{i}}$
we care about is sufficiently similar. (iii) There can only be a finite number
of $θ_{i}\not\ll 1$, say, $θ_{i}$ for $i≤i_{0}$ are not small, then already
for moderately large $n\gg 1/θ_{i_{0}}$, all features $i≤i_{0}$ are observed
with high probability and hence do not contribute (much) to the expected error
(formally $e^{-nθ_{{}_{i}}}\ll 1$ for $i≤i_{0}$) hence can safely be ignored
in any asymptotic analysis.

Second, let $f:ℝ\textrightarrow ℝ$ be a smooth and monotone decreasing
interpolation of ${\bm{θ}}:ℕ\textrightarrow ℝ$, i.e. $f(i):=θ_{i}$ and
$f^{\prime}(x)≤0$. We can then approximate the error as follows:

$\displaystyle\text{\sf E$\\!\\!\\!\\!\;$E}_{n}~{}$
$\displaystyle=~{}∑_{i=1}^{∞}f(i)(1-f(i))^{n}~{}≈~{}\int_{1}^{∞}f(x)e^{-nf(x)}dx$
$\displaystyle=~{}\int_{0}^{θ_{1}}{ue^{-nu}du\over|f^{\prime}(f^{-1}(u))|}~{}\smash{\stackrel{{\scriptstyle×}}{{≈}}}~{}{1\over
n^{2}|f^{\prime}(f^{-1}({\textstyle\frac{1}{n}}))|}$ (4)

The first $≈$ uses the two approximations introduced above. The equality
follows from a reparametrization $u=f(x)$ and $f(1)=θ_{1}$ and $f(∞)=0$ and
$dx=du/f^{\prime}(x)$ and $f^{\prime}<0$. The numerator $ue^{-nu}$ is maximal
and (strongly) concentrated around $u=1/n$, hence $u≈1/n$ gives most of the
integral’s contribution. Therefore replacing $u$ by $1/n$ in the denominator
can be a reasonable approximation. The last $≈$ follows from this and
$∫_{0}^{θ_{1}}ue^{-nu}du≈∫_{0}^{∞}ue^{-nu}du=1/n^{2}$ for $nθ_{1}\gg 1$.

Intuitively, the expected error (2) is dominated by samples $i_{0}$ for which
$θ_{i_{0}}≈{\textstyle\frac{1}{n}}$. Estimating the number of such $i_{0}$
multiplied by $θ_{i_{0}}(1-θ_{i_{0}})^{n}≈θ_{i_{0}}e^{-1}$ leads to
approximation (3). In Appendix B we show that the approximation error of the
integral representation is bounded by $1/en+o(1/n)$.

Zipf-distributed data. Empirically many data have been observed to have a
power-law distribution, called Zipf distribution in this context, that is, for
a countable domain the frequency of the $i$th most frequent item is
approximately proportional to $i^{-(α+1)}$ for some $α>0$. In our model this
will be the case if $θ_{i}\propto i^{-(α+1)}$, so let $u=f(x)=α⋅x^{-(α+1)}$.
This implies $x=f^{-1}(u)=(u/α)^{-1/(1+α)}$ and
$f^{\prime}(x)=-α(α+1)x^{-(α+2)}=-α(α+1)(u/α)^{(α+2)/(α+1)}$, hence

$\displaystyle\text{\sf E$\\!\\!\\!\\!\;$E}_{n}~{}≈~{}{1\over
n^{2}|f^{\prime}(f^{-1}({\textstyle\frac{1}{n}}))|}~{}\smash{\stackrel{{\scriptstyle×}}{{=}}}~{}n^{-β},~{}~{}~{}\text{where}~{}~{}~{}β:={α\over
1+α}$

That is, Zipf-distributed data (with power $α+1$) lead to a power-law learning
curve (with power $β={α\over 1+α}<1$). The more accurate integral
representation leads to the same power law but with correct coefficient
$\text{\sf E$\\!\\!\\!\\!\;$E}_{n}≈c_{α}n^{-β}$ with
$c_{α}=α^{1/(α+1)}Γ({α\over 1+α})/(α+1)$.
$c_{1}={\textstyle\frac{1}{2}}\sqrt{\pi}~{}\dot{=}~{}0.886$ and
$c_{0.1}=1.177$ in excellent agreement with the fit curves in Figure 2.

Exponentially-distributed data. An exponential data distribution $θ_{i}\propto
e^{-γi}$ is more skewed than any power law. For $u=f(x)=γ⋅e^{-γx}$ we have
$x=f^{-1}(u)={\textstyle\frac{1}{γ}}\ln{\textstyle\frac{γ}{u}}$ and
$f^{\prime}(x)=-γ^{2}e^{-γx}=-γu$, hence both approximations in (3) give
$1/γn$. A rigorous upper bound $\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}≤({\textstyle\frac{1}{e}}+{\textstyle\frac{1}{γ}}){\textstyle\frac{1}{n}}$
follows from (11) in Appendix B, and a rigorous lower bound $\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}\smash{\stackrel{{\scriptstyle×}}{{≥}}}{\textstyle\frac{1}{n}}$
from the next paragraph. So even an exponential data distribution leads to a
power law learning curve, though the exponent $1$ is much larger than observed
in (most) experiments, which hints at that data are not exponentially
distributed, assuming this toy model has any real-world relevance.

Beyond exponentially-distributed data. For (quite unrealistic) decay faster
than exponentially, e.g. $θ_{i}\propto e^{-γi^{2}}$, the approximations (3)
are too crude, but somewhat surprisingly we _always_ get a (sort of) power law
as long as $θ_{i}>0$ for infinitely many $i$. First, the previous paragraph
implies that $\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}\smash{\stackrel{{\scriptstyle×}}{{≤}}}n^{-1}$ for any
$θ_{i}\smash{\stackrel{{\scriptstyle×}}{{≤}}}e^{-γi}$ for any $γ>0$, i.e. the
error decreases at least with $n^{-1}$ if the $i$th item has at most
exponentially small probability in $i$. For a (partial) converse, define
$n_{i}:=\lceil 1/ϑ_{i}\rceil≤1/ϑ_{i}+1$. Plugging $ϑ_{i}:=-\ln(1-θ_{i})≥θ_{i}$
and $2θ_{i}≥ϑ_{i}≥1/n_{i}$ for $θ_{i}<0.79$ into $\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}≥θ_{i}(1-θ_{i})^{n}=θ_{i}e^{-nϑ_{i}}$ we get

$\displaystyle\text{\sf
E$\\!\\!\\!\\!\;$E}_{n_{i}}~{}≥~{}θ_{i}e^{-n_{i}ϑ_{i}}~{}≥~{}{\textstyle\frac{1}{2n_{i}}}e^{-(1/ϑ_{i}+1)ϑ_{i}}~{}≥~{}{\textstyle\frac{1}{2n_{i}e^{2}}}~{}\smash{\stackrel{{\scriptstyle×}}{{=}}}~{}n_{i}^{-1}$

Hence, if $θ_{i}>0$ for infinitely many $i$, then there are infinitely many
$n$ for which $\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}\smash{\stackrel{{\scriptstyle×}}{{≥}}}n^{-1}$. For
$θ_{i}$ going to zero exponentially or slower, the spacing between $n_{i+1}$
and $n_{i}$ has bounded ratio $n_{i+1}/n_{i}≤e^{γ}$, which implies $\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}\smash{\stackrel{{\scriptstyle×}}{{≥}}}n^{-1}$ for all
$n$. For faster decaying $θ_{i}$, e.g. $θ_{i}=e^{-γi^{2}}$ this is no longer
the case. So in some weak sense, power law learning curves are universal, but
it’s mostly $1/n$, so not useful to explain observed power laws.

##  4 Learning Curve Variance

So far we have considered _expected_ learning curves. This corresponds to
averaging infinitely many experimental runs. In practice, only finitely many
runs are possible, sometimes as few as 5 or even 1. In the following we
consider the variance $\mathbb{V}_{n}$ of the instantaneous error $\text{\sf
E}_{n}=[\\![i_{n+1}\not\in i_{1:n}]\\!]$ as a function of $n$. The standard
error when averaging $k$ runs is then $\sqrt{\mathbb{V}_{n}/k}$. The question
we care most about here is whether (for large $n$) this is small or large
compared to $\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$, because this determines
whether learning curves (for small $k$) are smooth or look random, and how
large $k$ suffices for a good signal-to-noise ratio. We also consider time-
average expected learning curves and their variance, which are much smoother.
Note that cumulative errors are like attenuated drifting random walks, a
property time-average learning curves qualitatively inherit (red curve in
Figure 1 right).

Instantaneous Variance. $\text{\sf E}_{n}∈\\{0,1\\}$, hence $\text{\sf
E}_{n}^{2}=\text{\sf E}_{n}$, hence

$\displaystyle\mathbb{E}[\text{\sf E}_{n}^{2}]~{}$
$\displaystyle=~{}\mathbb{E}[\text{\sf
E}_{n}]~{}=~{}\sum_{i=1}^{∞}θ_{i}(1-θ_{i})^{n}~{}=:~{}μ_{n},~{}~{}~{}\text{hence}$
$\displaystyle\mathbb{V}[\text{\sf E}_{n}]~{}$
$\displaystyle=~{}\mathbb{E}[\text{\sf E}_{n}^{2}]-\mathbb{E}[\text{\sf
E}_{n}]^{2}~{}=~{}μ_{n}(1-μ_{n})$

Since $μ_{n}\textrightarrow 0$ for $n\textrightarrow∞$, the standard deviation

$\displaystyle σ_{n}~{}:=~{}\sqrt{\mathbb{V}[\text{\sf
E}_{n}]}~{}=~{}\sqrt{μ_{n}(1-μ_{n})}~{}≈~{}\sqrt{μ_{n}}~{}~{}\gg~{}~{}μ_{n}~{}=~{}\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}$

That is, the standard deviation is much larger than then mean for large $n$.
Indeed, for a single run, there is no proper learning _curve_ at all, since
$\text{\sf E}_{n}∈\\{0,1\\}$ (see Figures 4&5 top left). In order to get a
good signal-to-noise ratio one would need to average a large (and indeed
increasing with $n$) number $k\gg 1/μ_{n}$ of runs (see Figures 1&4&5).

Time-averaged Mean and Variance. In practice, beyond averaging over runs,
other averages are performed to reduce noise.One alternative is to report the
time-averaged error $\overline{\text{\sf E}}$, rather than the instantaneous
error E. We can calculate its mean and variance as follows

$\displaystyle\overline{\text{\sf E}}_{N}~{}:$ $\displaystyle=~{}{1\over
N}\sum_{n=0}^{N-1}\text{\sf E}_{n}$ (5)
$\displaystyle\mathbb{E}[\overline{\text{\sf E}}_{N}]~{}$
$\displaystyle=~{}{1\over N}\sum_{n=0}^{N-1}\mathbb{E}[\text{\sf
E}_{n}]~{}=~{}{1\over
N}\sum_{i=1}^{∞}θ_{i}\sum_{n=0}^{N-1}(1-θ_{i})^{n}~{}\stackrel{{\scriptstyle(a)}}{{=}}~{}{1\over
N}\sum_{i=1}^{∞}1-(1-θ_{i})^{N}$ (6)
$\displaystyle\mathbb{E}[\overline{\text{\sf E}}_{N}^{2}]~{}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}~{}{1\over
N^{2}}\sum_{i=1}^{∞}[1-(1-θ_{i})^{N}]~{}+~{}{1\over
N^{2}}\sum_{i≠j}[1-(1-θ_{i})^{N}-(1-θ_{j})^{N}+(1-θ_{i}-θ_{j})^{N}]$
$\displaystyle\mathbb{V}[\overline{\text{\sf E}}_{N}]~{}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}~{}{1\over
N^{2}}\sum_{i=1}^{∞}(1-θ_{i})^{N}[1-(1-θ_{i})^{N}]~{}-~{}{1\over
N^{2}}\sum_{i≠j}[(1-θ_{i})^{N}(1-θ_{j})^{N}-(1-θ_{i}-θ_{j})^{N}]$ (7)

where $(a)$ is simple algebra, $(b)$ follows from inserting the definition of
$\overline{\text{\sf E}}_{N}$ and some rather tedious algebraic manipulations
(see Appendix B), and $(c)$ from inserting $(a)$ and $(b)$ into the definition
of variance and simple algebraic manipulation. We now revisit the exponential
and Zipf case studied earlier, after a trivial but note-worthy observation.

Case $θ_{i}=[\\![i=1]\\!]$. In this case $i_{n}=1~{}∀n$, hence $\text{\sf
E}_{0}=1$ and $\text{\sf E}_{n}=0~{}∀n≥1$ and $\mathbb{V}[\text{\sf
E}_{n}]=0~{}∀n$. This is the fastest any error can decay, $0$ after $1$
observation, hence the fastest any time-averaged error can decay is
$\overline{\text{\sf E}}_{N}=1/N$. This means, for any learning problem that
has instantaneous error decaying faster than $1/N$, one should report the
instantaneous error rather than the slower decaying and hence much larger
time-averaged error. Most problems of interest in Deep Learning have much
slower learning curves though, and for those, the time-averaged and the
instantaneous error have the _same_ decay rate, but the time-averaged has
lower variance, so is the preferred one to plot or report.

Case $θ_{i}={\textstyle\frac{1}{m}}[\\![i≤m]\\!]$. In this case, while
$\text{\sf E$\\!\\!\\!\\!\;$E}_{n}=(1-{\textstyle\frac{1}{m}})^{n}≈e^{-n/m}$
decays exponentially, the average quantities decay with $1/N$ (or $1/N^{2}$):

$\displaystyle\mathbb{E}[\overline{\text{\sf E}}_{N}]~{}$
$\displaystyle=~{}{\textstyle\frac{m}{N}}[1-(1-{\textstyle\frac{1}{m}})^{N}]~{}\longrightarrow~{}{\textstyle\frac{m}{N}}~{}~{}~{}\text{for}~{}~{}~{}N\textrightarrow∞$
$\displaystyle\mathbb{V}[\overline{\text{\sf E}}_{N}]~{}$
$\displaystyle=~{}{\textstyle\frac{m^{2}}{N^{2}}}[{\textstyle\frac{1}{m}}(1-{\textstyle\frac{1}{m}})^{N}+(1-{\textstyle\frac{1}{m}})(1-{\textstyle\frac{2}{m}})^{N}-(1-{\textstyle\frac{1}{m}})^{2N}]$
$\displaystyle\textrightarrow~{}{\textstyle\frac{m}{N^{2}}}[e^{-N/m}-e^{-2N/m}]~{}\textrightarrow~{}{\textstyle\frac{m}{N^{2}}}e^{-N/m}~{}~{}~{}\text{for}~{}~{}~{}N\textrightarrow∞$
$\displaystyle σ[\overline{\text{\sf E}}_{N}]~{}$
$\displaystyle≈~{}{\textstyle\frac{\sqrt{m}}{N}}e^{-N/2m}~{}~{}\ll~{}~{}{\textstyle\frac{m}{N}}~{}≈~{}\mathbb{E}[\overline{\text{\sf
E}}_{N}]~{}~{}~{}\text{for}~{}~{}~{}N\gg m$

The expressions for the mean and variance follow from the general expression
(6) and (7) above, by inserting $θ_{i}={\textstyle\frac{1}{m}}$ for $i≤m$ and
noting that $i>m$, for which $θ_{i}=0$, give no contribution, hence $∑_{i}1=m$
and $∑_{i≠j}1=m(m-1)$, and rearranging terms. The conclusion most interesting
to us is that the standard deviation is (much) smaller than the mean for $N$
(much) larger than $m$, so the time-averaged learning curves have a much
better signal-to-noise ratio; see Figure 1. Also $σ[\overline{\text{\sf
E}}_{N}]≈N^{-1/2}\ll 1≈\mathbb{E}[\overline{\text{\sf E}}_{N}]$ for $m\gg N$.
The intuition is easy: For $m\gg N$, at ever $n<N$, a new $i_{n+1}$ is
observed, i.e. $\text{\sf E}_{n}=1$ w.h.p. For $N\gg m$, all $m$ errors have
been made, i.e. $\overline{\text{\sf E}}_{N}={\textstyle\frac{m}{N}}$ w.h.p,
i.e. in both cases the variance is small. Only for $m≈N$ is there sizeable
uncertainty in $\text{\sf E}_{N}$. The situation is similar for the most
interesting Zipf case:

Case $θ_{i}\propto i^{-(α+1)}$. Recall that for Zipf-distribution
$θ_{i}\propto i^{-(α+1)}$, the expected error followed power law $\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}≈c_{α}n^{-β}$, where $0<β={α\over 1+α}<1$. The time-
averaged error

$\displaystyle\mathbb{E}[\overline{\text{\sf E}}_{N}]~{}≈~{}{1\over
N}\sum_{n=1}^{N}\mathbb{E}[\text{\sf E}_{n}]~{}≈~{}{c_{α}\over
N}\int_{0}^{N}n^{-β}dn~{}=~{}c^{\prime}_{α}N^{-β}~{}~{}~{}\text{with}~{}~{}~{}c^{\prime}_{α}:=\frac{c_{α}}{1-β}=α^{\frac{1}{1+α}}Γ({\textstyle\frac{α}{1+α}})$

follows the same power law with the emphsame exponent $β$, which is a generic
property as foreshadowed earlier. As for the variance, we show in Appendix B
that

$\displaystyle\mathbb{E}[\overline{\text{\sf E}}_{N}^{2}]~{}$
$\displaystyle\smash{\stackrel{{\scriptstyle×}}{{≈}}}~{}\mathbb{E}[\overline{\text{\sf
E}}_{N}]^{2},~{}~{}~{}~{}~{}\mathbb{V}[\overline{\text{\sf
E}}_{N}]~{}\smash{\stackrel{{\scriptstyle×}}{{≈}}}~{}~{}N^{-{1+2α\over
1+α}},~{}~{}~{}\text{hence}$ $\displaystyle σ[\overline{\text{\sf E}}_{N}]~{}$
$\displaystyle\smash{\stackrel{{\scriptstyle×}}{{≈}}}~{}N^{-{1/2+α\over
1+α}}~{}~{}\ll~{}~{}N^{-{α\over
1+α}}~{}\smash{\stackrel{{\scriptstyle×}}{{≈}}}~{}\mathbb{E}[\overline{\text{\sf
E}}_{N}]$ $\displaystyle\text{In particular, the signal-to-noise ratio
is}~{}~{}{σ[\overline{\text{\sf E}}_{N}]\over\mathbb{E}[\overline{\text{\sf
E}}_{N}]}~{}\smash{\stackrel{{\scriptstyle×}}{{≈}}}~{}N^{-1/(2+2α)}$

That is, the standard deviation is much smaller than then mean. A single run
suffices to get a good (and excellent for $n\gtrsim 500$) signal-to-noise
ratio for the averaged and cumulative error (see Figures 2&3&6 (right) and
Figures 4&5 (top left)). Still, the infinite Zipf model leads to a more noisy
learning curve than the finite uniform model. Intuitively, for every $N$, new
$i_{N+1}\not\in i_{1:N}$ have small but sufficient chance, contributing to the
error and variance, decreasing exponentially in the uniform model, but only as
a power law in the Zipf model.

General ${\bm{θ}}$ Case. One can show that the signal-to-noise ratio for the
time-averaged error improves with $N$ in general for any choice of ${\bm{θ}}$.
First note that the argument of $∑_{i≠j}[...]$ in (7) is non-negative, hence
the variance is upper-bounded by the first $∑_{i}$. Using
$1-(1-θ_{i})^{N}≤θ_{i}N$, we get $\mathbb{V}[\overline{\text{\sf
E}}_{N}]≤{\textstyle\frac{1}{N}}\text{\sf E$\\!\\!\\!\\!\;$E}_{N}$, so the

$\displaystyle\text{signal-to-noise ratio is}~{}~{}~{}{σ[\overline{\text{\sf
E}}_{N}]\over\mathbb{E}[\overline{\text{\sf
E}}_{N}]}~{}≤~{}{\sqrt{\smash{{\textstyle\frac{1}{N}}}\text{\sf
E$\\!\\!\\!\\!\;$E}_{N}}\over\mathbb{E}[\overline{\text{\sf
E}}_{N}]}~{}=~{}{\sqrt{N\smash{\text{\sf
E$\\!\\!\\!\\!\;$E}_{N}}}\over\sum_{n=0}^{N-1}\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}}~{}\textrightarrow~{}0~{}~{}\text{for}~{}~{}N\textrightarrow∞$

To prove the limit $\textrightarrow 0$ we have to distinguish two cases: First
note that $\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$ is monotone decreasing
($\text{\sf E$\\!\\!\\!\\!\;$E}_{n}\\!\\!\\!\searrow$). (i) For bounded total
error $∑_{n=0}^{∞}\text{\sf E$\\!\\!\\!\\!\;$E}_{n}≤c$ (e.g. exponential error
decay in finite models), $\text{\sf E$\\!\\!\\!\\!\;$E}_{n}\\!\\!\\!\searrow$
implies $\text{\sf E$\\!\\!\\!\\!\;$E}_{N}=o(1/N)$, which implies that the
numerator tends to 0; the denominator is lower-bound by $\text{\sf
E$\\!\\!\\!\\!\;$E}_{0}=1$. (ii) For unbounded total error
$∑_{n=0}^{N-1}\text{\sf E$\\!\\!\\!\\!\;$E}_{n}\textrightarrow∞$ (most
infinite models, e.g. Zipf and even exponential $θ_{i}$), we factor the
denominator as $\sum_{n=0}^{N-1}\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}≡\sqrt{\smash{Σ_{n=0}^{N-1}}\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}}⋅\sqrt{\smash{Σ_{n=0}^{N-1}}\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}}$ and lower-bound one term by
$\sum_{n=0}^{N-1}\text{\sf E$\\!\\!\\!\\!\;$E}_{n}≥N\text{\sf
E$\\!\\!\\!\\!\;$E}_{N}$, which is true since $\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}\\!\\!\\!\searrow$.

##  5 Experiments

Figure 1: (Learning Curves) _(left)_ for uniform data distribution
$\mathbb{P}[i_{n}=i]=θ_{i}={\textstyle\frac{1}{m}}$ for $i≤m=10$ averaged over
$k=100$ runs. _(right)_ for Zipf-distributed data
$\mathbb{P}[i_{n}=i]=θ_{i}\propto i^{-(α+1)}$ for $α=1$ averaged over $k=10$
runs. See Figures 4 and 5 for more plots for $k=1,10,100,1000$.

Figure 2: (Power Law fit to Zipf-Distributed Data) for Zipf-distributed data
$\mathbb{P}[i_{n}=i]=θ_{i}\propto i^{-(α+1)}$ for $α=1$ _(left)_ and $α=0.1$
_(right)_ ; averaged over infinitely many runs (dots), for fitted $\hat{β}$
(solid) and theoretical $β={\textstyle\frac{α}{1+α}}$ (dash), and empirical
error for a single run ($k=1$, dashdot).

Figure 3: (Word-Frequency in Text File, Learning Curve, Power Law) _(left)_
Log-linear plot of the relative (left scale) and absolute (right scale)
frequency of words in the first 20469 words in file ‘book1’ of the Calgary
Corpus, and fitted Zipf law. _(right)_ Power law fit to learning curve for
this data set for a word classification task.

We performed some control experiments to verify the correctness of the theory
and claims, and the accuracy of the theoretical expressions.

Uniform and Zipf-distributed data. Figures 1 and4 plot learning curves for
uniformly distributed data $\mathbb{P}[i_{n}=i]=θ_{i}={\textstyle\frac{1}{m}}$
for $i≤m=10$ averaged over $k=1,10,100,1000$ runs. Figure 1 and 5 plot
learning curves for Zipf-distributed data $\mathbb{P}[i_{n}=i]=θ_{i}\propto
i^{-(α+1)}$ for $α=1$, also averaged over $k=1,10,100,1000$ runs. In both
cases, 1000 synthetic data sets ${\cal D}_{50}$ have been generated, and the
average is taken over $k$ of them. Various errors are plotted as functions of
the sample index/size $n$. The crosses are the instantaneous errors $\text{\sf
E}_{n}$ averaged over $k$ runs. The black curves are the exact expected
instantaneous error $\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$. The shaded regions
are 1 standard deviation $σ_{n}/\sqrt{k}$ from the theory (not empirical).
Similarly the blue dots, lines, and shadings are the time-averaged errors
$\overline{\text{\sf E}}_{N}$, their exact expectation
$\mathbb{E}[\overline{\text{\sf E}}_{N}]$ and theoretical standard error
$\sqrt{\mathbb{V}[\smash{\overline{\text{\sf E}}_{N}}]/k}$. The red triangles,
lines, and shadings are the empirical cumulative errors $∑_{n=0}^{N}\text{\sf
E}[n]≡N\overline{\text{\sf E}}_{N}$, their exact expectation
$∑_{n=0}^{N}\text{\sf E$\\!\\!\\!\\!\;$E}[n]≡N\mathbb{E}[\overline{\text{\sf
E}}_{N}]$, and theoretical standard error. The dashed lines connecting the
empirical errors are for better visibility (only).

Fitting power laws to learning curves. We now fit power laws to the learning
curves of (exactly) Zipf distributed data. Figure 2 shows fits for synthetic
data with Zipf-exponents $α=1$ and $α=0.1$. The fit is “perfect” except for
very small values of $n$. This is consistent with our approximation, which is
good for $nθ_{1}\gg 1$. Theoretically we expect and empirically we found the
approximation (3) to be good for $nθ_{1}\gtrsim 2$. For $α=1$ we have
$θ_{1}=0.5$, hence the approximation should be good for $n\gtrsim 4$, while
for $α=0.1$ we have $θ_{1}~{}\dot{=}~{}0.067$, hence the approximation should
be good for $n\gtrsim 30$; both are consistent with the plots. To avoid
clutter we only present expected curves. They perfectly match the averaged
curves over infinitely many runs anyway (see Figures 1&5). The fitted power
law exponents $\hat{β}$ are also close to the theoretical predictions
$β={\textstyle\frac{α}{1+α}}$ (${\textstyle\frac{1}{2}}=0.5$ for $α=1$ and
${\textstyle\frac{1}{11}}~{}\dot{=}~{}0.091$ for $α=0.1$).

Text data. It is well-known that the frequency of a word in typical texts is
about inversely proportional to its rank in the frequency table: The most
frequent word (‘the’) occurs about twice as often as the second most frequent
word (‘a’), about three times as often as the third most frequent word, and so
on. That is, word frequency follows a Zipf distribution with $α≈0$. Figures
3&6 (left) show the frequency distributions of the first 20469 words in file
‘book1’ of the Calgary Corpus. Apart from the steps, caused by word
frequencies being integers, the distribution is very close to Zipf. Note that
more than half of the words only appear once. Figures 3 (right) shows the
learning curves for any word classification task. The power-law fit is
reasonably good, but not perfect. The reason is the step structure of
especially rare words. Indeed, many $θ$s are equal, and only finitely many are
non-zero, so the learning curve is a finite superposition of exponentials as
in (3). For moderate $n$ this mixture amalgamates to an approximately power
law. For large $n$, the error decays exponentially as $\exp(-θ_{min}n)$.
Indeed, for larger $n$, Figures 6 shows that the power fit becomes worse, and
the true error decays faster than the fit power law. Note that for $α≤0$,
$i^{-(α+1)}$ is not summable, hence _any_ such distribution must break down
after some $i$, our approximation becomes invalid, and $β≤0$ makes no sense in
any case.

##  6 Extensions

In the following we discuss some potential extensions of the toy model. Some
look feasible, others are hard or wishful thinking. We discuss the more
realistic case of noisy labels, other loss functions, continuous features, and
more realistic models that generalize, e.g. deep learning algorithms.

Noisy labels. In most machine learning applications, labels (or more general
targets) are themselves noisy, not just the feature vector $x∈{\cal X}$, e.g.
$y=h(x)+$Noise. The major implications are as follows:

  * (a)

The learning algorithms need to be a bit smarter than just memorization,
e.g. predicting the average or by majority.

  * (b)

Due to the label noise, the error cannot converge to $0$ anymore but to the
intrinsic “entropy”, which should be subtracted before studying scaling.

  * (c)

For absolute (locally quadratic) loss there will be an extra $n^{-1/2}$
($n^{-1}$) additive error term due to parameter estimation error, hence

  * (d)

the instantaneous loss will not decay exponentially anymore even if the model
is finite.

  * (e)

Otherwise the scaling laws for Zipf data are _unchanged_.

In summary, the error/loss should be a sum of 3 terms, at least conceptually:

  * (1)

The inherent entropy in the data,

  * (2)

the parameter learning rate $n^{-1/2}$ for absolute loss, squared, i.e.
$n^{-1}$ for (locally) quadratic loss,

  * (3)

the same power law $n^{-β}$ as in the deterministic case.

In Appendix C we verify claims (b,c,d,e) for our toy model extended to noisy
binary classification for square loss. What is remarkable is that the
_instantaneous_ square loss $\text{\sf Loss}_{n}(A)$ for noisy labels turns
out to include a term proportional to the _time-averaged_ (0-1) error
$\mathbb{E}[\overline{\text{\sf E}}_{n}]=$(6) in the deterministic case. But
this “magically” ensures (c,d,e), since $\mathbb{E}[\overline{\text{\sf
E}}_{n}]\smash{\stackrel{{\scriptstyle×}}{{≈}}}\max\\{\text{\sf
E$\\!\\!\\!\\!\;$E}_{n},{\textstyle\frac{1}{n}}\\}$, at least for the choices
of ${\bm{θ}}$ discussed in Section 3. For instance, for a finite model,
$\text{\sf
Loss}_{n}(A)\smash{\stackrel{{\scriptstyle×}}{{≈}}}\mathbb{E}[\overline{\text{\sf
E}}_{n}]\smash{\stackrel{{\scriptstyle×}}{{≈}}}{\textstyle\frac{1}{n}}$.

Other loss functions. For our deterministic toy model, the loss function has
little to no influence on the results as discussed in Appendix A. For noisy
labels, this also seems to be the case, except that $n^{-β_{0}}$ is now the
fastest possible decay, with $β_{0}$ _depending_ on the loss-function:
$β_{0}={\textstyle\frac{1}{2}}$ for absolute loss and $β_{0}=1$ for locally
quadratic loss such as KL and square. Loss functions with any (other) value of
$β_{0}>0$ are possible but rare. This is another potential universality of
scaling laws, their independence from the loss function for large models.

Continuous features. Countable feature spaces have some applications, e.g. in
NLP, words can be identified with integer features $i∈ℕ$. In most
applications, feature spaces are (effectively) continuous, often vector spaces
$ℝ^{d}$, and no feature ever repeats exactly ($x_{n}≠x_{m}$ for $n≠m$). A
simple model with a continuous domain is the Dirichlet Process, or the
essentially equivalent Chinese Restaurant Process (CRP) and Stick-Breaking
process. In the CRP, the continuous domain is essentially reduced to an
exponentially distributed countable number of sticks=features, leading to
power law learning curves $n^{-β}$, but the exponent is restricted to $β=1$,
which is too limiting. But even the CRP is not exactly a special case of our
toy model and much harder to analyse. In some form of “mean-field”
approximation it reduces to a special case of our model. The generalized
2-parameter Poison Dirichlet Process [BH10] also only leads to $β=1$. Finding
analytically tractable models with continuous features that exhibit
interesting learning curves remains an open problem.

Generalizing algorithms. Proper models/algorithms for continuous features need
to generalize from observed inputs to similar future not-yet-observed inputs,
which is at the heart of virtually all interesting machine learning
model/algorithms. Such models are much more varied and harder to analyze. If
the domain could be partitioned into countably many cells, each cell
containing only sufficiently similar features, and this can be done a-priori
and is fixed independent of the actually realized data ${\cal D}_{n}$ and most
importantly independent of the data size $n$, we arrive back at our countable
toy model (usually with noisy labels) and our analysis (nearly) applies. But
it is more plausible that a suitable partitioning, e.g. clustering of data, is
in itself data (size) dependent, and hence will affect the scaling. A more
interesting non-parametric model, potentially amenable to theoretical
analysis, is $k$-Nearest-Neighbors (kNN), likely with interesting learning
curves. The ‘perfect prediction for exact repetition’ in our toy model can be
viewed as an abstraction of ‘classify features in the same cell alike’ which
itself is a toy model for ‘classify similar observations alike or similarly’,
so maybe some of our findings or analysis tools approximately transfer.

Deep learning. (Deep) neural networks are a particularly powerful class of
models/algorithms that can generalize, but are also notoriously difficult to
theoretically analyse. It may be a long way from our toy model to a similar
analysis of NNs. Furthermore we have not at all considered the equally
interesting questions of scaling with model size and compute.

##  7 Discussion

Summary. We introduced a very simple model that can exhibit power laws
(decrease of error with data size) consistent with recent findings in deep
learning. The model is plausibly the simplest such model, and that choice was
deliberate to not get bogged down with intractable math or forced into crude
approximations or bounds at this early stage of investigation. Many but not
all data distributions lead to power laws. We do not know whether the
discovered specific relation between the Zipf exponent $α$ and the power law
exponent $β=α/(1+α)$ is an artifact of the model, or has wider validity beyond
this model. The signal-to-noise ratio for the time-averaged error tend to
zero, which implies that a single experimental run suffices for stable
results.

Limitations. The toy model studied in this work is admittedly totally
unrealistic as a Deep Learning model, but we believe it captures the (or at
least a) true reason for the observed scaling laws w.r.t. data. Whether it has
any predictive power, or can be generalized to NNs and/or scaling laws for
model size and/or compute, is beyond the scope of this paper. We hope that
this initial investigation spurs more advanced theoretical investigations, and
ultimately lead to predictive models. We have outlined some ideas in Section
6, some (more) are hopefully feasible. In any case, finding the simplest model
which captures the essence is a necessary first step, and we believe our toy
model fits this bill.

Applications. Besides providing scientific insight, a good theoretical
understanding of scaling laws could ultimately help tune network and algorithm
parameters in a more principled way, and thus save significant compute for
finding good large NNs by reducing hyper-parameter sweeps. The cost of
training recent models has reached millions of dollars and can exhaust and
exceed even FAANGs computational resources.

Acknowledgements. I thank David Budden and Jörg Bornschein for encouraging me
to look into the topic of scaling laws, and for interesting discussions.

## References

##

  * [BH10] Wray Buntine and Marcus Hutter.  A Bayesian review of the Poisson-Dirichlet process.  Technical Report arXiv:1007.0296, NICTA and ANU, Australia, 2010.
  * [BHM18] Mikhail Belkin, Daniel Hsu, and Partha Mitra.  Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate.  arXiv:1806.05161 [cond-mat, stat], June 2018.
  * [BHMM19] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal.  Reconciling modern machine-learning practice and the classical bias–variance trade-off.  Proceedings of the National Academy of Sciences, 116(32):15849–15854, August 2019.
  * [Bub15] Sébastien Bubeck.  Convex Optimization: Algorithms and Complexity.  Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015.
  * [Cha81] Anne Chao.  On Estimating the Probability of Discovering a New Species.  Annals of Statistics, 9(6):1339–1342, November 1981.
  * [Cho20] Kyunghyun Cho.  Scaling laws of recovering Bernoulli, November 2020.  Blog Post http://kyunghyuncho.me/scaling-law-of-estimating-bernoulli/.
  * [DHM89] Ronald A. DeVore, Ralph Howard, and Charles Micchelli.  Optimal nonlinear approximation.  manuscripta mathematica, 63(4):469–478, December 1989.
  * [Haz16] Elad Hazan.  Introduction to Online Convex Optimization.  2016\.
  * [HKHM21] Danny Hernandez, Jared Kaplan, Tom Henighan, and Sam McCandlish.  Scaling Laws for Transfer.  arXiv:2102.01293 [cs], February 2021.
  * [HKK+20] Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B. Brown, Prafulla Dhariwal, Scott Gray, Chris Hallacy, Benjamin Mann, Alec Radford, Aditya Ramesh, Nick Ryder, Daniel M. Ziegler, John Schulman, Dario Amodei, and Sam McCandlish.  Scaling Laws for Autoregressive Generative Modeling.  arXiv:2010.14701 [cs], November 2020.
  * [HNA+17] Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou.  Deep Learning Scaling is Predictable, Empirically.  arXiv:1712.00409 [cs, stat], December 2017.
  * [KMH+20] 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.  arXiv:2001.08361 [cs, stat], January 2020.
  * [Mha96] H. N. Mhaskar.  Neural Networks for Optimal Approximation of Smooth and Analytic Functions.  Neural Computation, 8(1):164–177, January 1996.
  * [Pin99] Allan Pinkus.  Approximation theory of the MLP model in neural networks.  Acta Numerica, 8:143–195, January 1999.
  * [RRBS19] Jonathan S. Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit.  A Constructive Prediction of the Generalization Error Across Scales.  In International Conference on Learning Representations, September 2019.
  * [SK20] Utkarsh Sharma and Jared Kaplan.  A Neural Scaling Law from the Dimension of the Data Manifold.  arXiv:2004.10802 [cs, stat], April 2020.

##  Appendix A Other Loss Functions

We can (slightly) generalize the learning algorithm $A$ to other loss
functions and behaviors on $i_{n+1}\not\in i_{1:n}$. We continue to assume
that $A^{\prime}$ suffers $\text{\sf Loss}_{n}=0$ if $i∈i_{1:n}$ by using
stored ${\cal D}_{n}$. Assume $A^{\prime}$ suffers $\text{\sf Loss}_{n}$ if
$i_{n+1}\not\in i_{1:n}$, then

$\displaystyle\mathbb{E}[\text{\sf Loss}_{n}]~{}$
$\displaystyle=~{}\mathbb{E}[\text{\sf Loss}_{n}|i_{n+1}\not\in
i_{1:n}]⋅\mathbb{P}[i_{n+1}\not\in
i_{1:n}]+0⋅\mathbb{P}[i∈i_{1:n}]~{}=~{}\mathbb{E}[\text{\sf
Loss}_{n}|i_{n+1}\not\in i_{1:n}]⋅\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$

The second factor is our primary object of study. The first factor is often
constant or bounded by constants: For instance for $A$ in (1), $\text{\sf
Loss}_{n}=1$ if $i_{n+1}\not\in i_{1:n}$, hence $\mathbb{E}[\text{\sf
Loss}_{n}]=\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$. Assume a classification problem
with $K$ labels ${\cal Y}=\\{0,...,K-1\\}$, and modify $A$ to randomize its
output (samples $y∈{\cal Y}$ uniformly) if $i_{n+1}\not\in i_{1:n}$, then
there is a $1/K$ chance to accidentally predict the correct label, hence
$\mathbb{E}[\text{\sf Loss}_{n}|i_{n+1}\not\in i_{1:n}]=1-1/K$, where the
expectation is now also w.r.t. the algorithm’s randomness. For continuous
${\cal Y}$ and if $A^{\prime}$ samples $y$ from any (non-atomic) density over
${\cal Y}$ if $i_{n+1}\not\in i_{1:n}$, the probability of accidentally
correctly predicting $y_{n+1}$ is $0$, hence $\mathbb{E}[\text{\sf
Loss}_{n}]=\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$. For binary classification
($K=2$) we could also let $A^{\prime}$ predict $y={\textstyle\frac{1}{2}}$ and
use absolute loss $\text{\sf Loss}_{n}=|y-y_{n+1}|$, in which case
$\mathbb{E}[\text{\sf Loss}_{n}|i_{n+1}\not\in
i_{1:n}]={\textstyle\frac{1}{2}}$. If $A^{\prime}$ instead samples $y$
uniformly from $[0;1]$, then $\mathbb{E}[\text{\sf Loss}_{n}|i_{n+1}\not\in
i_{1:n}]=∫_{0}^{1}|y-y_{n+1}|dy={\textstyle\frac{1}{4}}$. If ${\cal Y}=[0;1]$,
then $\mathbb{E}[\text{\sf Loss}_{n}|i_{n+1}\not\in
i_{1:n}]=∫_{0}^{1}|y-y_{n+1}|dy={\textstyle\frac{1}{4}}+({\textstyle\frac{1}{2}}-y_{n+1})^{2}$,
hence ${\textstyle\frac{1}{4}}\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}≤\mathbb{E}[\text{\sf
Loss}_{n}]≤{\textstyle\frac{1}{2}}\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$.

More generally, for any compact and uniformly rounded set ${\cal Y}⊆ℝ^{d}$,
for any loss of the form $\text{\sf Loss}_{n}:=\ell(||y-y_{n+1}||)$, for any
norm $||⋅||$, for any continuous strictly increasing $\ell≥0$, and
$A^{\prime}$ sampling $y$ from any density $p_{alg}(y)>0$ over ${\cal Y}$ if
$i_{n+1}\not\in i_{1:n}$, we have, for some constants $c_{1},c_{2}>0$,

$\displaystyle c_{1}\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}~{}≤~{}\mathbb{E}[\text{\sf
Loss}_{n}]~{}≤~{}c_{2}\text{\sf E$\\!\\!\\!\\!\;$E}_{n},~{}~{}~{}$
$\displaystyle\text{or}~{}~{}~{}\mathbb{E}[\text{\sf
Loss}_{n}]~{}\smash{\stackrel{{\scriptstyle×}}{{=}}}~{}\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}~{}~{}\text{for short}$

and this fact holds even more generally. Since a multiplicative constant in
the loss is irrelevant from a scaling perspective, all scaling results for
$\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$ also apply to this (slightly) more general
setting.

The proof of this is as follows: A uniformly rounded set by definition can be
represented as a union of $ε$-balls for some fixed $ε>0$, i.e. ${\cal
Y}=\bigcup_{\tilde{y}∈\tilde{\cal Y}}B_{ε}(\tilde{y})$ for some $\tilde{\cal
Y}$, where $B_{ε}(\tilde{y}):=\\{y:||y-\tilde{y}||≤ε\\}$. Then

$\displaystyle\mathbb{E}[\text{\sf Loss}_{n}|i_{n+1}\not\in i_{1:n}]~{}$
$\displaystyle=~{}∫_{\cal Y}\ell(||y-y_{n+1}||)p_{alg}(y)dy$ (8)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{≥}}~{}δ∫_{B_{ε}(\tilde{y})}\ell(||y-y_{n+1}||)dy$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{≥}}~{}δ∫_{B_{ε}(y_{n+1})}\ell(||y-y_{n+1}||)dy$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}~{}δ∫_{B_{ε}(0)}\ell(||z||)dz~{}=:~{}c_{1}~{}\stackrel{{\scriptstyle(d)}}{{>}}~{}0$

In (a), $\tilde{y}∈\tilde{\cal Y}$ is chosen such that
$y_{n+1}∈B_{ε}(\tilde{y})⊆{\cal Y}$, and $p_{alg}>δ>0$, since $p_{alg}>0$ and
${\cal Y}$ is compact. In (b), $B_{ε}(y_{n+1})$ can be obtained from
$B_{ε}(\tilde{y})$ by cutting out the moon $B_{ε}(\tilde{y})\setminus
B_{ε}(y_{n+1})$, and point-mirroring the moon at
${\textstyle\frac{1}{2}}(\tilde{y}+y_{n+1})$. The flip brings every point
closer to $y_{n+1}$, hence decreases the integral since $\ell$ is monotone
increasing. (c) just recenters the integral, which now is obviously
independent of $y_{n+1}$. It is non-zero (d), since $\ell$ is strictly
increasing. Since $\ell$ is continuous and ${\cal Y}$ is compact, $\ell$ is
upper bounded by $\ell_{max}<∞$. This immediately implies (8) is upper bounded
by $c_{2}:=\ell_{max}<∞$.

##  Appendix B Derivation of Expectation and Variance

Expectation. Recall the error of (the basic form of) Algorithm $A$ is
$\text{\sf E}_{n}=[\\![i_{n+1}\not\in i_{1:n}]\\!]$. Hence the probability
that Algorithm $A$ makes an error under distribution ${\bm{θ}}$ given data
${\cal D}_{n}$ is

$\displaystyle\mathbb{E}[\text{\sf E}_{n}|{\cal
D}_{n}]~{}=~{}\mathbb{P}[A(i_{n+1},{\cal D}_{n})≠y_{n+1}|{\cal
D}_{n}]~{}=~{}∑_{i\not\in i_{1:n}}\mathbb{P}[i_{n+1}=i]~{}=~{}∑_{i\not\in
i_{1:n}}θ_{i}$ (9)

The expectaion of this w.r.t. ${\cal D}_{n}$ is

$\displaystyle\text{\sf E$\\!\\!\\!\\!\;$E}_{n}~{}$
$\displaystyle:=~{}\mathbb{E}[\text{\sf
E}_{n}]~{}=~{}\mathbb{E}[\mathbb{E}[\text{\sf E}_{n}|{\cal
D}_{n}]]~{}=~{}∑_{i_{1:n}}\mathbb{P}[A(i_{n+1},{\cal D}_{n})≠y_{n+1}|{\cal
D}_{n}]\mathbb{P}[{\cal D}_{n}]$
$\displaystyle=~{}∑_{i_{1:n}}\Big{(}∑_{i\not\in
i_{1:n}}θ_{i}\Big{)}∏_{t=1}^{n}θ_{i_{t}}~{}=~{}∑_{i_{1:n}}\Big{(}∑_{i=1}^{∞}[\\![i≠i_{1}∧...∧i≠i_{n}]\\!]θ_{i}\Big{)}∏_{t=1}^{n}θ_{i_{t}}$
$\displaystyle=~{}∑_{i=1}^{∞}θ_{i}∑_{i_{1:n}}∏_{t=1}^{n}[\\![i≠i_{t}]\\!]θ_{i_{t}}~{}=~{}∑_{i=1}^{∞}θ_{i}∏_{t=1}^{n}∑_{i_{t}≠i}θ_{i_{t}}~{}=~{}∑_{i=1}^{∞}θ_{i}(1-θ_{i})^{n}$

The result can actually more easily be derived as

$\displaystyle\text{\sf E$\\!\\!\\!\\!\;$E}_{n}~{}$
$\displaystyle=~{}\mathbb{P}[i_{n+1}\not\in
i_{1:n}]~{}=~{}∑_{i=1}^{∞}\mathbb{P}[i_{n+1}=i∧i_{1}≠i∧...∧i_{n}≠i]$
$\displaystyle=~{}∑_{i=1}^{∞}\mathbb{P}[i_{n+1}=i]∏_{t=1}^{n}\mathbb{P}[i_{t}≠i]~{}=~{}∑_{i=1}^{∞}θ_{i}(1-θ_{i})^{n}$
(10)

but the former derivation is more suitable for generalization to other loss
functions and noisy labels.

Approximation. Let $f:(0;∞)\textrightarrow(0;∞)$ be a continuously
differentiable and decreasing extension of ${\bm{θ}}:ℕ\textrightarrow ℝ$, i.e.
$f(i):=θ_{i}$ and $f^{\prime}(x)<0$. Let $g(x):=f(x)e^{-nf(x)}$. Since
$u\mapsto ue^{-nu}$ is unimodal with maximum $1/en$ and at $u=1/n$ and $f$ is
monotone, $g(x)$ is unimodal with maximum $g_{max}=1/en$ at
$x_{max}=f^{-1}({\textstyle\frac{1}{n}})$. We hence can use (18) (any
$a∈[0;1]$) to upper bound the sum in (10) by an integral as follows:

$\displaystyle\text{\sf E$\\!\\!\\!\\!\;$E}_{n}~{}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:eerrA}}}{{=}}~{}∑_{i=1}^{∞}θ_{i}(1-θ_{i})^{n}~{}≤~{}∑_{i=1}^{∞}θ_{i}e^{-nθ_{i}}~{}=~{}∑_{i=1}^{∞}f(i)e^{-nf(i)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:incdec}}}{{≤}}~{}g_{max}+\int_{a}^{∞}f(x)e^{-nf(x)}dx~{}=~{}\frac{1}{en}+\int_{0}^{f(a)}{ue^{-nu}du\over|f^{\prime}(f^{-1}(u))|}$

where the last equality follows from a reparametrization $u=f(x)$ and $f(∞)=0$
and $dx=du/f^{\prime}(x)$ and $f^{\prime}<0$.

For a lower bound, we need a lower bound on $(1-θ_{i})^{n}$. For $0≤x≤2ε$ we
have

$\displaystyle
e^{-x}~{}≤~{}1-x+{\textstyle\frac{1}{2}}x^{2}~{}=~{}1-(1-{\textstyle\frac{1}{2}}x)x~{}≤~{}1-(1\\!-\\!ε)x$

Inserting $x=θ_{i}/(1-ε)$, we get

$\displaystyle
1-θ_{i}~{}≥~{}e^{-θ_{i}/(1-ε)}~{}~{}~{}\text{for}~{}~{}~{}θ_{i}≤2ε(1-ε)$

Let $i_{0}$ be an index such that $θ_{i_{0}}≤2ε(1-ε)$. We define
$\tilde{n}:=n/(1-ε)$. That $\tilde{n}$ is not an integer is no problem, and
could even be avoided by renormalizing $θ_{i}$ instead. Similarly as for the
upper bound, we get a lower bound

$\displaystyle\text{\sf E$\\!\\!\\!\\!\;$E}_{n}~{}$
$\displaystyle≥~{}∑_{i=i_{0}}^{∞}θ_{i}(1-θ_{i})^{n}~{}≥~{}∑_{i=i_{0}}^{∞}θ_{i}e^{-\tilde{n}θ_{i}}~{}=~{}-∑_{i=1}^{i_{0}-1}θ_{i}e^{-\tilde{n}θ_{i}}+∑_{i=1}^{∞}θ_{i}e^{-\tilde{n}θ_{i}}$
$\displaystyle≥~{}-∑_{i=1}^{i_{0}-1}θ_{i}e^{-\tilde{n}θ_{i_{0}}}-\tilde{g}_{max}+\int_{a}^{∞}f(x)e^{-\tilde{n}f(x)}dx$
$\displaystyle≥~{}-e^{-\tilde{n}θ_{i_{0}}}-\frac{1}{e\tilde{n}}+\int_{0}^{f(a)}{ue^{-\tilde{n}u}du\over|f^{\prime}(f^{-1}(u))|}$

Let us choose $i_{0}$ such that $θ_{i_{0}}≥ε(1-ε)$, which is possible as long
as $θ_{i}≥{\textstyle\frac{1}{2}}θ_{i-1}$. This finally leads to

$\displaystyle\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}~{}≥~{}-e^{-εn}-\frac{1}{en}+\int_{0}^{f(a)}{ue^{-\tilde{n}u}du\over|f^{\prime}(f^{-1}(u))|}$

Since we can choose $ε$ arbitrarily small, combining both bounds, and choosing
$a\textrightarrow 0$ and $f$ such that $f(x)\textrightarrow∞$ for
$x\textrightarrow 0$, we have

$\displaystyle\Big{|}\text{\sf E$\\!\\!\\!\\!\;$E}_{n}-\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}^{∫}\Big{|}~{}≤~{}\frac{1}{en}+o(1/n)~{}~{}~{}\text{with}~{}~{}~{}\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}^{∫}~{}:=~{}\int_{0}^{∞}{ue^{-nu}du\over|f^{\prime}(f^{-1}(u))|}$
(11)

The integral is dominated by $u\lesssim{\textstyle\frac{1}{n}}$, so for large
$n$ is determined by the asymptotics of $f^{\prime}(f^{-1}(u))$ for
$u\textrightarrow 0$. Assume

$\displaystyle|f^{\prime}(f^{-1}(u))|~{}≈~{}c^{\prime}u^{δ}~{}~{}~{}\text{for
~{}~{}$u\textrightarrow 0$~{}~{} for some ~{}~{}$c^{\prime}$ and $δ$}$ (12)

Substitution $u=v/n$ leads to

$\displaystyle\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}^{∫}~{}≈~{}\int_{0}^{∞}{ue^{-nu}\over
c^{\prime}u^{δ}}du~{}=~{}{n^{δ-2}\over
c^{\prime}}\int_{0}^{∞}v^{1-δ}e^{-v}dv~{}=~{}{\textstyle\frac{Γ(2-δ)}{c^{\prime}}}n^{δ-2}$
(13)

where $Γ$ is the Gamma function.

Zipf distribution. For Zipf-distributed $θ_{i}=αi^{-(α+1)}$, let
$u=f(x)=α⋅x^{-(α+1)}$. This implies

$\displaystyle
x=f^{-1}(u)=(u/α)^{-{\textstyle\frac{1}{1+α}}}~{}~{}~{}\text{and}~{}~{}~{}f^{\prime}(x)=-α(α+1)x^{-(α+2)}=-α(α+1)(u/α)^{{\textstyle\frac{α+2}{α+1}}}$

hence approximation (12) is actually exact with
$δ={\textstyle\frac{α+2}{α+1}}$ and $c^{\prime}=α(α+1)/α^{(α+2)/(α+1)}$
leading to

$\displaystyle\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}^{∫}=c_{α}n^{-β}~{}~{}~{}\text{with}~{}~{}~{}c_{α}={\textstyle\frac{Γ(2-δ)}{c^{\prime}}}={\textstyle\frac{α^{1/(1+α)}}{1+α}}Γ({\textstyle\frac{α}{1+α}})~{}~{}~{}\text{and}~{}~{}~{}β=δ-2={\textstyle\frac{α}{1+α}}$

Note that $\tilde{n}^{-β}=n^{-β}+o({\textstyle\frac{1}{n}})$ for e.g.
$ε={\textstyle\frac{2}{n}}\ln n$, and $e^{-εn}=1/n^{2}$. Numerically one can
check that $c_{α}≤1.214$ for all $α>0$ and $c_{α}≥0.886$ for (the interesting)
$α≤1$, that is, $c_{α}$ is nearly independent of $α$.
$c_{1}={\textstyle\frac{1}{2}}\sqrt{\pi}~{}\dot{=}~{}0.886$ and
$c_{0.1}=1.177$ are in excellent agreement with the fit curves in Figure 2.

Time-averaged expectation and variance. We now consider the time-averaged
error

$\displaystyle\overline{\text{\sf E}}_{N}~{}:$ $\displaystyle=~{}{1\over
N}\sum_{n=0}^{N-1}\text{\sf E}_{n}$

We derive the expressions for its expectation $\mathbb{E}[\overline{\text{\sf
E}}_{N}]$ and variance $\mathbb{V}[\overline{\text{\sf E}}_{N}]$ stated in
Section 4. The expectation is trivial:

$\displaystyle\mathbb{E}[\overline{\text{\sf E}}_{N}]~{}$
$\displaystyle=~{}{1\over N}\sum_{n=0}^{N-1}\mathbb{E}[\text{\sf
E}_{n}]~{}=~{}{1\over
N}\sum_{i=1}^{∞}θ_{i}\sum_{n=0}^{N-1}(1-θ_{i})^{n}~{}=~{}{1\over
N}\sum_{i=1}^{∞}[1-(1-θ_{i})^{N}]$

For the variance, we first compute $\overline{\text{\sf E}}_{N}^{2}$, then
$\mathbb{E}[\overline{\text{\sf E}}_{N}^{2}]$, then
$\mathbb{V}[\overline{\text{\sf E}}_{N}]=\mathbb{E}[\overline{\text{\sf
E}}_{N}^{2}]-\mathbb{E}[\overline{\text{\sf E}}_{N}]^{2}$:

$\displaystyle\overline{\text{\sf E}}_{N}^{2}~{}$ $\displaystyle=~{}{1\over
N^{2}}\sum_{n=0}^{N-1}\sum_{m=0}^{N-1}\text{\sf E}_{n}\text{\sf
E}_{m}~{}\stackrel{{\scriptstyle(b)}}{{=}}~{}{2\over
N^{2}}\sum_{n=0}^{N-1}\sum_{m=0}^{n-1}\text{\sf E}_{n}\text{\sf E}_{m}+{1\over
N^{2}}\sum_{n=0}^{N-1}\text{\sf E}_{n}^{2}$

where $(b)$ breaks up the double sum into lower=upper and diagonal terms.
Since $m<n$ we have

$\displaystyle\text{\sf E}_{n}⋅\text{\sf E}_{m}~{}$
$\displaystyle=~{}[\\![i_{n+1}\not\in i_{1:n}]\\!]⋅[\\![i_{m+1}\not\in
i_{1:m}]\\!]$
$\displaystyle=~{}\sum_{i=1}^{∞}[\\![i_{n+1}=i∧i_{n}≠i∧...∧i_{1}≠i]\\!]⋅\sum_{j=1}^{∞}[\\![i_{m+1}=j∧i_{m}≠j∧...∧i_{1}≠j]\\!]$
$\displaystyle=~{}\sum_{i,j}[\\![i_{n+1}=i∧i_{n}≠i∧...∧i_{m+2}≠i∧i_{m+1}{=j\atop≠i}∧i_{m}{≠j\atop≠i}∧...∧i_{1}{≠j\atop≠i}]\\!]$

For $i=j$, $i_{m+1}{=j\atop≠i}$ (meaning $i_{m+1}=j∧i_{m+1}≠i$) is a
contradiction, so we can limit the sum to $i≠j$. Taking the expectation and
noting that $\text{\sf E}_{n}∈\\{0,1\\}$ and all $i_{t}$ are independent and
$\mathbb{P}[i_{t}=i]=θ_{i}$ we get

$\displaystyle\mathbb{E}[\text{\sf E}_{n}⋅\text{\sf E}_{m}]~{}$
$\displaystyle=~{}\sum_{i≠j}\mathbb{P}[i_{n+1}=i]\mathbb{P}[i_{n}≠i]...\mathbb{P}[i_{m+2}≠i]\mathbb{P}[i_{m+1}{=j\atop≠i}]\mathbb{P}[i_{m}{≠j\atop≠i}]...\mathbb{P}[i_{1}{≠j\atop≠i}]$
$\displaystyle=~{}\sum_{i≠j}θ_{i}(1-θ_{i})^{n-m-1}θ_{j}(1-θ_{i}-θ_{j})^{m},~{}~{}~{}\text{hence}$
$\displaystyle\mathbb{E}[\sum_{n=0}^{N-1}\sum_{m=0}^{n-1}\text{\sf
E}_{n}\text{\sf E}_{m}]~{}$
$\displaystyle=~{}\sum_{i≠j}b_{ijN}={\textstyle\frac{1}{2}}\sum_{i≠j}b_{ijN}+b_{jiN},~{}~{}~{}\text{where}$
$\displaystyle b_{ijN}~{}$
$\displaystyle:=~{}\sum_{n=0}^{N-1}\sum_{m=0}^{n-1}θ_{i}(1-θ_{i})^{n-m-1}θ_{j}(1-θ_{i}-θ_{j})^{m}$
$\displaystyle=~{}θ_{i}θ_{j}\sum_{m=0}^{N-1}(1-θ_{i}-θ_{j})^{m}\sum_{n=m+1}^{N-1}(1-θ_{i})^{n-m-1}$
$\displaystyle=~{}θ_{i}θ_{j}\sum_{m=0}^{N-1}(1-θ_{i}-θ_{j})^{m}{1\over
θ_{i}}[1-(1-θ_{i})^{N-m-1}]$
$\displaystyle=~{}θ_{j}\sum_{m=0}^{N-1}(1-θ_{i}-θ_{j})^{m}~{}-~{}θ_{j}(1-θ_{i})^{N-1}\sum_{m=0}^{N-1}\Big{(}{1-θ_{i}-θ_{j}\over
1-θ_{i}}\Big{)}^{m}$ $\displaystyle=~{}θ_{j}{1\over
θ_{i}+θ_{j}}[1-(1-θ_{i}-θ_{j})^{N}]~{}-~{}θ_{j}(1-θ_{i})^{N-1}{1-θ_{i}\over
θ_{j}}\bigg{[}1-\Big{(}{1-θ_{i}-θ_{j}\over 1-θ_{i}}\Big{)}^{N}\bigg{]}$
$\displaystyle=~{}{θ_{j}\over
θ_{i}+θ_{j}}[1-(1-θ_{i}-θ_{j})^{N}]~{}-~{}(1-θ_{i})^{N}~{}+~{}(1-θ_{i}-θ_{j})^{N},~{}~{}~{}\text{hence}$
$\displaystyle b_{ijN}$
$\displaystyle+b_{jiN}~{}=~{}1-(1-θ_{i})^{N}-(1-θ_{j})^{N}+(1-θ_{i}-θ_{j})^{N}$

The diagonal term is easy:

$\displaystyle{1\over N^{2}}\sum_{n=0}^{N-1}\mathbb{E}[\text{\sf
E}_{n}^{2}]~{}$ $\displaystyle=~{}{1\over
N^{2}}\sum_{n=0}^{N-1}\mathbb{E}[\text{\sf E}_{n}]~{}=~{}{1\over
N}\sum_{n=0}^{N-1}\mathbb{E}[\overline{\text{\sf E}}_{N}]~{}=~{}{1\over
N^{2}}\sum_{i=1}^{∞}1-(1-θ_{i})^{N}$

Putting everything together, non-diagonal $i≠j$ and diagonal $i=j$ expressions
we get our final expression

$\displaystyle\mathbb{E}[\overline{\text{\sf E}}_{N}^{2}]~{}$
$\displaystyle=~{}{1\over
N^{2}}\sum_{i≠j}[1-(1-θ_{i})^{N}-(1-θ_{j})^{N}+(1-θ_{i}-θ_{j})^{N}]~{}+~{}{1\over
N^{2}}\sum_{i=1}^{∞}[1-(1-θ_{i})^{N}]$

In order to get the variance of $\overline{\text{\sf E}}_{N}$ we have to
subtract the squared expected error

$\displaystyle\mathbb{E}[\overline{\text{\sf E}}_{N}]^{2}~{}$
$\displaystyle=~{}\Big{(}{1\over
N}\sum_{i=1}^{∞}1-(1-θ_{i})^{N}\Big{)}^{2}~{}=~{}{1\over
N^{2}}\sum_{i,j}[1-(1-θ_{i})^{N}]⋅[1-(1-θ_{j})^{N}]$ $\displaystyle=~{}{1\over
N^{2}}\sum_{i≠j}[1-(1-θ_{i})^{N}-(1-θ_{j})^{N}+(1-θ_{i})^{N}(1-θ_{j})^{N}]$
$\displaystyle~{}+~{}{1\over
N^{2}}\sum_{i=1}^{∞}[1-2(1-θ_{i})^{N}+(1-θ_{i})^{2N}]$

where we expanded the product and separated the $i≠j$ from the $i=j$ terms,
which now easily leads to

$\displaystyle\mathbb{V}[\overline{\text{\sf E}}_{N}]~{}$
$\displaystyle=~{}\mathbb{E}[\overline{\text{\sf
E}}_{N}^{2}]-\mathbb{E}[\overline{\text{\sf E}}_{N}]^{2}$
$\displaystyle=~{}{1\over
N^{2}}\sum_{i≠j}[(1-θ_{i}-θ_{j})^{N}-(1-θ_{i})^{N}(1-θ_{j})^{N}]~{}+~{}{1\over
N^{2}}\sum_{i=1}^{∞}[(1-θ_{i})^{N}-(1-θ_{i})^{2N}]$

Approximation. We can approximate the variance similarly to the expectation
$\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$. We only provide a heuristic derivation
analogous to (3):

$\displaystyle\mathbb{V}[\overline{\text{\sf E}}_{N}]~{}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{≈}}~{}{1\over
N^{2}}\sum_{i≠j}[e^{-(θ_{i}-θ_{j})N}-e^{-θ_{i}N}e^{-θ_{j}N}]~{}+~{}{1\over
N^{2}}\sum_{i=1}^{∞}[e^{-θ_{i}N}-e^{-2θ_{i}N}]$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{≈}}~{}0~{}+~{}{1\over
N^{2}}\int_{1}^{∞}e^{-f(x)N}-e^{-2f(x)N}dx~{}\stackrel{{\scriptstyle(c)}}{{=}}~{}{1\over
N^{2}}\int_{0}^{θ_{1}}{e^{-uN}-e^{-2uN}\over|f^{\prime}(f^{-1}(u))|}du$
$\displaystyle\stackrel{{\scriptstyle(d)×}}{{≈}}~{}{1\over
N^{2}|f^{\prime}(f^{-1}({\textstyle\frac{\ln
2}{N}}))|}\int_{0}^{θ_{1}}e^{-uN}-e^{-2uN}du~{}\stackrel{{\scriptstyle(e)}}{{≈}}~{}{1\over
2N^{3}|f^{\prime}(f^{-1}({\textstyle\frac{\ln 2}{N}}))|}$
$\displaystyle\smash{\stackrel{{\scriptstyle×}}{{≈}}}~{}{1\over 2N}\text{\sf
E$\\!\\!\\!\\!\;$E}_{N}~{}\left\\{{\smash{\stackrel{{\scriptstyle×}}{{≈}}}~{}~{}~{}{\textstyle\frac{1}{N}}\mathbb{E}[\overline{\text{\sf
E}}_{N}]~{}~{}\text{if}~{}~{}\text{\sf
E$\\!\\!\\!\\!\;$E}_{N}\smash{\stackrel{{\scriptstyle×}}{{≈}}}N^{-β}\atop≤~{}{\textstyle\frac{1}{2N}}\mathbb{E}[\overline{\text{\sf
E}}_{N}]~{}~{}\text{always}~{}~{}~{}~{}~{}~{}~{}~{}}\right.$

$(a)$ follows from $1-θ_{i}≈e^{-θ_{i}}$, $(b)$ by setting $f(i):=θ_{i}$, and
replacing the sums by integrals, $(c)$ follows from a reparametrization
$u=f(x)$ and $f(1)=θ_{1}$ and $f(∞)=0$ and $dx=du/f^{\prime}(x)$ and
$f^{\prime}<0$. The numerator $e^{-uN}-e^{-2uN}$ is maximal and (strongly)
concentrated around $u=\ln 2/n$, hence $u≈\ln 2/n$ gives most of the
integral’s contribution. Therefore in $(d)$ replacing $u$ by $\ln 2/n$ in the
denominator can be a reasonable approximation. $(e)$ follows from
$∫_{0}^{θ_{1}}...≈∫_{0}^{∞}...=1/2N$ for $θ_{1}N\gg 1$. We could use this
approximation for various concrete $f$, but if we substitute $u=1/N$ instead
of $\ln 2/N$ in $(d)$ we only make a multiplicative error $(×)$, and the
expression nicely reduces to the _instantaneous_ expected error $\text{\sf
E$\\!\\!\\!\\!\;$E}_{N}$. For slowly decreasing error $\text{\sf
E$\\!\\!\\!\\!\;$E}_{N}\smash{\stackrel{{\scriptstyle×}}{{≈}}}N^{-β}$, we have
$\mathbb{E}[\text{\sf
E}_{N}]\smash{\stackrel{{\scriptstyle×}}{{≈}}}\mathbb{E}[\overline{\text{\sf
E}}_{N}]$. In general $\mathbb{E}[\text{\sf
E}_{N}]≤\mathbb{E}[\overline{\text{\sf E}}_{N}]$, since $\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}$ is monotone decreasing.

##  Appendix C Noisy Labels

Here we generalize our model to noisy labels. We first derive generic
expression expressions for (somewhat) general algorithm and loss. We then
instantiate them for frequency estimation and square loss. Finally we outline
how to derive similar expressions for the absolute loss.

General loss. Consider a binary classification problem where labels
$y_{t}∈\\{0,1\\}$ are noisy. Let $γ_{i}:=\mathbb{P}[y_{t}=1|i_{t}=i]$ be the
probability that feature $i∈ℕ$ is labelled as $1$. The probability of
observing feature $i$ itself remains $θ_{i}:=\mathbb{P}[i_{t}=i]$ as in the
deterministic case. Algorithm $A_{i}:=A(i,{\cal D}_{n})∈[0;1]$ now aims to
predict $γ_{i}$. The square loss if predicting $A_{i}$ while the true label is
$y$, and its expectation w.r.t. $γ_{i}$, are

$\displaystyle\text{\sf Loss}_{n}(A|{\cal
D}_{n},i_{n+1}=i,y_{n+1}=y)~{}=~{}(y-A_{i})^{2}$ $\displaystyle\text{\sf
Loss}_{n}(A|{\cal
D}_{n},i_{n+1}=i)~{}=~{}γ_{i}(1-A_{i})^{2}+(1-γ_{i})(0-A_{i})^{2}~{}=~{}(γ_{i}-A_{i})^{2}+γ_{i}(1-γ_{i})$

The most naive learning algorithm would predict $γ_{i}$ from observed
frequencies: $A_{i}=k_{i}/n_{i}$ if feature $i$ occurred
$n_{i}:=\\#\\{t≤n:i_{t}=i\\}$ times and has label $1$ for
$k_{i}:=\\#\\{t≤n:i_{t}=i,y_{t}=1\\}$ times. Obviously
$k_{i}/n_{i}\textrightarrow γ_{i}$ provided $n_{i}\textrightarrow∞$, hence
$\text{\sf Loss}_{n}(A|{\cal D}_{n},i_{n+1}=i)$ converges to the intrinsic
label “entropy” $γ_{i}(1-γ_{i})$, rather than to $0$, which has to be
subtracted for a power law analysis to make sense. Similarly the expectation
of log-loss $-y\ln A_{i}-(1-y)\ln(1-A_{i})$ w.r.t. $γ_{i}$ leads to Kullback-
Leibler loss $\text{KL}(γ_{i}||A_{i})$ \+ Entropy $H(γ_{i})$. More generally
let us assume $A(i,{\cal D}_{n})$ depends (somehow) only on $k_{i}$ and
$n_{i}$ (e.g. Laplace rule), and hence

$\displaystyle\text{\sf Loss}_{n}(A|{\cal
D}_{n},i_{n+1}=i)~{}=~{}\ell(γ_{i},A_{i})~{}=~{}\ell(γ_{i},k_{i},n_{i})~{}=~{}\text{\sf
Loss}_{n}(A|k_{i},n_{i},i_{n+1}=i)$

for some function $\ell$. We now take the expectation over ${\cal D}_{n}$:

$\displaystyle L_{i}~{}$ $\displaystyle:=~{}\text{\sf Loss}_{n}(A|i_{n+1}=i)$
$\displaystyle=~{}\sum_{{\cal D}_{n}}\text{\sf Loss}_{n}(A|{\cal
D}_{n},i_{n+1}=i)\mathbb{P}[{\cal D}_{n}]$
$\displaystyle=~{}\sum_{n_{i}=0}^{n}\sum_{k_{i}=0}^{n_{i}}\bigg{(}\sum_{{\cal
D}_{n}:k_{i},n_{i}}\mathbb{P}[{\cal D}_{n}]\bigg{)}\ell(γ_{i},k_{i},n_{i})$

where $\sum_{{\cal D}_{n}:k_{i},n_{i}}$ means that the sum is restricted to
${\cal D}_{n}$ for which $i$ ($(i,1)$) appears $n_{i}$ ($k_{i}$) times. The
probability of each of this happening is binomial:

$\displaystyle\sum_{{\cal D}_{n}:k_{i},n_{i}}\mathbb{P}[{\cal
D}_{n}]~{}=~{}\sum_{i_{1:n}:n_{i}}\mathbb{P}[i_{1:n}]\sum_{y_{1:n}:k_{i}}\mathbb{P}[y_{1:n}|i_{1:n}]~{}=~{}{\textstyle\Big{(}{\textstyle
n\atop\textstyle
n_{i}\\!}\Big{)}θ_{i}^{n_{i}\\!}(1-θ_{i})^{n-n_{i}\\!}}{\textstyle\Big{(}{\textstyle
n_{i}\atop\textstyle k_{i}}\Big{)}γ_{i}^{k_{i}}(1-γ_{i})^{n_{i}-k_{i}}}$

This is obvious or follows by explicit calculation of the sums and some
algebra. Putting everything together and finally taking the expectation over
$i$ we get

$\displaystyle\text{\sf Loss}_{n}(A|n_{i},i_{n+1}=i)~{}$
$\displaystyle=~{}\sum_{k_{i}=0}^{n_{i}}{\textstyle\Big{(}{\textstyle
n_{i}\atop\textstyle
k_{i}}\Big{)}γ_{i}^{k_{i}}(1-γ_{i})^{n_{i}-k_{i}}}\ell(γ_{i},k_{i},n_{i})$
(14) $\displaystyle L_{i}≡\text{\sf Loss}_{n}(A|i_{n+1}=i)~{}$
$\displaystyle=~{}\sum_{n_{i}=0}^{n}{\textstyle\Big{(}{\textstyle
n\atop\textstyle
n_{i}\\!}\Big{)}θ_{i}^{n_{i}\\!}(1-θ_{i})^{n-n_{i}\\!}}~{}\text{\sf
Loss}_{n}(A|n_{i},i_{n+1}=i)$ (15) $\displaystyle\text{\sf Loss}_{n}(A)~{}$
$\displaystyle=~{}\sum_{i=1}^{∞}θ_{i}L_{i}$ (16)

In the deterministic case $γ_{i}∈\\{0,1\\}$ and our memorizing algorithm (1)
with 0-1 loss, $\ell(γ_{i},k_{i},n_{i})=[\\![n_{i}=0]\\!]$ is independent
$k_{i}$, so the $k_{i}$ sums the binomial to 1, and the $n_{i}$-sum collapses
to $n_{i}=0$, leading back to $\text{\sf
Loss}_{n}(A)=\sum_{i=1}^{∞}θ_{i}(1-θ_{i})^{n}=\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}=$(10).

Square loss. For noisy labels, $γ_{i}∈[0;1]$, frequency estimator
$A_{i}=k_{i}/n_{i}$, square loss
$\ell(γ_{i},k_{i},n_{i})=(γ_{i}-k_{i}/n_{i})^{2}$ for $n_{i}>0$ (with
“Entropy” $γ_{i}(1-γ_{i})$ removed), and keeping $\ell(γ_{i},k_{i},0)=1$, we
proceed as follows: The $k_{i}$-sum in (14) becomes the variance of
$k_{i}/n_{i}$, hence $\text{\sf
Loss}_{n}(A|n_{i},i_{n+1}=i)=γ_{i}(1-γ_{i})/n_{i}$. Unfortunately plugging
this into the next $n_{i}$-sum in (15) leads to a hypergeometric function. We
tried various approximations, all leading essentially to the same end result.
The simplest approximation is to approximate $γ_{i}(1-γ_{i})/n_{i}$ by
$γ_{i}(1-γ_{i})/(n_{i}+1)$, which is asymptotically correct and within a
factor of 2 also valid for $1≤n_{i}<∞$, and avoids hypergeometric functions
altogether:

$\displaystyle L_{i}~{}$
$\displaystyle=~{}\sum_{n_{i}=0}^{n}{\textstyle\Big{(}{\textstyle
n\atop\textstyle
n_{i}\\!}\Big{)}θ_{i}^{n_{i}\\!}(1-θ_{i})^{n-n_{i}\\!}}~{}\text{\sf
Loss}_{n}(A|n_{i},i_{n+1}=i)$
$\displaystyle=~{}(1-θ_{i})^{n}~{}+~{}\sum_{n_{i}=1}^{n}{\textstyle\Big{(}{\textstyle
n\atop\textstyle
n_{i}\\!}\Big{)}θ_{i}^{n_{i}\\!}(1-θ_{i})^{n-n_{i}\\!}}~{}\frac{γ_{i}(1-γ_{i})}{n_{i}}$
$\displaystyle≈~{}(1-θ_{i})^{n}~{}+~{}\sum_{n_{i}=1}^{n}{\textstyle\Big{(}{\textstyle
n\atop\textstyle
n_{i}\\!}\Big{)}θ_{i}^{n_{i}\\!}(1-θ_{i})^{n-n_{i}\\!}}\frac{γ_{i}(1-γ_{i})}{n_{i}+1}$
$\displaystyle=~{}(1-θ_{i})^{n}~{}-~{}(1-θ_{i})^{n}γ_{i}(1-γ_{i})~{}+~{}\sum_{n_{i}=0}^{n}{\textstyle\Big{(}{\textstyle
n\atop\textstyle
n_{i}\\!}\Big{)}θ_{i}^{n_{i}\\!}(1-θ_{i})^{n-n_{i}\\!}}\frac{γ_{i}(1-γ_{i})}{n_{i}+1}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}~{}[1-γ_{i}(1-γ_{i})](1-θ_{i})^{n}~{}+~{}\frac{γ_{i}(1-γ_{i})}{(n+1)θ_{i}}\sum_{k=1}^{n+1}{\textstyle\Big{(}{\textstyle
n+1\atop\textstyle k}\Big{)}θ_{i}^{k}(1-θ_{i})^{n+1-k}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}~{}[1-γ_{i}(1-γ_{i})](1-θ_{i})^{n}~{}+~{}\frac{γ_{i}(1-γ_{i})}{(n+1)θ_{i}}[1-(1-θ_{i})^{n+1}]$

where (a) follows from substituting $n_{i}=k-1$ and rearranging terms, and (b)
from adding and subtracting the missing $k=0$ contribution, and the fact that
a complete binomial sums to 1. If we assume that the noise level is the same
for all features, i.e. $γ_{i}=γ$ or $γ_{i}=1-γ$, then

$\displaystyle\text{\sf Loss}_{n}(A)~{}$
$\displaystyle=~{}\sum_{i=1}^{∞}θ_{i}L_{i}~{}≈~{}[1-γ(1-γ)]\sum_{i=1}^{∞}θ_{i}(1-θ_{i})^{n}~{}+~{}\frac{γ(1-γ)}{n+1}\sum_{i=1}^{∞}[1-(1-θ_{i})^{n+1}]$
$\displaystyle=~{}[1-γ(1-γ)]\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}~{}+~{}γ(1-γ)\mathbb{E}[\overline{\text{\sf E}}_{n+1}]$

Again, in the deterministic case $γ∈\\{0,1\\}$, we get back $\text{\sf
Loss}_{n}(A)=\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$. If we assume that $γ_{i}$ are
bounded away from 0 and 1, then still within a multiplicative constant

$\displaystyle\text{\sf
Loss}_{n}(A)~{}~{}\smash{\stackrel{{\scriptstyle×}}{{=}}}~{}~{}\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}~{}+~{}\mathbb{E}[\overline{\text{\sf E}}_{n}]$

This is quite remarkable, that the _instantaneous_ square loss for noisy
labels includes a term proportional to the _time-averaged_ (0-1) error in the
deterministic case. As we have seen in the main paper, roughly, as long as
$\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$ goes to 0 slower than $1/n$, $\text{\sf
E$\\!\\!\\!\\!\;$E}_{n}$ and $\mathbb{E}[\overline{\text{\sf E}}_{n}]$ have
the same asymptotics, which in turn implies that the results for deterministic
classification transfer to noisy labels, in particular $α$-Zipf-distributed
data lead to $β$-power law learning curves with $β={\textstyle\frac{α}{1+α}}$.
While E E can decay faster than $1/n$, e.g. exponentially for finite models,
$\mathbb{E}[\overline{\text{\sf E}}_{n}]$ and hence $\text{\sf Loss}_{n}(A)$
can never decay faster than $1/n$. As discussed in the introduction, the
reason is that the accuracy to which parameters (here $γ_{i}$) can be
estimated from $n_{i}$ i.i.d. data is
$\smash{\stackrel{{\scriptstyle×}}{{=}}}n_{i}^{-1/2}\smash{\stackrel{{\scriptstyle×}}{{≥}}}n^{-1/2}$,
which squares to $\text{\sf
Loss}_{n}(A)\smash{\stackrel{{\scriptstyle×}}{{≥}}}n^{-1}$ for (locally)
quadratic loss.

Absolute loss. For absolute loss $\ell=|γ_{i}-k_{i}/n_{i}|$ there is no
closed-form solution for (14). For large $n_{i}$, the binomial is
approximately Gaussian (in $k_{i}/n_{i}$) with mean $γ_{i}$ and variance
$γ_{i}(1-γ_{i})/n_{i}$, and (14) can be evaluated to
$\sqrt{γ_{i}(1-γ_{i})/n_{i}}$. Plugging this into (15) we can approximate the
$n_{i}$-sum for $nθ_{i}\ll 1$ and for $nθ_{i}\gg 1$. Plugging each into (16),
and approximating the $i$-sum for $α$-Zipf-distributed $θ_{i}$ one can show
that each, again, scales as $n^{-β}$ with $β={\textstyle\frac{α}{1+α}}$, but
the latter has an additional $n^{-1/2}$ term. For $α<1$ this is swamped by
$n^{-β}$, but for $α>1$ it dominates the learning curve. The intuition for
this happening is explained in the main text.

##  Appendix D Approximating Sums by Integrals

Sums $∑_{i=1}^{∞}g(i)$ can be approximated by integrals $∫_{1}^{∞}g(x)dx$. To
upper bound the approximation error classically requires computing a
cumbersome integral (Euler-Maclaurin remainder) or only works for finite sums
(Trapezoid rule). In the following we derive an upper bound on the
approximation accuracy, suitable for our purpose. First, note that for a
monotone increasing function

$\displaystyle\int_{n-1}^{m}g(x)dx~{}≤~{}\sum_{i=n}^{m}g(i)~{}≤~{}\int_{n}^{m+1}\\!\\!g(x)dx$
(17)

with inequalities reversed for monotone decreasing functions. Consider now any
measurable function $g:[0;∞)\textrightarrow[0;∞)$ increasing up to
$g_{max}=g(x_{max})$ and thereafter decreasing (In our application
$g(x)=f(x)e^{-nf(x)}$). Let $i_{m-1}≤x_{max}≤i_{m}$. We split the integral
into the increasing and decreasing part and use (17) to lower-bound the error:

$\displaystyle\sum_{i=1}^{∞}g(i)~{}$
$\displaystyle=~{}\sum_{i=1}^{i_{m-1}}g(i)+\sum_{i=i_{m}}^{∞}g(i)~{}≥~{}\int_{0}^{i_{m-1}}g(x)dx+\int_{i_{m}}^{∞}g(x)dx$
$\displaystyle=~{}\int_{0}^{∞}g(x)dx-\int_{i_{m}}^{i_{m-1}}g(x)dx~{}≥~{}\int_{0}^{∞}g(x)dx-
g_{max}$

To obtain an upper bound we have to exclude $i_{m-1}$ and $i_{m}$ from the
sums:

$\displaystyle\sum_{i=1}^{∞}g(i)~{}$
$\displaystyle=~{}\sum_{i=1}^{i_{m-2}}g(i)+\sum_{i=i_{m+1}}^{∞}\\!\\!g(i)+~{}~{}[g(i_{m-1})+g(i_{m})]$
$\displaystyle≤~{}\int_{1}^{i_{m-1}}g(x)dx+\int_{i_{m}}^{∞}g(x)dx+~{}\min\\{g(i_{m-1}),g(i_{m})\\}+\max\\{g(i_{m-1}),g(i_{m})\\}$
$\displaystyle≤~{}\int_{1}^{i_{m-1}}g(x)dx+\int_{i_{m}}^{∞}g(x)dx+\int_{i_{m-1}}^{i_{m}}g(x)dx+g_{max}~{}=~{}\int_{1}^{∞}g(x)dx+g_{max}$

Together this leads to the following bound on the approximation error:

$\displaystyle\bigg{|}∑_{i=1}^{∞}g(i)-∫_{a}^{∞}g(x)dx)\bigg{|}~{}≤~{}g_{max}$
(18)

for any=every choice of $a∈[0;1]$. Without further assumptions on $g$, this
bound is tight. For the lower bound consider $g(x)=g_{max}$ for
$i_{m-1}<x<i_{m}$ and $0$ otherwise. For the upper bound consider
$g(i_{m})=g_{max}$ and $0$ otherwise.

##  Appendix E List of Notation

Symbol  |  Explanation
---|---
$a/b⋅c=(a/b)⋅c$ |  but $a/bc=a/(bc)$
$[\\![\text{Bool}]\\!]$ | 1 if Bool=True, 0 if Bool=False
$\\#{\cal S}$ | Number of elements in set ${\cal S}$
$\mathbb{P},\mathbb{E},\mathbb{V}$ | Probability, Expectation, Variance
$i∈i_{1:n}$ | is short for $i∈\\{i_{1},...,i_{n}\\}$
$~{}\dot{=}~{}$ | Equal within the stated number of numerical digits
$\smash{\stackrel{{\scriptstyle×}}{{=}}}$ | Equal within a multiplicative constant
$\smash{\stackrel{{\scriptstyle×}}{{≈}}}$ | Asymptotically or approximately proportional
$i,j∈ℕ$ | natural number “feature”
$t,n,m∈ℕ$ | time/sample index
$N∈ℕ$ | sample size
$θ_{i}$ | probability of feature $i$
$A$ | tabular learning algorithm
$h:ℕ\textrightarrow{\cal Y}$ | classifier, e.g. binary ${\cal Y}=\\{0,1\\}$
$f:ℝ\textrightarrow ℝ$ | Theoretical data distribution/scaling $f(i)=θ_{i}$
${\cal D}_{n}$ | Data consisting of $n$ (feature,label) pairs
$\text{\sf E}_{n}$ | Instantaneous Error of $A$ on $i_{n+1}$ predicting $y_{n+1}$ from ${\cal D}_{n}$
$\text{\sf E$\\!\\!\\!\\!\;$E}_{n}$ | Expectation of Instantaneous Error $\text{\sf E}_{n}$ w.r.t. ${\cal D}_{n}$
$\overline{\text{\sf E}}_{N}$ | Time-Averaged Error from $n=1,...,N$
$α$ | Exponent of Zipf distributed data frequency
$β$ | Exponent of power law for error as a function of data size
$γ$ | Decay rate for exponential data distribution

##  Appendix F More Figures

Figure 4: (Learning Curves) for uniform data distribution
$\mathbb{P}[i_{n}=i]=θ_{i}={\textstyle\frac{1}{m}}$ for $i≤m=10$ averaged over
$k=1,10,100,1000$ runs.

Figure 5: (Learning Curves) for Zipf-distributed data
$\mathbb{P}[i_{n}=i]=θ_{i}\propto i^{-(α+1)}$ for $α=1$ averaged over
$k=1,10,100,1000$ runs.

Figure 6: (Word-Frequency in Text File, Learning Curve, Power Law) _(left)_
Relative (left scale) and absolute (right scale) of frequency of words in the
first 20469 words in file ‘book1’ of the Calgary Corpus, and fitted Zipf law,
which is a straight line in the Log-log plot. _(right)_ Power law fit to
learning curve for this data set for a word classification task. For large
$n$, low frequency words break the Zipf law and hence the power law. The solid
line is the same as in Figure 3 (right) fit to the reliable region $n≤1000$
and then extrapolated. The dashed line is fit over the whole range of $n$.