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_cc_2024_Conference
Published: 2024-05-10 18:21:56

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.

Main paper: 
 introduction: 
 Emergence in large language models (LLMs) has attracted a lot of recent attention [1] [2] [3] [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 on 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 are learned for larger models raises many challenging questions: when 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] .Another widely observed property of deep learning models is that the loss improves predictably as a power-law in the number of data points or the number of model parameters or simply in the amount of compute thrown at a problem. These neural scaling laws [8, 9] have been widely observed across different architectures and datasets [10] [11] [12] [13] [14] [15] [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?A challenge in answering the questions raised by the phenomena of emergence and scaling laws arises from the enormous scale and expense of training cutting-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 in 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 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 a proxy for studying emergence and neural scaling in LLMs. For this data set, the authors empirically measure the scaling laws of a 2-layer multilayer perceptron (MLP) as a 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 a 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 a skill that can be learned, and their respective frequencies are distributed following a power-law with exponent α + 1. We then propose a simple multilinear expansion in these orthogonal functions that introduces a 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 a function of data exponents α, T, D, N , and optimal compute C. Our simple model can, with just one parameter calibrated to the emergence of the first skill, predict the ordered emergence of multiple skills in a 2-layer MLP. We summarize our contributions as follows:1. Skills as basis functions. We establish a framework for investigating emergence by representing skills as orthogonal functions that form a basis in function space (Section 2). We apply our methods to controlled experiments on the multitask sparse parity dataset. 2. Multilinear model. We propose an analytically tractable model that is expanded in the basis of skill functions, and is multilinear with respect to its parameters so that it 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 to training time (T ), dataset size (D), number of parameters (N ), and optimal compute (C = N × T ), see Section 4. We show that the scaling exponents for these factors are -α/(α + 1), -α/(α + 1), -α, -α/(α + 2), respectively, where α + 1 is the exponent of the power-law input data. 4. Predicting emergence. We demonstrate that our multilinear model captures the skill emergence 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. 1 and Section 5. We obtain an equivalent result on the time emergence for a transformer architecture (Fig. 4 ). k = 1 k = 2 k = 3 k = 4 k = 5 k = 1 k = 2 k = 3 k = 4 k = 5Figure 1 : Predicting emergence. The skill strength R k , defined as the k th coefficient if a model is expanded in the basis of the skill functions (g k ), measures how well the k th 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). R k is normalized by the target scale S such that R k /S = 1 means zero skill loss. The dashed lines show the abrupt growth -emergence -of 5 skills for a 2-layer MLP (Appendix K) trained on the multitask sparse parity problem with data power-law exponent α = 0.6 (shaded area indicate 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 n sdimensional 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 S multiplied by the parity computed from the relevant bit set M (i, x). The last columns show the values of the skill basis functions g k (i, x), defined in Eq. (2) .Skill idx (I) Control bits Skill bits (X) y M (i, x) g 1 (i, x) g 2 (i, x) . . . g ns (i, x) 1 
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 in a model by calculating the linear correlation between the model output and the skill basis functions. For a comprehensive list of notations, refer to the glossary in Appendix A. Our code is also available online. 1Multitask sparse parity problem. In the sparse parity problem, n b skill bits are presented to the model. The target function is a parity function applied to a fixed subset of the input bits. The model must detect the relevant m < n b sparse bits and return the parity function on this subset (M (i, x), see Table 1 ). Michaud et al. [18] introduced the multitask sparse parity problem by introducing n s unique sparse parity variants -or skills -with different sparse bits (for a representation, see Table 1 ). Each skill is represented in the n s control bits as a 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 s skills (random variable I ∈ {1, 2, . . . , n s }) follow a power law distribution P s , and the skill bits (random variable X ∈ {0, 1} n b ) are uniformly distributed. Because P s and P b are independent, the input distribution P(I, X) follows a product of two distributions:P s (I = i) := i -(α+1)ns j j -(α+1) , P b (X = x) := 2 -n b , P(I, X) := P s (I)P b (X).We denote A = ns j=1 j -(α+1) -1 so that P s (i) := Ai -(α+1) .Skill basis functions. We represent the k th skill as a function g k : {0, 1} ns+n b → {-1, 0, 1} that returns the parity ({-1, 1}) on the k th skill's sparse bits if i = k, but returns 0 if the control bit mismatches that of the k th skill (i ̸ = k):EQUATIONwhere M : {0, 1} ns+n b → {0, 1} m is the map that selects the relevant sparse bits for the i th skill (Table 1 ) and M j (i, x) is the j th entry of M (i, x). Note that different skill functions have 0 correlation as the supports of skills functions are mutually exclusive:EQUATIONThe target function. The target function is a sum over n s skill functions multiplied by a target scale S:EQUATIONThe target scale S is the norm of the target function (E I,X [f * (I, X)f * (I, X)] = S 2 ). Note that the skill functions serve as 'features' or countable basis for describing the target function as in Hutter [20] .MSE loss. We use MSE loss for analytic tractability:EQUATION)where f is the function expressed by a given model. We define the skill loss L k as the loss when only the k th skill is given, which can be weighted by their skill frequencies to express the total loss:EQUATION)Skill strength. The skill strength or the linear correlation between the k th skill (g k ) and a function expressed by the model at timeEQUATIONThe skill strength R k is the k th coefficient if a model is expanded in the basis of the skill functions (g k ). The skill strength, like the test loss, can be accurately approximated by a sum (see Appendix K.3). The skill loss L k (Eq. ( 6)) can be expressed by the skill strength and the norm of the learned function for I = k:EQUATIONThe skill loss becomes 0 if and only if fT (I = k, X) = Sg k (I = k, X).Experimental setting. We use a 2-layer MLP that receives the n s + n b bits as inputs and outputs a scalar ({0, 1} ns+n b → R). In most of the experiments, the NN is trained with stochastic gradient descent (SGD) with width 1000, using n s = 5, m = 3, and n b = 32, unless otherwise stated. A decoder transformer is also used for the time emergent experiments. See Appendix K for details. 
multilinear model: 
 We propose a simple multilinear model -multilinear with respect to the parameters -with the first N most frequent skill functions g k (i, x) as the basis functions (features):EQUATIONwhere a, b ∈ R N are the parameters. The model has built-in skill functions g k -which transform control bits and skill bits into the parity outputs of each skill -so the model only needs to scale the parameters to a k b k = S.The multilinear structure (product of a k , b k ) is analogous to the layered structure of NNs and results in emergent dynamics (Fig. 1 (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 a k (T )b k (T ) is the skill strength R k (Eq. ( 7)) and the skill loss (Eq. ( 6)) is a function of S and R k only:EQUATION)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 g k 's supports are mutually exclusive. This decouples the dynamics of each skill (R k (T )), which is analytically solvable under gradient flow (Appendix C.1).EQUATIONwhere d k is the number of samples of the k th skill (i.e., number of samples (i, x) with g k (i, x) ̸ = 0), η is the learning rate, and 0 < R k (0) < S is the skill strength at initialization. 
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 (T ), data (D), parameters (N ) and optimal compute (C). We define compute asC := T × N [21].Table 2 shows our analytical scaling laws including their prefactor constants (Appendix J) and Fig. 2 compares the simulation of our model with our 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 < α < 1, the exponents are 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 as a function of time (T ), data (D), parameters (N ), and the number of observations for each skillEQUATIONUnder suitable assumptions (e.g., for the T scaling law, we take D, N → ∞ and d k /D → P s (k)), we can use Eq. ( 12) to derive the scaling laws. For T, D, and N , we used Eq. ( 11) -decoupled dynamics induced the basis functions g k -to decouple the evolution of each skill loss:1. For the time scaling law, each L k shares the same dynamics with T scaled by P s (k).For the data scaling law, each L k depends only on the observation the k th skill (d k > 0).For the parameter scaling law, each L k depends on whether the model has g k 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 to fit the N th skill (Fig. 3 ). In Appendix J, we show rigorous derivations of all scaling laws, including the prefactors, error bounds, and conditions (e.g., how large N must be compared to T to be treated as 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. 
predicting emergence: 
 The literature on emergence has rapidly expanded lately; for a review of these developments, see Section 7. In this section, we analyze the emergence of a 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 g k . 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 s = 1) system and use it to predict the emergence of subsequent skills for the n s = 5 setup (Fig. 1 ).In our multilinear model, the layerwise structure -the product of parameters a k b k -leads to a sigmoidal saturation where an update of one layer hastens the update of the other layer. Feature 1)). See the appendices for 1) rigorous derivations of the theoretical scaling laws including the exponents, prefactors (e.g., A N for L = A N N -α ), and conditions (Appendix J); 2) simplified derivations of the exponent only (Appendix E); 3) details of the experiment (Appendix K.4).α = 0.3 α = 0.6 α = 0.9 L = A T T -α/(α + 1) D, N → ∞ L = A D D -α/(α + 1) N, T → ∞ L = A N N -α T, D → ∞ α = 0.3 α = 0.6 α = 0.9Table 2 : 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 be treated as infinity. The fourth column is the bottleneck resource'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) in Appendix J. (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 N skills (i.e. when the solid lines plateau). For the case α = 0.3, the optimal C for the model decays faster than the power-law, see Appendix E.1.α = 0.3 α = 0.6 α = 0.9 α = 0.3 α = 0.6 α = 0.9learning dynamics in a 2-layer MLP shares the positive feedback between the layers but require a non-trivial update of parameters to express g k .Extended model. Given that feature learning, though nonlinear, involves parameter updates, we compensate for the additional delay in feature-learning by multiplying g k by a calibration constant 0 < B < 1:EQUATIONThe calibration constant B rescales the dynamics in T (Eq. ( 11)):EQUATION)where d k /D → P s (k) because we assume D → ∞. We observe that B 2 = 1/22 fits the NN trained on one skill (see Fig. 11 in Appendix I), and the calibrated model predicts emergence in the n s = 5 system (Fig. 1 (a)): suggesting that the dynamics of feature-learning g k in 2-layers NNs is similar to that of parameter learning (a k b k ) in a simple multilinear model. For further intuition of the extended model, see an example of time emergence in an NN in Appendix G.Our multilinear model can learn the k th skill with a single observation of the skill because the skill functions g k are built in (see Corollary 1 in Appendix C.2). NNs, without the fixed basis functions, must 'discover' each g k , which requires multiple samples from the k th skill.Extended model. To make our model a D c -shot learner, we extend it by replacing g k with the e k,l basis:EQUATIONwhere the matrix B ∈ R N ×Dc is an extension of b ∈ R N in Eq. ( 9), D c is a fixed scalar, and e k,l (i, x) : {0, 1} ns+n b → R are functions with the following properties:EQUATIONThe first property states that e k 's, when I = k, are orthonormal in X. The second property asserts that, similar to g k (Eq. ( 2)), e k,l is non-zero only when I = k, and fitting of the k th skill only occurs among e k,l 's, keeping the skills decoupled. The third property states that g k can be expressed using e k,l .For the k th skill, the extended model overfits g k when there are fewer observations (d k ) than the dimension of the e k,l basis (D c ), and fits g k when d k ≥ D c , making our model a D c shot learner.D c shot learner. If 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 → ∞) on D datapoints isEQUATION)The number d k is the number of samples in the training set for the k th skill (i.e., datapoints with g k (i, x) ̸ = 0).Proof See Appendix F.3. ■ Using Eq. ( 17), we can calculate the emergence of R k /S as a function of D. Note that Eq. ( 17) is similar to the model in Michaud et al. [18] in that, to learn a skill, the model requires a certain number of samples from the skill.The derivation of Eq. ( 17) follows trivially from the dynamics of the extended model (Eq. ( 15)) and well-known results in linear/kernel regression [23] [24] [25] [26] [27] . To be more specific, the model finds the minimum norm solution as if we performed ridgeless regression on g k with basis functions [e k,1 , • • • e k,Dc ]. See Appendix F.3 for details.We observe that D c = 800 approximates the data emergence for the n s = 1 system (see Fig. 11 in Appendix I) and also the emergence for n s = 5 system (Fig. 1(b )), suggesting that the NN discovers g k when it observes D c samples from the k th skill.Since our multilinear model has g k 's as the basis functions, it requires only one basis function (2 parameters) to express a skill (see Corollary 2 in Appendix C.3). A 2-layer NN cannot express a skill with a single hidden node (i.e., a hidden layer with width 1); it requires multiple hidden nodes to express a single skill.Extended model. To compensate for the need for multiple hidden nodes in expressing one skill, we extend our model similarly to Eq. (15) . Because the number of parameters is now a bottleneck, we ensure the model has N basis functions (e k,l 's):f T (i, x; a, B) = q-1 k=1 Nc l=1 a k (T )B k,l (T )e k,l (i, x) + r l ′ =1a q (T )B q,l ′ (T )e q,l ′ (i, x),where N c is the number of basis functions needed to express a skill, quotient q is ⌊(N -1)/N c ⌋ + 1 and remainder r is such that (q -1)N c + r = N . In short, the N basis functions areEQUATIONSimilar to Eq. ( 16), the basis functions satisfy the following propertiesEQUATIONN c basis functions for a skill. For the extended model in Eq. (18), the skill strength at T, D → ∞ for a given N becomesEQUATION)Proof See Appendix F.4. ■The model can express the k th skill based on the number of available basis functions for the given skill (Eq. ( 21)). For example, skills with k < q have all N c basis functions [e k,1 , • • • , e k,Nc ] to express the k th skill (Eq. ( 20)), while for k = q, only r of the N c basis functions are available.We observe that N c = 4 fits the parameter emergence for the n s = 1 system (see Fig. 11 in Appendix I) and also the emergence for the n s = 5 system (Fig. 1(c )), suggesting that the NN requires 4 nodes in expressing g k . 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.To test whether our conceptual framework extends to other architectures, we perform a time emergence experiment with a transformer (Fig. 4 ). Note that the emergent time τ emerge -when the skill strength is sufficiently larger than 0 -follows the same power-law relationship as Eq. ( 11): τ emerge (k) ∝ k α+1 (see Fig. 6 in Appendix D 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. The emergent times follow a power law of k α+1 , following the same relationship in the multilinear model (Eq. ( 11)).R k /S k = 1 k = 2 k = 3 k = 4 k = 5The 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 a single calibration. The weakness of our model is that it simplifies the more complex dynamics of NNs. Time emergence. We note that the NN and the multilinear model emerge at similar instances, but the NN takes longer to saturate fully. This is because, for a given skill, the dynamics of the NN is not one sigmoidal saturation but a 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-linearity and the function it expresses, each neuron is updated at different rates, and the slowly saturating neurons result in a longer tail compared to our multilinear model. For an example, see Fig. 8 in Appendix G. Data point emergence. Our extended model (Eq. ( 17)) deviates from NNs when d k ≪ D c and NNs show a more abrupt change in R k as a function of D. This is because our model asserts strict decoupling among the skills: even a few d k will contribute to learning g k from e k,l . 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 as '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 I for an example of such outliers). Because NNs are less strictly biased toward frequent skills than our model, we 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 a 2-layer MLP using a 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 is observed in 2-layer MLPs.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] [34] [35] [36] [37] [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] ), we studied a simple model on an idealized powerlaw distributed dataset. Also, our model cannot capture the complex non-linear interactions among multiple skills but can express any linear superposition of skills. In future work, we will explore 'complex skills' in language as a superposition of linearly independent skills. By validating our findings in language tasks, we aim to contribute to a broader understanding of how neural networks acquire and exhibit complex behaviors. 
