An exactly solvable model for emergence and scaling laws in the multitask sparse parity problem
Authors: Yoonsoo Nam
Nayara Fonseca
Seok Hyeong Lee
Chris Mingard
Ard A. Louis
Venue: NeurIPS 2024 poster (2024)
Keywords: science of deep learning
emergence
skills
scaling laws
Primary area: other
TL;DR: We can predict emergence in neural networks using a simple model that also demonstrates scaling laws.

Abstract: Deep learning models can exhibit what appears to be a sudden ability to solve a new problem as training time, training data, or model size increases, a phenomenon known as emergence. In this paper, we present a framework where each new ability (a skill) is represented as a basis function.  We solve a simple multi-linear model in this skill-basis, finding analytic expressions for the emergence of new skills, as well as for scaling laws of the loss with training time, data size, model size, and optimal compute.  We compare our detailed calculations to direct simulations of a two-layer neural network trained on multitask sparse parity, where the tasks in the dataset are distributed according to a power-law.  Our simple model captures, using a single fit parameter,  the sigmoidal emergence of multiple new skills as training time, data size or model size increases in the neural network.

An exactly solvable model for emergence and scaling laws in the multitask sparse parity problem
Yoonsoo Nam* Nayara Fonseca** Seok Hyeong Lee", Chris Mingard and Ard A. Louis
Rudoll Peierls Centre for Theoretical Physics, University of Oxford
Center for Quantum Structures in Modules and Spaces, Seoul National University Physical and Theoretical Chemistry Laboratory, University of Oxford
Abstract
Deep learning models can exhibit what appears to be a sudden ability to solve a new problem training time, training data, or model size increases, a phenomenon known as emergence. In this paper, we present a framework where each new ability (a skill) is represented as a basis function. We solve a simple multi-linear model in this skill-basis finding analytic expressions for the emergence of new skills, as well as for scaling laws of the loss with training time, data size, model size, and optimal compute. We compare our detailed calculations to direct simulations of a two-layer neural network trained on multitask sparse parity, where the tasks in the dataset are distributed according to power-law. Our simple model captures, using single fit parameter, the sigmoidal emergence of multiple new skills training time, data size or model size increases in the neural network.
Introduction
Emergence in large language models (LLMs) has attracted lot of recent attention [1-4]. It motivates the costly drive to train ever larger models on ever larger datasets, in the hope that new skills will emerge. While the concept of emergence has been critiqued the grounds that the sharpness of the transition to acquiring a new skill may be sensitive to the measure being used [5], the observation that important new skills the skills emerge and what drives the emergence. These questions are complicated by difficulties in formally defining skills or capabilities [6), and by our general limited understanding of the internal representations of deep neural networks [7].
learned for larger models raises many challenging questions: when
Another widely observed property of deep learning models is that the loss improves predictably power-law in the number of data points or the number of model parameters or simply in the amount of compute thrown at problem. These neural scaling laws [8, 9] have been widely observed across different architectures and datasets [10-16]. While the scaling exponents can depend on these factors, the general phenomena of scaling appear to be remarkably robust. This raises many interesting questions such as: What causes the near-universal scaling behavior? How does the continuous scaling of the loss relate to the discontinuous emergence of new skills?
challenge in answering the questions raised by the phenomena of emergence and scaling laws arises from the enormous scale and expense of training cutting cutting-edge edge modern LLMs, which are optimized for commercial applications, and not for answering scientific questions about how they work. One way that progress can be made is to study simpler dataset/architecture combinations that are more tractable. The current paper is inspired part by recent work in this direction that proposed studying emergence in learning the sparse parity problem [17, 18), which is easy to define, but known to be
'These authors contributed equally; fyoonsoo nam, nayara. paa.aara.foosscccddeeaaaapyyiiie
ac.uk.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

computationally hard. In particular, Michaud et al. [18] introduce the multiple unique sparse parity problem where tasks are distributed in the data through a power-law distribution of frequencies as proxy for studying emergence and neural scaling in L.MMs. For this data set, the authors empirically measure the scaling laws of a 2-layer multilayer perceptron (MI.P) as function of training steps (T), parameters (N), and training samples (D). Based on their quanta model of abrupt skill acquisition, they schematically derive neural scaling laws as sum of emergences of new skills. However, no link was established between the neural network dynamics and the quanta model.
In this paper, we introduce an analytically tractable model by defining a basis of orthogonal functions for the multitask sparse parity problem. Each basis function corresponds to skill that can be learned, and their respective frequencies are distributed following a power-law with exponent a + We then propose simple multilinear expansion in these orthogonal functions that introduces layered structure reminiscent of neural networks (NNs) and gives rise to the stage-like training dynamics [19]. With our simple model, we can analytically calculate full scaling laws, including pre-factors, as function of data exponents a, T, D, N, and optimal compute C. Our simple model can, with just one parameter calibrated the emergence of the first skill, predict the ordered emergence of multiple skills in a 2-layer MLP. We summarize our contributions as follows:
Skills as basis functions. We establish a framework for investigating emergence by repre- senting skills orthogonal functions that form basis in function space (Section 2). We apply our methods to controlled experiments on the multitask sparse parity dataset.
2. Multilinear model. We propose analytically tractable model that is expanded in the basis of skill functions, and is multilinear with respect to its parameters so that possesses a layerwise structure (Section 3). The multilinear nature of the model produces non-linear dynamics, and the orthogonal basis decouples the dynamics of each skill.
3. Scaling laws. We derive scaling laws for our multilinear model, including the prefactor constants, which relate the model's performance training time (T), dataset size (D), number of parameters (N), and optimal compute (C = x I), see Section 4. We show that the scaling exponents for these factors -a/(a 1), -a/(a+ 1), -a. -a/(a + 2), respectively, where a + is the exponent of the power-law input data.
4. Predicting emergence. We demonstrate that our multilinear model captures the skill emer- gence of an MLP with 2 layers for varying training time, dataset size, and number of trainable parameters. Our results show that the multilinear model, calibrated only on the first skill, can predict the emergence of subsequent skills in the 2-layer MLP, see Fig. I and Section 5. We obtain an equivalent result on the time emergence for a transformer architecture (Fig. 4).
k=1
k=
k=
k=
k=
1.0
1.0
1.0
Skill strength R. /s
SMI1 strang R
Shill strength RA/8
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.2
0.2
0.0
0.0
0.0
103
10
103
10a
100
10a
T
D
N
(a) Time emergence
(b) Data emergence
(c) Parameter emergence
Figure 1: Predicting emergence. The skill strength Ra, defined as the tthh coefficient if model is expanded in the basis of the skill functions (gk), measures how well the 4thh skill is learned, and is plotted against (a) time T, (b) data set size D. and (c) number of parameters N (width of the hidden layer). R2 is normalized by the target scale S such that R//S = means zero skill loss. The dashed lines show the abrupt growth emergence of 5 skills for 2-layer MLP (Appendix K) trained on the multitask sparse parity problem with data power-law exponent = 0.6 (shaded area indicate 1 1-standard deviation over at least 10 runs). Solid lines are the predictions (Eqs. (14), (17) and (21), respectively) from our multilinear model calibrated on the first skill (blue) only.

---

