Learning Curve Theory

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,

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

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).

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.

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 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:

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

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

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.

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 , 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

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:

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

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

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.

Learning Curve Variance

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

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

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

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}={\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}$):

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

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

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.

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.

Experiments

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

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.

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:

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

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

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

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

Otherwise the scaling laws for Zipf data are unchanged.

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

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

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

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.

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

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

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.

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

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

The result can actually more easily be derived as

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:

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

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

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

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

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

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

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

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

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

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

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

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

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.

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 , 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

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:

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

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

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

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

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:

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

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

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 otherwise. For the upper bound consider $g(i_{m})=g_{max}$ and otherwise.

Appendix E List of Notation

Appendix F More Figures