related works: 
 In this section, we review the literature on scaling laws and emergence in NNs. Focusing on data scaling, Hutter [20] develops a model with a discrete set of features. Under the assumption of a power-law distribution of features, this model demonstrates that the error decreases as a power law with increasing data size. In a related vein, Michaud et al. [18] propose a model of neural scaling laws in which the loss is 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 random-feature models [41, 21] , 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] [2] [3] [4] document examples of such emergent abilities. Arora and Goyal [44] propose a framework for the emergence of tuples of skills in language models, in which the task of predicting text requires combining different skills from an underlying set of language abilities. Okawa et al. [45] demonstrate that a capability composed of 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 a methodology for grading such evaluations, and Chen et al. [47] , who formalize the notion of skills and their natural acquisition order in language models. The computation cost T × N n s 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA]  
 
 Appendix: The number of skills in the multitask sparse parity problem I Random variable of the control bits X Random variable of the skill bits P s Probability of skills (control bits) P bProbability of skill bits SThe target scale or the norm of the target function R kSkill strength of the k th skill (Eq. ( 7)) L Total (generalization) loss L (D) Empirical loss for D samples L k Skill loss of the k th skill (Eq. ( 6))d kNumber of observation of the k th skill (i.e. number of training pointsEQUATION)) g kThe k th skill basis functionEQUATION))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 a powerlaw distribution. In this example, there are n s = 10 tasks, and skill bits are length n b = 15. The y column is the resulting parity computed from m = 3 bits (highlighted in colors). The multitask dataset provides a controlled experimental setting designed to investigate skills. In this section, we review the multitask sparse parity dataset, as described by Michaud et al. [18] and discuss the nonlinear dynamics of two-layer linear networks, following the work of Saxe et al. [19] .The sparse parity task can be stated as follows: for a bit string of length n b , the goal is to 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 s unique sparse parity variants in the dataset. The input bit strings have a length of n s + n b . The first n s bits function as indicators by assigning a specific task. The frequency of the distinct parity tasks follows a rank-frequency distribution with an inverse power law relation (power-law distribution). The last n b bits are uniformly distributed. This sets a binary classification problem {0, 1} ns+n b → {0, 1} where only a single bit of the initial n s bits is nonzero. In Table 3 , the many distinct parity tasks represent different skills. 2The 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 of computations, are distinct and separate; (ii) these skills differ in their effectiveness, leading to a ranking based on their utility to reduce the loss; and (iii) the pattern of how frequently these skills are used in prediction follows a power-law distribution. Interestingly, the multitask problem has a 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 a sudden shift occurs after an initial phase of no noticeable improvement, leading to reverse sigmoid-shaped learning curves. Michaud et al. [18] empirically show that for a 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 in a smooth decrease in the overall loss as the number of skill levels increases.Saxe et al. [19] have solved the exact dynamics for two-layer linear neural networks with gradient descent under MSE loss (Fig. 5 (a)). 3 The dynamics decompose into independent modes that show sigmoidal growth at different timescales (Fig. 5 (c)). The setup assumes orthogonal input featuresEQUATION... ... 24)). The product of parameters a k b k are learnable parameters and vectors u k , v k are obtained from SVD of the input-output correlation matrix Σ (Eq. ( 22)). (c): The temporal evolution of a k b k under gradient descent, which follows a sigmoidal growth (Eq. ( 25)). Note that smaller λ k -the singular value of Σ -results in a more delayed saturation of a k b k .By performing SVD (singular value decomposition) on input-output correlation matrix Σ = U ΛV , the target function f * : R d1 → R d3 becomes:EQUATIONwhereu k ∈ R d1 ,v k ∈ R d3are the row vectors of U, V and λ k ∈ R are the singular values of Λ.Saxe et al. [19] have shown that the dynamics of a two-layer (one-hidden-layer) undercomplete (the width of the hidden layer is smaller than the width of the input and output) linear neural network decomposes into that of the following 'modes':EQUATION)where a k , b k ∈ R are the parameters. Note that Eq. ( 24) are d 2 decoupled functions v T k f (x) : R d1 → R (Fig. 5(b) ). Assuming small and positive initialization (0 < a k (0)b k (0) ≪ λ k ), the dynamics of Eq. ( 24) under gradient descent with learning rate η can be solved analytically; the product of parameters a k b k grows sigmoidally with saturation time proportional to λ -1 k (Fig. 5(c )):EQUATION)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)).In this section, we provide derivations of how the skill loss of our multilinear model evolves with a given resource: time (Lemma 1), data (Corollary 1), and parameters (Corollary 2). Note that two corollaries for data and parameters (Corollaries 1 and 2) follow from the decoupled dynamics (Lemma 1).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 2 (input distribution: Eq. (1), target function: Eq. (4), and MSE loss: Eq. ( 5)). Let k ≤ N be a skill index in the multilinear model and the input distribution (k ≤ n s ). Then assuming the following initializationEQUATIONand the skill loss isEQUATION)where η is the learning rate and d k is the number of observations withg k (I = k, x (j k ) ) ̸ = 0. Proof For j = 1, • • • , D, denote (i (j) , x (j)) be the j th data point in the training set. Then the empirical loss for D datapoints is given asEQUATION)We note thatf * (i (j) , x (j) ) -f (i (j) , x (j) ) 2 = ns k=1 (S -a k b k )g k (i (j) , x (j) ) 2 = (S -a i (j) b i (j) ) 2 g i (j) (i (j) , x (j) ) 2 = (S -a i (j) b i (j) ) 2 ,as g i (i, j) ∈ {1, -1} and g k (i, j) = 0 for i ̸ = k. So if we denote d k the number of data points with i (j) = k, then we can concludeEQUATIONwhich is the decoupled loss in the main text (Eq. ( 11)). Using the gradient descent equation and Eq. ( 29), we obtainEQUATIONLikewise, we can obtain the equation for b k asEQUATIONBecause of symmetry between a and b (See Appendix B.2 or [19] ), assuming a k (0) = b k (0), andEQUATIONAssuming a k (0)b k (0) < S, we can solve the differential equation to obtainEQUATION)The equation for L k follows from Eq. (10) . ■ C.2 One-shot learner Corollary 1. For the setup in Lemma 1, theEQUATION)where d k is the number of k th skill's observations.Proof The corollary follows directly from Lemma 1. By takingEQUATIONWe obtain the result by using the relationship between R k and L k in Eq. (10) . ■ EQUATIONProof The corollary follows directly from Lemma 1. By takingEQUATIONWe obtain the result by using the relationship between R k and L k in Eq. ( 10) and R k (0) ≪ S. ■Even though we provide more detailed (Appendix E) and rigorous (Appendix J) derivation of the scaling laws, a less general yet more intuitive solution aids in understanding the scaling laws of our model and NNs. In this section, we 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. R k (T)/S 1 - τ (e)1 ( )τ (s)1 ( )τ (e)2 ( ) k = 1 k = 2When a model exhibits an emergence behavior -when saturation of skill occurs abruptly after a delay -and the intervals between each emergence are sufficiently large, the model admits stage-like training. The multilinear model (sigmoidal saturation of 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 R k /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 τ k (ϵ) = 1 2ηP s (k)S ln S R k (0) -1 1 ϵ -1 ∝ k α+1 , τ (s) k (ϵ) = 1 ηP s (k)S ln 1 ϵ -1 ∝ k α+1 .(40) For sufficiently small initialization (R k (0) ≪ S), we get a stage-like training:EQUATION)where the model finishes learning (saturating) the k th skill before starting to learn (emerging) the next skill.Assuming our model satisfies the stage-like training for all k of interest, we can derive the time scaling law from the stage-like training.At τ (e) k (ϵ), because of stage-like training, all skills with index up to but not including k have saturated (R i<k ≈ S), or equivalently L i<k ≈ 0 (Eq. ( 10)). The total loss, the sum of L j weighted by P s (j) ∝ j -(α+1) (Eq. ( 6)), becomes ∞ j=k P s (I = j)S 2 /2 (Fig. 6(b) ). The saturation of the k th skill results in a loss difference of P s (I = k)S 2 /2. Thus, we obtainEQUATIONAccordingly, the emergent interval between the k and k + 1 skills relative to the τEQUATIONEQUATIONAssuming k ≫ 1 and combining Eq. ( 43) and Eq. ( 45) to the largest order, we have the equation for the power-law with exponent -α/(α + 1) in Fig. 2(a) :EQUATIONIf 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.In Section 5, we have empirically demonstrated that the multilinear model predicts the emergence of a 2-layer NN (Fig. 1 ). In Section 6, we briefly discussed why NNs, despite their lack of the decoupling among the skills, behave similarly to the decoupled model with g k s as fixed basis functions: the stage-like training in 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 g k s are 'discovered' (feature learned) by non-tractable dynamics, we speculate that similar stage-like dynamics also hold in 'discovering' (feature learning) g k s: parameters 'useful' for expressing more frequent skills will be updated significantly faster than parameters useful for expressing less frequent skills.If skill discovery and saturation dynamics operate at different time scales (stages), with negligible interaction among the skills, the skill dynamics become effectively decoupled. Because the dynamics are decoupled in 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 of observations, and number of hidden layer neurons): resulting in a similar emergence to our multilinear model.A more concrete understanding of our speculation that feature learning also occurs in stages due to a layerwise structure is left for future work.This section provides a 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 skills, as a 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 α + 1 is the exponent of the Zipfian input data (Eq. ( 1)).Bottleneck Time Data Parameter Exponent Time (T ) T ∞ ∞ -α/(α + 1) Data (D) ∞ D ∞ -α/(α + 1) Parameter (N ) ∞ ∞ N -α Compute (C) C (α+1)/(α+2) ∞ C 1/(α+2) -α/(α + 2)To derive the time scaling law exponent, we assume the time as the bottleneck and take N, D → ∞. By using the decoupled dynamics of each skill loss (Lemma 1),EQUATION)Noting that d k /D → P s (k) as D → ∞, where P s (k) = Ak -(α+1) , we haveEQUATIONThis is a function of k -(α+1) T only, suggesting the decoupling dynamics for each skill. Thus,EQUATION)Using Eq. ( 6) and taking N, n s → ∞ at the same rate, 4 we can approximate the loss as an integral instead of a sum over k:EQUATION)where A is the normalization constant for P s . We can differentiate the loss and use Eq. ( 49) to express the equation in terms of k:EQUATIONIntegrating by parts, we obtainEQUATION)The first term goes to 0 as N → ∞ and the second term goes to 0 exponentially faster compared to the last term for T ≫ 1, which leads to the scaling law with exponent -α/(α + 1):EQUATION)Finite N correction for small α. In Fig. 7 , we observe that our model with α = 0.1 deviates from the expected power-law with exponent -α/(α + 1). The deviation can be explained by the antiderivative term in Eq. (52): A simulation of our multilinear model with N = 50, 000 (solid), a scaling law with exponent -α/(α + 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 α.limEQUATIONThe second term (k = 1) goes to 0 faster than O(T -1 ) for sufficiently larger T but the first term (k = N ) may not decay fast enough for finite N and sufficiently small α. For example, N = 50, 000 and α = 0.1 leads to N -α ≈ 0.3, which is not negligibly small.Assuming finite N and small α such that the first term in Eq. ( 55) is non-negligible, we can rewrite Eq. (52) asEQUATIONwhere we assumed a small initialization S/R k (0) ≫ 1 and sufficiently large number of parameters N α+1 ≫ T to approximate L C . Because the total loss at initialization is L(0) = S 2 /2, L C is non-negligible compared to the loss for sufficiently small α. Thus considering L C , 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.In this section, we derive the data scaling law exponent. The data scaling law assumes T → ∞ and N → ∞ 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 → ∞, and d k is the number of samples from the training set with g k (i, x) ̸ = 0, the k th skill loss after training isEQUATION)Proof See Appendix C.2. ■Our model requires only one sample from the k th skill to learn such a skill, similar to how language models are few-shot learners at inference. 5 The model can one-shot learn a skill since it has g k 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 a feature.Because the k th skill loss only depends on d k (number of observations for the k th skill), we can calculate the expectation of the skill loss for D data points from P observed (k|D) or the probability that d k > 0:P observed (k|D) = 1 -(1 -P s (k)) D .(58) Using the one-shot learning property (Eq. ( 57)), the probability of observing the k th skill (Eq. ( 58)), and the decomposition of the loss into skill losses (Eq. ( 6)), the expected loss for D datapoints isEQUATIONwhere the expectation E D 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 lossEQUATIONWe can integrate ∆L by parts.∆L = 1 2 - S 2 Ak -α (α + 1)(D + 1) 1 -Ak -(α+1) D+1 ∞ 1 - S 2 Aα 2(α + 1)(D + 1) ∞ 1 k -(α+1) 1 -Ak -(α+1) D+1 dk ≈ O (1 -P s (1)) D+1 - S 2 Aα 2(α + 1)(D + 1) ∞ 1 k -(α+1) 1 -Ak -(α+1) D 1 -Ak -(α+1) dk ≈ - α (α + 1)(D + 1) E D [L] + α (α + 1)(D + 1)∆L.In the second line, the first term goes to 0 for D ≫ 1. In the last line, we used the expression for ∆L (Eq. ( 62)) and E D [L] (Eq. ( 59)). Rearranging the equation above and using that D ≫ 1, we obtain the scaling law with exponent -α/(α + 1):EQUATION)where in the last line, ∆D/D = 1/D as the change in the number of data points relative to D is one.The parameter scaling law assumes T → ∞ and D → ∞, with the parameters N < n s as the bottleneck. Because our model is a one-shot learner (Eq. ( 57)), learning of the k th skill only depends on the existence of g k in the model; the model with[g 1 , • • • , g N ] will learn all k ≤ N skills with L k = 0.The L k dependence on g k is formalized in Corollary 2, which we repeat here.Equivalence between a basis function and a skill. Given T, D → ∞ and if the multilinear model has the N most frequent skill functions as a basis,L k (∞) = 0 : k ≤ N S 2 /2 : k > N.(66)Proof See Appendix C.3. ■ Using Eq. (66) and Eq. ( 6), we can express the total loss as function of N :EQUATION)By approximating N ≈ N + 1 for N ≫ 1, we obtain the power-law with exponent -α.For analytical tractability, we define compute as C := T × N . We start from Eq. ( 12) withEQUATION)We can use Eq. ( 56) to calculate the first term and integrate the last term to getEQUATIONwhere we used that L(0) ≫ L C and S 2 A/(2α) -L C > 0. 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, see Appendix J.Removing the irrelevant constant terms,EQUATION)We can use the method of Lagrangian multiplier to obtainEQUATIONEQUATION)where λ is the Lagrange multiplier and C is compute. We can solve the above set of equations to obtain T α+1 ∝ N or equivalentlyEQUATION)We can plug it in Eq. (71) to get L ∝ C -α/(α+2) .(76) This derivation is similar to that of Bordelon et al. [21] (see Appendix N: Compute Optimal Scaling from Sum of Power-Laws in [21] ). For a rigorous derivation of the optimal compute scaling law, see Corollary 4 and Appendix J.In this section, we show the derivation for the extended multilinear model.Lemma 2. Let the extended multilinear model Eq. (15) be trained with gradient flow on D i.i.d samples for the setup in Section 2 (input distribution: Eq. (1), target function: Eq. (4), and MSE loss: Eq. ( 5)). For the skill index k ≤ N be a skill index in the multilinear model, let the feature matrix Φ ∈ R Dc×d k for the k th skill beEQUATIONand SVD on Φ = U SV . Assuming that the system is overparametrized (EQUATION)Proof Similar to Lemma 1, the total loss can be decomposed into each skill such that the dynamics of B k,l relies only on d k observations of the k th skill:EQUATIONIn the second line, we used Eq. ( 16) that e k,l (I ̸ = k, x) = 0 and the orthogonality of g k (Eq. ( 3)). In the last line, we used Eq. ( 16) that g k = D c -1/2 l e k,l . We can find the gradient descent equation of B k,l from Eq. (81):EQUATIONwhich in the matrix form isEQUATIONwhereD c dimensional vectors ⃗ B k and ⃗ S are [B k,1 , • • • , B k,Dc ] and [S, • • • , S] respectively. It illustrates that dB k dt is contained in im(Φ), which is contained in im(U ) (immediate from Φ = U SV ). As U U T (U z) = U (U T U )z = U z, U U T acts as identity on image of U , showing that U U T d ⃗ B k dt = d ⃗ B k dt . ■ F.2 Conserved quantity of extended multilinear model Lemma 3. In the setup of Lemma 2, a 2 k -| ⃗ B k | 2 is conserved over time.Proof We can use Eq. ( 81) to find the equation for a k :EQUATIONwhich in the matrix form isEQUATIONThenEQUATIONwhere we used Eq. ( 83) in the last line. Thus,a 2 k -| ⃗ B k | 2 is conserved during the dynamics. ■ F.3 D c shot learner Proposition 1.Let the setup be as that in Lemma 2. Suppose that a k (T ) is eventually bounded away from zero, i.e. there exists δ > 0 andEQUATION)Proof First, we show that dL k dt ≤ 0 with equality only holding when the gradient is 0.EQUATIONThe equality holds only whenEQUATIONWe show that both a k and ⃗ B k are bounded throughout whole dynamics. AsL k = Φ ⃗ B k a k - ⃗ S √ D c 2 ≥ σ 2 U U T ⃗ B k a k - ⃗ S √ D c 2 (92)for σ 2 the smallest nonzero eigenvalue of ΦΦ T , where Φ = U SV . This shows thatU U T ⃗ B k a k - ⃗ S √ D c (93) is bounded, so U U T ⃗ B k a k is bounded. Meanwhile, in Lemma 2, we showed that (1 -U U T ) d ⃗ B k dt = 0, so (1 -U U T ) ⃗ B k a k is bounded. This shows that ⃗ B k a k is bounded. As a 2 k -| ⃗ B k | 2 is constant (Lemma 3) and | ⃗ B k a k | = |a k || ⃗ B k | is bounded, this shows that both a k and | ⃗ B k | are bounded.The dynamics moving in some bounded region always has at least one accumulation point, which we denote as p. We will show that dL k dt = 0 at p. The function L k (t) in t is a decreasing differential function which is positive. We also note thatd 2 L k (t) dt 2is globally bounded, as it can be expressed in polynomial expression in (a k , ⃗ B k ) and we showed that (a k (t), ⃗ B k (t)) is bounded. From Taylor's theorem, one can obtainEQUATIONand letting t 1 → ∞ here giveslim t1→∞ 1 2M dL k dt (t 1 ) 2 ≤ lim t1→∞ (L k (t 1 ) -inf L k (t)) = 0 (96) so dL k dt → 0 as t → ∞. Meanwhile, as p is accumulation point of (a k , B k ), dL k dt (p) is accumulation point of dL k dt (a k (t), ⃗ B k (t)).As lim t→∞ dL k dt (t) = 0, the only accumulation point of dL k dt (t) is zero, which shows that dL k dt (p) = 0. We have seen that a 2 k -| ⃗ B k | 2 and (I -U U T ) ⃗ B k are 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 2 -| ⃗ B| 2 = a k (0) 2 -| ⃗ B k (0)| 2 (Lemma 3); • (I -U U T ) ⃗ B = (I -U U T ) ⃗ B k (0) (Lemma 2);• dL k dt (a, ⃗ B) = 0, or equivalently the gradient is 0 at p.We will solve for p satisfying those three conditions. The third condition is equivalent to thatEQUATIONAs a k (T ) is eventually bounded away from zero, we have a ̸ = 0, soEQUATIONIt follows thatEQUATIONand substituting to first condition givesEQUATION)This is equivalent to a quadratic equation in a 2 , and has a following solution ofEQUATION)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 is impossible for L k (t) to have accumulation points both in regions a > 0 and a < 0, as it would imply a k (t) = 0 happens infinitely many often, contradicting that a k is eventually bounded away from zero. Thus it follows that L k (t) can only have one accumulation point. As dynamics having unique accumulation point should converge, it follows thatEQUATIONOne can check that theEQUATIONand this is bounded by |(1 -U U T )B k (0)|(S + a k (0)), so by our assumption this is negligible. Thus, we find that ⃗ B k (∞)a k (∞) is the pseudo-inverse solution, which is also found by the linear model with e k,l as basis functions. We can calculate L k (∞) using the result from kernel (linear) regression [23] [24] [25] [26] [27] (for a summary, see tables 1 and 2 in appendix A of [27] ). Using the terminology in table 1 (Eq. ( 16)); eigenvalues are uniform; the learnability is d k /D c for all i; and the overfitting coefficient is(1 -d k /D c ) -1 .Taking into account that we have halved the MSE loss (Eq. ( 5)), the test loss isEQUATION)We obtain the result by using Eq. (10) . ■ F.4 N c basis functions for a skill Proposition 2. Let the extended multilinear model Eq. (18) be trained with gradient flow on D → ∞ i.i.d samples for the setup in Section 3 with n s → ∞ (input distribution: Eq. (1), target function: Eq. (4), and MSE loss: Eq. ( 5), initialization: that of Proposition 1). For a model with the following finite N basis functionsEQUATION) where quotient q = ⌊(N -1)/N c ⌋ + 1 and remainder r is such that (q -1)EQUATIONProof Because we have D → ∞ and because [e k,1 , • • • e k,Nc ] can express g k (Eq. ( 20)), it is trivial to show that R k (∞) = S for k < q. For k = q, the gradient descent dynamics (Eq. ( 83)) leads toEQUATIONwhere the matrix Φ ∈ R r×d k and vector ⃗ B k ∈ R r are the feature matrix(Eq. ( 77)) and parameters for the k th skill respectively. As D → ∞, the matrix ΦΦ T becomes a rank r identity matrix scaled by the frequency of the skill:EQUATIONPlugging in ΦΦ T ,EQUATIONAssuming the initialization in Proposition 1, we can show thatEQUATIONwhere we used Eq. ( 20) for the linear correlation between e k,l and g k . ■In this section, we discuss an example for the time emergence case (Fig. 1(a) ) in which the saturation of skill in an NN consists of multiple saturating 'modes' as in Fig. 8 . The skill strength for each mode follows a near-sigmoidal curve with different emergent/saturation times (colors) whose sum results in the total skill strength (solid black). Note that different saturation times of each mode result in a deviation from the prediction of the multilinear model with B 2 = 1/3 (dashed black).Task. We assume an input X ∈ R 3×8 (note that we are not using X 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. X = 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 , Y = S -S -S S -S S S -S (112)NN. We assume a 2-layer width 3 NN with ReLU activation with the input dimension 3 (Fig. 8(a) ).The NN has 16 parameters, but to simplify the argument, we use weight sharing so NN has only 4 parameters:EQUATION)where σ is the ReLU activation and W, b, w areEQUATION)Modes. It is easy to see that α = β = γ = √ 2S and c = -S leads to the target parity function. We note that one parameter except c (i.e. α, β, γ) maps to one neuron or a mode (colors in Fig. 8(a) ). We define the first mode f (1) asEQUATIONwhere w 1 , b 1 are the first entry of w, b respectively and W 1 is the first row of W . Note that f (1) (x) takes a form similar to the multilinear model (Eq. ( 9)) but with h 1 as the respective basis. We define f (2) , f (3) similarly, and the sum of modes becomes the NN:EQUATIONwhich resembles the multilinear model with different skills.Mode strength. Analogous to the skill strength in Eq. ( 7), we define mode q's strength R (q) asEQUATIONwhere f (q) (X) = [f (q) (X 1 ), • • • , f (q) (X 8 )] and X j are the j th column of X. By the linearity of the expectation,EQUATIONNote that constant c always has zero correlation (inner product) to the target (Y ).Analysis. The dynamics of each mode R (q) (x) differs from that of the multilinear model (Eq. ( 11)) because h q (x) often depends on the parameter, and the dynamics are no longer decoupled among each mode. Nevertheless, each mode follows a sigmoid-like growth (Fig. 8(b) ). We note that each mode has a different saturation time scale or is updated at 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-linearity, each mode differs in the gradients it receives. We can explicitly calculate the gradient for each parameter as:EQUATIONEQUATIONEQUATIONEQUATIONWe immediately notice that c will grow the fastest for small initialization (α, β, γ, c ≪ 1) because it saturates exponentially while other parameters saturate sigmoidally. Considering that S is always the largest term and c saturate to S quickly, we notice that the saturation is in the order of α 2 (≈ 2S + 2c ≈ 4S), β 2 (≈ -S + 5c ≈ 4S), and γ 2 (≈ 2S). We observe that our crude approximation holds in Fig. 8 (b): the first (α) and the second (β) modes saturate at similar timescale, while the third mode (γ) requires approximately twice the time for saturation.The multilinear model (Fig. 9 (a)) has two identifying properties: 1) the layerwise structure and 2) g k as the basis functions. In this section, we discuss the role of each property in more detail.... Assuming a sufficiently fast decay of d k for the skills, the sigmoidal growth results in a stage-like training (Appendix D) where one skill fully saturates before the next skill emerges. In Appendix D, we discuss how the stage-like training can describe the quanta model [18] and how NNs, without explicit g k s, decouple each skill.Finally, note that even though sigmoidal saturation has a resemblance to the test accuracy in grokking [48] , our model is irrelevant to grokking because R k -which is defined over the expectation over the k th 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 g k that decouples the loss. To analyze the role of g k , we can ask whether a simpler linear model with g k 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 a k b k with w k , we obtain the linear model with skill basis functions:EQUATION)The dynamics of the linear model under gradient flow isEQUATIONwhere we assumed w k (0) = 0. The linear model follows an exponential saturation of the skill strength in contrast to the sigmoidal saturation of the multilinear model (Fig. 10 ). 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 dL k /dT anddL k /dk in Appendix E.1 because R k (T ) is a function of d k D T only (where d k /D = P s (k) for D → ∞).For the data scaling law, we recover Corollary 1 because each w k (i.e. R k ) is decoupled. For the parameter scaling law, we recover Corollary 2 trivially as the linear model shares the same basis functions.The data and parameter emergence in Section 5 can be obtained from the linear model in Eq. ( 124) if we extend the model analogous to Eqs. ( 15) and (18) . For example, we can extend the model for data emergence asEQUATION)where the matrix W ∈ R N ×Dc is an extension of w ∈ R N in Eq. ( 124), D c is a fixed scalar, and e k,l (i, x) : {0, 1} ns+n b → R are functions with the following properties:EQUATION)The equivalence can be shown by Lemma 2 which states that the multilinear model finds the minimum norm solution: the solution that the linear model finds in a ridgeless regression setup.Thus, for our setup, the basis functions play a 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 scaling laws and emergence behaviors. See Bordelon et al. [21] for a study of the scaling laws in linear models. The calibration of the extended multilinear model (solid) on the 2-layer NN (dashed) for n s = 1 system. For the calibrated parameters, we have B 2 = 1/22 for time (Eq. ( 14)), D c = 800 for data (Eq. ( 17)), and N c = 4 for hidden layer width (Eq. ( 21)). In Appendix E, we discussed the scaling laws in simplified settings, favoring intuition over mathematical 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 to quantify the associated error terms. By explicitly analyzing the error 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. A N for scaling law L = A N N -α ) and the scaling law (with the assumptions and explicit error terms) are given. Note that whenever T appears in theorems and corollaries, ηS is multiplied to make it dimensionless.Scaling law Constant StatementD ≫ T 3 N α+1 = o(T ) L = A N N -α Theorem 1 Theorem 1 D ≫ N T 2 , T 3 N α+1 ≫ T L = A T T -α/(α+1)Theorem 4 Theorems 2 and 3D ≫ T 3 N α+1 ≈ T L = A C C -α/(α+2) Corollary 5 Corollary 4 T ≫ D(log D) 1+ϵ N α+1 = o(D) L = A N N -α Theorem 5 Theorem 5 T ≫ D(log D) 1+ϵ N α+1 ≫ D L = A D D -α/(α+1) Theorem 5 Theorem 5We go back to the most general settings possible. Our starting point is Eq. ( 27), which describes the dynamics of R k and L k valid for k ≤ N :EQUATIONWe do not use skills for indices k > N in our model, but we can still denoteEQUATION)For P s (k) = Ak -α-1 , the total loss is given asEQUATION)When n s , N, T are all set, their dependency with the data is only determined by the statistics d k , the number of data with i (j) = k. We assumed that (i, x) ∈ I × {0, 1} n d was collected as random samples with i following the Zipfian distribution of size n s and exponent α + 1, or equivalentlyP (i = k) = P s (k) = Ak -α-1 for 1 ≤ k ≤ n s . Then (d 1 , • • • , d ns) is a vector denoting the number of occurrences in D independent sampling from that distribution. It follows that d i follows binomial distribution B(D, P s (k)).In this complete perspective, our loss is dependent on all of those parameters and variablesEQUATIONwhereR init = (R 1 (0), • • • , R N (0)) denotes the vector representing initial condition. We will also simply denote r k = R k (0). We will not assume much on r k , but we absolutely need 0 < r k < S for dynamics to hold, and we also should haveEQUATIONWe will not impose any particular distribution on R init . Instead, we will try to identify sufficient conditions on r k for our desired result to hold, and those conditions will differ by the situation we are considering. For example, in Theorems 2 and 3 where we prove time scaling law L = Θ(T -α/(α+1) ) for large enough D and bottleneck T , we only require ϵ < r k < S/2 for some ϵ > 0. However, the exact constant depends on the distribution of r k , and figuring out the explicit constant seems to be only feasible when we fix r k = r as in Theorem 4.We will first consider the situation where D becomes the 'large resource' so that its effect on the loss function is negligible. The number of data d k follows binomial distribution B(D, P s (k)), so d k /D converges to P s (k) for large enough D. So taking the limit of L when we let D → ∞ has the effect of replacing d k /D by P s (k) in the expression of L. We will establish an explicit inequality comparing the difference between L and this limit. Lemma 4. For a function F : R → R with its total variation V (F ) bounded, we haveEQUATIONwhere N (µ, σ 2 ) denotes normal distribution of mean µ and variance σ 2 .Proof This is just an application of the Berry-Esseen inequality (with constant 1, see [49] for modern treatment) applied to d k following binomial distribution B(D, P s (k)). ■ Lemma 5. Let F : R → R be a C 2 function such that F ′′ is bounded. Then we haveEQUATIONProof First, we apply Taylor's theorem to show thatEQUATIONTaking expectation when z follows normal distribution N (P s (k), Ps(k)(1-Ps(k))) givesEQUATION■ Proposition 3. We haveEQUATIONProof Consider the function F : R → R given asEQUATION)This function is monotone decreasing and C 2 on the whole domain, and its supremum and infimum are given asEQUATIONThis implies thatEQUATIONAlso, we will show that F ′′ is globally bounded. We first calculateEQUATION)We consider the following inequalitiesEQUATIONto show thatEQUATIONfor all z. Thus we can apply both Lemma 4 and Lemma 5 to this function F and we haveEQUATIONwhere the last line follows from that we always have α+1) . (148) ■ Lemma 6. For any integer N and σ ≥ 1/2 and σ ̸ = 1, we have1 -P s (k) ≥ 1 -P s (1) = 2 -(α+1) + • • • + n -(α+1) s 1 + 2 -(α+1) + • • • + n -(α+1) s > 2 -(α+1) 1 + 2 -(α+1) > 1 2 2(EQUATION)where ζ is the Riemann zeta function (defined over the whole complex plane except 1 via analytic continuation). In addition,EQUATIONwhere γ = 0.5772156649... is Euler's constant.Proof See Corollary 1.15 of [50] , or other analytic number theory textbooks. ■ Proposition 4. (Large D approximation) We haveEQUATIONwheref α (N ) =    1 if α > 1 log N if α = 1 N (1-α)/2 if α < 1. (153)The constant on the O term only depends on α.Proof From the description of L in Eq. (129), we haveEQUATION)We apply Proposition 3 to giveN k=1 P s (k)      E D [L k ] - S 2 2 1 + S r k -1 -1 e 2ηPs(k)ST 2      < N k=1 P s (k) 2 α S 2 DP s (k) + 4S 4 η 2 T 2 P s (k) D .(156) Each of these sum involving P s (k) is bounded asEQUATIONandEQUATIONwhich follows from Lemma 6. Combining those two givesEQUATIONWhile 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.We next discuss the effect of n s . When n s → ∞ heuristically, then intuitively we haveP s (k) → k -(α+1) /ζ(α + 1). We will discuss the difference between when we regard n s as ∞ and when we do not.Proposition 5. The following equations hold:EQUATIONEQUATIONAll implied constants on O only depend on α.Proof The first statement Eq. ( 160) follows from substituting σ = α + 1 in Lemma 6. As P s (k) = Ak -(α+1) , the second statement Eq. (161) immediately follows. If we substitute n s = N into Eq. ( 160) and calculate differences between them, we obtainEQUATIONThus we haveEQUATIONRegardless of the size of n s , We always haveEQUATIONso the third statement Eq. ( 162) follows. ■We go back to the description of total loss given in Eq. ( 129) asEQUATIONand we take its expectation in D. Proposition 4 suggests that its limit when D → ∞ is given asEQUATIONDenoteEQUATIONEQUATION)We discuss the effect of n s in L 1 and L 2 , by comparing limit of L 1 and L 2 when n s → ∞ and their original values.• For the term L 1 , the change of letting n s as finite value from n s → ∞ has effect of multiplying T by 1+n -α s /(αζ(α+1)), and multiplying whole L 1 by 1+n -α s /(αζ(α+1)). It can be equivalently put asL 1 (n s , N, T ) = 1 + n -α s αζ(α + 1) + O(n -α-1 s ) L 1 ∞, N, T 1 + n -α s αζ(α + 1) + O(n -α-1 s) .(169) We always have n s > N and N → ∞ eventually, so if dependency of L 1 with respect to T is at most polynomial order, then change of main term of L 1 is negligible. We can't establish exact statements yet without the descriptions of size of L 1 .• The term L 2 only depends on N and n s , not on T . Applying Proposition 5 (especially Eq. ( 162)) givesEQUATIONWhen n s grows faster than N then n -α s part is totally negligible, and when n s has same order as N then n -α s affects the constant for main term of L 2 . Things might get little complicated when n s = N + o(N ), where N -α -n -α s = o(N -α ) can happen then.• Comparing size of L 1 and L 2 mainly depends on time. The term L 2 is fixed, and L 1 decreases as T increases. For T = ∞ we have L 1 = 0, so L 2 having order N -α dominates (this proves scaling law for N of exponent α), so restriction on n s becomes quite substantial. For small T and large N where the size of L 2 is small, we can expect the restriction on n s to be less substantial. For example, in the extreme case N = ∞, we have L 2 = 0, and n s does not matter at all (except that, of course, it should satisfy n s ≥ N ).For such reasons, it is hard to quantify exact conditions for n s such that error terms are controlled, unless we specify relative growth of (N, T ). However, n s = ω(N ) suffices to assure that setting n s = ∞ has zero effect on the main term. We will not worry about n s in this setting anymore too, and come back to this at the very end to determine enough n s .We assume D = ∞ and n s = ∞ -virtually implying that d k /D = P s (k) and P s (k) = k -α-1 /ζ(α + 1) (calculated by rule of n s = ∞). We decomposed our main term intoEQUATIONwhereEQUATIONandEQUATIONBy Proposition 5, L 2 is determined almost completely asEQUATIONNow focus on L 1 . ForEQUATION(note: it really depends on r k so it is correct to write F k , but for convenience we will keep using F .) one can express L 1 asEQUATIONLemma 7. Let F (z) be defined as Eq. (175).1. (Estimate for large z) We haveEQUATION)2. (Estimate for small z) For z ≥ 0, we have 2. For the left side, it suffices to show -F ′ (z) ≤ 8ηS 3 T 27 . One can calculateEQUATIONEQUATIONandF ′′ (z) = -4S 3 r k (1 - r k S ) 2 η 2 T 2 e 2ηST z (1 -r k S -2r k S e 2ηST z ) 1 + r kS (e 2ηST z -1)(180) so F has unique inflection point atEQUATIONand this point is where -F ′ (z) obtains maximum. Substituting this to the expression of F ′ (z) gives -F ′ (z) = 8ηS 3 T 27 .Our threshold for distinguishing two approximation methods will be set as z = z 0 = (ζ(α + 1)ηST ) -1 , where both two error terms are bounded by O(S 2 ). The constant ζ(α + 1) is set to make later calculations much easier. Applying Lemma 7 gives (EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONProposition 6. Suppose that there exists 0 < r < √ S such that r ≤ r k < S/2 for all k. In the decomposition of limEQUATIONgiven as above, we have the following bound.1. If (ηST ) 1/(α+1) > N , thenEQUATIONEQUATION2. If (ηST ) 1/(α+1) < N , thenEQUATIONEQUATIONHere all constants in O and Θ terms are absolute with respect to η, S, T, N . (They may depend on α.)Proof We first note that the condition P s (k) < z 0 = (ζ(α + 1)ηST ) -1 is equivalent toEQUATION)Thus we can rephrase the descriptions of terms asEQUATIONEQUATIONEQUATIONApplying Proposition 5 easily shows thatEQUATIONFor M and E 1 , we will consider them by dividing two cases depending on whether (ηST ) 1/(α+1) > N or (ηST ) 1/(α+1) < N . If (ηST ) 1/(α+1) > N , then the condition (ηST ) 1/(α+1) < k ≤ N is never satisfied, so M = E 1 = 0. Now suppose (ηST ) 1/(α+1) < N . We first note thatEQUATIONAs (S -r k ) 2 = Θ(S 2 ), we can letEQUATIONand using Proposition 5 gives the desired estimate L 2 + M = Θ(S 2 (ηST ) -α/(α+1) ). For E 1 , estimating sum of P s (k) 2 using Lemma 6 givesEQUATIONFor E 2 we always haveE 2 ≤ S 2 k≤(ηST ) 1/(α+1) P s (k)min 1, S 2 r 2 e -4ηST Ps(k) (202)regardless of the size of N , so it suffices to bound this sum. If we denote l = (ηST ) 1/(α+1) and defineEQUATIONit suffices to show the bound k≤l P s (k)F 2 (P s (k)) = O (log(S/r)) α/(α+1) (ηST ) -α/(α+1) .(204)We will approximate this sum asEQUATION)to obtain the form of Riemann sum approximation for the integral ofEQUATIONat P s (l) < P s (l -1) < • • • < P s (1). As F 2 (z) is decreasing function, this Riemann sum is always less than the integral, so we obtainEQUATIONWe note that P s (l) = (ζ(α + 1)ηST ) -1 . The threshold for F 2 (z) to become 1 is given atEQUATIONAs r < √ S, this value is always greater than P s (l). Thus we can divide our integral asEQUATIONThe first part is bounded byEQUATIONwhich can be shown to be O (log(S/r)) α/(α+1) (ηST ) -α/(α+1) . For the second part, we apply substitution of w = 4ηST z to showEQUATIONand applying the asymptotic Γ(s, x) = O(x s-1 e -x ) suggests that this is bounded by≪ S 2 r 2 (4ηST ) -α/(α+1) log S r -1/(α+1)e -2 log(S/r) = O (ηST ) -α/(α+1) .■ Theorem 1. (Parameter scaling law) Assume the following conditions: n s > N with lim(N/n s ) = γ < 1 (γ can be zero), and there exists 0 < r < √ S such that r < R k (0) < S/2 for all k. If N, T → ∞ while satisfying N α+1 = o(T ), the expected loss E D [L] for all datasets D of size D satisfiesE D [L] = S 2 (1 -γ α ) 2αζ(α + 1) N -α+ O S 2 N -min(α+1,2α) + S 2 (log(S/r)) α/(α+1) (ηST ) -α/(α+1)EQUATIONwheref α (N ) =    1 if α > 1 log N if α = 1 N (1-α)/2 if α < 1.(218)The constant on the O term only depends on α. When D ≫ T 3 , then all the error terms involving D are negligible.Proof In the situation n s = ∞ and D = ∞, Proposition 6 shows thatEQUATION)We consider the effect of n s first. As L 1 becomes an error term in this estimation, letting n s as a finite value has no effect on overall estimation. The term L 2 accounts for the main term, and letting n s as finite value changes it toEQUATIONThis accounts for the factor (1 -γ α ) on the main term and O(N -min(α+1,2α) S 2 ) added to the error term. The effect of D is exactly described in Proposition 4, contributing the error term of O S 2 D -1/2 f α (N ) + S 4 η 2 T 2 D -1 . Regarding the sufficient condition for D, if D ≫ T 3 then we haveEQUATION) so all error terms involving D are less than O(T -α/(α+1) ). ■For the situation T = O(N α+1 ) however, the error terms E 1 and E 2 are of same size, so we can only say that the main term is of O(S 2 (ηST ) -α/(α+1) ). Theorem 2. (Upper bound for the time scaling law) Assume the following conditions: n s > N , and there exists there exists 0 < r < √ S such that r < R k (0) < S/2 for all k. If N, T → ∞ while satisfying ηST = O(N α+1 ), the expected lossE D [L] is E D [L] = O S 2 (log(S/r)) α/(α+1) (ηST ) -α/(α+1) + S 2 D -1/2 f α (N ) + S 4 η 2 T 2 D -1 (222)with constant on O only depending on α and lim sup((ηST ) 1/(α+1) /N ), with f α defined as in Theorem 1. If D ≫ N T 2 and D ≫ T 3 , 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 = ∞ for the rest of the proof. Also, we can let n s = ∞, as we observed that it contributes at most to the constant factor of the upper bound and does not change the scaling.In the decomposition of Proposition 6, we always haveEQUATIONandEQUATIONholding regardless of N , so it only remains to consider L 2 + M . If (ηST ) 1/(α+1) < N , then L 2 + M is of size O S 2 (ηST ) -α/(α+1) . If (ηST ) 1/(α+1) ≥ N , then N and (ηST ) 1/(α+1) has same order, so α+1) . Thus in either cases we have the desired bound. ■ Theorem 3. (Lower bound for the time scaling law) Assume the following conditions: n s > N and 0 < R k (0) < S/2. If N, T → ∞ while satisfying (8ζ(α + 1) -1 ηST ) 1/(α+1) < N , the expected lossL 2 + M = L 2 = Θ(S 2 N -α ) is O S 2 (ηST ) -α/(E D [L] is E D [L] ≥ κS 2 (ηST ) -α/(α+1) + O η -1 ST -1 + S 2 D -1/2 f α (N ) + S 4 η 2 T 2 D -1 (225)for κ and constant on O only depending on α, with f α defined as in Theorem 1. If D ≫ N T 2 and D ≫ T 3 , 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 = ∞ for the rest of the proof. We only show the lower bound for L 1 , holding regardless of N and n s . In Lemma 7 (Eq. ( 178)) we haveEQUATIONfor z ≥ 0, so if z ≤ (4ηST ) -1 then F (z) ≥ S 2 /8 -2S 2 /27 > S 2 /20. The condition P s (k) ≤ (4ηST ) -1 is equivalent to that k ≥ (4ζ(α + 1) -1 ηST ) 1/(α+1) . In evaluating L 1 = N k=1 P s (k)F (P s (k)), we will only add over k in range of (4ζ(α + 1) -1 ηST ) 1/(α+1) < k < (8ζ(α + 1) -1 ηST ) 1/(α+1) .(227) From the assumption, this interval sits inside 1 < k < N . For such k we use upper bound of F (P s (k)) > S 2 /20. Then by using Proposition 5 we can obtainEQUATIONEQUATIONThe possible effect of n s on the main term is to multiply both the main term by and T by (1 + n -α s ), so it increases the bound. ■The condition (8ζ(α + 1) -1 ηST ) 1/(α+1) < N is not absolutely necessary for lower bound. The condition (ηST ) 1/(α+1) = Θ(N ) and n s ≥ 2N would suffice and one can formulate a similar theorem, although the constant of lower bound might be much smaller if (ηST ) 1/(α+1) /N is small.Lastly, we provide a simpler version of those results combined and discuss the special case where the optimal compute C = N T , or the given engineering budget, is specified. Corollary 3. (Summary of the large data estimation) Assuming D ≫ N T 2 , T 3 and n s ≫ N 1+ϵ such that effects of n s and D are negligible, then for N, T → ∞ we haveEQUATIONwhere Θ η,S,r denotes that the implied constant depends on η, S, α and r = min R k (0) > 0. In particular, we have (233) When N = Θ(C 1/(α+2) ) and T = Θ(C (α+1)/(α+2) ), we achieve E D [L] = Θ(C -α/(α+2) ). (Its implied constant may depend on implied constant for growth of N and T .)EQUATIONProof The first part follows fromEQUATION)The second part can be checked by substituting (N, T ) = (C 1/(α+2) , C (α+1)/(α+2) ) (or their constant multiples) to Corollary 3. ■ J.5 Computing the constant for time scaling law While we have found the time scaling law E[L] = O(T -α/(α+1) ) holding for T = O(N α+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 a more refined estimation, but we require additional assumptions on parameters. We will focus on the setting where D and n s are large enough to be negligible, R k (0) = r is fixed, and T = O(N α+1 ) with fixed constant such that time scaling law holds. Theorem 4. (Constant for time scaling law) Denote L ∞ as the loss when D, n s → ∞ so that their effect is negligible:EQUATION)When T, N → ∞ and lim N/(ηST ) 1/(α+1) = λ for a fixed constant λ ∈ (0, ∞], the following limit exists:EQUATIONThe prefactor constant A as the a function of λ (when λ = ∞ then let λEQUATIONwhereEQUATIONProof We first observeEQUATION)We will seek to convert it into Riemann sum form of certain integral. We start by noting thatEQUATIONDenote u k = ηST P s (k), then the sum can be approximated to EQUATIONEQUATIONinstead. As Φ S,r shows exponential decay, we can ignore values at small k, so this showsEQUATIONJ.6 Estimates for large T and threshold between data/parameter scalingThe estimates for small D 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 -α/(α+1) ) happens. We will consider a simpler setting of 'n s = ∞' or equivalently that effects of n s are negligible (n s = ω(N ) seems to suffice) and R k (0) = 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 L(∞). We remindEQUATIONand its limit when T → ∞ is given asEQUATIONProposition 8. Suppose that R k (0) = r < S is fixed. For large T , we haveEQUATIONEQUATIONSo we only need to establish an upper bound forEQUATIONwhere 1 d k >0 denotes the characteristic functionEQUATIONWe use simple bound ofEQUATIONAs d k follows binomial distribution B(D, P s (k)), considering its moment generating function givesEQUATIONso thusEQUATIONMeanwhile, for 0 ≤ u, v ≤ 1 real numbers, we haveEQUATIONso, applying this inequality to above givesEQUATIONThus, we can deduceEQUATIONEQUATIONand thusEQUATIONThis provides an almost complete account for the effect of very large T . We will let T = ∞ from this point. We haveEQUATIONApplying Lemma 6 givesEQUATIONso it suffices to focus on the first sum. We will divide the range of k into two 1 ≤ k ≤ 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 1 -x ≤ e -x )EQUATIONFor the sum over M < k ≤ N , we will approximate the sum into some integral, which happens to be incomplete gamma function. Proposition 9. For 2 < M < N integers, we haveEQUATIONEQUATION)Here Γ denotes the incomplete gamma functionEQUATIONProof Consider the interval [P s (N ), P s (M )] and its partition P = {P s (N )< P s (N -1) < • • • < P s (M )}. For a function f (x) = x -1/(α+1) (1 -x) D, we will consider its upper and lower Darboux sums with respect to P. As f is decreasing in (0, 1], its upper and lower Darboux sums are given respectively asEQUATIONand those give bound of the integral of f asEQUATIONMeanwhile, by noting thatEQUATIONTheorem 5. (Scaling laws for large time estimation) Suppose that N, D → ∞ and n s ≫ N 1+ϵ for some ϵ > 0 so that effect of n s is negligible. Suppose that R k (0) = r for all 1 ≤ k ≤ N .1. (Parameter scaling law) If N = o(D 1/(α+1) ), then we haveEQUATION2. (Data scaling law) If D = O(N α+1 ) and µ = lim(D/N α+1 ) exists (it can be zero), thenEQUATIONHere Γ denotes the incomplete gamma functionEQUATIONIn particular, if D = o(N α+1 ) such that µ = 0, we haveEQUATIONIn either case, T ≫ D(log D) 1+ϵ for some ϵ > 0 implies that error terms involving T are negligible.Proof Proposition 8 statesEQUATIONand we showedEQUATIONandEQUATIONFor the sum of P s (k)(1 -P s (k)) D over 1 ≤ k ≤ N , we use the estimate (see Eq. ( 276)) ofEQUATIONand the estimate of Proposition 9. Combining all those givesEQUATIONWe will prove our main statement by choosing appropriate M depending on size comparison between D and N . where Θ η,S,r denotes that the implied constant depends on η, S, r and α. In particular, we have Proof Just summarize the results of Theorem 5. ■In this section, we present the methods used in our experiments.We trained a 2-layer fully connected neural network (MLP) with ReLU activations. All parameters of the MLP were initialized with a Gaussian distribution with a standard deviation of 0.001. The input dimension of the model was n s + n b = 5 + 32 where n s is the length of control bits (number of skills) and n b is the length of the skill bits. Each skill has m = 3 mutually exclusive sparse bits that are used to express the skill function. The target scale was S = 5. The model was trained with SGD without momentum and no weight decay (the exception is the parameter emergence experiment where Adam with learning rate 0.001 and weight decay of 5 × 10 -5 was used to escape the local minima). 6 For the data emergence experiment, the learning rate was halved every 50, 000 step.The skill strength R k (T ) (Eq. ( 7)) was measured using 20, 000 i.i.d samples from the k th skill. 7 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 → ∞, we used the model of width 1000 (for the hidden layer). To mimic the infinite time T → ∞, we trained for 5 × 10 This section outlines the transformer architecture used in Fig. 4 . Data is encoded as for the 2-layer MLP, but with one-hot positional encoding appended to the data. We use a basic decoder transformer with 1 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-linearity, 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 × 10 -5 , weight decay of 10 -5 , and momentum with β = 0.9. At every 100 steps, the skill strength R k (T ) (Eq. ( 7)) was measured using 20, 000 i.i.d samples from the k th skill.The skill strength R k is a simple linear correlation between the learned function f -function expressed by NN -and g k for P b given I = k. We approximate the expectation over X by taking the mean over 20, 000 i.i.d samples from P b for the k th skill:EQUATIONwhere the notation x (j) denotes the j th sample.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 s (Table 2 ). For the scaling laws (dotted lines) in Fig. 2 , we used the exponents from Appendix E or Appendix J and the prefactor constants from Theorem 4 (time scaling law), Theorem 5 (data scaling law), and Theorem 1 (parameter scaling law).For the hyperparameters of the simulation, we used n s = 10 5 such that n s is large compared to other resources; S = 1 and R k (0) = 0.01 such that S -R k (0) ≈ S; and η = 1.Time scaling law. The total loss as a function of T for D, N → ∞ (Fig. 2 (a), solid) isEQUATIONwhich follows by taking D → ∞ and N = n s on Eq. ( 12). The scaling law (Fig. 2 (a), dotted) isEQUATIONwhere the exponent is derived in Appendix E.1 or Theorems 2 and 3. The prefactor constant isEQUATIONζ(α + 1) -1/(α+1) (α + 1)(ηS) α/(α+1) EQUATIONEQUATIONwhere the exponent follows from Appendix E.2 or Theorem 5. The prefactor constant isEQUATIONwhich we obtained by taking N → ∞ in Eq. (302).Parameter scaling law. The total loss as a function of N when T, D → ∞ (Fig. 2 (c), solid) isEQUATIONwhich follows from taking T, D → ∞ on Eq. ( 12). The scaling law (Fig. 2 (c), dotted) isEQUATIONwhere the exponent follows from Theorem 1. The prefactor constant isEQUATIONwhich we obtained by taking D, T → ∞, N/n s → 0, and ζ(α + 1) ≈ α -1 in Eq. ( 217).• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at 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. • It 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 a 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.Justification: The research conducted in this paper adheres to the principles outlined in the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).https://github.com/yoonsoonam119/Skill_Eigenmode.gitNote that here we follow the even/odd parity convention used in[18], i.e., {0, 1}, instead of {1, -1} as used in the main text.To be specific, it is under gradient flow or the continuous limit of full batch gradient descent.We take N and ns to ∞ at the same rate since we do not want the number of parameters to be a bottleneck in this setup.Few-shot learning is typically discussed in the context of models that have undergone pre-training (see, e.g.[1]). We speculate that expanding in the basis g k in our framework can model aspects of the pre-training process.We are free to choose any optimizer as long as it preserves the order in which the skills are learned. Additionally, the parameter emergence experiment uses infinite data; we expect the same solution for Adam and SGD.Note that except the data scaling law experiment, the training set size is infinite. 


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