Table 1: Multitask sparse parity dataset and skill basis functions. The control bits are nz dimensional one-hot vectors encoding specific parity tasks, indexed in the first column. The frequency of the distinct parity tasks follows a rank-frequency distribution with an inverse power law relation (Eq. (1)). The skill bits are binary strings with m = 3 relevant sparse bits (highlighted in colors) with their locations varying by skill. The y column shows the target scale multiplied by the parity computed from the relevant bit set M (i, 2).. The last columns show the values of the skill basis functions ge (i, x), defined in Eq. (2).
Skill idx (1) Control bits
Skill bits (X)
y
M(i,))
91 (i,
92(1,
In. (i, x)
1000000
1101 10000000000
S [1,1,0]
1
0
0
1000000
100101010001
S [0,1,0]
-1
0
0
: :
:
2
0100000
101001011011
- [0.0.1]
0
:
T2
0000001
001010100110
S [1,1,1]
0
0
2 Setup
In this section, we define the multitask sparse parity problem under the mean-squared error (MSE) loss. We represent skills as orthogonal functions and measure their strength model by calculating the linear correlation between the model output and the skill basis functions. For comprehensive list notations, refer to the glossary in Appendix A. Our code also available online.
Multitask sparse parity problem. In the sparse parity problem, n skill bits are presented to the model. The target function is parity function applied to a fixed subset of the input bits. The model must detect the relevant m < ny sparse bits and return the parity function on this subset (M, x). see Table 1). Michaud et al. [18] introduced the multitask sparse parity problem by introducing n, unique sparse parity variants or skills with different sparse bits (for a representation, see Table 1). Each skill is represented in the n, control bits as one-hot string, and the model must solve the specific sparse parity task indicated by the control bits (for more details, see Appendix B.1).
The n, skills (random variable E (1, )2 follow power law distribution P., and the skill bits (random variable X {0, 1)m*)) are uniformly distributed. Because Pa and P/ are independent, the input distribution P(I, X) follows product of two distributions:
(a(+))
P.(1 1) Σ j-(a+))
Pa(X = x) 2-
P (1)
We denote A =
Σ (E (((tt))
so that P.(1): = (i+(1+1)
Skill basis functions. We represent the 4thh skill as a function 9s {0, 10,11)xam 1).tttm + (-1,0, 1} that returns the parity (f) on the Wtth skill's sparse bits if but returns 0 if the control bit mismatches that of the 8th skill (i + k):
gx(1, : (,,)E,,,(0,
ifi=k otherwise
(2)
n.tms - {0, 1m is the map that selects the relevant sparse bits for the 5th skill (Table 1) and M, x) is the jth entry of (i, Note that different skill functions have 0 correlation as the supports skills functions are mutually exclusive:
where M 10
gb (i, x)g (i, = 61,
(3)
hhaps://gitubb.co//yoosssooooo 19/Skill Eigenmode.ii

---

The target function. The target function is sum over n, skill functions multiplied by target scale S:
B2 ( 2)).
x1, =
The target scale is the norm of the target function (E,,x (f,, S²). Note that the skill functions serve as 'features' or countable basis for describing the target function in Hutter [20].
MSE loss.
We use MSE loss for analytic tractability:
:: Ex.1 -
(5)
where f the function expressed by given model. We define the skill loss Ls as the loss when only the tt skill is given, which can be weighted by their skill frequencies to express the total loss:
1 Ex -
Lx =
L P.(I ((1=k)C K)
(6)
Skill strength. The skill strength or the linear correlation between the hthh skill (gk) and a function expressed by the model at time T (ST) is
R& (T) Ex ()
The skill strength Rr is the htth coefficient if model is expanded in the basis of the skill functions (gs). The skill strength, like the test loss, can be accurately approximated by sum (see Appendix K.3). The skill loss La (Eq. (6)) can be expressed by the skill strength and the norm of the learned function for I = k:
1 (s (S2 + Ex [fr k. x) 28))
(T) -
(8)
The skill loss becomes if and only if fr(I X) Sgk (I= X).
Experimental setting. We use 2-layer MLP that receives the + n4 bits as inputs and outputs scalar ((0, 1] 1n + R). In most of the experiments, the NN is trained with stochastic gradient descent (SGD) with width 1000, using n, = 5, m = 3, and nı, = 32, unless otherwise stated. A decoder transformer is also used for the time emergent experiments. See Appendix K for details.
Multilinear model
We propose simple multilinear model multilinear with respect to the parameters with the first N most frequent skill functions ge (i, æ) as the basis functions (features):
N
fr(i,
Σ au (T)( k=1
(9)
where b E R are the parameters. The model has built-in skill functions 9v. which transform control bits and skill bits into the parity outputs of each skill so the model only needs to scale the parameters andb S.
The multilinear structure (product of ag, by) analogous to the layered structure of NNs and results in emergent dynamics (Fig. ((a)) different from a linear model with the same basis functions (Appendix H). A similar model has been studied by Saxe et al. [19] in the context of linear neural networks (Appendix B.2).
For the multilinear model, note that as (T) is the skill strength R2 (Eq. (7)) and the skill loss (Eq. (6)) is a function of S and Rr only:
Qg (T) = (T)...
Cx(T) (s -R(
(10)

---

Assuming that we are training the model on D samples from P(I,X), the empirical loss decomposes into a sum of empirical skill losses because I& supports are mutually exclusive. This decouples the dynamics of each skill (R)())). which is analytically solvable under gradient flow (Appendix C.I).
n2 Σ Rx
Rx (T) S
1 e
(T)) 2D
(11)
1
-1 [2(0]
2n ST
where de is the number of samples of the kdhh skill (i.e., number of samples (i, with ge (i, x:) * 0),
is the learning rate, and ( < (0) < S is the skill strength at initialization.
4 Scaling laws
Recent literature has extensively explored scaling laws; see Section 7 for an overview. In this section, we derive the scaling laws of our multilinear model (Section 3) for time (2), data (D), parameters (N) and optimal compute (C). We define compute as C. == N [21].
Table 2 shows our analytical scaling laws including their prefactor constants (Appendix J) and Fig. compares the simulation of our model with scaling law predictions. For the scaling law exponents, we achieve the same exponent as in Hutter [20] for D and in Michaud et al. [18] for T. D, and N. Assuming 0 < a 1, the exponents
consistent with the small power-law exponents reported in large-scale experiments, see, e.g., [9, 14, 22].
Using Eqs. (6). (10) and (11), we derive the loss function of time (T), data (D), parameters (N), and the number of observations for each skill [d1, dn,]:
5 L
1
S2
nx Σ
(k(
P.(k).
(12)
2
1
s R2((0)
-1)
22n ST
k=N+1
Under suitable assumptions (e.g., for the scaling law, we take D, - oc and dz/D + (k))) use Eq. (12) to derive the scaling laws. For T, D, and N, used Eq. (11) decoupled dynamics induced the basis functions Jk to decouple the evolution of each skill loss:
1. For the time scaling law, each La shares the same dynamics with T scaled by (k)..
2. For the data scaling law, each L2 depends only on the observation the hth skill (d2 >> 0).
3. For the parameter scaling law, each La depends on whether the model has gb as a basis function.
For the optimal compute scaling law, we show in Corollary 4 (Appendix J) that the optimal tradeoff between T and N for given C' is when T is large enough fit the 4 skill (Fig. 3). In Appendix J, show rigorous derivations (e.g., how large N must be compared to T to be treated infinity). For simplified derivations for the exponents only, see Appendix E. For an intuitive derivation (stage-like training) and connection to Michaud et al. [18), see Appendix D.
all scaling laws, including the prefactors, error bounds, and conditions
5 Predicting emergence
The literature on emergence has rapidly expanded lately; for a review these developments. see Section 7. In this section, we analyze the emergence of 2-layer NN (Section 2) and discuss to what degree the emergence in NNs can be described with our model. At initialization, NNs lack the information about the data and must 'discover' each gk- To take this effect into account in our model, we add an extra parameter which we calibrate (fit) on an NN trained on one skill (n, = 1) system and use it to predict the emergence subsequent skills for the n, 5 setup (Fig. 1).
5.1 Time emergence
In our multilinear model, the layerwise structure the product of parameters aghs leads sigmoidal saturation where update of one layer hastens the update of the other layer. Feature
5

---

a= 0.3
a=
0.99
10a1
10-1
1
N. -
N
7,0
10-2
C= 1/
C= AnD
C=AnD-o/++1
-o/o++
10
...
L= Au
100
10
10
103
104
10
10a
10a
10a
10
10a
10a
T
D
N
(a) Time scaling
(b) Data scaling
(c) Parameter scaling
Figure 2: Scaling laws. The learning curve (C is the MSE loss) of the multilinear model (solid) and the theoretical power-law (dotted) for (a) time T, (b) data D. and (c) parameters N. Lower left legends show the condition (top) and the scaling law (bottom) where a + is the exponent of the power-law input data (Eq. (I)). See the appendices for 1) rigorous derivations of the theoretical scaling laws including the exponents, prefactors (e.g., AN for C = Ay and conditions (Appendix J); 2) simplified derivations of the exponent only (Appendix E); 3) details of the experiment (Appendix K.4).
Table Summary of the scaling laws for the multilinear model. The leftmost column indicates the bottleneck resource while the next two columns are the conditions for the 'large resources' large enough to treated infinity. The fourth column is the bottleneck resource's 's scaling law exponent for the loss. The last two columns show the statement for the prefactor constant and the scaling law (with the assumptions and explicit error terms) Appendix J.
Bottleneck
Condition
Condition 2
Exponent
Prefactor
Scaling law
Time (T)
D > 2 TT3
No+1 > T
aa/(a+1)
Thm.4
2,
Data (D)
T >
D(log Djate
No+1
>> D
-a/(a+1)
Thm.5
Thm.5
Parameter (N)
D > 7
Na+1
(())
-a
Thm.1
Thm.1
Compute (C)
D >> T3
No+1 2 T
-a/(a+2)
Cor. 5
Cor. 4
0.3
0.6
0.9
10a
10a
10-1
10
10-2
102
104
106
10a
10a
104
106
10a
102
10*
106
10a
C
C
C
Figure Scaling law for optimal compute. The solid lines are the learning curves of the multilinear model as function of compute C = T x N with varying parameters N from 10a (top plateau) to 10d (bottom plateau). The dotted lines are optimal compute scaling laws with exponent -a/(a (a + 2) (Appendix E.4) and calculated prefactor constants (Appendix J). See Appendix K.4 for details of the experiment. For a given C, we achieve the optimal tradeoff when T' is large enough to fit all skills (i.e. when the solid lines plateau). For the case 0.3, the optimal C' for the model decays faster than the pawer-law, see Appendix E.

---

learning dynamics in 2-layer MLP shares the positive feedback between the layers but require non-trivial update of parameters to express 9k-
Extended model. Given that feature learning, though nonlinear, involves parameter updates, compensate for the additional delay in feature-leamnnng by multiplying g& by a calibration constant 0 O<B<l 1:
N Σ k=1
fr(i,;;
as (T) (1,
< B
(13)
The calibration constant rescales the dynamics (Eq. (11)):
(T)
1
(14)
S
1 +
g [O]
- 1) 2np (1))65))
where dz/D - (k) because we assume D - oc. We observe that B 1/22 fits the NN trained on one skill (see Fig. 11 in Appendix 1), and the calibrated model predicts emergence in the n, = 5 system (Fig. (a)):: suggesting that the dynamics of leature-learning Ok in 2-layers NNs is similar to that of parameter learning (a&b)) in simple multilinear model. For further intuition of the extended model, see example of time emergence an NN in Appendix G.
5.2 Data point emergence
Our multilinear model can learn the kt skill with single observation of the skill because the skill functions Ohe are built in (see Corollary in Appendix C.2). NNs, without the fixed basis functions, must 'dscovvr'' each 9k. which requires multiple samples from the 1tth skill.
Extended model. To make our model a D2-shot learner, we extend by replacing Is with the ex, basis:
De Σ
fr 2; 0 B)
Σ ak (T)
B (T),,(()))
(15)
where the matrix B E RND. is an extension of b E RN in Eq. (9), De is fixed scalar, and (x)( (0, 1jnctts + are functions with the following properties:
Ex]== ow: +k, =0,
Σ 1=1 VD.
Ekil gk.
(16)
The first property states that es's, when I k. are orthonormal in X. The second property asserts that, similar to gl (Eq. (2)), 6x,1 is non-zero only when / = k, and fitting of the h skill only occurs among ek, keeping the skills decoupled. The third property states that 9k can be expressed using ex,1-
For the tthh skill, the extended model overfits ge when there are fewer observations (d&) than the dimension of the ex, basis (D.), and fits gu when de De. making our model D. shot learner.
De shot learner. we initialize the extended model in Eq. (15) with sufficiently small initialization and if the conditions in Eq. (16) are satisfied, then the skill strength after training (T' - oo) on D datapoints is
R₂ Ro = { (1-V
: dl < De dg 2 De-
(17)
S
The number dę is the number of samples in the training set for the whh skill (i.e., datapoints with gl (i, x) # 0).
Proof See Appendix F.3.
Using Eq. (17), we can calculate the emergence of Re/S S as a function of D. Note that Eq. (17) similar to the model in Michaud et al. [18] in that, to learn skill, the model requires a certain number of samples from the skill.
7

---

The derivation of Eq. (17) follows trivially from the dynamics of the extended model (Eq. (15)) and well-known results in linear/kemel regression [23-27]. To be more specific, the model finds the minimum norm solution as if we performed ridgeless regression 9 with basis functions [ex,,,-- See Appendix F.3 for details.
We observe that D. = 800 approximates the data emergence for the n. = 1 system (see Fig. 11 in Appendix 1) and also the emergence for ns 5 system (Fig. 1(b)), suggesting that the NN discovers Ih when it observes De samples from the hthh skill.
5.3 Parameter emergence
Since our multilinear model has gs's as the basis functions, it requires only one basis function (2 parameters) to express skill (see Corollary Appendix C.3). A 2-layer NN cannot express skill with single hidden node (i.e., a hidden layer with width 1); it requires multiple hidden nodes to express single skill.
Extended model. To compensate for the need for multiple hidden nodes in expressing one skill, extend our model similarly to Eq. (15). Because the number of parameters is now bottleneck, we ensure the model has N basis functions (ex,'')):
ΣE No au (T
1; B)
Σ ag (g(T)) (T)e, (1,
(18)
where N₂ is the number of basis functions needed to express a skill, quotient is L(N - 1)/Ne] + and remainder is such that (q 1) + N. In short, the N basis functions are
[er,1, N1, 1, ... 62,N.
6q.,,'- [.,r).
(19)
Similar to Eq. (16), the basis functions satisfy the following properties
No
1
Ex I=k
I [ex,er)) ow, ex kk x) = 0,
Σ
VN
CEI
gk-
(20)
1=1
Ne basis functions for a skill. for a given N becomes
For the extended model in Eq. (18), the skill strength at T, oo
: k > k 9
Rx(00)
5
(21)
5 : k < q.
Proof See Appendix F.4.
The model can express the 4thh skill based on the number of available basis functions for the given skill (Eq, (21)). For example, skills with k < q have all No basis functions (e,,1,-* , ..,,N.] to express the ttth skill (Eq. (20)), while for k: = q, only of the N₂ basis functions are available.
We observe that No 4 fits the parameter emergence for the n. 1 system (see Fig. 11 in Appendix I) and also the emergence for the n, = 5 system (Fig. I(c)), suggesting that the NN requires 4 nodes in expressing 9k. The results also suggest that an NN, while lacking the ordering of basis functions (Eq. (19)), prefers to use the hidden neuron in fitting more frequent skills. The 'preference' toward frequent skills agrees with Fig. 1(a) where the NN learns more frequent skills first. Note that for the parameter emergence experiment, Adam [28] was used, instead of SGD, to increase the chance of escaping the near-flat saddle points induced by an insufficient number of parameters.
5.4 Time emergence in transformer
To test whether our conceptual framework extends to other architectures, we perform a time emergence experiment with transformer (Fig. 4). Note that the emergent time Temerge when the skill strength is sufficiently larger than 0 follows the same power-law relationship as Eq. (11): Temerge (k) x k0+11 (see Fig. in Appendix for a discussion on emergent time). This suggests that, in the multitask sparse parity setup, other architectures may follow similar decoupled dynamics (Eq. (11)) and the consequent scaling laws (Section 4) and emergence (Section 5). An in-depth study of these findings across different architectures is left for future work.
8

---

h =
k= 2
==3
k=
k
1.0
10a
Tomerue (k)
R
0.5
104
Tomergel (k) k
0.0
10a
104
10
106
1
2
3
4 5
Skill index k
Figure 4: Transformer on multitask sparse parity task. We trained transformer on the multitask sparse parity task with 0.9; see Appendix for details. Left: An example of the time emergence (measued in steps) for the transformer in the n, = 5 setup. See Appendix I for enlarged plots showing the saturation of each skill in linear scale. Right: The htth skill's emergent time Temerge (k) (i.e. R&. (Temerre (k))/S S = 0.05) function of k (error bars indicate 1-standard deviation over 5 runs). The emergent times follow power law of gatl, following the same relationship in the multilinear model (Eq. (11)).
5.5
Limitations of the multilinear model
The strength of our extended multilinear model comes from the decoupled dynamics for each skill: leading to the prediction of the time, data, and parameter emergence with single calibration. The weakness of our model is that simplifies the more complex dynamics of NNs.
Time emergence. We note that the NN and the multilinear model emerge similar instances, but the NN takes longer to saturate fully. This because, for a given skill, the dynamics of the NN not one sigmoidal saturation but sum of multiple sigmoidal dynamics with different saturation times. To express the parity function, the NN must use multiple hidden neurons, and the skill strength can be divided into the skill strength from each neuron whose dynamics follow a sigmoidal saturation. Because of the non- non-linearity and the function it expresses, each neuron is updated at different rates, and the slowly saturating neurons result in a longer tail compared our multilinear model. For an example, see Fig. 8 in Appendix G.
Data point emergence. Our extended model (Eq. (17)) deviates from NNs when dg < De and NNs show
abrupt change in R2 function of D. This is because model asserts strict decoupling among the skills: even a few dę will contribute to learning 9k from Êx This differs from the NN, which lacks strict decoupling among the samples from different skills. We speculate that because NNs can perform benign [29] or tempered [30] overfitting, they treat a few data points from less frequent skills 'noise' from more frequent skills: requiring more samples to learn the infrequent skills.
Parameter emergence. Note that Fig. 1(c) has high variance compared to other emergence plots in Fig. 1; this is because the NN sparsely, over many repeated trials, uses the hidden neurons to learn less frequent skills over more frequent ones (see Table 5 in Appendix for an example of such outliers). Because NNs are less strictly biased toward frequent skills than our model, speculate that initial conditions favoring less frequent skills may contribute to the outliers.
Discussion and conclusion
This work demonstrated scaling laws and predicted emergence in 2-layer MLP using tractable multilinear model. We found that representing skills as mutually exclusive functions leads to the decoupled dynamics, resulting in the scaling laws observed in a 2-layer MLP. The layerwise structure leads to emergent (sigmoidal) saturation of the skill strength, similar to what observed in 2-layer MIPs.
Despite lacking explicit skill functions, NNs exhibit similar emergence patterns. We speculate that the model's layerwise structure and power-law frequencies of the skills induce stage-like dynamics

---

(Appendix D) in NNs. The parameters relevant for expressing more frequent skills are updated significantly faster than those for less frequent skills. When skill 'discovery' operates on different time scales with minimal interaction, the skill dynamics effectively become decoupled, justifying our model setup.
Our results suggest a link between feature learning and emergence [6] driven by decoupled. stage-like dynamics. The layerwise dynamics leading to sigmoidal saturation may also disentangle the problem into skills (features) of varying importance (frequencies). Then feature learning, or discovering the basis functions that describe the target function [31, 32] (for recent studies, see [33-38],, likely occurs in stages. Investigating this connection through layerwise dynamics is left for future work.
Similar to many prior works (see, e.g.. [20, 18]), studied simple model on an idealized power- law distributed dataset. Also, our model cannot capture the complex non-linear interactions among multiple skills but express any linear superposition of skills. In future work, "complex skills' in language as a superposition of linearly independent skills. By validating our findings in language tasks, aim to contribute to broader understanding of how neural networks acquire and exhibit complex behaviors.
will explore
7 Related works
In this section, we review the literature on scaling laws and emergence in NNs. Focusing on data scaling, Hutter [20] develops model with a discrete set of features. Under the assumption of power-law distribution of features, this model demonstrates that the error decreases as power law with increasing data size. In a related vein, Michaud et al. [18] propose a model of neural scaling laws which the loss decomposed into a sum over 'quanta'. Their model aims to reconcile the apparent discrepancy between loss metrics' regular power-law scaling and the abrupt development of novel capabilities in large-scale models. Various other models for neural scaling laws have been proposed in recent research, including connecting neural scaling exponents to the data manifold's ' dimension [39] and their relation with kernels [40], proposing solvable aandom-fcature models [41, 21J, and developing data scaling models using kernel methods [42, 43, 25).
Closely related to the study of neural scaling laws is the understanding of emergent abilities in large language models. Several studies [1-4] document examples of such emergent abilities. Arora and Goyal [44] propose a framework for the emergence of tuples of skills language models, which the task of predicting text requires combining different skills from underlying set of language abilities. Okawa et al. [45] demonstrate that capability composed smoothly scaling skills will exhibit emergent scaling due to the multiplicative effect of the underlying skills' performance. Other works related to the skill acquisition include Yu et al. [46], who introduce a new evaluation to measure the ability to combine skills and develop methodology for grading such evaluations, and Chen et al. [47], who formalize the notion of skills and their natural acquisition order in language models.
10

---

Acknowledgements
NF acknowledges the UKRI support through the Horizon Europe guarantee Marie Sklodowska-Curie grant (EP/X036820/1) SL was supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIT) (No.2020R 16.22020R1AAA1D0 A5A10061126), We thank Charles London, Eric Michaud, Zohar Ringel, and Shuofeng Zhang for their helpful comments.
References
[1] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:187711901, 2020.
[2] Deep Ganguli, Danny Hernandez, Liane Lovitt. Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova Dassarma, Dawn Drain, Nelson Elhage, et al. Predictability and surprise in large generative models. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1747-1764, 2022.
[3] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garviga-Alonso, et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint: 220..44615.. 2022.
[4] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint: 2266.0762,, 2022.
[5] Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo. Are emergent abilities of large language models mirage? Advances in Neural Information Processing Systems, 36, 2023.
[6] Usman Anwar, Abulhair Saparov, Javier Rando, Daniel Paleka, Miles Turpin, Peter Hase, Ekdeep Singh Lubana, Erik Jenner, Stephen Casper, Oliver Sourbut, Benjamin L. Edelman, Zhaowei Zhang, Mario Günther, Anton Korinek, Jose Hernandez- Lewis Hammond, Eric Bigelow, Alexander Pan, Lauro Langosco, Tomasz Korbak, Heidi Zhang, Ruiqi Zhong. Seán Ó hEigeartaigh. Gabriel Recchia, Giulio Corsi, Alan Chan, Markus Anderljung. Lilian Edwards, Yoshua Bengio. Danqi Chen, Samuel Albanic, Tegan Maharaj. Jakob Foerster, Florian Tramer, He He, Atoosa Kasirzadeh, Yejin Choi, and David Krueger. Foundational challenges in assuring alignment and safety of large language models. arXiv preprint: 2404.09932. 2024.
[7] Trenton Bricken, Adly Templeton, Joshua Batson, Brian Chen, Adam Jermyn, Tom Con- erly, Nick Turner, Cem Anil, Carson Denison, Amanda Askell, Robert Lasenby, Yifan Wu, Shauna Kravec, Nicholas Schiefer, Tim Maxwell, Nicholas Joseph, Zac HatfieldDoodds, Alex Tamkin, Karina Nguyen, Brayden McLean, Josiah E Burke. Tristan Hume, Shan Carter, Tom Henighan, and Christopher Olah. Towards monosemanticity: Decomposing language models with dictionary learning. Transformer Circuits Thread, 2023. https:/trrassfrmmer wttppp//22/////ooommtmttfeeeeeee
[8] Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling predictable, empirically, arXiv preprint: 17tprin::::11.... 1712000099 2017.
[9] 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 preprimt:2001.0885 2020.
[10] Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. arXiv preprint: 1909. /2673, 2019.
[11] Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B Brown, Prafulla Dhariwal, Scott Gray, al. Scaling laws for autoregressive generative modeling. arXiv 2reprint:0110.44701 2020.

---

[12] Mitchell A Gordon, Kevin Duh, and Jared Kaplan. Data and parameter scaling laws for neural machine translation. In
Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih, editors, Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, pages 5915-5922, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguisties.
[13] Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transform- ers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pages 12104-12113, 2022.
[14] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbi, Aidan Clark, al. Training compute- -ptpual-optimal large language models. arXiv preprint:2203, Seprrint:203.1155666 2022.
[15] Vivien Cabannes, Elvis Dohmatob, and Alberto Bietti. Scaling laws for associative memories. arXiv preprint urXiv:2310.029666 2023.
[16] Gregor Bachmann, Sotiris Anagnostidis, and Thomas Hofmann. Scaling mips: A tale of inductive bias. Advances in Neural Information Processing Systems, 36, 2024.
[17] Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Hidden progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systems, 35:21750-21764, 2022.
[18] Eric Michaud, Ziming Liu, Uzay Girit, and Max Tegmark. The quantization model of neural scaling. Advances in Neural Information Processing Systems, 36, 2023.
[19] Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dy- namics of learning in deep linear neural networks. Proceedings of the International Conference on Learning Representations 2014, 2014. arXiv:1312.6120.
[20] Marcus Hutter. Learning curve theory. arXiv preprint: 2tpprinn:202.040744: 2021.
[21] Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. A dynamical model of neural scaling laws. arXiv preprint:2402.0 01092, 2024.
[22] Tamay Besiroglu, Ege Erdil, Matthew Barnett, and Josh You. Chinchilla scaling: replication attempt. arXiv preprint:2404.110000 2024.
[23] Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature communications, 12(1):2914 2021.
[24] Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Kernl alignment risk estimator: Risk prediction from training data, Advances in Neural Information Processing Systems, 33:1 1568--5775,, 2020.
[25] Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34: 14110111-10143, 2021.
[26] Ouns El Harzli, Bernardo Cuenca Grau, Guillermo Valle-Pérez, and Ard A Louis. Double- descent curves in neural networks: a new perspective using gaussian processes. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 11856-11864, 2024.
[27] James B Simon, Madeline Dickens, Dhruva Karkada, and Michael DeWeese. The eigenlearn- ing framework: A conservation law perspective kernel regression and wide neural networks. Transactions on Machine Learning Research, 2023. urXiv:21
[28] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint: 1412. 6980, 2014.
[29] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):3003-330770 2020.
12

---

[30] Neil Mallinar, James Simon, Amirhesam Abedsoltan, Parthe Pandit, Misha Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: Toward a refined taxonomy of overfitting. Advances in Neural Information Processing Systems, 35:1 15:1182-1195, 2022.
[31] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8):1798- 1828, 2013.
[32] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning, Nature, 521(7553):436, 2015.
[33] Greg Yang and Edward J Hu. Tensor programs iv: Feature learning in infinite-width neural networks. In International Conference on Machine Learning, pages 11727-11737. PMLR, 2021.
[34] Alexander Atanasov, Blake Bordelon, and Cengiz Pehlevan. Neural networks kernel learners: The silent alignment effect. arXiv preprint arXiv:2111.0003: 2021.
[35] Arthur Jacot, Eugene Golikov, Clément Hongler, and Franck Gabriel. Feature learning in l_2- regularized dnns: Attraction/repulsionn and sparsity. Advances in Neural Information Processing Systems, 35:6763-6774 2022.
[36] Blake Bordelon and Cengiz Pehlevan. Self-consistent dynamical field theory of kernel evolution in wide neural networks. Advances in Neural Information Processing Systems, 35:32240-32256. 2022.
[37] Inbar Seroussi, Gadi Naveh, and Zohar Ringel. Separation of scales and a thermodynamic description of feature learning in some cnns. Nature Communications, 14(1):908, 2023.
[38] Hugo Cui, Luca Pesce, Yatin Dandi, Florent Krzakala, Yue M Lu, Lenka Zdeborová, and Bruno Loureiro. Asymptotics of feature learning in two-layer networks after gradient-step. arXiv preprint wrXiv:2402.049800 2024.
[39] Utkarsh Sharma and Jared Kaplan. Scaling laws from the data manifold dimension. Journal of Machine Learning Research, 23(9):1-34, 2022, arXiv:2004. 10802.
[40] Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. arXiv preprinn:2/02.006701 2021.
[41] Alexander Maloney, Daniel A Roberts, and James Sully. A solvable model of neural scaling laws. arXiv 2reprint:2210.16859, 2022.
[42] Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymptotic learning curves of kernel methods: empirical data versus teacher-student paradigm. Journal of Statistical Mechanics: 2020.
Theory and Experiment, (0200(2)):1444
[43] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pages 1024-1034, PMLR, 2020.
[44] Sanjeev Arora and Anirudh Goyal. A theory for emergence of complex skills in language models. arXiv nreprint:2307.159366 2023.
[45] Maya Okawa, Ekdeep $ Lubana, Robert Dick, and Hidenori Tanaka. Compositional abilities emerge multiplicatively: Exploring diffusion models synthetic task. Advances in Neural Information Processing Systems, 36, 2024.
[46] Dingli Yu, Simran Kaur, Arushi Gupta, Jonah Brown- Cohen, Anirudh Goyal, and Sanjeev Arora. Skill-mix: flexible and expandable family of evaluations for ai models. arXiv 270p71nt:2310.15567, 2023.
[47] Mayee Chen, Nicholas Roberts, Kush Bhatia, Jue Wang, Ce Zhang, Frederic Sala, and Christo- pher Ré. Skill-it! a data-driven skills framework for understanding and training language models, Advances in Neural Information Processing Systems, 36, 2023.
13

---

[48] Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets, arXiv:2201.02177, 2022.
[49] Irina Gennad evna Shevtsova. Sharpening of the upper bound of the absolute constant in the berry-esseen inequality. Theory of Probability and Its Applications, 51(3):549-553, 2007.
[50] Hugh L Montgomery and Robert C Vaughan. Multiplicative Number Theory I: Classical Theory. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2007.
14

---

A Glossary
Normalization constant for Pa such that P.(k) Ak (a+(++)
T
Time step
D
Number of data points
N
Number of parameters (skill basis functions in the model for the multilinear model; the width of hidden layer for MLP)
C
The computation cost T x N
Ts
The number of skills in the multitask sparse parity problem Random variable of the control bits Random variable of the skill bits Probability of skills (control bits)
I
X
P.
Po
Probability of skill bits
The target scale or the norm of the target function Skill strength of the 4th skill (Eq. (7))
Rx
Total (generalization) loss Empirical loss for D samples
((D)
Lk
Skill loss the kd skill (Eq. (6))
dp
Number of observation of the tt skill (i.e. number of training points
(i,z) with O (1, x) & 0)
f
Target function
10 + (-S,S) $} (Eq. (4))
The tthh skill basis function 9k {0, 1m (-1,0,11 1} (Eq. (2))
gk
15

---

Table 3: Representation of the multitask sparse parity as presented in [18]. The control bits are one-hot vectors encoding a specific parity task. The frequency of the different tasks follows power- law distribution. this example, there are nt column is the resulting parity computed from m 3 bits (highlighted in colors). The multitask dataset provides a controlled experimental setting designed investigate skills.
tasks, and skill bits are length 74, 15. The
Control bits
Skill bits
y
10000000000
I 110001000000100 010100100001000
01000000000
00100000000
001101010110101
1
00000000001
10001 000000001001100
B Background
In this section, we review the multitask sparse parity dataset, as described by Michaud al. [18] and discuss the nonlinear dynamics of two-layer linear networks, following the work of Saxe et al. [19].
B.1 Multitask sparse parity
The sparse parity task be stated as follows: for a bit string of length ny. the goal is determine the parity (sum mod 2) of a predetermined subset of m bits within that string. The multitask sparse parity [18] extends this problem by introducing n, unique sparse parity variants in the dataset. The input bit strings have a length of n. + n4-- The first nt, bits function as indicators by assigning a specific task. The frequency of the distinct parity tasks follows rank-frequenc distribution with inverse power law relation (power-law distribution). The last ni bits are uniformly distributed. This sets a binary classification problem {0, - {0, 1} where only single bit of the initial n. bits is nonzero. In Table 3, the many distinct parity tasks represent different skills. 2
The proposal in [18] aims to reconcile the regularity of scaling laws with the emergence of abilities with scale using three key hypotheses: (i) skills, represented as a finite set computations, are distinct and separate: (ii) these skills differ in their effectivvnesss, leading
ranking based on their utility to reduce the loss; and (iii) the pattern how frequently these skills are used in prediction follows power-law distribution. Interestingly, the multitask problem has consistent pattern across scaling curves: each parity displays a distinct transition, characterized by a sharp decrease in loss at a specific scale of parameters, data, or training step. Such sudden shift occurs after initial phase of no noticeable improvement, leading to reverse sigmoid-shaped learning curves, Michaud et al. [18] empirically show that for one-hidden-layer neural network with ReLU activation, trained using cross-entropy loss and the Adam optimizer, these transitions happen at different scales for distinct tasks. This results smooth decrease in the overall loss as the number of skill levels increases.
B.2 Nonlinear dynamics of linear neural network
Saxe et al. [19] have solved the exact dynamics for two-layer linear neural networks with gradient descent under MSE loss (Fig. 5(a)). The dynamics decompose into independent modes that show sigmoidal growth at different timescales (Fig. 5(c)). The setup assumes orthogonal input features X E di and onput-output correlation matrix E IR xdy for target output f (X) Rda;
Ex [X,X,] 8zj.
== Ex
X (X)]
(22)
NNot that here we follow the evenfodd parity convention used [18]. ie.. (0, 1). instead (1,-1) as used the main text. TTo be specific, it is under gradient flow the continuous limit of full batch gradient descent.
16

---

fi(
A =.0
A== 0.5
) 0.25
21
:
R Rdixds
Rd
:
1.0
dd
fdz (x)
0.8
0.6
(a) Linear neural network
0.4
wie 2
f(x)"
0.2
ad, as
0.0
fxx)"od
25
50
75
100
(h) Independent modes
(c) Dynamics of modes
Figure 5: Nonlinear dynamics of linear neural networks. (a): A two-layer undercomplete linear neural network, which is multiplication of two matrices, where d2 < d1 and d2 d3. (b): The d2 independent modes of dynamics for linear neural network (Eq. (24)). The product parameters Og learnable parameters and vectors üg. U obtained from SVD of the input-output correlation matrix Σ (Eq. (22)). (c): The temporal evolution of agby under gradient descent, which follows sigmoidal growth (Eq. (25)). Note that smaller d the singular value of Σ results in more delayed saturation of azbb.
By performing SVD (singular value decomposition) on input-output correlation matrix Σ UAV, the target function f* Rdi R2 becomes:
(x)
Σ uk akAuu
UTAV = Ex [XF
(23)
where E Rdi,un E RRds are the row vectors of U, V and X E lK are the singular values of A. Saxe et al. [19] have shown that the dynamics of two-layer (one-hidden-layer) undercomplete (the width of the hidden layer smaller than the width the input and output) linear neural network decomposes into that of the following 'modes':
" fxr; b) aubaub
1: (1,2, dd...
(24)
where aue by
the parameters. Note that Eq. (24) are d2 decoupled functions oi f(x) Rd R (Fig. 5(b)). Assuming small and positive initialization (0 < as (0)bb, (0) & Ag). the dynamics of Eq. (24) under gradient descent with learning rate 7) can be solved analytically: the product of parameters oghg grows sigmoidally with saturation time proportional A ((c):
Og (T)
(25)
+
e 2npeet
(1(
Using the analytic equation of the multilinear model. Saxe et al. [19] have empirically demonstrated that the dynamics of both linear and nonlinear neural networks closely resemble that of the multilinear model (Eq. (25)).
17

---

C Derivation of the multilinear model
In this section, we provide derivations of how the skill loss of our multilinear model evolves with given resource: time (Lemma 1), data (Corollary 1), and parameters (Corollary 2). Note that two corollaries for data and parameters (Corollaries and 2) follow from the decoupled dynamics (Lemma I).
C.1 Decoupled dynamics of the multilinear model
Lemma 1. Let the multilinear model Eq. (9) be trained with gradient flow on D i.i.d samples for the setup in Section (input distribution: Eq. (1), target function: Eq. (4), and MSE loss: Eq. (5)). Let N be a skill index the multilinear model and the input distribution (k S nz)). Then assuming the following initialization as (0) = by. (0) and O < (0) < 8, the dynamics of the k skill strength (Rt) is
S
RT)
(26)
1 +
S
1)
e 28
(0]
and the skill loss is
5
(T(T)
(27)
2 1
S
-1)
Rx(0)
where 17 the learning rate and dg the number of observations with gk k. x(ع)) #
Proof For j = 1.... D, denote (26)) x()) be the jth data point the training set. Then the empirical loss for D datapoints is given
D
((D)
Σ
f(10),200))
(28)
2D
1=1
We note that
(1(10),000)) (100)-((1 s(i6) ,(16))x((01)
Σ (S anbr Ia (i0) (i .010))
(S a bucn )a geas (i0) z21)/2
= (S amm buor)
as gi. E {1, -1} and gx(i,)) 0 for i o k. So if we denote d, the number of data points with
g(i) = k. then we can conclude
1
m2 de(S axbx)²
(DD)
Σ SS (no))))))
(29)
2D
2D
j=1
which is the decoupled loss in the main text (Eq. (11)). Using the gradient descent equation and Eq. (29), we obtain
day
dLD
(30)
di
dus dx ba(arbx S)-
n D
(31)
Likewise, we can obtain the equation for by as
dbs
ds a larbb S).
n
(32)
dt
D
18

---

Because of symmetry between and (See Appendix B.2 or [19]), assuming ax(0) by (0), and (x(0))b (0) >> 0 results in (T) (T) for all T. The equation for R₁ agbb
dRx dt
dak by + ag
dbg
dt - de (b) (a S)
11 dt
(33)
D
2n da
R& (Rx S).. D
(34)
Assuming (0)bb)((0) < S, solve the differential equation to obtain
S
RT(
(35)
1 +
9
1)
2n5 2T
The equation for L* follows from Eq. (10).
C.2 One-shot learner
Corollary 1. For the setup Lemma I, the 1tth skill loss (Cx) at T,N + xo is
Lx(()) { (s- (5-
:4 > 0
(36)
:4. 0,
where dy is the number of whth skill's 's observations.
Proof The corollary follows directly from Lemma 1. By taking T, - oc.
Ra( {
d4 > 0 d =0
(37)
(0)
We obtain the result by using the relationship between R4 and La in Eq. (10).
C.3 Equivalence between basis function and skill
Corollary 2. Let the multilinear model Eq. (9) be trained with gradient flow on i.idd samples for the setup in Section (input distribution: Eq. (1), target function: Eq. (4), and MSE loss: Eq. (5)).
Assume o₂ (0) = (0), < (0)),(()) < S, and that the model has the N most frequent skills as basis functions. Then R2 for the hh I n, skill at T, + 00 is
N k>>N
(x( S2/2
(38)
Proof The corollary follows directly from Lemma 1. By taking T, D + oc.
(x() = { S
: N
(39)
k
We obtain the result by using the relationship between R2 and Cs in Eq. (10) and R+(0) < S.
19

---

D Stage-like training: intuitive derivation of the scaling laws
Even though we provide more detailed (Appendix E) and rigorous (Appendix J) derivation of the scaling laws, less general yet more intuitive solution aids in understanding the scaling laws of our model and NNs. In this section, define stage-like training one skill is completely learned before the next skill initiates learning (Fig. 6(a)) and state the conditions for it to occur. We provide an example of how stage-like training results in the time scaling law and explain how the model in Michaud et al. [18] may arise from the NN dynamics. Finally, we discuss the stage-like training's role in emergence in NNs.
1.0
13.0
kT=
0.8
11
k k=
12.5
k
Rx(0)
0.6
12.0
PP.1 O(c)
0.4
11.5
0.2
10
(e)
(c)
11.0
0.0
10.5
0
50
100
150
200
0
50
100
150
200
T
(a) Emergent and saturation time
(b) Loss change between emergences
Figure 6: Stage-like training. The multilinear model is trained on the multitask sparse parity problem 5. (a): Skill strength of the model as function of time. The emergent (e) (e) is the time required for the ttth skill to reach R4 S = The saturation time Tg (e) time Th
with a 0.6 and
(*)
the time required for R& R₂/S /S to saturate from to 1 c. The model shows stage-like training if
the emergent time interval 24411 (c) Tr. (e) (c) is larger than the saturation time =h (c) for sufficiently
(e)
small (0.05 in the figure). (b): The loss a function of time for the same system as (a). For
stage-like training, the change in the loss for the hthh emergence is Pa ( + O(e) and the interval
for the next emergence is ()( ((4) (e) Th (e).
D.1 Stage-like training
When model exhibits emergence behavior when saturation skill occurs abruptly after delay and the intervals between each emergence are sufficiently large, the model admits stage-like training. The multilinear model (sigmoidal saturation skills strength, Eq. (11)) in the multitask sparse parity dataset (power-law decay of skill frequencies, Eq. (1)) can satisfy such conditions: In Fig. 6(a), we observe the stage-like training in time in which one skill saturates (reaches Re/S 1) before the next skill initiates its emergence. To quantify this behavior, we define two intervals for each skill (see Fig. 6(a)):
The emergent time (e) (c): the time for R&/S S to reach e;
(4) The saturation time T (e): the time for R₂/S S to saturate from to 1
Using the dynamics equation (Eq. (11)) and that dz/D - Pa(k), the emergent time and saturation time of the ktth skill becomes
(c)
1 In
x 1
(0) = IPP (K)S
(1-1) x b
(k)S
T
(40)
For sufficiently small initialization (Rx (0) < S). we get stage-like training:
T (d) < (c) (e) = (e) (c), * E
(41)
where the model finishes learning (saturating) the th skill before starting to learn (emerging) the next skill.
20

---

D.2 Time scaling law from stage-like training
Assuming our model satisfies the stage-like like training for all & of interest, we can derive the time scaling law from the stage-like training.
At (e) (e), because of stage-like training, all skills with index up to but not including & have saturated (Rick Re 5), or equivalently Lick s (Eq. (10)). The total loss, the sum of 2 weighted by Pa(i) x (a+t)) (Eq. (6)), becomes Σj=e P. = j),5²/2 (Fig. 6(b)). The saturation of the 4th skill results in a loss difference of Pa(I k) Thus, we obtain
AC
P. k) hj ()
A (a+1)
k-
~
(42)
C
Sx j-
-ak + +0k
(43)
Accordingly, the emergent interval between the lt and h + skills relative to the (e) (c) is
AT
(c) - Th (e)
(e)
(k: + 1)at1 kat1
(44)
T
Tk (c)
ko+1
(a 1)k- 1 + 0(k
(45)
Assuming l > and combining Eq. (43) and Eq. (45) to the largest order, we have the equation for the power-law with exponent -a/(a + in Fig. 2(a):
AC a AT
(46)
a+17 C
If the stage-like training holds for any resource (e.g.. time, data, or parameters), the scaling law can be derived using the ratio of change in loss per skill (Eq. (43)) and the ratio of change with respect to the resource (given by the emergent time in Eq. (45)). The quanta model in Michaud et al. [18] is an example where the stage-like training holds for all resources.
D.3 Discussion the effective decoupling of skills in neural networks
In Section 5, we have empirically demonstrated that the multilinear model predicts the emergence of a 2-layer NN (Fig. 1). In Section 6, briefly diseussed why NNs, despite their lack of the decoupling among the skills, behave similarly to the decoupled model with 9&8 as fixed basis functions: the stage-like training NNs induced by the model's layerwise structure and power-law frequencies of the skills effectively decouples the skills. In this subsection, we extend the discussion in more detail.
In NNs, even though 9&s are 'discovered' (feature learned) by non-tractable dynamics, we speculate that similar stage-like dynamics also hold in 'discovering' (feature learning) 94s: parameters 'useful' for expressing more frequent skills will be updated significantly faster than parameters useful for expressing less frequent skills.
skill discovery and saturation dynamics operate different time scales (stages), with negligible interaction among the skills, the skill dynamics become effectively decoupled. Because the dynamics are decoupled stages, NNs repeat the feature learning process - using the limited resource (time, data, parameters) to express the skill - for all skills with each iteration varying only in the scale of the resource (e.g. training time, number observations, and number hidden layer neurons): resulting in similar emergence to our multilinear model.
more concrete understanding of our speculation that feature learning also occurs in stages due to layerwise structure is left for future work.
E Derivation of the scaling law exponents
This section provides detailed derivation of the scaling laws up to a rigor common in physics and engineering. For example, we approximate the Riemann sum as integral or treat k the number of
21

---

skills, as differentiable parameter. For more general and rigorous derivations including the prefactor constants, see Appendix J. Instead, for more intuition and the relationship to the quanta model in Michaud et al. [18], see Appendix D.
Table 4: Summary of the scaling laws. The leftmost column shows the bottleneck of the scaling law. The middle three columns show the resource values in terms of the bottleneck (either taken to infinity or proportional to the bottleneck). The last column shows the scaling exponent for the loss as power-law of the bottleneck where a + the exponent of the Zipfian input data (Eq, (1)).
Bottleneck
Time
Data
Parameter
Exponent
Time (T)
T
8
-a/(ar +
Data (D)
xc
D
06 N
-a/(a + +1)
Parameter (N)
00
-a -a/(a (a(++2)) +
Compute (C)
(lo+1)/(+22)
0
(1/(a-2)
E.1
Time scaling law exponent
To derive the time scaling law exponent, assume the time the bottleneck and take N, D co. By using the decoupled dynamics of each skill loss (Lemma 1),
S
L*
(47)
2.
2
11
s R2(
-1)
e 22 ST
Noting that dz/D - Po(k) as D + 0o, where Pk(k) = Ak (a+1), we have
S
C#
(48)
2 1
g R2(0]
-1)
22nAk-(0+D88)
This is function of k (a(+)) only, suggesting the decoupling dynamics for each skill. Thus,
dLs
dLx
(49)
dT
(a
1)T dk
Using Eq. (6) and taking N, n, at the same rate,* we can approximate the loss integral instead of sum over k:
L L
lim [ N
N
Ak (a+1) Lxdk,
(50)
where A is the normalization constant for P.. We can differentiate the loss and use Eq. (49) to express the equation in terms of k:
dL lim
Ak 1o+1) dLs dT
I,
N
dLx
dk
lim N
Ak-a
dk.
(51)
dT
(a 1)T
dh
Integrating by parts, we obtain
d. lim
a (a+ 1)T f Ak (a+1))
lim
Lydk
(52)
dT N Noo
(a + 1)T
N
lim O (N-aa 1 [N-a + +
(53)
N 000
Tet
(a 1yT
The first term goes to N + oo and the second term goes to exponentially faster compared to the last term for T > 1, which leads to the scaling law with exponent -a/(a + 1):
dC(T) L(T) a T
df
(54)
WW take N and nt, to oo at the same rate since we do not want the number of parameters to be a bottleneck in this setup.
22

---

dx > 0 : : 0. Finite N correction for small a. In Fig. 7, we observe that our model with = 0.1 deviates from the expected power-law with exponent a/(a + 1). The deviation can be explained by the antiderivative term in Eq. (52):
0.1
0.3
a=0.5
0.7
10
simulation
10
poier (owooorod)
power law
10
10
102
10a
Figure 7: Scaling law and corrected predictions. A simulation of our multilinear model with N = 50, 000 (solid), a scaling law with exponent -a/(a + 1) (dotted), and a corrected scaling law considering finite N (dashed, Eq. (56)). The finite N corrected scaling law better predicts the dynamics, especially for smaller a.
N
S
k
lim (o N N00
(o(N-a)) T
Te )) (55)
1
lim 100
0
1 2(a + 1) (1+ 5/Rm(0) -1 2nSA (11IT)
T
The second term (k 1) goes to 0 faster than O(T for sufficiently larger T but the first term (k: N)) may decay fast enough for finite N and sufficiently small a. For example, N 50, 000 and a = 0.1 leads to N x 0.3, which is not negligibly small.
Assuming finite N and small such that the first term in Eq. (55) is negligglg,,,,,, Eq. (52) as
rewrite
dc
L+Cc
Lo R AN 1/2,
(56)
dT (a+1) T
where we assumed a small initialization S/Rx >>> and sufficiently large number of parameters Na+1 >> T to approximate Le. Because the total loss initialization is L()) S2 /2, Lo is non-negligible compared to the loss for sufficiently small a. Thus considering Le, we obtain the corrected power-law which better approximates the time scaling law (dashed lines in Fig. 7). For a rigorous and comprehensive analysis of the time scaling law, see Theorem 2 and Theorem 3 in Appendix J.
E.2
Data scaling law exponent
In this section, we derive the data scaling law exponent. The data scaling law assumes T + co and + oc with data as the bottleneck. From the decoupled dynamics of the multilinear model (Lemma 1), we can show that our model is a one-shot learner (Corollary 1):
One shot learner. Given that N >> k, T + oo, and dy is the number of samples from the training set with gu () + 0, the th skill loss after training is
Cu(co) - - 5212
(57)
Proof See Appendix C.2.
23

---

Our model requires only one sample from the h* skill to learn such a skill, similar to how language models are few-shot learners at inference. 'Tee model can one-shot learn a skill since has Jk as the basis functions, and the dynamics among different skills are decoupled. A similar one-shot learner has been studied in Hutter [20] where the error depends on a single 'observation' of feature.
Because the kthh skill loss only depends on ds (number of observations for the kth skill), we can calculate the expectation of the skill loss for D data points from P' Pbssereed D) or the probability that dę > 0:
Pobserved (k] D) = 1 - (1 -P(K))
(58)
Using the one-shot learning property (Eq. (57)), the probability of observing the hthh skill (Eq. (58)), and the decomposition of the loss into skill losses (Eq. (6)), the expected loss for D datapoints is
ED [C] = 2
1
Σ
20
(1)(( - (odserved(k))
(59)
k=
1 S A
80
k (a+))) (1 (1)))(
(60)
2
1 5
k-(a))) (1- Ak-(at))) D
A
dk.
(61)
2
where the expectation Ep is over all possible training sets of size D, and A is the normalization
constant such that P(k) Ak((++1) The difference in the loss AC = ED+1 [C] Ep [C] is
AC
1 A A 2
/
k k-(at1) (1- AK AR-(att))
(1-AR-1Op)
((1-AR (1-Ak-(att)) - 1) dk
(62)
2 5² A²
/
Ak b 2((++]) (1-Ak-lat3)) dk.
(63)
We can integrate AL by parts.
1
(a +) (1-AK (1-Al-(at))) D+1700 00
82 AkAk-
AC
2
2(a + +D(+1)(D+))) + 1) J 00
S²Aa
k-(a+1) (1-Ak-(a+))) D+1
dk
S²
000
-aat)) (1- D (1 Ak (at1)) (atti) dl
0 ((1 Pe(1))
2(a + ++((DDD +1)
(a 1)(D+) ED [4 + ta+ D) 1) AC.
In the second line, the first term goes 0 for D > 1. In the last line, we used the expression for AL (Eq. (62)) and Ep [C] (Eq. (59)). Rearranging the equation above and using that D > 1, we obtain the scaling law with exponent caaeneentta/// -a/(a+ 1):
AC
1
(64)
Ep [4]
1 (a + 1)D
(a + 1)
a AD
(65)
= (a+1) D
where in the last line, AD/D= 1/D as the change in the number of data points relative to D is one.
E.3 Parameter scaling law exponent
The parameter scaling law assumes T - and D co, with the parameters N < ny as the bottleneck. Because our model is a one-shot learner (Eq. (57)), learning of the tthh skill only depends on the existence of 9k in the model; the model with [g1, (9,,"". gNl will learn all l < N skills with LE 0.
The La dependence gu is formalized in Corollary 2, which we repeat here.
Few-shot learning is typically discussed in the context of models that have undergone pre- pre-training (see, e.g. (1). We speculate that expanding the basis ga in our framework model aspects of the pre- training process.
24

---

Equivalence between a basis function and a skill. has the N most frequent skill functions as a basis,
Given T, D - oo and if the multilinear model
Ca(oo)
- 5212 k N.
k
(66)
Proof See Appendix C.3.
Using Eq. (66) and Eq. (6), we can express the total loss as function of N:
$
L
Ak-la+1) dk (N + 1)
(67)
2 N+1
By approximating N N for N >> I, we obtain the power-law with exponent -a. -a.
E.4 Optimal compute scaling law
For analytical tractability, we define compute as C == x N. We start from Eq. (12) with D + oo
L ~ / Ak (a- Ak- Lydk + lim
S
JN
//
Ak (a+1) dk.
(68)
2
We can use Eq. (56) to calculate the first term and integrate the last term to get
S N
L x (C(0) + Lc)T a/(at)))) - Lo +
(69)
20
O(T O(TT O(N
(70)
where we used that L())= >> LC and A/(aa) Lc > Intuitively, the approximation shows the tradeoff between T when increased, decreases the loss of the first N skills and N when increased, decreases the loss at sufficiently large T for fixed compute C. For a comprehensive analysis of the approximation above, Appendix J.
Removing the irrelevant constant terms,
T= aa(at) + N
(71)
can use the method of Lagrangian multiplier to obtain
(a 1)+1)-11 + ANN 0,
(72)
-N (a+1) AT 0,
(73)
NT = 0,
(74)
where À is the Lagrange multiplier and C is compute. We can solve the above set of equations to obtain 7 x N or equivalently
T x C(a+1)/(+2))
No (2/(a+2)
(75)
We can plug it in Eq. (71) to get
L x Caa/(a+2)
(76)
This derivation is similar to that of Bordelon et al. [21] (see Appendix N: Compute Optimal Scaling from Sum of Power-Laws [21]). For rigorous derivation the optimal compute scaling law, Corollary 4 and Appendix J.
25

---

Derivation of the extended multilinear model
In this section, we show the derivation for the extended multilinear model.
F1 Gradient flow in the extended multilinear model
Lemma Let the extended multilinear model Eq. (15) be trained with gradient flow on D i.i.d
samples for the setup in Section 2 (inpul distribution: Eq. (I), larget function: Eq. (4), and MSE loss:
Eq. (5)), For the skill index k S N skill index in the multilinear model, let the feature matrix
E R. Dexd for the w skill be
b1 =1 ki x,)))
(77)
and SVD on USV. Assuming that the system is overparametrized (dg < Dc), the gradient on BR Re (BBRI..... B.) is contained the column space of semi-orthooonal matrix U E Dexds:
UTT dBs dBs
(78)
dt dt
Proof Similar to Lemma 1, the total loss can be decomposed into each skill such that the dynamics of B& relies only dg observations of the 1.th skill:
D
f (166) - -(1()) -((1)))0))))))
CD = 2D
(79)
k=1Ø=1
1 The
Sgu(k, - a (o.
(80)
2D
B2y
dg
De
S VD.
2
Σ
- au (e.,))e.,(k,,,bb)
(81)
2D
In the second line, used Eq. (16) that e (1 + k, x) 0 and the orthogonality of gh (Eq. (3)). In the last line, we used Eq. (16) that Ok D. 1/2 11/ Σ, Ck.I. We can find the gradient descent equation of BRG from Eq. (81):
dB
dg D
De Ba.
s DD.
Jeu (
(82)
dt
J=1
/=1
which in the matrix form is
dB
5 VDe
Iaak क
BEaR
(83)
dt
D
where De dimensional vectors B& and $ are [BE,,,... BR,D.] and S] respectively. dB, is contained in im()), which is contained in im(U) (immediate from +b = USV).
illustrates that dt
As (U= Uz, UU acts as identity on image of U, showing that UUT dB, df
dBs de
F22 Conserved quantity of extended multilinear model
Lemma 3. In the setup of Lemma 2, d 1B 12 is conserved over time.
Proof
We can use Eq. (81) to find the equation for as:
dx
D.
da
(k, (0))
(ak B
S VD.
Jear(k,
(84)
j=1
26

---

dx is globally bounded, as it can be expressed in which in the matrix form is
da
11
Bk pp²
5 Bran VD.
(85)
di
D
Then
da
nak
B3 20²"
$ Brar
(86)
dt
D
VD.
dBk
B
(87)
dt
where used Eq. (83) in the last line. Thus, o B is conserved during the dynamics.
F.3 De shot learner
Proposition 1. Let the setup be as that in Lemma 2. Suppose that ag (T) eventually bounded away
from zero, iee. there exists ō > O and M >> O such that T > M > [ax(T)) 2 5. Also assume that U Uomponneeet of Ba)0))x (0) and (0) is negligible. Then the skill strength RR is
Ru(co)= = de < De: dx 2 De:
-11-V1-dd//D d////e
(88)
S
Proof First, we show that dC < 0 with equality only holding when the gradient is 0.
dCx
dCk day dl da dl
De dCk
dBua
+ Σ dBR dl
(89)
dr
dLR dfx dan dan
De dCx dCk
--
1l
Σ dBu, dBu
S..
(90)
The equality holds only when
dLx
daæ
dLx
dBa,i = 0. dt
and
(91)
do
dt
dB
We show that both ag and Bg are bounded throughout whole dynamies. As
C = + Brax
3
2
2 JUT Beax
3 2
(92)
VD.
VD.
for o² the smallest nonzero eigenvalue ΦØ"", where USV. This shows that
5 VDe
UUT
Brak
(93)
is bounded, so UUT Beau is bounded. Meanwhile, in Lemma 2, we showed that (1- (1-UUT) di 0.
so (1 U bounded. This shows that Bgaz is bounded. As aj [B is constant (Lemma 3) and BRarl= = [ax B& is bounded, this shows that both 0ş and [7g are bounded.
The dynamics moving in some bounded region always has at least one accumulation point, which we denote p. We will show that dC, at The function (t) in t is a decreasing differential dt
function which is positive. We also note that
dr2
polynomial expression (at, B&) and we showed that (t) (t)) is bounded. From Taylor's theorem, one can obtain
dCx dt
2 M
inf (t))) S (t 12) Lx(ti)
(t1)
(94)
2
27

---

for M sup dt
Choosing - dCu (41 M-
dt
shows that
dl* (ti)
La((1)
2 inf (x((t)
(95)
2M
dt
and letting t - oc here gives
1
dCk (11) di
lim
lim (Lx(41) - inf Lx(()) =0 Es 10000
(96)
41 +00 2M
so dCs + 0 as f + co. Meanwhile, as is accumulation point of (ax. Bx), dls (p) is accumulation point of dCu (t). (t). As lim dt (t) = 0, the only accumulation point of dCx at (t) zero,
or
which shows that dC* dt (p) = O. We have seen that a |&l and (I-UUT) )x conserved in our dynamics. A quantity conserved in dynamics should also be conserved at p. so p = (a, B) should satisfy the following conditions:
a² - = -
(1, ) (Lemma 3);
(I - -1--0"
(Lemmaa 2);
dCa (a, B) = 0, or equivalently the gradient is 0 at p.
dt
We will solve for p satisfying those three conditions. The third condition is equivalent to that
Ba Ba-- 5 vD.
aUUT
=
(97)
As ag.() is eventually bounded away from zero, we have 0, so
Ba 3
UUT
0.
(98)
VD.
follows that
$
B -=
+ (1 -1-
(99)
VD
and substituting to first condition gives
5
2
a² a
UUT
- (T-UT) (o) (0)
(x) - 10)(
(100)
VD
This is equivalent to a quadratic equation in a², and has following solution of
UUT 3 VDe + (a)(0)) UUT Bx + as (0)² - IUL B.)) a² V-VUVr
(101)
4
2
This shows that there are two candidates for p. with a given as two square roots of Eq. (101) and B determined from a by Eq. (99). It impossible for (t(t) have accumulation points both in regions >> 0 and a < 0, as it would imply (t) 0 happens infinitely many often, contradicting that a eventually bounded away from zero. Thus it follows that (x(t) can only have one accumulation point. As dynamics having unique accumulation point should converge, it follows that
(a, B3) (oo) Ba (oo)).
(102)
One can check that the U coopponen of (2)) is given
(1- UUU
= 11- UU (1,
(103)
and this is bounded by [11 - UU Bx + (0)). so by our assumption this is negligible. Thus, find that B3 (o0) (0o) is the pseude-inverse solution, which is also found by the linear
28

---

model with C,,7 as basis functions. We can calculate Lx (oo) using the result from kemel (linear) regression [23-27] (for summary, see tables 1 and 2 appendix A of [27]). Using the terminology in table of [27], the sample size is dæ; the number of parameters is Des ridge and noise are absent; the eigenfunctions
(x))))x(()) [ ... Ck, D.l: the eigen coefficients are (
SD
(Eq. (16)); eigenvalues are uniform; the learnability is / De for all i; and the overfitting coefficient (1 d Taking into account that we have halved the MSE loss (Eq. (5)), the test loss
52
Lx(00)
(104)
2
Dr
We obtain the result by using Eq. (10).
F,4 No basis functions for skill
Proposition 2. Let the extended multilinear model Eq. (18) be trained with gradient flow on D + op
iid samples for the setup in Section 3 with ns (input distribution: Eg. (1), target function: Eq. (4), and MSE loss: Eq. (5), initialization: that of Proposition 1). For a model with the following
finite N basis functions
[e1.1, C1,No1 62 Eq,r),
(105)
where quotient q = I(N - 1)/NeJ + 1 and remainder r is such that (q - 1)Ne + r= N. The skill strength at T - 00 becomes
k > q: 0 = q:
(x() =
(106)
N:
k <<q q:
S.
Proof Because we have D + oo and because [ex,1, ... Nx,N.] can express 9a (Eq. (20)), it is trivial to show that Rx(x))= = S for k < q. For k q, the gradient descent dynamics (Eq. (83)) leads to
dB₁ 17ak TΦ
[Baa=
5 VN.
(107)
dt
where the matrix & E IRrxde and vector B& E R" are the feature matrix(Eq. (77)) and parameters for the 4thh skill respectively. As D oc, the matrix o6" becomes rank identity matrix scaled by the frequency of the skill:
lim D-000
] (D0T)) Ju Ex.x (k,, X)eu, X)] P(k)o
(108)
Plugging in Φ
dBx.1 (PP(kaa (BELUR
S
(109)
dt
VN.
Assuming the initialization in Proposition 1, we can show that a (2.)) From Eq. (7), the skill strength R4 is
8/ /N, for S
(x0) = Σ
S
Ex
(110)
VN.
(111)
N
where we used Eq. (20) for the linear correlation between ex,y and 9k-
29

---

G Time emergence example in NN
In this section, we discuss an example for the time emergence case (Fig. ((a) in which the saturation of skill in an NN consists of multiple saturating 'modes' as in Fig. 8.
1.0
0.8
0.6
mode
f(i, x)
mode
0.2
NN
Mu
0.0
0
250
500
750
1000
(a) neuron modes for parity function
(b) mode/skill strength
Figure 8: Modes in NN. A 2-layer MLP with ReLU activations with a width of 3 and weight sharing (Eq. (114)) is trained fit the parity function. (a): The skill strength R. because of the last layer's linearity, can be decomposed into skill strength from each hidden neuron or each 'mode' (shown in different colors, Eq. (119)). (b): The skill strength for each mode follows a near-sigmoidal curve with different emergent/saturatien black). Note that different saturation times of each mode result in a deviation from the prediction of the multilinear model with 8 1/3 (dashed black).
times (colors) whose sum results in the total skill strength (solid
Task. We assume an input X E 3x8 (note that we are not using as a random variable) that is all 8 possible inputs for bits with dimension 3. The target Y is the parity function scaled by S.
00001111
X
(U110011):
Y - - -
(112)
01010101
NN. We assume 2-layer width 3 NN with ReLU activation with the input dimension (Fig. 8(a)). The NN has 16 parameters, but to simplify the argument, we use weight sharing so NN has only 4 parameters:
f(x; a. 7. = wn oooooW + b) +
(113)
where a is the ReLU activation and W, b, are
W-
a
B )
b= 3
0
20
(114)
7
Modes. It is easy see that = 33 2S and leads the target parity function. We note that one parameter except e (i.e. a, B, 7) maps to one neuron or a mode (colors in Fig. 8(a)).
We define the first mode (1) as
(() wio x b1) -2a -1 xz3)
(115)
22 ha(x) = ax2 Iı xz),
(116)
where W1, are the first entry of w, b respectively and W1 is the first row of W. Note that f()) (x) takes form similar to the multilinear model (Eq. (9)) but with hy as the respective basis. We define f(2), (3) similarly, and the sum of modes becomes the NN:
f(x) Σ (x)
(117)
which resembles the multilinear model with different skills.
30

---

Mode strength.
Analogous to the skill strength in Eq. (7), we define mode q strength R(
as
R 85
YT (x),
(X);
(118)
where (X) (X1,,., f (Xs)] and X, are the jth column of X. By the linearity of the expectation.
R
R(9)
(119)
q=1
Note that constant always has zero correlation (inner product) to the target (Y).
Analysis. The dynamics of each mode (()(x) differs from that of the multilinear model (Eq. (11) because (a) often depends on the parameter, and the dynamics are longer decoupled among each mode. Nevertheless, each mode follows a sigmoid-like growth (Fig. 8(b)). We note that each mode has different saturation time scale or is updated different frequencies. A mode with a longer time scale leads to a longer 'tail' of saturation as discussed in the main text.
Update frequency. Because of the non- non-linearien aon-iinearity, each mode differs in the gradients receives. We can explicitly calculate the gradient for each parameter as:
da²
(-5 - (-2a² + 23² + c)) 2na
(120)
df
d32
di 3 (-2a² + 5,8 + 5c))
(121)
dy2
? (7² + +c))
(122)
dl
de
12o2 - 5,3² -72 8c).
(123)
dt
We immediately notice that will grow the fastest for small initialization (a, 3, < because it saturates exponentially while other parameters saturate sigmoidally. Considering that is always the largest term and saturate
S quickly, we notice that the saturation is in the order of a² (RU 25 + 2c ze 4S), 3 (iz - + 5c Rs 45), and (² 25). We observe that our crude approximation holds in Fig. 8(b): the first (a) and the second (3) modes saturate at similar timescale, while the third mode (7) requires approximately twice the time for saturation.
31

---

H Details of the multilinear model
The multilinear model (Fig. 9a)) has two identifying properties: 1) the layerwise structure and 2) gk as the basis functions. In this section, we discuss the role of each property in more detail.
d,/D 0.5
d2/12 0.2
dz/12 0.1
1.0
0.8
a
bj
gl(
Re/S
0.6
f(i, a,
0.4
x)( bn
aN
0.2-
0.0
25
50
75
100
(a) Multilinear model illustration
(b) Decoupled dynamics
Figure 9: Multilinear model. (a): An illustration of the multilinear model which is multilinear in terms of parameters, generating a layerwise structure. The model also has the skill functions g&S as basis functions.
(b): The dynamics of the multilinear model are decoupled and each skill strength (Rx) shows a sigmoidal growth in time. Note that less frequent skills have a more delayed growth.
Multilincarity. The product of two parameters (axba) creates the layerwise structure (Fig. 9()) that gives rise to the emerging dynamics (sudden saturation or sigmoidal growth) in Fig. 9(b). The time emergence of NN is well-described by the sigmoidal dynamics (Fig. (a)); non-sigmoidal saturation dynamics, for example, that of linear models (Fig. 10(a),, would inadequately describe the time emergence. Such dynamics have first been studied by Saxe al. [19] (See Appendix B.2 for an overview).
Assuming sufficiently fast decay of dg for the skills, the sigmoidal growth results in stage-like training (Appendix D) where one skill fully saturates before the next skill emerges. In Appendix D, discuss how the stage-like training can describe the quanta model [18] and how NNs, without explicit g&S, decouple each skill.
Finally, note that even though sigmoidal saturation has resemblance to the test accuracy in grokking [48], our model is irrelevant to grokking because R2 which is defined over the expectation over the tthh skill (Eq. (7)) appears both in the empirical loss (Eq. (11)) and the test loss: failing to describe the discrepancy between train and test accuracy in grokking.
Connection to linear models. In Section 4 and Appendix E, we have shown how the scaling laws follow from the basis functions Jk that decouples the loss. To analyze the role of yes we can ask whether simpler linear model with Is as basis functions (Eq. (124)) also recovers the scaling laws. The answer is yes and we outline how a linear model can recover all scaling laws. In addition, we also outline how extended linear models extended similar to Section 5 such that skills are decoupled - can recover all emergence behaviors shown in Appendix F except the time emergence.
By replacing ag with Wk, we obtain the linear model with skill basis functions:
N
fr w) = Σ wu (T)gg)) (i,
(124)
1=1
The dynamics of the linear model under gradient flow
R₂ (T) ux (7) S(1 - -
(125)
where we assumed wn (0) 0. The linear model follows an exponential saturation of the skill strength in contrast to the sigmoidal saturation of the multilincar model (Fig. 10).
32

---

-
d2/D=00 0.2
dg/ 0.1
1.0
1.0
R /
R
0.5
0.5
0.0
0.0
0
50
100
0
50
100
T
T
(a) Linear
(b) Multi Linear
Figure 10: Dynamics of linear and multilinear model. (a): Skill strength dynamics of the linear model (Eq. (125)) (b): Skill strength dynamics of the multilinear model (Eq. (11)). For the linear model, R& emerges from T 0 for all dx/D DD >> O: obstructing the stage-like training. For the multilinear model, R₂ shows a delayed emergence depending on de/ D: allowing the stage-like training and describing the sigmoidal time emergence in Fig. ((a).
Nevertheless, the linear model Eq. (125) results in the same scaling laws in Section 4. For the time scaling law, we recover the relationship between dlCx/ / /T and dL dk in Appendix E. because (T) function of de T only (where d we recover Corollary because each w/ (i.e. R2₂) is decoupled. For the parameter scaling law, we recover Corollary 2 trivially the linear model shares the same basis functions.
P, for D -> oc). For the data scaling law,
The data and parameter emergence in Section 5 can be obtained from the linear model in Eq. (124) if we extend the model analogous Eqs. (15) and (18). For example, can extend the model for data emergence
N
De
Sr v; W) =
ΣΣ
Wa. (T),(T)e,,(i.zz)
(126)
k=
where the matrix W NxDx is extension of E N in Eq. (124), D. fixed scalar, and ex)(i,x) {0, 13 tastns + IR are functions with the following properties:
Exi== [ex,en ow: ( Σ EVD
VD. - gk-
(127)
The equivalence be shown by Lemma 2 which states that the multilinear model finds the minimum norm solution: the solution that the linear model finds in ridgeless regression setup.
Thus, for our setup, the basis functions play critical role in the scaling laws and data/parameter emergences. The choice of basis functions, also known as the task-model alignment (see [23, 27]). determines the linear model's is scaling laws and emergence behaviors. See Bordelon et al. [21] for study the scaling laws in linear models.
33

---

I
Additional plots and tables
NN
extended model
1.0
1.0
1.0
Skall strongth R
Skall strength R
0.8
Ski strough R
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.0
0.0
0.0
1000
2000
1000
2000
0
10
T
D
N
(a) Time calibration
(b) Data calibration
(c) Parameter calibration
Figure 11: Calibration and prediction on emergence. The calibration of the extended multilinear model (solid) on the 2-layer NN (dashed) for n 1 system. For the calibrated parameters, we have 2 = 1/22 for time (Eq. (14)). De 800 for data (Eq. (17)), and N = 4 for hidden layer width (Eq. (21)).
Table 5: Samples of skill strength R The table shows the skill strength N 10 for 10 different runs the parameter emergence experiment (Fig. ((c)). Note that the variance of R is amplified by the outliers shaded columns that learn less frequent skill at the cost of more frequent skill (second column) or fail to learn skill (seventh column).
k 0.98
0.98
0.98
0.98
0.98
0.98
0.98
0.98
0.98
0.98
A 2
4.5
0.95
0.95
0.95
0.96
0.96
0.04
0.96
0.96
0.95
k 3
0.6
0.0
0.72
0.90
0.92
0.64
0.88
0.8
0.58
0.52
A 4
0.0
0.78
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
k 5
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
1.0
R2.5
0.6
RR,15
R.18
RA13
0.0
2000
1000
1000
2000
21000
23000
01000
45090
HUDO
71000
10000
81000
321000
120000
33000
11000
4
Figure 12: Enlarged emergence. Enlarged view of skill emergence from Fig. 4, showing that
saturations also follow a sigmoidal pattern. The a-axis is measured in steps.
34

---

J Rigorous derivation of the scaling laws
In Appendix E,, we discussed the scaling laws in simplified settings, favoring intuition mathe- matical rigor. Building upon the intuitive understanding developed in Appendix E, we now turn our attention to a rigorous analysis of the scaling laws. In this section, we will derive general scaling laws by considering a comprehensive set of parameters and variables. Our goal is to establish the conditions under which these scaling laws hold and quantify the associated error terms. By explicitly analyzing the eтror terms, this section aims to provide a rigorous assessment of the validity and limitations of our scaling law estimates.
Table 6: Scaling laws and their conditions. The leftmost column indicates the condition for the 'large resource' large enough to be treated as infinity, while the second column is the condition between the other two resources for the scaling law (third column). The last two columns show where the statement for the prefactor constant (e.g. Av for scaling law L = Ax and the scaling law (with the assumptions and explicit error terms) are given. Note that whenever T appears theorems and corollaries, 7/S' is multiplied to make it dimensionless.
Large resource
Condition
Scaling law
Constant
Statement
> T
No+1_ o(T)
AN
Theorem
Theorem
> NT
Na+1 TT
L = ATT-a/(at)
Theorem 4
Theorems 2 and
> T
No+1 T
AcC-a/lat2)
Corollary 5
Corollary
T > Dloo D) D)
No+1 o(D)
L= ANNN
Theorem 5
Theorem 5
T > D(log D)
Na+1 >> D
L. = A-DDDDaaaatt
Theorem 5
Theorem 5
J.1 General set up, repeated
We go back the most general settings possible. Our starting point is Eq. (27), which describes the dynamics of R2 and La valid for k < N:
S2
Lk
(27)
2 1 +
S - Ru(
2n to ST
We do skills for indices l
N in our model, but we can still denote
S
R2 and
L4
(128)
For Pa(k) ak- the total loss is given as
N C Σ Pa(k)C== P..0)
Σ Pa(k) 52 2
(129)
N+1
When n2 N,T T are all set, their dependency with the data is only determined by the statisties de. the number of data with z(5) = k. We assumed that r)) E I {0, 1)ndd was collected as random samples with following the Zipfian distribution of size n, and exponent a + or equivalently P(i P k) (k) Ak- for < k n2. Then (di, dd,,) is vector denoting the number of occurrences in D independent sampling from that distribution. follows that d, follows binomial distribution ((D, P. (k)).
In this complete perspective, our loss is dependent on all of those parameters and variables
L L(ng, D, Rinit, N,T)
(130)
where Rinit (R, (0). Rr (0)) denotes the vector representing initial condition. We will also simply denote (0). We will not assume much on rx. but we absolutely need 0 < rs < S for dynamics to hold, and we also should have
nx
- < S².
(131)
35

---

We will not impose any particular distribution on Rima. Instead, we will try to identify sufficient conditions on rg for our desired result hold, and those conditions will differ by the situation we are considering, For example, in Theorems and 3 where we prove time scaling law L ((T'a/(art a/(a+1)) for large enough D and bottleneck T', we only require < ты < S/2 for some e > O. However, the exact constant depends on the distribution of rk. and figuring out the explicit constant seems be only feasible when we fix Tæ as in Theorem 4.
J.2 Estimates for large D
We will first consider the situation where D becomes the 'large resource' that its effect on the loss function is negligible. The number of data dg follows binomial distribution B(D, (k)), so (k) for large enough D. So taking the limit of & when we let D - co has the effect of replacing d D by (k) in the expression of L. We will establish an explicit inequality comparing the difference between L and this limit.
/ Je/Dec converges
Lemma 4. For a function F RR + R with its total variation (F) bounded, we have
dk
V(F)
ED
F
[F(2]]
(132)
VDVP, Pa(k))
where (u,, O2) denotes normal distribution of mean μ and variance o².
Proof This is just application of the Berry-Esseen inequality (with constant 1, see [49] for modern treatment) applied to dg following binomial distribution BDD, P.)))).
Lemma 5. Let F ; R - I be a C function such that F is bounded. Then we have
E E2=N (1P1 (B))/D)) [F(2)] (FP)((()())))) S Pa(k))( - (k))) supl F"
(133)
2D
Proof First, we apply Taylor's theorem to show that
F(z) - F(P. - -.(k)) < (3 PP))) sup FF
(134)
Taking expectation when z follows normal distribution (V(P(kk), P.(K)(1PP((5) gives
D
E, [F(2) ((P) E, [F(2) F(P.(k)) (())( -P((k))
(135)
<E. [IF(2) F(P,(k)) F'(P)()))( P.(k)))
(136)
(= -P))
<E
sup F"
(137)
2
Pa(k)(1 - -P)(
sup/F"
(138)
2D
Proposition 3. We have
S
S2
48 2T2,21)
ED [Cx]
(139)
-1
2
(P),(K)
|
-
Pc
Proof Consider the function F + R given as
S2
F(2)
(140)
1 + S 11)
2
Ph
This function is monotone decreasing and C2 on the whole domain, and its supremum and infinum are given as
S2
sup F lim F(z)
and inf F lim F(z) 0.
(141)
2
2-000
36

---

This implies that
S
V(F) = sup F inf F
(142)
Also, we will show that F" globally bounded. We first calculate
2n (1
2re 2n5T=)
)3
Tk S
1212272
2
3
(143)
=2 a
+ 3
We consider the following inequalities
2nST=
S
Fk
+
Th e
2nST=
(144)
rk
5
2r
2nST=
Tk
+
2r
ST
< (+
<2(1+
- (2255T=-1)
(145)
S
S
s
5
to show that
28
(1 - 1 + 5 2n
[=) < 48 rM
Th
2
2
< 1,
(146)
5
(1 - S + T e
for all 2. Thus we can apply both Lemma and Lemma 5 to this function F and we have
V(F)
(a())(1 - (k)))
E
(())
sup sup[F" FM
D
(
2D
S²
(p)
2 Pk(k))
2º
4Ps(k)S11222
(147)
DP).(k)
D
where the last line follows from that we always have
2 2-(a+1) ns (a+1)
2 2-(a+1)
1
1+2-(0+1)) +... no (a+1)) >
+ (- 22(a-1))
(148)
Lemma 6. For any integer N and 2 1/2 and a + 1, have
N ΣK ((o) I-a O(N-9)
Nl-o
(149)
where Ç is the Riemann zeta function (defined over the whole complex plane except via analytic continuation). In addition,
N E log + +
(150)
1=1
where 7 = 0.5772156649... is Euler's constant.
Proof See Corollary 1.15 of [50], other analytic number theory textbooks. Proposition 4. (Large D approximation) We have
N
S2
S2 P.(k)
Ep|C] Σ
Pk(k)
(151)
2
k=1
2
11 [ 11)
22TP.(H)ST)
6=++1
-0 =0 1/2 (a) + 8 +
-
(152)
where
ifa 1 =
(N)
log N
(153)
/1
<f
The constant the O term only depends
37

---

Proof From the description of C in Eq. (129), we have
N
S
R,
8
Ep|C]
Σ (a(
Pa(k)
(154)
1=1
1 g - 1) -1) 2
-1
22)
k=N+1
2
N
$
Σ (k)
Ep|Ca]
(155)
-1) -1
1+ n2 (1
221PP(()STT)
We apply Proposition to give
N
2
N
20
Σ (k(
EpiCal
(k(
+
2 1 + (s. -1 111
(2)ST(
R 1
VDP.(k)
D
(156)
Each of these sum involving (k) is bounded as
(
N Σ Pa(k))
2
Σ Pa(k) <
<
(157)
and
N
N
Σ
(.(k)
<
Σ k (a+1)/2 =0fa((
(158)
k=1
which follows from Lemma 6. Combining those two gives
Σ (A)):)
S²
= =
-S(DD-V/))NN)) -
(159)
(k)
D
While Proposition 4 holds for any D. it becomes only meaningful if the resulting error terms are less than the main term we desire. We will revisit this when the exact main term is found, and determine the sufficient size of D for error terms to become small enough.
J.3 Estimates for not too small Th
We next discuss the effect of n2. When n. heuristically, then intuitively have (k(k) - --(++1) /=(at))/((a + 1). We will discuss the difference between when we regard n, as and when
do not.
Proposition 5. The following equations hold:
(a+1) = <(o + 1) 1) n a + 0(n
A =
(160)
1=1
--a-1
1 n a
Pk(k) ((a +1)
On -1
(161)
aC(a + 1)
N n ac(a 11) + + 1inmmi(++))20))
Σ
P.(k)
(162)
K=
All implied constants on O only depend
38

---

Proof The first statement Eq. (160) follows from substituting o = a + 1 in Lemma 6. As Pa(k) = Ak Ak-(a+1) the second statement Eq. (161) immediately follows. If we substitute n, N into Eq. (160) and calculate differences between them, we obtain
N ns
+O(N
(163)
K=
Thus we have
f1
Nx
N n1 a
Pa(k)
Σ N=
k- (a+1)
0 ONNNN--1 (N n1 nn5)) (164)
k=
Regardless of the size of n,, We always have
N
N-2a 2a
(N - n2 )m 2
(165)
2
4
so the third statement Eq. (162) follows.
We go back to the description of total loss given in Eq. (129) as
N
Σ Pa(k) S2
C E Pa(k)C&+ +
(129)
2
k=N+1
and we take its expectation in D. Proposition 4 suggests that its limit when D - 0o given as
NV
$2
52
lim ED|C]
(a(
Pa(k)
(166)
D-+00
2 1
s
-1)
-1
2
k=N+1
2
Denote
S²
L
Σ (k(
(167)
-1)²
k=
1+
(.)Px(
$2
L2
Pk(k)
(168)
2
k=
We discuss the effect of n, in Li and L2, by comparing limit of L1 and L2 when n, + oc and
their original values.
For the term L1 the change of letting n. finite value from n. - has effect of multiplying by 1nnn11/an((a==>> (/(((a++)) and multiplying whole Li by 1 " (a((a+ It can be equivalently put
(I,n..N.T) = (1 ac(a+1) + ((n L NN. N. (1+
n.
n -a
+ 0(m
ac(a +1) 1)
(169)
We always have n. > N and N + xo eventually, so if dependency of Li with respect at most polynomial order, then change of main term of Li is negligible. We can't establish exact statements yet without the descriptions of size of L1.
The term La only depends on N and na. not on T', Applying Proposition 5 (especially Eq. (162)) gives
N n, S a((a +
N,
+ +O(N-mino+11.20 52)
(170)
When n, grows faster than N then n part is totally negligible, and when n, has same order as N then n affects the constant for main term of L2. Things might get little complicated when n, N + o(N), where N n, a o(NNay can happen then.
39

---

Comparing size of .1 and La mainly depends on time. The term L2 is fixed, and L decreases as T increases. For T 30 we have .n 0, so Lg having order N dominates becomes quite substantial.
(this proves scaling law for N of exponent (x), so restriction For small 7 and large N where the size of L2 is small, we can expect the restriction on n, to be less substantial. For example, in the extreme case N does not matter at all (except that, of course, it should satisfy n1 2 N).
we have L2 0, and
For such reasons, it is hard quantify exact conditions for n, such that error terms are controlled, unless we specify relative growth of (N, T"). However, nt = w(N) suffices to assure that setting ns oo has zero effect the main term. We will not worry about n, in this setting anymore too, and come back to this at the very end to determine enough n.,
J.4 Estimating main terms
We assume D and ns k a-a-- /5(a + 1) (calculated by rule of n, = 00). We decomposed our main term into
virtually implying that dg/D Pk()) and P.(k)
lim lim Eoic] L1 + L2 n. 700 D00000
(171)
where
S
L1
Σ (k(
(172)
1+ -1) -1
2
22)PT
and
52
L2 =
P.(k)
(173)
2
N= -11
By Proposition 5, L2 is determined almost completely as
N
L2 2ac(a+1) + +(NNa-1).
(174)
Now focus on Li. For
52
F(2)
(175)
2
1
e2nST=
(note: really depends on r3 so it is correct to write Fk, but for convenience we will keep using F.) one can express LL as
N
Li = Σ (P()))((P.()))
(176)
k=
Lemma 7. Let F(z) be defined as Eq. (175).
1. (Estimate for large 2) We have
S F(2) (S (S-r
(1,
S2
min
_ 4nST=
(177)
2
k
2. (Estimate for small 2) For z 2 0, we have
(S rz)²
Sn
(S - r2 F(z)
(178)
27
2
Proof
1. The left side is obvious. For the right side, F(z) < (S rrx)2/2 follows from noting that
F(0) = [S-rz)² and proving (z) < 0, and F(z) < (S (S-re)²
g² 4nST= follows from
"
-1 2T in the denominator of by -1) -1 just replacing + ( -1)
2nSTS
Tb
40

---

2. For the left side, it suffices to show
(F) _
TT
One calculate
2nST=
-28))_2
Tk /
(179)
5
(1+ + 2 (
and
c 2 5 - 2ry e21STT2
(2) rx(1
Pk 3 2
(180)
g
(1+ 5 (c2nST== 1))
F has unique inflection point
1 - Tk
2TH 2nST== =0
SnSTZ
1 - -1)
(181)
S
S
2
and this point is where
(2) obtains maximum. Substituting this the expression of (2) gives - -F) 8T
Our threshold for distinguishing two approximation methods will be set 2 2u (S(a 1)1ST))- where both two error terms are bounded by O(5²). The constant Ç(a + 1) is set to make later calculations much easier. Applying Lemma gives
L (P)))(()(()))
(182)
(S - rk) rx) (k)
2
Pa(kmin (1,
S2 (A4STP..())
+0
SS
Σ
Pa(k)² 52
Σ
1.
ISKEN.P,(M)E
(183)
Denote
(8 (8- (k)
1
E
(184)
2
ISKEN (K)
81 = STT
Σ
Pa(k)²
(185)
(N)
P.(k)min (1, S2 = - -ISSTP.I))))
8 S2
Σ
(186)
Proposition 6. Suppose that there exists 0 <r< < V5 such that r S rk < S/2 for all k. In the decomposition lim lim ED(C = M + 22 06 + D-000
(187)
given above, we have the following bound.
1. If ((tt)) > N, then
- L1 2a((a+1) N0(S2N---1
(188)
M & =0
(189)
& O (5ogg (1/og((/1))////t((((/S//>> -o(o++)
(190)
41

---

2. ((ST))/att)) < N, then
L2 +1 = 5²
Σ
Ps(k) ((ST()))) (188())))aa((tt))
(191)
(>(SST)//(ut))
81 0 (s (nST) -
(192)
82 = 0 S (log(S/ ((og((8/)))/(ot))(()))) -a/7))a()+()))))))
(193)
Here all constants in O and & terms are absolute with respect 17, S,T,N, N. (They may depend on a.)
Proof We first note that the condition (k( 20 (S(a + 1)nST) -1 is equivalent
(k) < (S(a 1)mST) + k -ー-1
1
k > 1/aat1,
(194)
nST
Thus can rephrase the descriptions of terms as
(S rx)=
M
Σ
Pk(
(195)
(nST)
CKSN
61 STST
Σ
P,(k)²
(196)
(nST) (K+t)KkN
S2 PN)
8 8
Σ
Pa(k)min
(197)
(T M
Applying Proposition 5 easily shows that
N
L2 2ac(a + 0(S
(198)
For M and &,, we will consider them by dividing two cases depending on whether (1SST)I/(++)) > N or (nST))/(o+1) < N. (nST))/(a+1) N, then the condition (nST) 1/(+1) s N is
never satisfied, so M E1 O. Now suppose (nST))/(o+)) < N. We first that
(S - r
52
L2 + Ml
Σ
P.(k) + Σ
2 (k)...
(199)
2
(nST))/i++
k>N
As (S rz)² O(52), ) we can let
Ls 82+ 5²
Σ
Pa(k)
(200)
and using Proposition gives the desired estimate estimating sum of (k))) using Lemma 6 gives
L1 + +1 = (88T For c1
81 0
STT
Σ
1 a(a+t) = =0(S2(nST)) -a/st)))
(201)
kz(nST)//o+11
For &2 we always have
S2 - (n)TP.(4) - 1,
E S2 22
Σ
Pa(k)min
(202)
regardless of the size of N, so it suffices to bound this sum. If we denote / = ((o-)) and define
S
Fx(x) = min (1. ب AnSTs
-
(203)
42

---

it suffices to show the bound
Σ
PA(H)(((P(())) O (log(S//))o/aat)) -()tt))
(204)
We will approximate this sum as
Pk(k) Pe(k + +1) P.((k) (2)).(k))
P.(H)EE2PP((K))
(Pa(k) - P,(k
(205)
S-1
a---1
(Po(k) - P)( (a (11 + 0(k-1)) (2(P
(206)
kg!
=0
Σ
-Pa(k))Po((A 1
(207)
Eg1
to obtain the form of Riemann sum approximation for the integral of
F2())d
11((++11)
(208)
P.(1
at (l) <
P,(1). As F2(z) decreasing function, this Riemann sum always less than the integral, so we obtain
00
Σ PP(()))((P(())) =
:=P.() = 1-1((a-1) ((()
(209)
1:1
We note that P.()) (S(a + 1)1ST) -1 The threshold for (2(2) (2) become 1 given
82
4mSTs
2
21SST
log
(210)
As r VS, this value is always greater than PI)... Thus we can divide our integral as
1/(++)))
(211)
(cla+1)nST)
(BnST))>log(S)) log(s/r)
2 1/(a/)+1) S2
2 1/((a+11
-nSTs dz.
(212)
S())+1))ST)+
(2988)))10g(81)
x2
The first part is bounded by
log(S/r)
-1((a+1) do dz (((2))))==((((SS)))))))( (((e)sS))-(og((/n))))
(213)
(cia+1))ST)-
which can be shown to be O substitution of w = SnST= to show
For the second part, we apply
111((a+1) 52
52 (4nsST)-a/aat) aa((+1)) f
AnST'
w 11(aat1) du
22
2
2l0g(S//)
(og(s/r)
(214)
52 (4nST) (aat))aa(a+11p 2
(- (_ 2 log
S
(215)
a +
and applying the asymptotic T(s, x) = 0(1--1e-2
suggests that this is bounded by
52
5 -1/(a+1)
< e (4nST) aa((a+1)
log
é - =0 (ISTT) -o(T))))(+++)
(216)
43

---

Theorem 1. (Parameter scaling law) Assume the following conditions: n, > N with lim lim (N/n2))
< 1 ( can be zero), and there exists 0 < VS such that Ra < S/2 for all k. If N,T + oo while satisfying Na+1 = o(T), the expected loss Ep|C] for all datasets D of size D satisfies
S - (11))) No
Ep|C]
20<(ax +1)
+0 M-N-min(at1200 + Sa (log(S) (oo((S/)))/(att)) (nST) -astt))a(att))
+ +0 5
(5 D 1/2 fa() + -
(217)
where
ifa > 1
fa(N)
log N N(L-a)/2
ifa =
(218)
if <.
The constant on the O term only depends a. When D >>> T8, then all the error terms involving D are negligible.
Proof In the situation n, = 00 and D = oo, Proposition 6 shows that
S
Ep|C] 2aς(a + 1) N +0 N52 (a+1) + S (log(S/r)) (n)ST) (n/ST)-a/att))) (219)
We consider the effect of n, first. As L1 becomes an error term in this estimation, letting n., finite value has no effect on overall estimation. The term La accounts for the main term, and letting n. as finite value changes it to
N - nn 5²
aç(a + 2 + +O min(a+ -0(N=mmn((+1.20) s²).
(220)
This accounts for the factor (1 70) on the main term and O(N m,2 5²) added to the error term. The effect of D exactly described in Proposition 4, contributing the error term of
O (S2 D-522-1/2/00 faN) + 2T,2T22--1 Regarding the sufficient condition for D, if > T then we
have
S D-1 & T aaat(a11), S²D-1/2 (N() < 3/2 <
(221)
so all error terms involving D are less than O(T-a/(a+)).
For the situation T O(N+1)) however, the error terms &1 and &g of same size, so we can only say that the main term is of (($((nS))aa/(at)))
Theorem (Upper bound for the time scaling law) Assume the following conditions: n. > N, and there exists there exists 0 < r < v5 such that r (0) f/r all If N, T + oo while satisfying SST O(N++1), the expected loss Ep [ is
EDIC] = (s² (log(S/r))a//at)) (nST)-a/(a+) + 5 D fa() + 1 (222)
with constant on O only depending and lim sup (nn(((TT))()/(++) /N), with fa defined as in Theorem 1. If D > 2 and D >> T3, then all the error terms involving D are negligible.
Proof The error term regarding D can be obtained in the same way as Theorem 1, so we will let D do for the rest of the proof. Also, we can let n, cc, observed that it contributes most to the constant factor of the upper bound and does not change the scaling.
In the decomposition of Proposition 6, we always have
&-- = 0 ( (log(S/r)) (11ST)-/((-1))
(223)
and
6 = (5 -a(st1)))((
(224)
holding regardless of N, so it only remains consider La + M. If (nST))/(a+)) N, then La + M is of size O (n -a/a+)))) If (IST)//((+)) 2 N, then N and ((ST) has -a((t)) Thus in either cases we
same order, so L2 + + L2 = -eSe have the desired bound.
44

---

Theorem 3. (Lower bound for the time scaling law) Assume the following conditions: n, > N and 0 < R₂(00 S/2. If N, + oo while satisfying (8C(a + 1) 1) < N, the expected
loss ED [ is
Ep|c] 2 K (nST) (nSS)))a(aat) (00
(225)
for K and constant on O only depending on a, with fo defined as Theorem 1. If > NT and D > T then all the error terms involving D are negligible.
Proof The error term regarding D can be obtained in the same way as Theorem 1, so we will let D 3c for the rest of the proof. We only show the lower bound for L,, holding regardless of N and
ng. In Lemma 7 (Eq. (178)) we have
F(2) 2 (S 22)
8n,OT
52
81
27 2 22
8 27 2
(226)
2
for 2 2 0, so if 2 < (4nST)- then F(z) 2 52/8 25 2 > S2 20. The condi-
tion (k) I (4nST))- is equivalent to that k 2 (4C(a + 1) D1))SS))/((att In evaluating
L = Σ k= P. (P)))())))) we will only add over k in range of
(45(a + "))=++
< k < (8C(a + (S=)))))//((t)))
(227)
From the assumption, this interval sits inside 1 k N. For such k use upper bound of (().(k)) > $2/20. Then by using Proposition we can obtain
S
81
Σ
Ps(k)
(228)
20
5² (5(a + 1n5 aa(a+1))
(4-a/(a+1)) - g-a/(o+1)) + O ((nST)=
(229)
20
a5(a +
The possible effect of n, on the main term is to multiply both the main term by and T by (1 + n2 so it increases the bound.
The condition (8Ç(a + - ((at)) N is not absolutely necessary for lower bound. The condition (1,ST) 1/(++1) = ((N) and n, 2 2N would suffice and one can formulate similar theorem, although the constant of lower bound might be much smaller if (nST)) (nST))/(+1)) I/N is small.
Lastly, we provide a simpler version of those results combined and discuss the special case where the optimal compute C NT, or the given engineering budget, is specified.
Corollary 3. (Summary of the large data estimation) Assuming D >> NT T and n. > N++c such that effects of n, and D are negligible, then for N, - 00 we have
ED[C] = 0,,s.r (max(NN-, (-al(a+)))
(230)
where Snr denotes that the implied constant depends 17, S, a and r min Ra(0) > 0. In particular, we have
No+1 = =O(T)
Ex[A] = ,,
(231)
and
= (
ED[[] = S, (T,Ss)(T-a/(a))) a/(a)))).
(232)
Proof Apply Theorem 1 No+1 o(T) and Theorem 2 and Theorem if Na+1 > T.
Corollary 4. (The 'computationally optimal' case) Denote C' = NT and assume the conditions in
Corollary 3. Then we have
EpIC > (
(233)
When N = ((C\/a+42) and T = 1)/(o++))(a-2)) we achieve E = @CC-o/(0+2)), (Its implied constant may depend on implied constant for growth of N and T.)
Proof The first part follows from
ED[C] > max(N ".Traa(aa)))
(234)
and
max( aN The second part can be checked by substituting (N,T) = ////0++22.c(at3//at3))) (or their constant multiples) to Corollary 3.
max(Naa,Taaaaat TTa/(a+))) 2 (N ( -NT) (235)
45

---

J.5 Computing the constant for time scaling law
While we have found the time scaling law E|c] O(T-o/(o+1)) holding for T O(No-1). bounds in Theorem 2 and Theorem 3 were chosen rather lazily and do not depict the correct picture. We will find the constant using more refined estimation, but we require additional assumptions on parameters. We will focus on the setting where D and n, are large enough to be negligible, (0) = r fixed, and T O(N++1) with fixed constant such that time scaling law holds.
Theorem 4. (Constant for time scaling law) Denote _ as the loss when D, ng - that their effect is negligible:
S²
N
~ -L, = Σ Pa(k)
(236)
2(1 ( -1)- (f-1)-1(22P(00)) (2)ST(
2aC(a +
k=1
When T,N N + oc and lim N/(nST)3/(at)) for a fixed constant E (0, ool, the following limit exists:
A(A) =
lim
(237)
T,N-100
The prefactor constant A as the function of À (when À = 00 then let \ = x- is
A(A) <(a + 1)-1/(a11)
S
" / s, 2aς(a + 7
(238)
a a+1
(xt111/(((+1)
where
52
(239)
2 1 (1 -1) ezu 2.
Proof We first observe
N (p(4)99ss((STPPP(() +
S2N-a
-
(240)
a((a+1)
We will seek to convert it into Riemann sum form of certain integral. We start by noting that
k
P.(k) = (P.(k) - Pa(k: + 1))
+ + (1+-)))))
(241)
((a + 1 a ++1
(ka(k) - Ps + (k) 1//aa)))) 0
(242)
Denote uk = nTSSTPP (k), then the sum can be approximated to
Σ (nSPP())
(243)
~ > (P)(k)) Pa(k + -1/( 1/(0+1))()))))))11) (1n
(244)
= -(SS)))o/(ot) 1)(++))
Σ (ux - - 1/(a (wx)
(245)
we ignore small k. As s is decreasing, this corresponds to Riemann sum taking minimum the interval [uk-1, ug]. So integral provides upper bound for this sum. Similarly, approximate with Riemann sum taking maximum in [ug, u we use
(k) <(a 1) 1/(+t)
++ 1 (P. 1) - P.(k)P. 11) OKK)))
(246)
instead. As Ds,r shows exponential decay, we can ignore values at small ks this shows
(n,ST)-a/(a+) (a(a+1) Σ [uk uk+1) ) 11((++1)) 11 (uk) R 1/1((a+1) srr (.r (u)
(247)
UN
46

---

and from that we obtain our desired result.
1)-1 UN 1STN (att) ((a ((a+)) -= X cla
(248)
Theorem basically tells that for N = A(nST) and D, n, large enough, we have
C~ (A)A(((S))=//(()t)
(249)
with A()) given as Eq. (238), thus specifying the constant for time scaling law, For finite X, this theorem covers the computationally optimal case of (N,T) = (A, C2/(aa2+)) x2C(a+1/((+22) for some nonzero constant A1; A2. For À oc, it describes the case T o(Natl) where effect of N is negligible.
Corollary Denote - _ as the loss when D, ny > DC same as Eq. (236). Denote NT and suppose that
(N,nST) = (n
(250)
for a fixed constant 0 < X < co. Then as C. we have
-= = A (x(at))((+ti)) Xa/(art)) (mSC) -a/lat2) (1 + o())
(251)
where given as Eq. (238) of Theorem 4.
Proof As lim N/(1ST)) 1/(+11) x under above conditions, we can apply Theorem and substituting Eq. (250) into Eq. (249) gives the desired result.
Technically can optimize _ for given fixed value of C NT by letting À as argument of minimum of A (X(++2)((a+1)) X x-+((a+1) although it seems almost impossible to obtain any form of formula for such X.
Lastly, we provide the following estimate for the time scale constant (A(A)) when is small, especially the first term in Eq. (238).
Proposition 7. As r + O, we have (A > 0 ffxeed
(lo S --r) a/(a+1) 22/(a+1)5 1)
/ u 11//ot+))
$1 (,)
(252)
r
4a
Proof Denote M - 1), and replace u by (log M)v. Then we have
J (l = (log M) M)a/(a+1)
S
-11((a+1) du
(253)
2
A/logM (1+ [1+M2-1) 1)²
52
-1/(at1)
= -log M)aa(at1))))
1u2A/log
(254)
2
(1+ M2
As M + oo, the integrand converges to y. --1/(a+1) du
1 1/(at)
if S 1/2 if t 1/2.
lim Lo2 M M
(255)
(1 M/2 1)²
The integrand is bounded by u 1a) if < 1/2 and w e if > 1 1/2, those of which are all integrable. So
apply Lebesgue's dominated convergence theorem show
111((++)
-11((o+1) do
lim M A/ log M (1 41+M20-113
lim Lo2A/log (1 22 M
(256)
v 11(a+t)
(257)
Thus we have
S r
-a/(a+1)
fre u -1/(a++1))
52
1/2
lim
log
2 (w)
v --1/(a-1)
(258)
2 J
2 22 +1)
(259)
which can be observed to be equivalent to the desired expression of Eq. (252).
47

---

J.6 Estimates for large T' and threshold between data/parameter scaling
The estimates for small require different techniques from estimates for large D. We will consider the situation T grows much faster than D and N, and discuss when data scaling law of L @(D=a/(a+1) happens. We will consider a simpler setting of 'ns = oo" or equivalently that effects of n. are negligible (n, w(N) seems to suffice) and Rx r < S is fixed, although it won't be impossible to discuss their subtle effects.
First we single out effect of T by comparing L(T) and [(oo). We remind
5²
(T)
(27)
2
1 2(1
- - -11 11- 22/d)SST/D) 2
and its limit when T oo is given
(S-r)²
if d2 = if dR 0.
[x(00) = lim (T) =
(260)
T-000
Proposition 8. Suppose that (0) = < S is fixed. For large T, we have
Ep[C(T)] -ED[((s)) - 0 (5* D----DD-nS An5T/D).
(261)
Proof As (T) is decreasing in T, we always have (T) 2 fx( so therefore
Ed[[(T) Ep|[(oo)] 2
(262)
So we only need to establish an upper bound for (T) - (oo)). We note that La (T)
(x(())
when dę 0, so one can write
(T( - (x(2)) = oo (T)
(263)
where Ia,>0 denotes the characteristic function
[1 if ds > 0
Ide
(264)
00
if dz 0.
We use simple bound of
54 r-- -nd2--n
Cx(T)
<
(265)
21 -1) 1)- (2ndeST/D)
2
As de follows binomial distribution
considering its moment generating function gives
Ede le 4nd,,ST/D] (1- (1-P, (k) + Pa(k)e 4nST/D)
(266)
so thus
Ea, [1, 4nd, ST/D -1- P.(k) + P.(Ke AnsTyD) -n)) -(1 (1-P8 PP(K)))
(267)
Meanwhile, for 0 S u, v < 1 real numbers, we have
|u P = Iu - u1| + D 20 ..... 1 D/u vl
(268)
so, applying this inequality to above gives
Ed, 10d 4T/4ST/D (K) 4nST/D
(269)
Thus, we can deduce
Es, [Cx( Ed, [cx()]]
Ed, [o
(270)
S4,-2
Edi. [1d ST/d
(271)
2
De -n.5S//PPPPPp
(272)
2
48

---

and thus
S-r-2
20
0 s Ex[C(T) - Ex[[(oo)]
De InST/D
P.(k) 0 205-22e-Ans77
2
k=1
(273)
This provides an almost complete account for the effect of very large T. We will let T this point. We have
from
(S - r) N
S
0
Ep Ep[[([o)]
Σ (
Σ
Pk(
(274)
2
N41
Applying Lemma 6 gives
N a<(a 1)
P.(k)
+ O(N-a-1)
(275)
A= N+1
so suffices focus on the first sum. We will divide the range of i into two 1 k S M and M < k < N. For the sum over 1 < k < M, we will apply the following simple bound (in the last
part, we used
x S 7
0
Σ k=1
S (1 -1-77 P.(M)) < PM
(276)
For the over M < k N, we will approximate the sum into some integral, which happens be incomplete gamma function.
Proposition 9, For 2 M < N integers, we have
N
Σ
(.(k) - (1))()))
(277)
1mm M+1
=D-a/(o+1) S(a + 1)-1))1--1 1)-1/(ot)) r a ( - (P(TT
(278)
a a+1
+0 +D(D(aatt)/(aat) + D-
(279)
Here I denotes the incomplete gamma functionn
[(, = 1 e
(280)
Proof Consider the interval P.. and its partition / (P) P. <..<
(M)). For function f(x) = x- 1/(++))(1 - =r)". we will consider its upper and lower Darboux
sums with respect to P. As decreasing (0, 1). its upper and lower Darboux sums are given respectively as
N-1
U(, = Σ
(P.(k) - 1)
Pa(k (1-k 1))
(281)
K=M
N-1
LU, 3 = Σ
(P.(k) P.(k (,0 (P))))))
(282)
k=M
and those give bound of the integral of f as
L(f, < Pc(2))
f(z)dx S 9))
(283)
P.(N)
Meanwhile, by noting that
(.(k) Ç(a 1) 11(a+1) a a+1
(pa(k) P, (k: -1/0))))) 0(k-1))
(284)
49

---

one can show
Σ (1 k=M
(285)
<(a + +1)-1/(a+1)
N-1
Σ M
(P.(k) - Pa(k+ ((
(1+ O(M-)))
a+1
(286)
S(a + +(a+1)
(00++)-1/(at)) [ff, (1 + O(M
(287)
a+1
Applying a similar argument for upper Darboux sum gives
N
(s(k)( (L())))))()))) ((a + 1) 1((+))
Σ
((,,)](-((~T))
(288)
a+1 1
K=M
and from Eq. (283) it follows
Σ P)())(L)P(())) S(a + 1) 1)=1/(+11)
(Frm))) x (1- (1+0
(P
a ++1
P.(N)
M=
(289)
From now will estimate the integral
P.(M)
x (1= dz.
(290)
P.(N)
We replace x // the integral inside, then becomes
(P( x 111 (1 dx -Daa((a+1)
(P.(M)
y/ -1/(a+1)
(1-
D
dy. (291)
P.(N)
DP.(N)
We want to approximate (1 - b)² D bye " so we will estimate difference between them. We have
Dlog(1 - y y
(292)
D
k=2
so if D > 2y then
x
20 k -1 - D
y² -1
-y > -y> log(1 - b/ = - -
(293)
D k=
2(2
D
k=
so
e- (1 82 822
<c VID <(1-1) D) <.
(294)
where we used the inequality 1 - - S As (M) < 1/2 if M > 2 (obvious from P.(M) < (P.(1) + P2(2))/2 1/2), any y in the interval (N), (PM()) satisfies D > 2y. So, can apply this approximation in every y. It follows that
DP)(M)
D 1/(a+1) (1 (1- --'''a dy
(295)
DP.(N)
(P.(M)
( 1 11((+1) -p u0 (
11 1/(at1) - +0
-1/(a+1))-17
dy
(296)
DP.(N)
D
DP.(N)
DP.(M
y -1((at1) - dy +0 D-1 1o y 1l((a+1)e -
(297)
DP,(N)
a DPP - a =T 1
: (P.A)) +
+O
(298)
Combining this with Eq. (289) and Eq. (291) gives the desired result.
We combine Proposition 8 and Proposition 9 together to obtain this final estimation result.
50

---

Theorem 5. (Scaling laws for large time estimation) Suppose that N, - oc and >> N for
some so that effect of n, negligible. Suppose that R₂ (0) f all 1 I k S N.
1. (Parameter scaling law)
N o(D)//att)) then we have
Ep[C| 2aC(a +
S
N N-=+0 +0 +0( +
+ - De AnSTT D
(299)
2. (Data scaling law) If O(N++1) and μr lim exists (it can be zero), then
ED[[] = D D-a//at1)
(S - ((a + 11(1a+1111/0++))
a+ Nott((a+1)) (
D
S (D/No* (
+
2( 1)
2aς(a + +1
+0 (5 (2atD-(at (20+1)((2++))) + De (De=/////)))
(300)
Here I denotes the incomplete gamma function
T [ x)
y1" e ddy.
(301)
In particular, if D o(Nat1) such that μ 0, we have
Ep[C] = 1) a(( (S - (r) + 1) 1)-1/(a+1)
D a
(a41 (1 (1+
2(a + 1)
+ +0 (0s De InST/D De-
(302)
either case, > Dlog D)
tc for some 6 implies that error terms involving T are negligible.
Proof Proposition 8 states
ExI((T)] - Ep|C(oo)] O (S -Se DDD-AnSD/D)
(261)
and we showed
ED[[[[o)] (S r)² Pa(k)(1 Pa)k))
52 0
Σ
Pa(k)
(274)
2
k=N+1
and
N-o
(k(k) aç(a +1 + O(N
(275)
1+1
For the sum of P. -P.))((1PP(())) over 1 k < N, we use the estimate (see Eq, (276)) of
M
Σ ( (F-P.1)1D)
(
(303)
and the estimate of Proposition 9. Combining all those gives
Ep [4]
(304)
52 N
(305)
2aç(a
+D a (S (S-r) +1)(((aa) ((_TT.DP.(N) - -ra0
: DP,((M)
(
2(a +1)
(306)
+0 (S((DD-Caa-))) +
- D-aa(att) + N-a-1 te P.(MDD + 2
(307)
We will prove our main statement by choosing appropriate M depending on size comparison between D and N.
51

---

1. IN = D) then we let M = 3, and also regard all incomplete gamma function
values as O(1). Then it follows
N Ep [ 2a((a+1) + D + -a-- + r-r-2 (
(308)
and thus obtaining the parameter scaling law.
2. Suppose D O(Na+1)) and μ lim
exists. We want
D D-a/(a+1) (S r)a + 1)-1/(a+1) 2(ax + 1)
(
a
S²N-a
(309)
2
be our main term, and set M N such that the term
(
s D
a+1 DP.(
(310)
and enror terms not depending on T given as
o 0 (DFDD((att)/(att) D-aalatt) M-1 N +e - -.((A)))))
(311)
are all bounded by O(D- Set M D1/(20+2), Then Ps(M)
D D-1/2/5(a 1), so applying the asymptotic [(s, = 002--1e-0 gives
a+ DP,(M)) (aan))=0---111 (D-1/2(at)) -D (i(lottteeDD/((ttt))))
(312)
This term and PMPDD e-VD/c(at)) are less than D D-a/(a+))M--
O(D-(2a++)) (20++ (2(202)2))))) and obviously D- (2(041))/(++] is less than D -2 (2/(2)22) Thus
it follows that
Ed[[] D-a/(a+1) (S r) +1)
D
N
2(a + 1)
a+11' Nati((a+1)
+
2ac(a +1)
+ ( (2 De
(313)
Regarding the final statement regarding sufficient condition for large T, T.T.>.
>>>>> D(log DY +e implics
De AnST/D -ng D D. 1nnnnnnnnnoDD DY
DーK
(314)
for any K > O, showing that the error term O ( De De-ST//D)) is negligible compared to all other error terms of Eq. (299) and Eq. (300).
We also provide summary of all large time estimation results.
Corollary 6. (Summary of large time estimation) Assuming T >> D(log D) and n. > Nl+e such that effects of n, and T are negligible, and Ra (0) for all S k N. Then for D, N co, we have
Ed[C] = O (max(NNo, (naxXN-0DD-0(00-1) D-aa/a-1)))
(315)
where Sg, denotes that the implied constant depends on 1): S.r and a. In particular, we have
No+1 = =OD))
= S.....(N (N-
(316)
and
D 0(N+t))
Ep[C] ,, -a/lo+)))
(317)
Proof Just summarize the results of Theorem 5.
52

---

K Methods
In this section, we present the methods used in our experiments.
K.1 2-layer MLP
We trained a 2-layer fully connected neural network (MLP) with ReLU activations. All parameters of the MLP were initialized with Gaussian distribution with standard deviation of 0.001. The input dimension of skills) and n, is the length of the skill bits. Each skill has m that are used to express the skill function. The target scale was = 5. The model was trained with SGD without momentum and weight decay (the exception is the parameter emergence experiment where Adam with learning rate 0.001 and weight decay of 5 x 10- was used to escape the local minima). For the data emergence experiment, the learning rate
the model was n, + n. = + 32 where n, is the length of control bits (number
mutually exclusive sparse bits
halved every 50, 000 step.
The skill strength (T) (Eq, (7)) was measured using 20, 000 i.i.d samples from the htth skill." For the time emergence, the skill strengths were measured every 50 steps, while for other experiments, they were measured after training. To mimic the infinite parameter N - co. we used the model of width 1000 (for the hidden layer). To mimic the infinite time T oo, trained for 5 10 steps (3 x 10 steps for time emergence) where each step had the batch size 4000 (2000 for the data emergence experiment). To mimic D -> oo, sampled new data points for every batch. The details are given in the following table.
Name
Values
width learning rate
1000
0.05
initialization standard deviation
0.01
activation batch size steps target scale number of skill bits
ReLU
4000
500,000
32
number of skills
K.2 Transformer
This section outlines the transformer architecture used in Fig. Data is encoded for the 2-layer MLP, but with one-hot positional encoding appended to the data. We use a basic decoder transformer with block, an initial embedding layer with output dimension 512, and a final linear layer. For the attention mechanism, we used 4 attention heads. For non- non-linearitty, we used ReLU. A batch size of 5000 was used with a target scale S 1 and default Pytorch initialization. The model was trained with SGD with a learning rate of 5 x 10-5, weight decay of 10-5, and momentum with B = 0.9. At every 100 steps, the skill strength R2 (T) (Eq. (7)) was measured using 20, 000 i.i.d samples from the kth skill.
K.3 Measurement of skill strength
The skill strength RĄ is a simple linear correlation between the learned function f function expressed by NN and gs for Pa given I = k. We approximate the expectation over X by taking the mean over 20, 000 i.id samples from P, for the 4th skill:
20000
R₂ Ex (k), s 20000
Σ f(k, ((k, gk)) x0)),
(318)
"We free to choose any optimizer long it preserves the order in which the skills learned. Additionally, the parameter emergence experiment uses infinite data; we expect same solution for Adam and SGD.
Note that except the data scaling law experiment, the training set size infinite.
53

---

where the notation 2هd) denotes the jth sample.
K.4 Details of the scaling law experiment
For the loss of the model (solid lines) in Fig. 2, we used the analytic equation for the model (Eq. (12)) under suitable assumptions such as sufficiently large n, (Table 2). For the scaling laws (dotted lines) in Fig. 2, we used the exponents from Appendix E or Appendix and the prefactor constants from Theorem (time scaling law), Theorem (data scaling law), and Theorem (parameter scaling law). For the hyperparameters of the simulation, we used n, 10 such that n, is large compared to other resources; and R& (0) 0.01 such that R4 (0) = S and fj =1.
Time scaling law.
The total loss as function of T for D, (Fig. 2(a), solid) is
S² R2
L
Pa(k)
(319)
[1 [x(0))
- 1) e2T/P(()SST)
which follows by taking D oo and N f2 on Eq. (12). The scaling law (Fig. 2(a), dotted) is
L= Ar Ar
(320)
where the exponent is derived in Appendix E.1 Theorems and 3. The prefactor constant is
Sa ((a + (11
/
u -11(a+1)
A (a 1)(1S)o/(0+1)
z
du,
(321)
( -1) 1) cZu
which we obtained by taking D Eq. (238).
Data scaling law.
The total loss function of D when N,T - oo (Fig. 2(b), solid) is
S
Ep [C]
(1 Ps(k)) (k))).
(322)
which follows from Eq. (58). The scaling law (Fig. 2(b), dotted) is
L ApD-a/(a+))
(323)
where the exponent follows from Appendix E.2 Theorem 5. The prefactor constant is
S2 ((a + 1)-1/(++1)
Ap 2
(324)
+
aK +
which we obtained by taking N oc in Eq. (302).
Parameter scaling law. The total loss as a function of N when T, T.D - oc (Fig. 2(c), solid) is
S2 P.(k),
=
Σ
(325)
2
k=N+1
which follows from taking T, D + oo on Eq. (12). The scaling law (Fig. 2(c), dotted) is
L= A
(326)
where the exponent follows from Theorem 1. The prefactor constant is
8 Av 2
(327)
which we obtained by taking D,T 00, N/n, O, and C(a + 1) a1
1 in Eq. (217).
54

---

Compute scaling law.
The total loss as function of T and N for D - oc (Fig. 3, solid) is
S2
N
C= (k)
Σ (k()),
(328)
1+
S [2(
- 1) 22)),(())T
k=N+1
which follows by taking D + oc in Eq. (12). In Fig. 3. we plotted for N E {10, 50, 70, 100, 200, 500, 700, 1000, 2000, 5000, 10000} and T [1, 1000] as examples of dif- ferent tradeoff between 7 and N for fixed C.
The scaling law (Fig. 3, dotted) is
L= A=A,C-a((at3)
(329)
where the exponent is derived in Appendix E.4 or Corollary 4. Using Corollary 5, the prefactor constant is
A A (xlat2)/(o=1)) xa/(at1) (1,5) a
(330)
where A : R + IR is defined in Eq. (238). We used the minimum value of A. for E (0, oo].
K.S
Estimates of the compute use
On CPU, our emergence experiments on the 2-1ayer MLP (Fig. I) take 2 ~ 5 hours for a single run of time emergence experiments and 20 ~ 40 hours for a single run of other experiments depending on the CPU. All experiments were repeated 10 times (except for parameter emergence where repeated the experiment 50 times). Each experiment requires memory of at most 5GB. The CPU cluster in which experimented contained the following CPUs: Intel(R) Core(TM) i5-7500, i7- 9700K, i7-8700; and Intel(R) Xeon(R) Silver 42 121,, Gold 5220R, Silver 4310, Gold 6226R, E5-2650 v2, E5-2660 v3, E5-2640 v4, Gold 5120, Gold 6132. The transformer experiment (Fig. 4) takes 48 ~ 72 hours for each run; we used an RTX4090 with 24GB RAM, with CPU from the list above.
55

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The claims in the abstract and introduction accurately reflect the paper's contributions, as evidenced by the contribution list in the introduction section, which references the sections presenting each result.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses the limitations of the multilinear model in Section 5.5 and the general limitations regarding the assumptions about the framework in Section (Discussion and Conclusion). These sections address the robustness of the results and the scope of the claims made.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
56

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results are accompanied by intuitive explanations in the main text, with detailed derivations (Appendices C and E) and rigorous proofs (Appendix J) in the supplemental material. In addition, an alternative derivation of the scaling laws via stage-like training is given in Appendix D.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have provided details architecture, initialization, learning setup, and measurements - of our experiments in Appendix K including the details of NN for emergence experiment (Fig. 1) in Appendíx K.1, the details of scaling law experiment (Figs. 2 and 3) in Appendix K.4, the details of the transformer experiment (Fig. 4) in Appendix K.2.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe
the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
57

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We provide a link to our source code in the main text.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
collooiioo icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nips. wwtppppcccggppieeeeccoccoococcpe wwwpc//ggg/e//eeee gtwddd//ooeduuuaiiiiii/////// wwwniisssoooooooo oonooicy)))) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify the details in Appendix K.1 (2-layer NN) and Fig. (transformer).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, all our figures in the main text, which are not simulations (Figs. and 4), have I-standard deviation error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
58

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the compute resource details in Appendix K.5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https::/ http:///wwerrrssssccut.ieee//e// cccppublic/Ehhessuuddee ines?
Answer: [Yes]
Justification: The research conducted in this paper adheres to the principles outlined the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
59

---

This research aims to deepen the fundamental understanding of emergence phenomena and scaling laws deep learning. As our theoretical and empirical investigations are conducted in carefully controlled, idealized environment, we do not anticipate any immediate societal consequences arising directly from the findings of this particular study.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The research presented this paper does not involve the release of data or models that pose risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
This paper does not use any existing assets from other sources.
Guidelines:
The answer NA means that the paper does not existing assets.
60

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve any crowdsourcing experiments or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No IRB approvals equivalent reviews were required.
61

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
62


Reviews:
[{"review_id": "cITX8UH2dA", "reviewer": "Reviewer_NXT5", "summary": "The paper proposes to use a certain generalization of the well-known sparse parity problem, as a theoretical framework for neural scaling laws.\n\nThe theoretical setup doesn't seem to make sense (I'm open to changing my mind). Indeed, equations (2) and (4) taken together give\n\\begin{equation*}\n    f^*(i,x) = S\\sum_{k=1}^{n_s} g_k(i,x) = S\\sum_{k=1} \\delta_{ki}g_i(i,x) = S g_i(i,x).\n\\end{equation*}\nThis is definitely not \"a sum of $n_s$ skills\" (as claimed by the authors); it is a single skill. The same issue repeats itself in (9) when the authors introduced their so-called multi-linear model. Indeed, that model simplifies to (again thanks to (2))\n\\begin{equation*}\n    f_T(i,x) = \\sum_{k=1}^{n_s} a_k(T)b_k(T)g_k(i,x) = \\ldots = a_i(T)b_i(T)g_i(i,x).\n\\end{equation*}\nFrom this point onward, it is not clear what the paper is trying to do. \n\nSecond, it is not clear what the paper is trying to achieve beyond what was already done in Michaud et al's \"Quantization Hypothesis\" paper (for the record, the paper proposed the multi-task sparse parity problem as a example exhibiting scaling laws w.r.t sample size and model size, within the framework of their quantization hypothesis).\n\nFinally, the paper seems to be missing some important literature, for example Cabannes et al. \"Scaling Laws for Associative Memories\" (ICLR 2024), which proposes finite-capacity extension of Hutter's model, and establishes an array of different scaling laws for different learning algorithms.", "questions": "In what way do (3) and (9) represent \"a sum of skills\" ?", "limitations": "Yes (in Section 5.4)", "rating": 3, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "As explained already, my low score is because I think the theoretical setup of the paper is unclear. I'm open to changing my mind.", "weaknesses": "As explained already, my low score is because I think the theoretical setup of the paper is unclear. I'm open to changing my mind.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, thank you for being open to discussing what was unclear to you in the paper. Please see our response below.\n\n * Theoretical setup clarification\n\nRegarding the sum of skill functions, we believe the confusion arose from interpreting the input variable $i$ – which depends on the data points – as a fixed index such as $k$: note that $(i,x)$ as a pair form the input. \n\nThe $k^{th}$ skill function $g_k$ and the target function $f^*$ are different functions. For example, a datapoint $(i,x)$ with $i=k+1$ and any $x$ will result in $|g_k(k+1,x)| = 0$ (Eq. (2)) while $|f^*(k+1,x)| = |Sg_{k+1}(k+1,x)| = S$. Of course, a datapoint $(i,x)$ with $i=k$ will lead to $S|g_k(k,x)| = f^*(k,x)$.\n\nThe Kronecker delta in your equation appears only if $i=k$, which is true only for datapoints from the $k^{th}$ skill (the skill bits are one-hot with the $k^{th}$ entry equal to 1), but not for other datapoints. We believe the clarification will also remove the confusion regarding Eq. (3) and Eq. (9).\nIf still in doubt, please look at our example below using Table 1.\n\n\n * Contributions beyond Michaud et al.\n\nOur goal was to provide the simplest quantitative model that captures the intuition of Michaud et al. 2023, to provide a rigorous derivation of the scaling laws, and to predict the emergence of an MLP. Please see “Contribution beyond Michaud et al. 2023” in the global rebuttal for details.\n\n * Recent literature\n\nFinally, we thank the reviewer for suggesting some related literature, which we will add to our related work section (in particular, the work: Cabannes et al. \"Scaling Laws for Associative Memories\" (ICLR 2024)).\n\n\n * Table 1 Example\n\nIn our Table 1, note that the first column represents $i$ for a given datapoint, the second column represents $i$ in control bits, and the third column the skill bits $x$. The $(i,x)$ as a pair form the input to the model. The fourth column, which is noted as $y$ is equivalent to the target function $f^*(i,x)$. From the sixth to the last columns are the skill functions from $g_1(i,x)$ to $g_{n_s}(i,x)$.\n\nIt is indeed true that for a single datapoint (a row), $f^*(i,x)$ (column 4) is a multiple of $g_i(i,x)$ (column $i+5$). However, no single skill function $g_k$ (a single column between $6$ and $n_s + 5$) can represent $f^*$ (column 4) for **all datapoints (all rows)**. Thus, we need the target function $f^*$ to be a sum of all skill functions (scaled by $S$) in Eq.(4).\n\nIn order for the relationship provided by the reviewer to hold, we must assume that the data distribution is generated by a single skill only (justifying that the Kronecker delta $\\delta_{ik}$ holds for all datapoints), making the problem a sparse parity and not a `multitask’ sparse parity problem.\n\nIf the reviewer finds our clarification insufficient or unclear, please do not hesitate to let us know.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PoCmy99DkK", "reviewer": "Reviewer_owz9", "summary": "This paper provides an in-depth study of a toy dataset and model, both in terms of scaling laws and emergent skills. They study the ‘multitask sparse parity’ synthetic problem introduced by Michaud et al. (target is the parity function of a string of random bits, each task indicates a different subset of bit ids, task frequency follows a power law). New in this work, they consider a ‘multilinear’ model (i.e. $y=ab x$ rather than simply $y=cx$) to incorporate the dynamics of a two layer neural net (as per Saxe et al. in a different setting).\n\nThe paper recovers scaling laws (which agree with Michaud et al.’s coefficients for T, D & N, and additionally adds for C=TN). The model also gives rise to emergence of each skill with a sigmoidal shape. Rarer skills are learned later on.", "questions": "See weaknesses.", "limitations": "Fine.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- From a technical perspective, the paper is a very strong and complete piece of work. It exhaustively sweeps through results and surrounding analysis of the setup studied in the paper (even, for example, having proofs of the scaling laws in increasing resolution).\n\n- I have confidence in the claims and analysis. I spot checked several parts in depth, however, I have not been able to interrogate all claims and analysis in the paper (the appendix pushes the paper to 54 pages).\n\n- Providing a model that unites sigmoidal-shaped skill emergence with scaling laws, is a tantalizing prospect, as these are two major properties of LLMs. A theoretical model combining the two aspects would be of high interest to several parts of the community.", "weaknesses": "- The paper contains a huge amount of material. A lot of the good stuff is buried in the appendix (related work is important, the contrast with a linear $y=cx$ model, the scaling law proof sketches, the stage-like training discussion). The reading experience suffers from this, and a conference paper struggles to do it justice. It's possible it would be better suited to a long-form journal format (and would allow reviewers more time to comb through the details).\n\n- The scaling laws derived by the paper match the coefficients found in Michaud et al. (with the addition of $C$). There is a slight difference in that the setup now uses $y=abx$, but I generally felt that given the repeated outcome, providing scaling laws derived with varying resolutions need not be such a major focus of the paper and appendix (maybe some nuance has been lost on me?). Reducing this would free up bandwidth to allow readers to absorb the other more interesting parts.\n\n- A concern I have is in how realistic the setup of the dataset and model is. The emergence and scaling laws come from a lightweight two-parameter linear regressor which receives ideal task indicators as input. The closest interpretation in a real setting I can think of, is as a two-layer linear MLP head, placed on top of a deep pretrained model that is frozen with powerful representations for each task already learned. This paper is still valuable, but I might suggest a more scoped title because of this – ‘an exactly solvable model for emergence and scaling laws’ is not inaccurate, but might be a little broad.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, thank you for your kind comments and especially for dedicating the time to read through the appendix in depth.\n\n * Material in the appendices \n\nWe appreciate your suggestion regarding the suitability of our paper for a journal format. We fully agree that a journal-style paper would allow for a more detailed narrative and potentially provide an easier reading experience. At the same time, we believe that presenting this work at a conference like NeurIPS is valuable: scaling laws and emergence are of great current interest to the broad ML community, and the conference format enables us to share our findings with a general audience and receive valuable community feedback, potentially inspiring further research. \n\nWe have strived to balance the conference format constraints with the depth of our work by including substantial appendices. These appendices serve to clarify our intuitions and make connections for readers from various backgrounds, while keeping the main paper focused and concise. We appreciate your thorough review of both the main paper and the appendices, and we thank you for recognizing the value of the additional material we provided.\n\n\n * Focus on the scaling laws\n\nEven though we wanted to put only the formal derivations in the appendix (mainly C, E, F, and J)  and present all our intuition in the main text, some intuitive arguments had to be added to the appendix (mainly D, G, and H) for an integrated presentation of our contributions. That said, we still think there is room for further emphasizing the effective decoupled dynamics of MLPs and emergence in our work as suggested by the reviewer.\n\n * Realistic setups \n \nWe appreciate your comment regarding the connection between our model and MLPs.\nWhile our current paper provides a focused exploration of our theoretical model, we acknowledge that a comprehensive justification of its applicability to general setups, encompassing (both theoretical and empirical), would constitute a significant body of work meriting its own dedicated study.\n\nWe, however, share our intuition on why a simple model with prebuilt powerful representation approximates the properties of an MLP in the following paragraphs: in the second paragraph of Section 6 in the main text, in the discussion of the effective-decoupling in Appendix D.3, in an example scenario of MLP in Appendix G. Please see “Intuition and limitations of our model” in the global rebuttal for details.\n\nRegarding the scope and the title, we fully appreciate your concerns and plan to change the title of the paper as suggested. Please see “Scope of the paper and its title” in the global rebuttal.\n\nWe again thank the reviewer for investing the time to thoroughly read our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Yy2iejxTVc", "reviewer": "Reviewer_D3CL", "summary": "I’ll write two summaries: one to state my “moral” understanding of the work and another to state the specific contributions \n\n**“Moral” Summary:** The authors propose an analytically solvable model to study scaling laws and emergent abilities by combining the problem of Barak et al 2022 + the data distributional assumptions of Michaud et al. 2023/2024 + the model of Saxe et al. 2024 + their own innovations.\n\n**Specific Summary:**\n\n- The authors study the multi-task sparse parity problem studied by Barak & Michaud\n- The authors propose a multilinear model that identifies each sparse parity problem as a “skill” and then define the learned function as a “multilinear” (i.e. two independent linear parameters) function of the “skill” basis functions\n- In this model, one can then exactly compute scaling and emergent abilities as a function of the typical scaling parameters (compute, data, parameters)\n- The authors also train 2 layer MLPs and transformers to test how closely their maths match empirical results", "questions": "Figure 4: What is the timescale of each skill’s emergence for the transformer? I can’t tell if the higher k lines are step functions or sigmoidal functions that are compressed by the log scaling of the x axis. To be clear, I’m not asking for when the skills emerge, but how long it takes for each skill to emerge.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Overall, I think this is a really well done paper (although I’m concerned about Figure 1 - see weaknesses). What it does, it does thoroughly.\n- Table 1 is useful in helping explain the multi-task parity problem\n- Table 2 is a great way to summarize and organize both the results as well as the conditions of each result", "weaknesses": "- Emergence is a phenomenon studied at scale, and while I strongly support trying to find simplified models of large-scale phenomena, I feel that there needs to be an attempt to connect back to the original phenomena of interest. For instance, Michaud et al. 2023/2024 (Citation 17 in this paper) - on which this work most closely connects - at least attempts to look into real language model pretraining data. In contrast, this paper makes no such attempt, which I think strongly limits it. This is the #1 reason I don't feel comfortable giving a higher score.\n- Following the above point, I consequently think a more focused title (e.g., “An exactly solvable model for emergence and scaling laws in the multitask sparse parity problem”) would better represent this paper.\n- For an exactly solvable model, Figure 1 shows that the predictions only roughly match the experimental results. This becomes especially pronounced for higher k. For instance, look at Figure 1(c) orange. The prediction is that there should be a rapid leap from 0 to 1, but instead, there is a sigmoid-like transition with long tapering tails. Green, red and purple are all similar. The inability to predict 2-layer MLPs makes me think that this analytically solvable model is already only an approximation of incredibly simple networks", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, thank you for your comments on the paper and for appreciating our tables. Your moral summary represents our motivation in the paper well. \n\n * Realistic setup and the title of the paper\n\nWe fully appreciate your comment on the scope/limitation of the paper and thank you for suggesting to change the title to specify its scope and motivation. Please see “Scope of the paper and its title” in the global rebuttal.\n\n * Theory and experiment matching in Fig.1(c) \n\nWe appreciate the reviewer's careful observation of Figure 1. The discrepancies noted, particularly for higher $k$, are indeed due to the abstraction of our model. We expect the deviation to enlarge at higher $k$ as the SGD noise becomes more comparable to the difference in the skill frequencies and the effective-decoupling assumption (second paragraph of Section 6) weakens. Please see “Intuition and limitations of our model” in the global rebuttal. \n\nWe acknowledge that our model is an approximation as its purpose is to serve as a baseline for understanding more complicated dynamics in NNs. The strength of our approach lies in its ability to provide analytical predictions and an intuitive understanding of key phenomena, which would be challenging to achieve with more complex models. We believe this trade-off between simplicity and predictive power is valuable for advancing theoretical understanding in the field. Please see “Scope of the paper and its title” in the global rebuttal.\n\nWe discuss the limitations of our model in Section 5.5 and share our intuition on why it closely approximates an MLP in Section 6. Regarding the specific case of Figure 1(c), the discrepancy observed in MLPs is partly due to initialization-dependent learning outcomes, which our model doesn't explicitly incorporate. As discussed in the last paragraph of Section 5.5 and in Table 5 in Appendix I, the initialization-dependent learning failures in MLPs affect $\\mathcal{R}_k$, especially when MLP has only a handful of hidden neurons to learn the skills: Even when an MLP can express all skill functions, it may fail to learn due to unfavorable initialization or inefficient use of its hidden neurons. We have argued how such outliers increase the standard deviation of the overall performance metric $\\mathcal{R}_k$, but the argument also explains why the mean of $\\mathcal{R}_k$ fails to saturate to $S$. \n\n\n * Question: The time scale of each skill’s emergence in transformers\n\nThe timescale of the transformer is in optimization steps. Analogous to the assumption in the stage-like training (Figure 6 in Appendix D), the saturation time is typically significantly smaller compared to the emergence time (when it starts to emerge) even in linear time scale. Please see Figure 1 of the attached pdf in the global rebuttal. \n\nThe saturation time (how long it takes to emerge) is approximately 500 steps for the first skill and 5,000 for the fifth skill. All saturations show a sigmoid-like saturation, but are more distorted compared to that of the 2-layer MLP. Please see Figure 2 of the attached pdf in the global rebuttal. If the reviewer has additional comments or questions, please do not hesitate to let us know.\n\n \nWe again thank the reviewer for the suggestion of the title and for dedicating the time to review our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Hge0LnmCdw", "reviewer": "Reviewer_TV9v", "summary": "The paper presents a model capable of predicting the appearance of emergent abilities, using only information on the emergence of the first ability. The model successfully predicts emergence in a 2-layer MLP solving the multitask sparse parity problem, a toy-model problem constructed with a power-law skill distribution, to mimic the theorized distribution of language datasets. The model also exhibits scaling laws known to exist in this problem.", "questions": "The main section of the paper does not explain why the input data is distributed as a power law (Zipf's law), making it hard to understand the justification for readers unfamiliar with previous literature, i.e. Michaud et. al. I would suggest adding a short explanation when introducing the problem.", "limitations": "Limitations are adequately discussed, including scope limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper expands on recent works, in a significant and active field of research. The authors present convincing results when evaluating the proposed emergence model against MLP training data. Extensive derivations are provided in the appendix, although I did not carefully check them. The paper is written in a clear manner and results are visualized in clear formats.", "weaknesses": "- The scope of the experiments is too small in my opinion, specifically Figure 1. It would be nice to see results for a lot more than 5 skills, since it seems possible that predicting the emergence of less-frequent skills becomes harder at higher orders of magnitude. My impression is that the experimental setup is light enough that scaling up will not require unreasonable resources.\n\n- The general scope of the paper is a bit small, focusing only on the multitask sparse parity problem. It would have been nice to see results on more natural settings. That said, the current results on the chosen problem setting are still interesting on their own.\n\n- Regarding the scaling laws presented in Table 2, glossing over the paper gives the impression that these are new scaling laws found by the authors, when in fact they are reproductions of the scaling laws calculated by Michaud et. al. It might help to clarify the relation to Michaud et. al. in the main section of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, thank you for taking the time to review our paper. We appreciate your comments and suggestions.\n\n * Scope of the experiments\n\nAdditional learning of the skills, as correctly spotted, requires another order of magnitude of computation which challenges our computational budget. The predictive power of our model indeed relies on the effective-decoupling assumption (second paragraph of Section 6 and Appendix D.3) of the skills in MLP, which is weakened at larger $k$ because of the noise in SGD. Please see “Intuition and limitations of our model”  in our global rebuttal for details. \n\n\n * Scope of the paper\n\nIndeed, we agree that we focused on a more idealized, abstract, and more feasible setup over more complicated but practical scenarios requiring significant computation budgets. We believe a more specific title correctly informs the scope and motivation of the paper. Please see “Scope of the paper and its title”  in the global rebuttal. \n\n * Scaling laws presented in Table 2\n\nIn fact, as described in the second paragraph of Section 4, we arrive at the same scaling law as Hutter 2021 for data and Michaud et al. 2023 for time, data, parameters. Table 2 was to emphasize our novel contribution: how the proposed model leads to rigorous derivation of the scaling laws (please see “Contributions beyond Michaud et al. 2023” in our global rebuttal for details). That said, we are happy to incorporate this information in the caption of Table 2 for clarification.\n\n * Question: the power-law input data\n\nWe appreciate the reviewer's suggestion to provide more context on the power-law distribution of input data. We agree that a brief explanation in the main text would benefit readers less familiar with the literature. We will update our paper to include this explanation.\n\nRegarding the justification for the power-law assumption: As the reviewer recognizes, real-world tasks often exhibit a spectrum of skill frequencies (such as Zipf's law). For instance, in language tasks, placing common words like 'the' or 'is' in a sentence occurs frequently, while correctly using specialized technical terms or rare words occurs much less often. \n\nWe again thank the reviewer for helpful comments and for taking the time to review our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear reviewers and AC, we present a global rebuttal to address the overlapping reviews. 

 
## Scope of the paper and its title 

As most reviewers have pointed out, the primary strength of our paper is the detailed theoretical analysis of the scaling laws and emergence with a concrete model while the main weakness lies in the lack of empirical work on larger models in more natural setups.

Even though we fully appreciate the importance of gaining predictive power in larger models with real-world datasets, we mainly focused on theoretical tractability over realism, and believe the work is meaningful on its own by providing 1. clear isolation of key phenomena (emergence and scaling laws) without confounding factors present in more complex systems and 2. rigorous mathematical analysis and derivation from fundamental principles for future works.

On that note, we fully appreciate the comments on how the title is less focused and potentially suggests a scope beyond our intentions. As commented, a more detailed title such as **“An exactly solvable model for emergence and scaling laws in the multitask sparse parity problem”** better represents the scope and motivation of the paper. We thank the reviewers for pointing this out.

## Contributions beyond Michaud et al. 2023

As acknowledged by some reviewers, our work can be viewed (though not limited to) as a theoretical formalization of the quanta hypothesis Michaud et al. 2023 in which we wish to emphasize our contribution in more detail.

The quanta hypothesis from Michaud et al. 2023 lacks mathematical formalism (i.e., both quanta and skills are not mathematical objects) and lacks the derivation of scaling laws under “gradient descent dynamics” (it was stated that the skills were learned by some criteria, see e.g., the Quantization Hypotheses on page 3 of Michaud et. al, https://openreview.net/pdf?id=3tbTw2ga8K).

We provide a formal model trained on gradient flow that 1. analytically reproduces the scaling laws (including the prefactor constants) and 2. predicts emergence in 2-layer MLPs. The quantitative prediction of emergence in 2-layer MLPs is novel and no modeling or prediction for the emergence phenomenon was studied in Michaud et al. 2023. We believe such formalism serves as a baseline for future more complex models for understanding scaling laws and emergence in more practical NNs.

 ## Intuition and limitations of our model

Our work presents a simplified model that approximates complicated feature learning dynamics of an MLP with a decoupled basis functions and a product of parameters. Even though our work suggests that our assumptions effectively capture the emergence in MLP (e.g. Fig.(1)), the exact conditions for the assumptions to hold and whether it holds in larger models with realistic dataset requires further study.

We, however, extensively share our intuition on why our model approximates the emergence in MLPs (Second paragraph of Section 6, Appendix D.3, Appendix G, and Appendix I) and also the limits of our model of why it may diverge from the dynamics of MLPs (Section 5.5). 

For example, we give some evidence that our model well-approximates the MLP because of the effective decoupling in MLPs or that skills are feature-learned in stages (Second paragraph of Section 6 and Appendix D.3). The large difference in skill frequencies, analogous to stage-like training (Appendix D) of parameters in multilinear models, allows each $g_k$ to be learned at different time scales: justifying why the decoupled dynamics of our multilinear model is a good approximation. Unfortunately, the absolute difference in skill frequencies becomes comparable to SGD noise as $k$ increases: creating a larger divergence for larger $k$. The noise from SGD can be mitigated with a larger batch size, but we then require another magnitude in training time and batch size that challenges our limited computational budget.

Meta-review: This paper introduces an analytically solvable model to explain neural scaling laws and presents a thorough analysis of the model. All reviewers gave positive reviews and were supportive of acceptance.
Decision: Accept (poster)