Reviews: review: paper_summary: paper_summary: The paper proposes to use a certain generalization of the well-known sparse parity problem, as a theoretical framework for neural scaling laws.

The theoretical setup doesn't seem to make sense (I'm open to changing my mind). Indeed, equations (2) and (4) taken together give
\begin{equation*}
    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).
\end{equation*}
This 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))
\begin{equation*}
    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).
\end{equation*}
From this point onward, it is not clear what the paper is trying to do. 

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

Finally, 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.
strength_weakness: strength_weakness: 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.
questions: questions: In what way do (3) and (9) represent "a sum of skills" ?
limitations: limitations: Yes (in Section 5.4)
paper_summary: paper_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).

The 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.
strength_weakness: strength_weakness: - 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).

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

- 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.
questions: questions: See weaknesses.
limitations: limitations: Fine.
paper_summary: paper_summary: I’ll write two summaries: one to state my “moral” understanding of the work and another to state the specific contributions 

**“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.

**Specific Summary:**

- The authors study the multi-task sparse parity problem studied by Barak & Michaud
- 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
- In this model, one can then exactly compute scaling and emergent abilities as a function of the typical scaling parameters (compute, data, parameters)
- The authors also train 2 layer MLPs and transformers to test how closely their maths match empirical results
strength_weakness: strength_weakness: - 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.
- 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.
- 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
questions: 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

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

- 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.
questions: 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: Limitations are adequately discussed, including scope limitations.

Comments: title: Response to Authors' Rebuttal
Brief Comment on Contributions beyond Michaud et al. 2023
comment: Dear reviewer,

Thank you for your review and efforts. Please update your score on the original review as well.
Dear reviewer, 

We are glad that we clarified the confusion and thank you for updating the score.
- Thanks for the clarification; a notation problem indeed. 

- I have a good understanding of the paper now. I think the contribution is interesting but still incremental (based on current literature on provable scaling laws).

I'm increasing my score to 6.
Dear reviewer, we thank you for increasing confidence in your assessment. We are glad that additional plots have clarified your question.
Dear reviewer, we deeply appreciate updating the score.

The specification of setup is detailed in Appendix K.5. Each run of the experiment – one point in the figure – requires 2 to 5 hours for time emergence and 20 to 50 hours for other experiments on a CPU. We ran the experiments on a CPU cluster because the small size of the MLP allows less pronounced difference in the running on GPU and CPU (running on RTX 4090 GPU was typically only 3X faster than an average CPU in the cluster) while we benefited from parallelism in a larger CPU cluster.

The most demanding experiment was Fig.1(b) with data emergence. The figure has 30 different numbers of datapoints ($30$ runs), repeated $10$ times for the error bars. We ran for $5 \times 10^5$ steps for data and parameter emergence (compared to $3 \times 10^4$ for time emergence) to remove the potential effect from early stopping (i.e. to assure $T \gg D$).
To observe the emergence of an additional skill, we require a magnitude increase in $D$ which leads to a magnitude increase in $T$ – to assert $T \gg D$ – and a magnitude increase in the batch size – to mitigate the SGD noise.
Thank you for your comments! I appreciate the additional figures in the global response and your answers to my questions.

I'm going to increase my confidence but keep the score. I don't feel comfortable increasing my score because while I feel this paper is very thorough, I feel it is limited in its general applicability without strong connections back to more realistic (larger, more data, real data) models.
I thank the authors for their detailed response. In light of the changes proposed, I will change my score to accept (7).

One question about the experimental setup: What were the hardware requirements for the 2-layer MLP experiments in figure 1?
I'll respond to the authors tomorrow, but briefly, on this overall comment, I'd like to clarify one point concerning "Contributions beyond Michaud et al. 2023" today in case other reviewers look at this in the interim.

I personally think that this work extends far beyond the Michaud et al. 2023 paper. If any other reviewers feel differently, please explain why or please point me towards where you might have already explained in your review.

Thank you!