A universal compression theory for lottery ticket hypothesis and neural scaling laws
Authors: Hong-Yi Wang
Di Luo
Tomaso Poggio
Isaac L. Chuang
Liu Ziyin
Venue: ICLR 2026 Poster (2026)
Keywords: Neural scaling law
model compression
lottery ticket hypothesis
deep learning theory
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We prove that permutation symmetry enables polylogarithmic compression of neural networks and datasets, thus establishing the dynamical lottery ticket hypothesis and boosting neural scaling laws

Abstract: When training large-scale models, the performance typically scales with the number of parameters and the dataset size according to a slow power law. A fundamental theoretical and practical question is whether comparable performance can be achieved with significantly smaller models and substantially less data. In this work, we provide a positive and constructive answer. We prove that a generic permutation-invariant function of $d$ objects can be asymptotically compressed into a function of $\operatorname{polylog} d$ objects with vanishing error, which is proved to be the optimal compression rate. This theorem yields two key implications: (Ia) a large neural network can be compressed to polylogarithmic width while preserving its learning dynamics; (Ib) a large dataset can be compressed to polylogarithmic size while leaving the loss landscape of the corresponding model unchanged. Implication (Ia) directly establishes a proof of the dynamical lottery ticket hypothesis, which states that any ordinary network can be strongly compressed such that the learning dynamics and result remain unchanged. (Ib) shows that a neural scaling law of the form $L\sim d^{-\alpha}$ can be boosted to an arbitrarily fast power law decay, and ultimately to $\exp(-\alpha' \sqrt[m]{d})$.

Published as a conference paper at ICLR 2026
A UNIVERSAL COMPRESSION THEORY FOR LOTTERY TICKET HYPOTHESIS AND NEURAL SCALING LAWS
Hong- Yi Wang
Di Luo
Princeton University & NTT Research hywang@pr nww.on. edu
Tsinghua University & UCLA diluo@tsinghua edu
Tomaso Poggio
Isaac L. Chuang
Liu Ziyin
MIT
MIT
MIT & NTT Research
tp@ai , mmit. edu
ichuangemit.cc
ziyinlemit, edu
ABSTRACT
When training large-scale models, the performance typically scales with the num- ber of parameters and the dataset size according to a slow power law. A fun- damental theoretical and practical question is whether comparable performance can be achieved with sigmificantly smaller models and substantially less data. In this work, we provide positive and constructive answer. We prove that generic permutation-invee invarrian function of d objects can be asympiotically compressed into function of polylog d objects with vanishing error, which is proved to be the op- timal compression rate. This theorem yields two key implications: (Ia) large neural network can compressed to polylogarithmic width while preserving its learning dynamics;
(Ib) large dataset can be compressed to polylogarithmic size while leaving the loss landscape of the corresponding model unchanged. Impli- cation (Ia) directly establishes proof of the dynamical lottery ticket hypothesis, which states that any ordinary network can be strongly compressed such that the learning dynamics and result remain unchanged.
(Ib) shows that neural scaling law of the form L ~ d can be boosted to an arbitrarily fast power law decay, and ultimately to exp(-a' Vd)..
INTRODUCTION
Training contemporary neural networks has become extremely costly. Modern models very large and are often trained on enormous datasets. For example, GPT-4 is believed to have on the order of trillion 21012) parameters and have been trained roughly trillion tokens. Training runs can occupy clusters comparable in scale to an entire data center. By contrast, the brain, comparable biological computer, appears to require far less data. A rough thee---- estimate illustrates the gap: suppose the auditory system of a person receives one word second from birth. Then by age ten, child would have heard about 10 words, by which time most children have mastered their native language. This difference of roughly four orders of magnitude data efficiency between artificial and biological systems suggests that current Al systems may not be using data optimally.
The data efficiency of large Al models is often summarized by neural scaling laws (NSL), in which the error L decays approximately power of the dataset size (holding other factors fixed):
L(N) xx -
Empirical values of a for large language models typically lie between 0.1 and 0.3 (Kaplan et al.] 2020). If we assume 0.1 and that current models already achieve human-like language pability, then attaining the same capability with only 10a tokens would require a modestly larger exponent, roughly 0.15. Hence, even a small increase in the scaling exponent could substan- tially reduce training cost by bringing models closer to human-level data efficiency. Yet we currently lack principled guidance whether, and by how much, the neural scaling laws can be improved.
In this work, we prove a universal result that, under suitable definitions of model width, enables sub- exponential compression (i.e., from objects to polylog( d)) of essentially arbitrary neural networks

---

Published as a conference paper at ICLR 2026
(9)
(W Mig)
(Lo, (e (8)
Width
100
1(0")
Figure 1: (a) Illustration of the main idea behind the compressibility of neural networks and datasets. (1) Permutation symmetry allows high-dimensional function he decomposed into composition of low- dimensional "objects" (dots the figure). (2) When is large, these objects become crowded, and those lying in denser regions are essentially redundant; they can be compressed into = (polylog d) objects. The potential curse of dimensionaliity can thus be mitigated, even removed, when the underlying function is smooth-a lesson well known in nonparametric statisties. (b) Decomposing the linear weights of neural network into "objects" symmetric status.
and/or their training data, thereby opening the possibility of substantially improving wide range of neural scaling laws. Our contributions are:
1. Proof of universal compression theorem, showing by construction that almost any smooth symmetric function of elements can be compressed a function with (ppoyyogg(d) elements losslessly (Section 4 Moreover, such compression rate optimal up a constant factor. Application to network compression, which leads to a proof of what we call the dynamical lottery ticket hypothesis (LTH), which states that large network can be compressed such that its training dynamics the same as the original (Section
3. Application to compress datasets, which is proof-of-concept showing that one improve neural scaling laws significantly (Section 6).
Figure 1 provides schematic of the main idea. All proofs appear in the Appendix; numerical experiments are presented alongside the related theoretical results.
2 PROBLEM SETTING
We begin with two motivating examples to illustrate the ubiquity of permutation symmetry in ma- chine learning, and then introduce the permutation-symmetre functions we study.
Data Permutation Symmetry. The simplest form of permutation symmetry exists among data points. The loss function we minimize is L(0, {2 where d is the number of data points, and zi (x;; yi) is a data point consisting of input-label pairs. The loss function is the average of per-sample loss E over training data:
d Σ (.., 0) =[[[<,,,
L
Because the loss function L is over the same function é of each data point, permuting any pair of data points results the same value of loss function. Moreover, since the dataset affects any trained model prediction via the gradient of the loss function, all model predictions are thus naturally permutation invariant.
Neuron Permutation Symmetry. Permutation symmetry in model parameter space depends on the structure of the model submodules. Consider the model f(x) (W)(Wx where W1 and W2 are weight matrices, and a is an element-wiss non non-linearity. Let wf" be the row vectors of W1, and 2 be the column vectors of We. Then the output reads
f(z) = Σ v.o i-1
where is the output dimension of W1, also the input dimension of W.. d is commonly known the width of the neural network. The output is symmetric under the exchange of any pair of (oe, w.) + w,), another example of permutation symmetry. For a deep net, different layers can have multiple decoupled permutation symmetries. More generally, other modules that have
2

---

Published as a conference paper at ICLR 2026
such permutation symmetry include fully connected layers, attention logits in self-attention, and attention outputs between different attention heads; it also exists when ensembling many models with the same architecture (Brea et al. 2019 Ziyin et al.) 2025). Particularly. we further elaborate on the permutation symmetry in attention modules in Appendix
General Permutation Symmetries. Since our theory concerns compressing the objects while pre- serving the values of such symmetric functions, this framework is unified approach to compressing either training data or any permutation -ymmmmorii-mm parameter set of a learning model. Generally, one inputs, while keeping
view the model loss as function of set of permutation-symmente other inputs implicit. We refer to each such input as an object, which may correspond to a data point or neuron weight (w;). In this paper, each object is embedded m dimensions, and is the number of such objects. We primarily consider the limit d + co.
Definition 1. Let each w; E V TR." f: V R is called a cenrmuttation-yyymmenn function in {w,] if. for any distinct i.j E [d]. f(..., W, w,,....
(....,W...... ................
Wi......
We also use 0 (wi...., wa) collective notation for all objects. To analyze the error induced by compression, we impose a mild regularity assumption on f. Specifically, it is known that any symmetric function admits a "deep set"-style universal representation (Zaheer et al. 2018 of the form
Figh.,,,,yy h f(w wa) (n (E
(4)
where h and g are suitable functions. Importantly, for smooth f. one can choose h and to be smooth as well (Tabaghi & Wang, 2023). We will use the following regularity assumption for the symmetric functions considered in this paper.
Assumption 1. For all symmetric functions f(0) studied in this paper, we assume that there exists deep-set representation of as in Eq. 44) such that
1. Neither h nor g depends on d;
2. h and g are both Kaylor-expandale with finite radii of convergence.
While many ML models are non-smooth (e.g., ReLU networks), our compression results often ex- tend to such settings at the level of conclusion (concretely, ReLU networks are studied the numer- ical results in Figs. 4 and 5) suggesting broader applicability beyond the analytic regime treated formally here.
Notation. Let
R" denote the space in which each object w; is embedded. @ represents tensor product. The shorthand [d] refers to the index set {1, (1, but when is a non-integer real number, [x:] denotes its closest integer. Sa denotes the symmetric group of d elements. For a nonnegative weight vector (c)) the support is defined as supp(c;) {i e [d] Q: * 0}. For set S & V. the diameter is diam(S) = max |x x'Il, where we use the Euclidean norm throughout this paper. N(u, (?) denotes the normal distribution with mean μ and variance o². All other notations will be introduced in context.
3 RELATED WORKS
Compression in AL. Model and dataset compression has long been central problem in AI (Han
al., 2015 Frankle & Carbin 2018 Sorscher et al.) 2022 Salomon 2002, Wang et al. 2018).
Yet, almost no theoretical framework exists to explain why, or to what extent, such compression is possible. A primary conceptual framework is the lottery ticket hypothesis (LTH) (Frankle & Carbin 2018), which posits that within every network there exists small subnetwork that, when retrained, can achieve the same performance as the original. Several theoretical works have established vari- ants of the LTH (Malach et al.) 2020) Pensia et al.) 2021 1 da Cunha et al., (022). However, these results typically fail to imply that the compressed model exhibits the same learning dynamics as the original-that is, that it reaches the same performance after training-whhe which is arguably the most practical implication of the LTH. To date, the original formulation of the LTH remains unproven, precisely because of its dual requirement of both training and compression. We provide a more detailed discussion of this point in Sec. 5 Another closely related work is Ziyin (2024), which suggests the connection between symmetries and emergent sparsity during training.
3

---

Published as a conference paper at ICLR 2026
Neural Scaling Laws. A major empirical guideline for training large language models (LLMs) is the neural scaling laws, which state that as the size of models and datasets increases, the generaliza- tion error decays a power law: L oc d= with often small (Kaplan et al.) 2020). Such small exponents pose central obstacle for scaling L.LMs. For example, when a = 0.1, reducing the gener- alization error by half would require increasing the dataset size by factor of 1000-an impractical demand given today's limited data availability. [Sorscher et al. (2022) suggests the possibility of improving scaling laws through data pruning; however, their theory applies only to linear regression and assumes knowledge of the ground-trutt model. Whether scaling laws can be improved in more general settings, and without requiring access to the ground truth, remains unknown.
UNIVERSAL COMPRESSION THEOREM
Compression is enabled by the observation that symmetric functions be characterized by far fewer degrees of freedom than their apparent dimensions, which follows from a variant of the fun- damental theorem of symmetric polynomials (FTSP). We then leverage this result to show that family of compression algorithms ensures asymptotically lossless compression.
4.1 SYMMETRIC FUNCTIONS ARE COMPRESSIBLE
The value of a symmetric function does not depend on the specific ordering of (Wi,..., wa), where each w; E IR.". As a simple example, the joint probability distribution of d i.i.d. random variables is symmetric in the sampled data points. This i.i.d. property underlies classical Shannon compression (Cover & Thomas 2006). In this sense, permutation symmetry can be viewed natural generalization of independence (see, e.g., Glleem-Reddy & Teh (2200), and it is thus natural that the compression of i..dd variables extends to the more general setting of permutation-symmectt variables. The following theorem shows that it suffices to keep track of the tensorial statistical moments of 0, idea traceable to Newton and Lagrange (Blum-Smith & Coskey 2017). The following version of FTSP directly relates multivariate symmetric polynomials to their moments.
Theorem 1 (Multivariate FTSP). Let 0 (wi...,, wa) with wi E R" Any symmetric polynomial f() (i.e., f(0) is permutation invariant and is a polynomial of all scalar components Wi,a) can be expressed as a function of the moments Pk. k [d]. defined by
Pk Σ
19k W
Σ
w @ Wt-
(5)
1: repetitions
If f(0) is a symmetric polynomial of degree k. then, f(0) is fully determined by the first k mo- ments. Thus, any change that preserves these moments leaves f() unchanged. In other words, the variables can be compressed into the size of their leading h moments as a linear space. The following theorem by Tchakaloff gives a direct upper bound on the number of elements required for the compression.
Theorem 2 (Tchakaloff (1957)) Let μ be a measure supported on D Rm.. Then there exist N points wj D, with N Nm,k (m=k), and positive weights Gj. such that the first k moments are matched: Vl e (0, ,k,,,,,,,, fD u du((w) = Z-=1 Cj 1
A proof follows from Carathéodory's theorem in dimension Nm.,k (Lonard & Lewis, 2015). Note that Nm,, is precisely the dimension of the linear space all moments up to order k (including a fictitious dimension for Po). Algorithm P in Appendix (D guaranttess such compression: whenever there are more than Nm, weighted objects, we can always reduce the support to at most Nm. objects while preserving the first & moments.
In the spirit of Tchakoloff's s theorem, one can compress the original parameter set 0 into a smaller set of weighted parameter set 8': Definition 2. weighted parameter set 6' is defined as collection of weightt-prameeer pairs 0' = {CL, wi), (c2, w2),..,, (Co w))).
(6)
where each oj 0 and Wj V = =m The moments of 0' and the values of symmetric functions are defined as an average over the discrete measure Je Edz cz0mg;
1 d'
Ph =
Σ
f(0') = h Σ (50(w)))
(7)
2x
4

---

Published as a conference paper at ICLR 2026
where f(0)= (10))=(Ei))) (wx)) is the deep-set representation of symmetric function.
We remark that the original 0 can also be viewed weighted, with unit weight for each object. A feature of our compression is that does not change any of the w; 's but instead adjusts the weights smaller subset. When ff and {ws)is(d)
so that they supported output as a function of only the weights (ci)sedd) Specifically, given f(0) = 1(E ((w))) we denote <<c) h (E cgg(w)).
fixed, may regard the
We are now ready to study approximating symmetric functions f that are Taylor-expandabee Ex- panding order k yields symmetric polynomial of degree k. and these moments can be matched with very few weighted objects. Consequently, the approximation error begins at order (k: + 1).
Theorem 3 (Moment matching in small ball). Let f be symmetric function acting on weighted parameter set 0- {(c, ( be[d]- and let & be its corresponding function acting on weights. Let r diam( (<())) Then, there exist nonnegative weights {ce) (Ceieed)) such that no more than Nm. (m+*) weights are nonzero, and
( O(dr""))
Theorem is main ingredient of our compression theory. lesson from this theorem that dealing with group of objects of small diameter is very effective in suppressing enror, as we can choose large enough & to greatly suppress the compression error.
4.2 ASYMPTOTIC LOSSLESS COMPRESSION
Theorem shows that compressing points in small diameter enables a tight control on the erron By a sphere packing argument (see Lemma D. if we put lot (d) of objects in a finite region, then we can always find a subset of diameter ((N/dd) 1/m) containing N objects. This gives rise to a general strategy of compression in Algorithm and any concrete algorithm that fits in this strategy is guaranteed to have vanishing compression error.
Algorithm 1: A compression algorithm family.
Input : a set of objects 0 = {wo ) target size d", moment-matching order k e E. Output: {cy, ( jesupp(e). (essppp))))))) where |supp(c))
Initialize c; for all i E [d]]
while supp(c)) > d' do
Step 1 (clustering): Find a cluster S supp(c) such that |S] Nm, and diam w;) j = O(1 (()pp(())))-1
Step 2 (moment matching): Update weights {c, Jes such that they are supported on Nm, objects, and the first moments are kept unchanged.
end
In terms of a practical compression algorithm, we first remark that Step (moment matching) can be realized by Algorithm 2 in Appendix [ although several other moment-matching algorithms exist, especially in the case of peeling many points in one cluster (Piazzon et al., 2017). The most time- consuming part in Algorithm 2 finding null vectors,
estimate its time complexity d.V2 m, which tells us that matching higher moments takes a much longer time. For clustering, ideally in each iteration one wants to greedily find the (Nm., + 1)-subset with the smallest diameter, but the k-nearest neighbor problem is known to be NP hard in general. For clarity, in Theorem of this sec- tion, we prove error bounds associated with the greedy strategy, indicating that a compression map satisfying our asserted error bounds universally exists. However, perform numerical experiments using k--means clustering (see Appendix [), which works sufficiently well and much faster.
The following theorem shows that with sufficiently large k (compared m, but still much smaller than d), one can compress the number of active objects to any power of d with vanishing error.
Theorem 4 (Universal Compression). Let [will s R for all i [d]. Algorithm | with moment- matching order ls can compress = {d into d' < d weighted objects 8', such that for any symmetric function f. satisfying Assumption
5

---

Published as a conference paper at ICLR 2026
1. The error is
o(c) o())
(9)
where stands for the function f treating weights variables;
2. If m - 1, d original objects can be compressed into
d' d'=o
R-
(10)
E(d)
weighted objects, such that the error is no larger than e(d).
implication of this theorem that we can keep vanishing portion of objects with vanishing emoor In fact, we can reach d' = do with any 0 < a < 1. To see this, we insert d' = d into Eq. (9) and get
((d') - ((e) 0ld k+l
(11)
This error bound is vanishing by choosing k > (1+o )) 1-m In Eq. compressing up to order & is enabled by the fact that the function is at least C -iiferrentiable, whereas the term m in the exponent is typical signature of the curse of dimensionality. This competing effect of dimensionality and differentiability is reminiscent common error scalings in nonparametric statistics (Wasserman, 2006).
Theorem 4 seems to imply that larger k always yields tighter error bounds. However, this stops being true when cluster of Nm. points becomes comparable to d. A more careful analysis shows that the optimal choice of is Kopt ((d (Theorem 7) It follows that there exists a moment matching algorithm such that the error at most stretched-exponentaall decaying as correspondingly, we can compress original objects into
x Vd);;
d' O
100g" log
(12)
E(d)
weighted objects, such that the error is no larger than (d). To better understand the d' lower bounds, we consider e.g., a power-law error <(d) = d=a Then Eq. (TO) becomes d=((+=)mm((-m=x-) which can always be made smaller than d by choosing large enough Eq. (12) becomes ((++a) log d)" which is still of order log" d. Despite we proved that compressing to log" (d) is possible, it should be noted that when Kopt. Nm, becomes comparable d, so compression becomes much more computationally expensive.
Compression rate lower bound. In Appendix B that cannot be compressed into less than log" d objects without inducing finite error. Hence, the compression rate d log" d is optimal up to a constant factor, and achievable by the moment- matching method we established.
we prove that there exists d-object distribution
To briefly summarize the reasoning, Theorem 8 we show that there is a d-point uniform distribu- tion such that, for any d' d'-point weighted distribution, we can find symmetric function such that its where A and B are constants.
values on the two distributions differ by at least Ad ddeepp[ddd The d-point distribution is chosen to be "quasi-uniform" (see Definition (3). This property makes intuitively hard to compress, since if otherwise, big cluster of objects concentrate, we can reduce them to fewer objects by moment matching. The adversarial symmetric function is constructed as degree d///m polynomial. If we want a compression to be universally lossless, Adexp[ MMeep[-Bddaa 11m1/m] must be vanishing as d + co. Solving this inequality gives the desired lower bound for d', which is Q(log" d).
Numerical simulation. Figure 2 presents a direct numerical test of the compression error scaling predicted in Theorem We study the following function:
1 (ws,
........................... J(wi,...,
S(wi
wa) -
(13)
where all we and v, are m-dimensional vectors, and ( denotes the inner product. We compress a fixed fraction of the original dataset across different dimensions and with varying moment-matching

---

Published as a conference paper at ICLR 2026
(8)
m=
(b)
m=2
For (a-d):
10
10"7
{-1
- k-4
|40) -000
10
[n0) R00)
km 2
+ km
10
10:10
I
k-3
+ k-6
10
10-13
For (e):
+
+ m=3
10
10a
10
10a
10*
10
d
+ m=2
+ m=4
(6)
m9
(d)
(6)
10
10-4
In0- R0))
[(t)- (t9)- Rebl
10.9
10-
10
12
10
10a
10a
10
10a
10
10a
Figure 2: Error scaling for compressing general symmetric function (Eq. 13 using the moment-matching method. (a d): each point shows the error in f after compressing d max No.1d),.mm..) input objects. Matching higher-order moments leads to faster error decay. (e): is fitted exponent in ( x d The dashed lines indicate (k + 1)/m 0.5, which show good agreement with the numerical results.
(a)
(b)
GD. Ir = 0.05, full batch
AdamW, == 0.01, full batch SGD, Ir = 0.01, batch size 256
Adaml,, = 10", batch size = 256
Teat loss
10P
10P
10P
10-1
10-1
10-1
10:1
10-?
10
0
Epoch
Epoch
Epoch
Epoch
Figure 3: Compression of the training dataset in seacher-student setup. Green dashed line: training with the original dataset of size d 10º; Orange line: training with compressed dataset of size 10 using order 5 moment matching. Blue line: training with size-10 subset of the original dataset. Each annealing learning-rate scheduler, annealing from the value shown the plot titles Test MSE loss values are plotted every 10 epochs. It is observed that learning with the compressed datasct closely approximates the original dataset, whereas learning with naively subsampled dataset does not.
cosine
orders. Specifically, we randomly sample vectors x, and inputs [w; perrform compression, and average results over 20 trials to obtain each data point in Fig. 2 (a-d); error bars indicate standard
deviation. Figure e shows that the error decays approximately as E d-(4-1))m-005, While Eq. (IT) predicts an upper bound & d (k+1)/m=2 the observed error lies well below this bound and shows a dependency on is and m that is similar to the theoretical bound.
Figure shows the effectiveness of dataset compression in a standard neural network training task. We consider supervised learning problem in teacher-studen setup. Specifically, the teacher f(11,12) is implemented as a random two-layer MLP of width 50 with ReLU activation. The stu- dent receives d data points of the form (æ1, (f
32)), where æ and 22 are uniformly sampled from [-1,1], 1], and the goal is to learn f( 22) using an identical network architecture. The loss function is exactly symmetric in the dataset. For full-batch update rules, which depend on the gradient of the full-batch loss, any model prediction or performance metric is thus a symmetric function of the dataset. Consequently, if the student is given a compressed dataset of size d' derived from an original dataset of size d, the performance approximates that of training on the full dataset, and typically surpasses that of training d' naively subsampled data points (Fig. 3 aa))).
In practice, however, stochastic update rules based on mini-batches are more common. In this case, permutation symmetry holds only in an averaged sense. Nonetheless, we find that compression remains useful. Figures c.dd) show the loss evolution with batch size 256, supporting this claim. Additional details are provided in Appendix
7

---

Published as a conference paper at ICLR 2026
5 DYNAMICAL LOTTERY TICKET HYPOTHESIS
The lottery ticket hypothesis (Frankle& Carbin 2018 postulates that within any sufficiently wide neural network, one can find subnetwork that, when trained in isolation, achieves performance comparable to the original. While widely observed, its theoretical understanding has remained elu- sive. This section proves a corollary of our compression theory: any layer of a neural network with width d can be asymptotically compressed, losslessly, to a size polylogarithmic in d such that the training dynamics before and after compression are identical. We refer to this statement as the dynamical LTH, which can be viewed as a stronger and more quantitative variant of the original hypothesis, which only requires the final result to be identical.
The key idea behind the dynamical LTH is that predictions and loss functions are not only symmetric functions of the trained parameters, but can also be regarded as symmetrie functions of the initial parameters. This holds because common update rules are equivariant, i.e., they commute with per- mutations (see Appendix C.. Let f denote a symmetric function, let T denote the training dynamics (a mapping from initial parameters to trained parameters), and let On denote the initial network pa- rameters. By equivariance, S(T(O)) is again a symmetric function of 0g- Therefore, assuming that f o T admits a finite radius of convergence, the moment- matchhng compression established earlier applies directly to f leading to the dynamical LTH.
To make the dynamical LTH practically applicable, we must define a compressed dynamics T', which maps compressed initial parameters to compressed trained parameters. The formal definition is given in Appendix C but in practice it is straightforward. For gradient-basee update rules such as SGD or Adam, the compressed dynamics acting on H' {(Cg, ( jet'r] is identical to the original dynamics on 6, except that each gradient 0L/Ow, is replaced by e 10./ With the notions of equivariance and compressed dynamics, one can prove the dynamical LTH:
Theorem 5 (Dynamical lottery ticket hypothesis). Let 0 {ws) ia[d] be set of permutation- symmetric trainable parameters of a neural network, and each |[::] S R. Suppose the model predic- tion f: Vd TR. is permutation invariant, and the training dynamics T Vd V is equivariant. Also, suppose f o T satisfies Assumption] [ pressed weighted parameter 8g (which does not depend on or T)), supported on d' O(log" =(d)) points, such that
Then, for any initial parameter Go. there exists a com- d
( = =(d).
(14)
More specific error scaling of the dynamical LTH takes the same form in Theorems and Here, Assumption T is needed for the o d scaling in Theorem 3 to hold. Theorem 5 not only applies to two-layer MLPs, but also naturally extends to e.g., mulli-headd attention. However, it requires some scrutiny to be extended to deep networks. From a similar reasoning we expect that each layer can be compressed
vanishing portion of its original width while respecting the dynamical LTH, but the scaling of d' is an open question. Regarding Assumption I it is theoretically not clear whether T respects this assumption even if does. We expect that when the single-step mappings are analytic and the number of steps is finite (compared to d), the analyticity of f T follows f and thus Theorem holds.
A subtlety of Theorem 5 is that compression produces "weighted neural network." However, such networks can be reduced to equivalent standard networks. To see this, recall the expression for the output in Eq.
3 For weighted network, this becomes
f(x) Σ cou (w)o). 3-1
(15)
If we redefine the second-layer weights as ny + CR then the expression reduces exactly to the output of a standard neural network (by incorporating c into the outgoing weight).
Numerical simulation. Figure/ 4 directly validates the dynamical LTH. The task is to leamn the function f( 22) shown in Fig. 4(a) from 10t data points of the form with 21/2 sampled uniformly from [-1, 1J. Across wide range of update rules and learning rates, the predictions of a wide network and its compressed counterpart are shown be nearly indistinguishable throughout the training dynamics.
8

---

Published as a conference paper at ICLR 2026
(8)
(b)
SGD, 10
(C)
Rorop, Ir 10
(d)
AdamW. It 10*
Testloss Train loss
6x
6 10
6x100²
5x10-
5x10-2
0.3
5xx10-2
4x10
-0.3
2x10-
2x10-2
10:2
10:2-
6x10-3
10-2
31
1
4x10-3
2000
2000
Epoch
Epoch
Epoch
Figure 4: Dynamical LTH (Theorem The demonstrated task learning bivariate function from noisy training data. (a) Ground-truth function f(11,T2) = Ja (20r) cos(6i), where r² = o 22 and 9 = pretan(22/21) ), known as a cylindrical harmonic. (b-d) MSE loss vs epoch under three different up- date rules. Green dashed line: randomly initialized network of width 10"; Orange line: compressed network of width 10", using & = 5 moment matching; Blue line: random subnetwork of the 10" -widht network, also of width 10a. Loss values are plotted every 50 epochs. All runs employ cosine annealing learning-rate sched- uler. Batch size is 512 for all cases, and for the three curves in each figure, enforce identical trajectories of mini-batch choices.
6 IMPROVING NEURAL SCALING LAWS
Theorem 4 shows that the predictions obtained from a large number of objects can be faithfully reproduced by much smaller set of weighted objects. This observation can be leveraged to asymp- totically improve neural scaling law. A commonly used empirical form of neural scaling laws is (Henighan et al. 2020)
(16) where L denotes the loss and d may represent dataset size or number of parameters, or similar re- sources. Theorem improves power-law scaling in dataset size or model parameters to at most streched-exponeential scaling. To see this, suppose we compress d objects into d' d" objects,
L(d) Lo (du/d)",
k+1 where 0 < 1. By Eq. (II), the loss takes the form I(d) Lo + (do/d)" O(d Choosing ht sufficiently large ensures that the compression-induced error vanishes compared to %d, leading to a improved scaling:
I(d') Lo + (dold'
(17)
In the same spirit, we can compress d to d' = O(log" TM d) (inducing arbitrarily fast power law error, which is negligible) so that any power-law scaling is improved to a stretched exponential scaling as
L(d') = Lo + a Lo + exp(-a' VVd').
(18)
Numerical simulation. We demonstrate improvements in scaling laws with respect to dataset size in Fig. 55a) and with respect to network width in Fig. (].). The learning tasks in Figs. 5la) and b
are the same as those in Figs. 3 and 4 respectively; additional details are provided in Appendix T
In both cases, compressing d objects to [16vd] objects effectively doubles the scaling exponent. As a practical remark, the error bound in Eq. (TT) guarantees sufficiently small compression error only & 13. However, in Fig. 5 we match only up the 6th moment and still observe quadratic speedup. Together with Fig. 2] this suggests that in practice the error scaling can be substantially faster than the worst-case upper bound.
DISCUSSION AND OUTLOOK
In this work, we established a rigorous framework showing that any permutation- -yymmatiioo---mmtiiiiici function admits strong asymptotic compression. A key advantage of the theory is that it is asstem-agnsticc, meaning that it can be applied to any architecture or loss function. The theory has strong implica- tions for deep learning and AI research. We showed that this result can be applied to understand the compressibility both neural networks and datasets, a connection that has not been identified previously. This leads to unified theory of compression for deep learning.
The central contribution of our theory is a proof of concept that it is theoretically possible to strongly compress neural networks and datasets, enabling far more efficient use of data and parameters. An

---

Published as a conference paper at ICLR 2026
(4)
(b)
Original,
Original,
10"1
Compressed.
Compressed, a-00077
Text foss
4x
10
10
2x10
10P
10
10P
10'
10
Dataset
Width
Figure 5: Improving neural scaling laws through compression. (a) MSE loss of the teacher-student task after training original dataset of size d compressed dataset of size d'. (b) MSE loss of the cylindrical harmonic task after training a two-layer neural network of width d versus its compressed counterpart of width d'. In both panels, compress d objects obtained by fitting d or a
[16vd] using moment matching. The exponent
important future direction is therefore to develop practical compression algorithms that can improve neural scaling laws at scale. We proposed a polynomial-time algorithm that achieves these scalings exactly, but is currently too slow and meeoryyintensivv in high dimensions. We expect future work to either optimize this algorithm or design scalable approximations. A potential limitation of moment- matnntng compression is slow eтror decay when the constituent dimension m is large, re- flecting the familiar curse of dimensionality. Another possible limitation that when m large the outputs are likely degrade in smoothness. However, many ostensibly high-dimensional objects actually lie near low-dimensional manifolds (Abbas al. 202T). particular, language data appear to have effective dimension 10 (Gromov al.) [023] Du & Tanaka- Ishii 2025). These obser- vations suggest that our compression framework can be extended to handle high high-dimensional yet structured data, where exploiting low-dimensional embeddings may greatly mitigate the apparent limitation.
Our framework also suggests new directions beyond direct compression. In particular, it points to improved data sampling strategies and model initialization schemes. For example, our proof of the dynamical LTH be interpreted showing that sufficiently well-initialized network may match the performance of a randomly initialized network orders of magnitude larger. The future direction construct initializations (or datasets) that behave if they were already compressed. Intuitively, well-chosen objects should be weighted and roughly eguidistant, making further compression dif- ficult. Such strategies may be connected to importance sampling (Hammersley. 2013] Bengio & Senecal 2008) and orthogonal initialization (Saxe et al. 2014). On the theory side, many questions remain open. Extensions of our results could refine approximation rates in Barron space (Barron)
1994 Ma et al.) 2022 Yang & Zhou| (025). Finally, while our framework is rooted in the symmetric group, generalizationns to other group structures may offer further insights.
ACKNOWLEDGMENT
The authors thank Yizhou Xu for discussion. ILC acknowledges support in part from the Institute for Artificial Intelligence and Fundamental Interactions (IAIFI) through NSF Grant No. PHY-2019788 This work was also supported by the Center for Brains, Minds and Machines (CBMM), funded by NSF STC award CCF-1231216.
REPRODUCIBILITY STATEMENT
realization of our compression algorithm and code for generating all the figures are available at https://github con/ www--Davi/moment. DDwva//mooeee_ccmmrrressoo.... wwwpression..gi.....
REFERENCES
Amira Abbas, David Sutter, Alessio Figalli, and Stefan Woerner. Effective dimension of machine learning models, 2021. http:ttts///a/v..orrrr
04807
10

---

Published as a conference paper at ICLR 2026
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 14(1):115-1333 1994.
Yoshua Bengio and -éanSStéastienn Senecal. Adaptive importance sampling accelerate training of a neural probabilistic language model. IEEE Transactions on Neural Networks, 19(4)7113-722, 2008. doi: 10011//TN..2000.9133333
Benjamin Eloem-Reddy and Yee Whye Teh. Probabilistic symmetries and invariant neural networks. Journal of Machine Learning Research, 21(90):1-61 2020.
Ben Blum-Smith and Samuel Coskey. The fundamental theorem on symmetric polynomials: his- tory's first whiff of galois theory. The College Mathematics Journal, 48(1): 2017.
Johanni Brea, Berfin Simsek, Bernd Illing, and Wulfram Gerstner. Weight-space symmetry in deep networks gives rise to permutation saddles, connected by equal-loss valleys across the loss land- scape. arXiv preprint arXiv:1907.022:
2019.
A. Brudnyi and Y. Yomdin. Norming sets and related remez-type inequalities. Journal of the Aus- tralian Mathematical Society, 100(2): 181, November 2015. ISSN 1446-8107. doi: 10. 10.1017/ 01146788715000488 URL /tt0::////...dd.oo/////0/////440
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecom- munications and Signal Processing). Wiley-Interscience, New York, NY, USA, 2006. ISBN 0471241954.
Arthur da Cunha, Emanuele Natale, and Laurent Viennot. Proving the lottery ticket hypothesis for convolutional neural networks. In International Conference on Learning Representations, 2022.
Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre- Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The faiss library, 2024.
Xin Du and Kumiko Tanaka-Ishi.. Correlation dimension of auto-regressive large language models, 2025.
21258
Michael J. Field. Equivariant dynamical systems. Transactions of the American Mathematical Society, 259(1):185-20) 1980.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXhv:1803.0333: 2018.
Vasilii A. Gromov, Nikita Borodin, and Asel S. Yerbolova. language and its dimensions:
Intrinsic dimensions of language fractal structures, 2023. URL https::/aa.iv..or//////o// 231
7
J. Hammersley. Monte Carlo Methods. Monographs on Statistics and Applied Probability Springer Netherlands, 2013. ISBN 9789400958197 URL. http::t/t//// http:///ookk... ggoogl googl e. com/books?
-d- 3rDDCAAAQBAA
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.0014 2015.
Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Hee- woo Jun, Tom B. Brown, Prafulla Dhariwal, Scott Gray. Chris Hallacy, Benjamin Mann, Alec Radford, Aditya Ramesh, Nick Ryder, Daniel M. Ziegler, John Schulman, Dario Amodei, and Sam McCandlish. Scaling laws for autoregressive generative modeling, 2020. URL https: //arxiv.org/abb/2000
14701
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836) 2020.
I.E. Leonard and J.E. Lewis. Geomerry of Convex Sets. Wiley, 2015. ISBN 9781 11922299. URL fittss//bbodt goog hhhr

---

Published as a conference paper at ICLR 2026
Chao Ma, Lei Wu, al. The barron space and the flow-induced function spaces for neural network models. Constructive Approximation, 55(1):369-406) 2022.
Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference on Machine Learning, pp. 6682- 6691. PMLR, 2020.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Op- timal lottery tickets via subsetsum: Logarithmic aver-parameterization sufficient, 2021. URL
ftttp:://arxi..orgege
2006 07990
Federico Piazzon, Alvise Sommariva, Marco Vianello, al. Caratheodory-tchaaaaloff least squares. In International Conference on Sampling Theory and Applications (Samp?AA), pp. 672-676, 2017.
David Salomon. Data compression. In Handbook of massive data sets, pp. 245-309. Springer, 2002.
Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dy- namics of learning in deep linear neural networks, 2014. URL URthttpss//axxiv.orrr
1312. 6120
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neu- ral scaling laws: beating power law scaling via data pruning. Advances in Neural Information Processing Systems, 35:19533- 2022.
Puoya Tabaghi and Yusu Wang. Universal representation of permutation-invariinn functions on vectors and tensors, 2023.
13829
V. Tchakaloff. Formules de cubatures mécaniques coefficients non négatifs. Bulletin des Sciences Mathématiques, 81:123-134, 1957.
Tongzhou Wang, Jun- Yan Zhu, Antonio Torralba, and Alexei Efros. Dataset distillation. arXiv preprint /8/ 1. 2018
Larry Wasserman. All of nomparametric statistics. Springer. 2006.
Yunfei Yang and Ding-Xun Xuan Zhou. Optimal rates of approximation by shallow relu neural net- works and applications to nonparametric regression. Constructive Approximation, (2(2):329-23)) 2025.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets, 2018.
06114
Liu Ziyin. Symmetry induces structure and constraint of learning. In Forty-first International Con- ference on Machine Learning, 2024.
Liu Ziyin, Yizhou Xu, Tomaso Poggio, and Isaac Chuang. Parameter symmetry breaking and restoration determines the hierarchical learning in ai systems. arXiv preprint arXiv:2502.05300 2025.
12

---

Published as a conference paper at ICLR 2026
A LEMMAS AND PROOFS OF THEOREMS
A.1 FTSP
The following theorem is well known. We quote and will use in the proof of Theorem
Theorem 6 (Fundamental theorem of symmetric polynomials). For any symmetric polynomial ((I1....,TE)) where 24 e IR for all E [d], there is unique polynomial P such that
f(11,.....a) = Pa)).
(19)
where Pk (k E [d]) is called the kth moment and is defined as
d
Ph
(20)
An arguably common statement of the FTSP is that any symmetric function is function of power sums Σ z for k 0,1,-...d, d, which differs from our statement by normalization of However, our convention fixes each moment Ps to constant order of magnitude. With our convention, we can treat / as dependent on
A.2 THEOREM
Proof. We write the coordinates of wi (W,,1...., W..)). For convenience, use the multi-index notation a = (a1, am). such that w.f = w am For a multi-index a, |a| a1 + ..... am-
Also, we define 9a Σ wi (we use q distinguish from p with a 1/d factor). Our proof is divided into a few steps: (1) Represent f in terms of q. 's (2) Repack {g.} into tensor moments {pk) (3) Show that only Pk for k 1....,d are independent (4) Show that the representation in terms of } is unique.
Generally, a polynomial f is linearly spanned by monomials in the form W u wi (note that N d), where all subscripts are distinct and each |ayل > Imposing permutation symmetry Sa, such monomials differing by index permutation must appear with the same coefficient. That is, the space of symmetric polynomials is linearly spanned by terms in the form
Σ DESA
w (11) (2)
WON ((N)
Σ
w 02 ... NN
(21)
Here, we introduced the notation X (ii iN) to denote the set of index list (fz,..., iN) such that all i are distinct and range from 1 to d.
We prove by induction on that such terms can all be written as polynomials of qa 's. When N = 1, Eq. 21 is simply 9, by definition:
Σ w = 9a
(22)
Now, suppose Eq.
21 is proven to be a polynomial of gu ss Replacing N - N + 1, we look at
Σ
w w
w
w
0x-1 ix
(23)
x(11...
We use the set decomposition
X(i iN) x (iN-11 x(ii, TeniiNNuUN (())), iN) {it}
(24)
U(... iN) {iN}
to rewrite Eq. (23)
Σ
Σ
ixel
ix-1
x(11...)x111
N(1....o)) iN+1
(25)
Σ
wht w00 ... w. ox axol
Σ
w wo ...
w w
ax axel
in 81
x(1)...)x)
{(1....)))
13

---

Specifically, is mapped to Published as a conference paper at ICLR 2026
On the right-hand side, the first term can be written
Σ
wi
w &v
gax-1
(26)
((1....))))
in which the parenthesis is polynomial of qa 's by induction assumption. The second term can be written as
Σ
win
w
(27)
X(1
which is polynomial of ja 's as well, and so are the other terms in the ellipse. Therefore, we proved that all terms in the form of Eq. (21) can be written polynomials of qa s.
Next, we repack qa into tensors. Define Pa = qa/dd Note that the set {Pa |a| = k3 is exactly the set of coordinates of the tensor pa Ei w /d. So indeed, the value of f relies only on the tensor moments Pk-
To show that I' only requires the first moments, we try to represent any pk (k > d) as a function of Pl.....Pd. P& is symmetric tensor of rank k. It is easy to see that the space of symmetric l- k-tensors is isomorphic to the space homogeneous polynomials of degree io (the argument is denoted as "R, by the homomorphism
T Ten....be
Σ $1
Tei....ie Usg ... Usz
(28)
1 N su(u) Σ
(u'w;)+ i=1
(29)
Using Theorem 0 for the variables {uTw; we] 1,2,, d), there is polynomial P such that
sx(u) = =...())......((
(30)
Because this holds for arbitrary u, it follows that pk is function of , as well.
The fact that the representation of f in terms of moments is unique is obvious: assume two poly- nomials I and I' are mapped to the same function. Taking the difference of the two equations f(0) P({pk)) and f0) P((px)). we find f(0) - f()) for any 0.
A.3 THEOREM
Proof. Choose m-dimensional ball of diameter r that contains all wy is. and let the center be wp E Rm We first Taylor-expand f(0) around On = (wo,..., w.) up to the kth order. The expansion symmetrie polynomial of degree Theorem we can find another set of weights {c]] supported on Nm,, = (m**) points, such that
it can be written as function of (Pi)....PP). By
Ed(w; -
(o) wo) Ee((: wp) p for 1....,k
(31)
Let 0' = (cc, w.). and denote its moments by {p/}. By construction, we have pi for 1= = 1....,k .k Since the first moments all match, there is no difference between 6(c) and ((c') up to the kthh order.
Next, we look the (k + 1)th order in the Taylor expansion of f(0 around 0g. It written as
Σ 0a. 00)"
1
(32)
Ja a!
is a degree-(k- (ktce) homogeneous symmetric polynomial, and we denote as Pk+1 (kk1)...
Hence,
fa(0) - fa Pk+1 ......... 1) - Pk+ (P.....,
(33)
In (pt1(p..... (p:1)..,P::),, the only term that depends on Pa+1 is linear in itself (be+1.Pk+)) where be-t is a (k + 1)-index symmetric coefficient tensor and here (+-)) denotes tensor contraction; all
Pk+1),
14

---

Published as a conference paper at ICLR 2026
other terms completely determined by {pi (pi)ii, To that bş+1 is most of order d, the deep-set representation: f(0) = h ([(ee(d] w.)) Then bx+1 can written down explicitly as
0f
(bx+1.
Σ
(ak+1, (w; ww) ((()))
dy i=1
(34)
0f
d
ax+1.,1 Pk+1
Oy
where y Eieee] O w;). and (aR+1, (w, mo) ( is the (I: 1)th order in the Taylor expansion of g around wo- All derivatives taken 0 On- By convention that h and g independent of d, we thus have bk+1 = O(d).
Also, since each llay woll $ r/2 we have pk+1 = O(rht1). Therefore, we conclude that fa(0) fa(0') (ddrtt)).
A.4 SPHERE PACKING LEMMA
This lemma used in proving Theorems and
Lemma (Sphere packing). Given d >> 1 objects in a closed m m--imensional ball of radius R: that is, 0 {wo | |wel| R. For any the diameter of the smallest ball containing N points is at most of order (N (Nld) i/m, That is,
sup min diam(S)= RO ((N/d)Vm).
(35)
0
SEN
Sca
Proof. We use ((x,)) to denote a closed m-ball centered at x.
Cover B(0, R) by M balls of radius By the pigeonhole principle, if d (N - 1)M, some ball contains at least N points, giving an N -opoint subset diameter 2r.
We show that there exists covering with M (1 2R/r)" points. We choose set of points [25)) B(0, R) to form a maximal r/2--maalrr/peeeeeeeeeee r22-packing of the ball B(0, R), meaning
x2. x, 2r, V.
(36)
and no further points can be added while maintaining this separation. By this definition, the balls (B(z,,r) form covering of B(0, R),, but the smaller balls (B(z,,r/2) are mutually disjoint and contained BO0 R r/2). By comparing volumes, we find
M(r/2)" s (R r/
(37)
Hence, the radius of each ball is r. there exists a covering of B(0, Rt) with [(1 2R/r)" balls. Also requiring d/(N 1) [[1 + 2R/r)"" we conclude that
4R
sup min diam #
N-1 - 1) 1/m (O((N)
(38)
N
A.5 THEOREM
Proof. Denote NN,, = (m) In this proof, we show that the general algorithm (Algorithm) 1 with greedy clustering strategy satisfies the asserted error bounds. By the greedy strategy (also described in Appendix D). we mean that in each iteration choose subset S s |sup(c)) of N objects among the active (i.e., with nonzero weight) objects. Then we reduce one object in S while maintaining up to the kth moment.
By Theorem 3, the output error of one step of order csr where cs is the total weight this cluster, and the diameter. Because the greedy strategy always look for optimizing the diameter,
15

---

Published as a conference paper at ICLR 2026
after (d) steps, there is no better upper bound for es than d. By Lemma objects, the smallest diameter is upper- aopereb by
when there N active
of
Nm, 1 N
1/m )mm) =(NN1/m)
(39)
Now, we up the error of all the steps. Denote the function's 's error as l0(c) -(()). Then, in one step of pruning, the error is
A = O(drktl) O(dN
(40)
We upper-bound the sum over by an integral using ENnw N s fø N- dN, and find that pruning d original objects into d' objects results in
3 0=3
d.N-(k-//mm aN)
(41)
= 0
k+1 (d))
d
d Ke1
or logarithmic if & = m. but we are only concerned with vanishing error, we will skip the analysis of k + 1 m. Since d' < d, we conclude that the error is upper-bounded by
{=)(d(d))~
(42)
which completes the proof of statement 1. To show statement 2, we look at the equation
cdd)= = (
m
(43)
Solving this equation with respect to d' gives the asserted scaling of d'.
A.6 OPTIMAL & AND polylog SCALING
In establishing Theorem we have been fixing as a hyperparameter which can be chosen at will. Here, will optimize over the choice of study the smallest achievable final size d' such that the error is vanishing. In the derivation below, could scale up with d, but we always set m to a finite constant.
Theorem 7. Assume |wwll S R for all i e [d]. There exists mapping from d uniformly weighted objects to d' weighted objects, such that for any symmetric function f satisfying Assumption 1
1. The error is
= 111m exp [ )(mllpdd))mmm)
E= E=(du((") =
(44)
where p the radius of convergence of the function g in the deep-set representation of (Eq. 44;
2. d uniformly weighted objects can be compressed into d' d=0
d
(45)
E(d)
weighted objects, such that the error is no larger than E(d).
Proof. Essentially, follow the greedy strategy and the same reasoning the proof of Theorem However, since & can be large, here we keep track of all factors that scales with & or d.
Recall that the upper bound for the radius cluster is (NNm. + 1) 1/m, and the upper bound for eg is d. Also, since the convergence radius of g be P. the constant factor for the (k: + 1)th
16

---

Published as a conference paper at ICLR 2026
order Taylor expansion scales as p* Putting these together, the error of step of pruning is upper-bounded by
AE = -
0 @/ppp
Nm, + N
k=l
(46)
For notation simplicity, we will drop the big-O notation and use AE to refer to the upper-bound expression on the right-hand side of Eq. (46). There is an optimal kops that minimizes the single- step error. We solve it by taking derivative of log(AE/d).
A+
log (Ag/AE/d) lo p+
(log(NM,, mm 1) N)
m h+1
=-klog p+
(log(m k)! log k! log(ml))))+ ((1)
(47)
m
= koo k log k k+1 log (og(m!Np)) 0(1.
In the third line, used Stirling's s formula log(n!) n log n (og(( 1 +O 3) when n oo and simplified the expression. The derivative the above reads
12m
d
1 log(m!N O(K-1).
log (E/d) log dk
(48)
m
Setting the derivative to zero, we obtain
log Kopt
log(m!N))
(49)
m
Plugging this value into Eq. (47
we get
log( (oop//d -oopt + 0(1)
(50)
E O dexp - (ml. pm)
Moving forward, we integrate over & from d' to d:
Eopt =0 o(d St exp - ( /) )NN)
(51)
-0 dT (m, 1
(mlpd") 1/mo)) Umm))
where I' is the incomplete Gamma function:
r(m,2) {( tm-le dtd.
(52)
Its asymptotic behavior oo reads
2m=1 I(m, exp[=2+0(2> m- (1+00111071)) (1+0
(53)
Inserting this expansion into Eq. 51, we get the asserted error scaling in part 1 of the theorem.
To obtain part 2, we solve the inequality
E(d) =
exp (mlpdd))
(54)
with respect to d'. One can take log on both sides of this inequality and safely neglect the factor 1-// to eventually get
d' = 0 log s(d)
(55)
17

---

Published as a conference paper at ICLR 2026
B polylog COMPRESSION RATE IS OPTIMAL
In this Appendix, we show that our algorithm of compressing d objects into O((og d) weighted objects is optimal up constant factor. The strategy prove this is find d-point uniform distribution show that for any d' -'poonn distribution j we can always find a function that evaluates to sufficiently distinct values on these two distributions.
What distribution is hard to compress? Inspired by the fact that we prioritize merging close-in- distance points in the main Algorithm [ in an adversarial distribution, all points should be roughly equidistant from the neighbors, so there is no cluster that is particularly "easy" to compress. Hence, we introduce the following notion of quasi-uniformin
Definition 3 (Quasi-nniformity) Let D R be a fixed compact set with nonempty interior. A set Xa = (21....,I. J c D is quasi-uniform if there is a constant Cp (independent of d) such that each Voronoi cell of v, has volume less than or equal to Cz.
A quasi-uniform point set obviously exists: for example, it can be a maximal Old > of the region D (see the proof of Lemma for the definition).
Another lemma we are going to use is the following. The basic message is that a nontrivial degree-k polynomial cannot be exponentially small most of D; a set of finite measure remains above e Ak
Lemma 2. Let D = Rm be a convex compact set, and let [D| denote its volume. Let be real polynomial on D of degree S normalized by ||p|| [=)()) supze [p(x)) = 1. For any 0, define
S = D: [p(x)]
(56)
Then
|
2 (1/ D
(57)
Proof. We begin by quoting a multivariate Remez inequality (Theorem 1.2 in Brudnyi & Yomdin
2015 ) for any measurable Ec D with A= [El e (0, 1] and any real polynomial of degree s k
7
1+ (1-
[alll=<D) s Th
(58)
1- (1- 1/m
1/m
where Tk is the Chebyshev polynomial of the first kind.
For L (0, 1), we use E, to denote the sublevel set:
Ed
E. (xED) D: [p(x)) S (),
A
(59)
[D]
Applying 558 with 9 = p, E= E, and using [|pl ()))) gives
1 (1- 2m
Tg
t.
(60)
1 1- Xx) > 1/m
Then, we make simplifications to the Chebyshev term in Eq. (60) For 2 1,
(x( += + -22
2 2 x
(61)
Moreover, since v o \/m is increasing and wm/m on [0,1].
1 + (1 X) 1/m
1
1
2 X
for Xe (0.
(62)
1 X) 1/m
1 1- (1- 11m
Combining (61) and 62 in 660). we obtain
5 } x
d s (1/
(63)
18

---

Published as a conference paper at ICLR 2026
Now pass to the superlevel set Sy. Note that |St| |Eg| [D]. Then
|
X, 2 1 (t/2)
(64)
D
The following theorem constructs an adversarial polynomial (i.e., has moderately large error how- ever we compress), Remember from Sec. Soc..ttie that our global assumption for functions is this paper is that they have finite convergence radius, so the polynomial constructed here lies within the assump- tion.
Theorem 8. Let y and μl be non-negative distributions supported on D: p Eiz òzg, pl
Σj-1 Cjoy, where all Di.y; E D and Cj > O. There exists a μ such that for any μl, there exists a polynomial g and constants A,B B 0 such that
1o gdu S. Adexpl-Bd
(65)
Proof. Let & be the smallest integer with Nm. = (m=*) d'. Let q R - R be degree-k polynomial. Since there are Nm. parameters in q, there exists a non-zero polynomial such that (vI) ((ua) = O. Also, q is normalized so that ([)))=((D) = 1. Let g = q² be the adversarial function that will be shown to satisfy Eq. (65). For y and pl, we have
f gdp' = Σ ==((v))==
(66)
Next, we consider fD 9 du. Denote the point set of {=r) by Xa. Quasi-uniformity of Xa implies that the number of points inside region is comparable to the volume: #(Xan5) 2 d |S| for some constant cp > 0. Let S be the superlevel set St, we have
ep
J -pp Σ [ dss. 2 a
d - (1/2)
(67)
where we used Lemma 2 in the last line. We further plug in t= 2c Ch to have
So Ladu
DD] d1
-CC
(68)
CD
Putting this together with fn 9 du' O and denote A= |2| (1 (1-E-c).
cp
Vn SA gdp' 2 2Ch
(69)
Finally, recall that & is the minimal integer with Nm.k > d'. Since Nm, = m ~ km /m/, there exist constants ej and cs (depending only on m) such that
lm k /m
(70)
Therefore,
1,, gdu - Sf gdp 2 dddexp[Bdd'//e
(71)
where B B= -22
Finally, we show that Theorem leads to O (((lgg ") compression lower bound. We require the compression error to be at most (d), which is a vanishing function when d + co. This is not possible if
Adexp[-Bal /mm 2 E(d).
(72)
which is equivalent to
Ad m
d' s B E(d)
log
(73)
A common choice for E(d) is (d) or d= In this case, the hand side of the above inequality is proportional to (log d" Therefore, a universal compression from d objects to O(llg d)") is optimal.
19

---

Published as a conference paper at ICLR 2026
C FORMAL THEORY ON THE DYNAMICAL LTH
In this Appendix, we formulate all ideas mentioned in Sec. with mathematical rigor.
Let Sa be the permutation group of d elements. Let V R We define the representation R Sa End(V") as
(())(w),..... wa) (1o(1), :.. Wo(4))
(74)
Note that the definition of f v + v being symmetric is equivalent to: for any e Sa. R(o)= f.
Definition 4 (Equivariant map). function T V V is called equivariant map if for any a e Sd.
To T(o) - R(o)
(75)
The dynamics induced by equivariant maps has been studied in conventional settings of dynamical systems (Field) 1980), but has not received much attention in deep learning. In fact, almost all update rules that commonly in this Appendix. Because compositions equivariant maps are also equivariant, it follows that the entire training dynamics (i.e., the mapping from initial model parameters to trained parameters) is equivariant.
equivariant, which we will verify for SGD and Adam later
The following lemma shows that the composition of a symmetric function with equivariant map- ping is also symmetric function.
Lemma 3. If f is a symmetric function and T an equivariant map, then f o T a symmetric function.
Proof. For any é Ss,
(76)
Thanks to this lemma, we can treat f o T as single symmetric function, and thus we expect that compressing weights by our moment matching method induces a vanishing error in the value of fo T, that is, literally any prediction of the trained model.
The following lemma establishes general representation equivariant maps in terms of moments, so it can be viewed as extension of the FTSP.
Lemma 4. T is an equivariant map if and only for all i [d],
T((0) (w:;, p), where is a collective notation for (pr- = 1 Σ w 2h dd-1 depend on and is uniquely determined by T.
(77)
JK-1 Note that T is a function that does not
Proof. First, verify that T.( T(w,, p) for any function T is equivariant map. Note that o = p. Following the definition cquivariance,
T (0) -T(..))) wo(a)) T(W (T(o)())))TT(()))))))
(78)
Thus, To
The rest of this proof is to show that all equivariant maps can be written in the asserted form. For a fixed let ô Sa be any permutation group element such that o(i) i. Consider the ith component of the equation T (()()) = (T(())):
T((
(79)
This means that T is invariant under any permutation on [d]][), which forms a representation of Sa-1. By Theorem T; be uniquely written function of w; and power sums Ef w Since Σjs; w is uniquely determined by w; and as dpx - w.t ok we conclude that there is unique function T, such that
T((0) (w...)).
(80)
20

---

Published as a conference paper at ICLR 2026
The final task is to show that T; does not depend on i. We use *i,y to denote the permutation group element that only exchanges and j. The ith component of the equation T (TTa = (T reads
T((w,,P) = (T;
(81)
which completes the proof.
We use Lemma to unambiguously define the compressed training dynamics:
Definition (Compressed dynamics). Suppose training dynamics is determined by an equivariant map 0 ((()) (arbitrarily initialized weights to trained weights), which can be written as in Eq. 77.. For the weighted parameters 0' {ej, jedd (cj never changes with the dynamics; some oj might be zero so that they are actually pruned), we define the compressed dynamics T' as
()( T(W,,p')
(82)
where p' is collective notation for (r4- E, w b Note that T' is uniquely determined by T.
The mapping from original learning dynamics to compressed ones is in fact easy in practice. Below common examples.
Stochastic gradient descent (SGD). Consider two-layer neural network used in supervised learning. For simplicity, we write the output as y = Σd I (w; which symmetric in 0 = (..,,..., wa). Each time we choose a batch of training data {( Ba) ne... We denote
the per-sample loss function as la = [(y(O, xx). ya). The SGD update rule
Ola
T((0) w; 1) E aeB dw,
(83)
Il. (g(w;,
w; 17 E aet Oy Ow;
where is the learning rate. Note that 06 is function of y, which is thus permutation invariant in 0. We can explicitly compute (T (() and (R(o) o (O),, which are both equal
Ola Og (g(W)(())F))
(o(()
7) oE By @wo(1)
(84)
SGD is indeed equivariant.
Then, derive the compressed SGD. Remember that the weighted neurons compute the output as y Ed (yg(w;,z)) Eq. (83) can indeed be written in the form (ww,,p) p) because ala/dy is a function of p, and Ög (w;,,x))Ous solely depends on wi. Therefore, the compressed update rule still looks like
Ti()) - Ol. 0g(ws, Wi, v.)
(85)
DEB Qy Owj
However, we emphasize that is not wi 1 Eost Hlal @ow because
al. ala dg(w;, va) Owy
Oy cj
(86)
Owj
Effectively, whenever there is gradient 0L/ōw, in the original update, we should replace it by e7 aL/Owy. This rule applies for all other gradient-based updates well.
Finally, we remark on non-deterministic updates. seems that choosing mini-batches turns the update into stochastic process, which complicates the problem. But in fact, for any fixed trajectory mini-batch choices, the update is explicitly equivariant (choosing a mini- batch breaks the permutation symmetry among the training dataset, but not the permutation symmetry of neurons). Therefore, we always expect to see good agreement between the original and compressed dynamics if we use the same choice of mini-batches for both.
21

---

Published as a conference paper at ICLR 2026
2. Adam. The Adam update rule for standard (i.e., uniformly weighted) parameters reads
+ Ve E aBB 08
(0(-1)
me 1 1 -1)1
P 12 (1 82)gr
m 1 1 B
M
(87)
Vt
0, 1 $3
m
0, 81_1 1l
Ve +
where denotes time step. To check that Adam is equivariant, only need that the gradient (gt) for wa takes the form
Oe, Üg(ws, va)
E a dy
(88)
Ow,
where 0c./Oy is symmetric, and 0g(w,, za /dw; is soiely function of wy Using this fact, is straightforward to check that (T o (0) and (R(o) o T) are identical. To define the compressed version of Adam, we need to keep the gradient exactly as in Eq. (88) as in discussion SGD. This in turn tells us that just need to replace OL/Ow, by c. OL/Wu. Special to Adam, because 1/c; appears in both m, and vo,, the compressed update rule is basically the same the original if neglect the small Indeed, in the numerical simulations we conducted with Adam W (the reasoning is the same Adam), did not observe any visible difference whether not scale the gradients by 1/c3.
Finally, we prove the dynamical LTH, which we restate here.
Theorem (Theorem
5 Dynamical lottery ticket hypothesis). Let 0 = {wrheedd) be set of permutation-symmeeree trainable parameters of neural network, and each [[w]]] s R. Suppose the model prediction f: V: R is permutation invariant, and the training dynamics T Vd V equivariant. Also, suppose f o T satisfies Assumption [ Then, for any initial parameter Oo. there exists compressed weighted parameter 0g (which does not depend on I or TT), supported on = Ollog" E(d) points, such that
((T) = e(d).
(89)
Proof. We compress 0g using moment matching. By construction, for all ( 0, 0,1, I,.... k we have
(wo), 01 -50===c,-- cc)(w))
(90)
JeS
For any f. o T and fo o T' can both be written as a function of moments. In this representation, using the definition in Eq. (82). one check that they are exactly the same function. The difference that f T takes in (Po)
E, (wo) while fo T' takes in (p6) = 1 E, Cy (wo) they are identical in the first k moments by construction. Using Theorem 4 we conclude that using large enough k, the difference between ((T(On)) and S(T' (T)())) can always be made vanishing, with the same error upper-bound as asserted in Theorem 4 Ultimately, using the optimal hopt given in
Theorem we achieve d' Of log" m c(d)
with error at most (d).
D AN EXAMPLE OF THE MOMENT-MATCHING COMPRESSION ALGORITHM
Here, we describe the concrete algorithm for compression that used all our numerical simula- tions.
22

---

Published as a conference paper at ICLR 2026
Runtine
162
10
Figure 6: Runtime benchmark of the hybrid compression algorithm. See description in Sec. The original dataset is i.i.d. uniformly sampled in an m-dimensional cube. The moment-matching order for all trials in this plot. Each marker the plot an average over trials, with error bar representing one standard deviation.
Recall that in Algorithm 1 we identified two main steps of the algorithm: (1) clustering and (2) moment matching. We first describe our moment matching strategy. For motent-matching. we consistently use Algorithm 2 in which vect(.) represents flattening all the moments into a vector. We remark that the existence of Algorithm is effectively a constructive proof Tchakaloff's theorem 2
Our actual clustering strategy is slightly more involved, because finding the smallest cluster points is known be NP hard. We implement coarser k-mmans clustering instead. Only when (supp(c) becomes close to the desired stopping size d', we switch to a greedy strategy, since the diameters of clusters likely be large when supp(c)] is small. Concretely, in k-means round, we divide into o< [supp(c)]/ Nm,, clusters. Then we apply Algorithm 2 to each cluster containing more than Nm, objects in parallel. In greedy round, we find the approximately smallest cluster of Nm, + points, which is implemented using the k-nearest neighbor algorithm provided by the faiss package (Douze al. 2024).
For the above k-means/greedyy hybrid strategy, we present the runtime benchmark in Fig. 6 The calculation conducted on a personal computer with Apple M4 Pro CPU. The runtime is observed to be roughly proportional to d. This is because the number of iterations over moment-matching reduction of support proportional
Finally, we remind the reader that our error bound Theorems 4 and are proved for the greedy strategy, where each round one finds the smallest cluster N Nm. 1 objects and reduce one object. For the above-mentioned hybrid clustering strategy, there is no theoretical guarantee as strong as Theorem for the error, but all numerical simulation turns out to meet our expectation.
Algorithm 2: Reducing support while matching moments
Input Moment matching order l
Input : N weighted parameters {(c,, wy w,)) }) where Nm, (m+
Output: Adjusted weights {ez} where suup((c) Nm,k
function ((w) vect(1, 1, w, 02 ...., WORTT / dim ((w) -m,kk
while (sup((e) > Nm,k do
Let supp(c) =
A = (o(w)) ((w))) (W") )):
Find nonzero R supp(e) such that Av 0; Ensure that at least one U, 0; 1= mo C/
Cj Cj luz.
end
23

---

Published as a conference paper at ICLR 2026
E DETAILS ON NUMERICAL EXPERIMENTS
We studied two main numerical tasks in Figs. 3 and 5 For all these experiments, the loss function
in training is the mean squared error (MSE) loss. The test loss shown in figures is the MSE loss evaluated on a randomly sampled dataset of the form (x), 22, f f(2), where f(x1, T2) is the
ground truth function. For Figs. 3 and 4. the test dataset size is 10 and for Fig. 5 is 2 x 10 All unspecified training hyperparameters follow PyTorch defaults. In particular, for AdamW, they are 31 0.9, B2 0.999, (weight decay) x= 0.01, and 10-
Fig. 3 and 5 a) concerns compressing the training dataset. The task is function fitting in a teacher- student setup, described in Sec. 4.2 When the training dataset is weighted, the data loader is im- plemented as follows: We draw i.i.d. samples from {wy))a{(s using (Cgbse[ar as the unnormalized probability distribution, to form a mini-batch.
Fig. 4 and (Jbb concerns compressing the width of a two-layer neural network. The task is fitting an oscillating bivariate function known cylindrical harmonic, described in the caption of Fig. The training dataset size for Fig. 4 is 109, and for Fig. 5 is 2 10a.
In Fig. [J we show the test MSE loss scaling with respect to training dataset size (a) and neural
network width (b). For both (a) and (b), the update rule is AdamW. The learning rate is initially 0.001, and is modulated by a cosine annealing learning rate scheduler, reaching 0 at the final epoch. Each data point is obtained by averaging 10 random instances of the train and test dataset and the neural network initialization, and the error bars indicate the standard deviation. For (a), we train each instance for 2048 epochs, each epoch containing one mini-batch of size 512, so that there is a constant compute budget for the original and the compressed datasets. For (b), we train each instance for 2000 epochs, each epoch enumerates over the train dataset. The batch size is 128.
F PERMUTATION SYMMETRY IN ATTENTION MODULES
In principle, the compression theory developed in this work can applied to attention mechanisms in two distinct ways. We briefly alluded to these ideas in Section 2; here, we provide a self-contained and more detailed discussion. The two applications concern (1) the compression of the query and key weight matrices, and (2) the compression of attention heads.
Compression of query and key matrices. The first application serves as straightforward verifi- cation of the theory. Consider the query and key matrices WqQ and Wx. The attention logits depend only on their product, which can be written as
a= <(WWWk)
(91)
with
d WoWk Σ Eno (wkk", F1
(92)
where w² denotes the i-th row of WQ and wxx the i-th column of W k. Since the index is a dummy summation index, its ordering is immaterial. This reveals an explicit permutation symmetry among the pairs {(wb) wxx) )
Because the output depends only on the sum of these outer products, the symmetry implies that the collection of these row-column pairs can be compressed. Moreover, if the left dimension of We is m. then WoWk has rank at most m, and the effective number of degrees of freedom is independent of d. Consequently, one can achieve not merely a polylog(d) compression but, in fact, constant-size representation. This serves useful sanity check for the consistency of our general theory.
A more interesting direction arises when the key-query interaction becomes nonlinear. For instance, one may consider replacing the bilinear form with
Σ "wkss
(93)
where is nonlinear function and X denotes the input data. In this setting, the permutation symmetry persists, and our theory guarantees that an polylog d) size compressed representation of this nonlinear attention layer is achievable in principle.
24

---

Published as a conference paper at ICLR 2026
3x10"
Original
2x10
Compressed
Trann cas
6x
3x
2x10-1
Test loss
6x10-
20
90
40
Epoch
Figure 7: Dynamical LTH extended transformers. The training dynamics of a large, dheads 4000-head attention model shows good agreement with its compressed multi-head attention model with dheadds 800 heads. See description of the task in Appendix
Compression of attention heads. The second application concerns the compression of entire at- tention heads, which is intrinsically more meaningful. Consider an attention layer with heads, and
let
A. = (w,,
(94)
denote the output of the ith head, where wi denotes its trainable parameter (including the query/key/value weight matrices Wo/K/V,; in the ith head) and B the head-level transformation. The standard output (denoted by y. of the attention layer is
y y=U
(95)
where U e Rexdh is the output projection matrix, z is the dimension of the final output, and h is the dimension of each head output. Partitioning U into blocks Uj e R this expression becomes
Σ U,B(w,,))
(96)
This summation structure again exposes permutation symmetry: the parameters
8, (U,, w:)
(97)
enter the model only through their over and their ordering is irrelevant. By the general theory, any such collection of d symmetric objects admits a compressed representation of size ((poyylogdd). Hence, the entire of attention heads can be compressed to polylog(d) effec- tive parameters while preserving the functional form of the output.
With the permutation symmetry among heads, it is easy formulate similar dynamical LTH for multi-head attention. Figure is a numerical demonstration of LTH in transformers. Here, the task is in-context learning on random piecewise-linear functions. We consider sealar in-context regression task in which each episode defines a random continuous piecewise-linear function f [0, R. For given episode, we first draw initial value fo (0, and segment slopes s, (0 for j O..... K 1, with K 16, Jo 0.5 and og 1.0. The interval [0, 1] is partitioned into K equal sub-intervals of length 1/K, and f is defined by enforcing continuity and setting the slope on segment j to 8j- For each episode we sample Tlxx = context inputs x; ~ [n, 1] with noisy observations yı (xx) + Es. where E; (O,, moise) with aoiss 0.3, together with an additional query point r. Unif (0, and a clean target y, = f(x)). The episode is presented to the model as a scalar sequence of tokens [I1. , , which is processed by single-layer causal multi-head attention module with dheads 4000 heads and head dimension dhead = 2. The model outputs a scalar prediction g. from the final token position. We compare three variants that share the same initialization: (i) the full model with all
[R2ee (token dimension din = 1),
4000 heads, (ii) a compressed model obtained by reducing the number heads to dheads = 800 via compression of order k (the effective dimension of each symmetric object is 8), and (iii)
25

---

Published as a conference paper at ICLR 2026
(8)
(0)
1120lgg
mm 1200ag'
10
(19) x5)]
10-11
(55) A())
10Th
10-19
10-11
10
10a
10
Figure 8: Error scaling of compressing general symmetric function using the moment-matching method. Here, various different values of k (the order moment matching) are attempted, from small to large, until the smallest eπrоr is found. Each data point is an average over 5 random in- stances, plotting the average with error bar standing for one standard deviation.
naive head- pruned model where 800 heads are selected uniformly random and the remaining heads are discarded. All three models are trained with Adam (learning rate 10 batch size 256) on the same sequence of mini-batches, using 5 gradient steps per epoch for 50 epochs. At epoch (before training) and after each epoch we report the MSE loss, for both training-like and test-like evaluations.
G NUMERICAL COMPRESSION TO polylog(d)
In this section, we numerically demonstrate the possibility the optimal rate, that is, compressing d objects into (log"" T d) objects. As we argued in Theorem 7 and Appendix [ compressing to this rate is computationally heavy for the moment-matching algorithm, so we only show it in low dimensions, i.e., m 1 or 2.
The error scaling is shown Fig. g The function we study is
1
f( fwi wa) = d 1-1 10
Σ Σ
(98)
A+
(w),
A 2.05. In Fig. a), plot the error of compressing 1d random objects into 120 log d]: in Fig. B(b), we plot the error of compressing d 2d objects into [20 log" d]. All unspecified setting of this numerical experiment identical with that of Fig. Despite pruning bigger fraction of the objects when d increases,
For (Fig. ((a)),
A = 1.05; for 2 (Fig. (b))
that the error is not increasing with d, but rather overall vanishing with d. Thus, this shows that is possible to compress d to Olog"" d)) objects losslessly. However, the numerical error shows visible oscillation, possibly due to the volatile moment- matching order hopt and finite-size (d) effect.
H USE OF LARGE LANGUAGE MODELS
ChatGPT is used in revising the language of the main text. All ideas, theorems and derivations are formulated by the authors.
ChatGPT and OpenAI Codex are used in partially completing the code for numerical experiments. However, all the main algorithms are designed and inspected by the authors.
26


Reviews:
[{"review_id": "vvIZ8RIzRX", "reviewer": "Reviewer_YxjE", "summary": "This work addresses dataset and neural network compression from a moment-matching perspective. Under certain assumptions, this approach establishes novel compression rates and power laws for these tasks. It also enables the boosting of neural power laws, which describe performance versus dataset size dynamics. A number of low-dimensional experiments are conducted to support the claims.", "questions": "1. Can you, please, provide additional experiments (e.g., for high dataset dimensionality or low sampling sizes) proving that your method avoids overfitting?\n2. I kindly ask to address my concerns in Weakness 1. In particular, I am interested in the numerical verification of the bounds provided.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The work is mathematically sound and easy to follow. The text is clear, supported by a decent and concise background overview. The authors provide both rigorous derivations and intuitive explanations for their theoretical results, and the experiments support their claims across a number of settings.", "weaknesses": "My main criticism revolves around the **curse of dimensionality**, which the authors underaddress several times throughout the paper.\n\n1. Both (9) and (10) have dimensionality-dependent exponents, which explode when $m \\to \\infty$ given that other constants are fixed. This is later combated by selecting $k > (1 = \\sigma^{-1}) m - 1$, which, in turn, explodes $\\binom{m+k}{k}$. Through some trickery in Theorem 7 (unfortunately, due to time constraints, I was not able to fully verify the math), the authors miraculously balance these issues by attaining a poly-log compression rate.\n\n    That said, one might expect that substituting $d'$ from (45) into (44) should yield errors which are (asymptotically) under some fixed $\\omega$. However, when done numerically for $m=10$, $\\rho=0.1$, $\\omega=0.1$, and any multiplicative constant in (45), I always get an exploding upper bound on the compression error. Reasonable variations of $\\rho$ and $\\omega$ do not alleviate the issue, which only worsens as $m$ grows.\n\n2. Since $k$ in Theorem 7 grows with increasing $d$, $f$ is required to be increasingly smooth. While most contemporary NNs are $\\infty$-smooth almost everywhere, their numerical smoothness degrades with increasing dimensionality or a decreasing learning rate [1]. In practice, this will take a toll on the derived bounds in terms of asymptotic constants or other parameters (e.g., $\\rho$ in (44)). This problem remains unaddressed in the main text.\n\n3. The experimental setups are toy, with the dimensionality being $4-12$ orders of magnitude lower than in real-world tasks. In my opinion, this might lead to the following problems:\n    - While showing decent performance in low-dimensional regimes, the proposed compression method might entail overfitting in high-dimensional setups. Stochastic gradient descent (SGD) is known to apply implicit regularization during training [2], thus selecting less overfitting solutions. Your method, however, might \"overcompress\" a NN/dataset: among all solutions, a non-generalizable one is selected (train error or even dynamics are the same, but test error is not).\n    - It is known that some problems in ML have exponential (in dimensionality) sample complexity (e.g., density estimation). Your result, however, suggests that these problems are also log-exponential in dimensionality (Theorem 7 applied to dataset compression) given the train error is preserved. The only logical conclusion I can arrive at is that such compression almost always entails overfitting when considering complex problems.\n\n4. While the authors briefly mention the manifold hypothesis in Section 7, it is not clear how one can use it to improve the method. Moment matching is agnostic to manifolds: i.e., it generally cannot capture such intricate structures. Therefore, another manifold learning strategy must be employed beforehand to decrease the dimensionality. Such a strategy typically requires the full dataset, as manifold learning is usually of exponential sample complexity.\n\n[1] Cohen et al. \"Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability\". Proc. of ICLR 2021.\n\n[2] Smith et al. \"On the Origin of Implicit Regularization in Stochastic Gradient Descent\". Proc. of ICLR 2021.\n\n**Minor issues:**\n\n1. Broken reference in line 190: \"Appendix ??\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iCi3cG9IVu", "reviewer": "Reviewer_1dtD", "summary": "The paper proves a universal compression theorem, showing that almost any symmetric function of $d$ elements can be compressed to a function with $O({\\rm polylog}$ (d)) elements losslessly. The theory leads to two key applications. First is the dynamical lottery ticket hypothesis, proving that large networks can be compressed to polylogarithmic width while preserving their training dynamics. Second is dataset compression, demonstrating that neural scaling laws can be theoretically improved from power-law to stretched-exponential decay.", "questions": "- The model assumes neuron permutation symmetry. Does the assumption is applicable to complex modules in neural networks, such as Transformer block?\n- In experiments such as Figure 3 or 4, how much real computation time does the proposed compression take?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The paper delivers a rigorous theoretical result that proves the dynamical lottery ticket hypothesis by showing that large networks can be compressed while preserving their original training dynamics.\n- Provides a generalized compression theory with broad applicability across diverse domains (e.g., dataset and model compression), demonstrating strong theoretical versatility and significant potential for cross-domain impact.\n- Establishes clear practical advantages, such as improved scaling laws and model compression, that are well grounded in the proposed theoretical framework.", "weaknesses": "- The paper lacks a thorough discussion on the applicability of the proposed theory to complex neural architectures such as Transformer blocks, which integrate linear projections, attention mechanisms, and normalization layers.\n- There seems to be a missing reference link to the Appendix at line 190 on page 4 (“Appendix ??”).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BvtKM40N8v", "reviewer": "Reviewer_ui4S", "summary": "The paper introduces the universal compression theorem as a step towards the dynamical lottery ticket hypothesis (LTH), which claims that in a dense network there exists a subnetwork, which when trained in isolation exhibits the same training dynamics as the original one. The theorem states (informally) that a permutation-invariant function of $d$ variables each of dimensionality $m$ can be asymptotically compressed to a function of $O(\\text{polylog } d)$ variables. The authors argue that, because many model / dataset objects are symmetric in parameters / datapoints, these results imply polylog-rate network and dataset compression under the assumptions of the theorem.  Another implication of polylog compression is the scaling law $L \\approx L_0 + C d ^{-\\alpha}$ changing from power law form to stretched-exponential form  $L \\approx L_0 + \\exp (- \\alpha’  \\sqrt[m]{d})$, both for model and dataset size.", "questions": "1. Can you show an example with the scaling laws of a form $L \\approx L_0 + c \\text{exp} (- \\alpha’ \\sqrt[m]{d})$ to illustrate the stretched-exponential regime?\n2. In numerical experiments in Section 6 the exponent should have improved by a factor of 2: $C d^{-\\alpha} = C (\\frac{d’}{16})^{-2 \\alpha} =C’ (d’)^{-2\\alpha} $. The reported values are close but lower, 1.271 vs $2\\alpha = 1.366$ and 0.608 vs $2 \\alpha=0.616$. Why does this difference appear? And why is it larger for dataset compression? \n3. Many elements of modern neural networks do not fall under the smoothness assumptions, like ReLU, top-k selections, sparse \\ quantized representations. How do you imagine expanding your work around those limitations and how would compression rates be affected?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper provides theoretical grantees on asymptotic polylogarithmic compression for symmetrical functions. The authors provide Algorithm 1 for compression of symmetric functions using moment-matching and validate it numerically.\n2. An important feature is the universality of the result: the implications of the theorem include both neural networks and datasets.\n3. A major practical consequence of the work is the potential speed up guarantees on the power-law scaling laws, which are known to \"be slow\", i.e. have small power exponentials.\n4. Although the main result is theoretical, the authors back each claim with numerical experiments: they show on a synthetic function that compression error drops with in agreement with the theoretical bound (Fig. 2); that training dynamics on a compressed dataset follows training on the full dataset (Fig. 3); training performances of full and compressed models are identical to support dynamical LTH (Fig. 4); and compressing a network or dataset leads to a larger scaling law exponent (Fig. 5). These comprehensive validations neatly complement the theoretical backbone of the paper.", "weaknesses": "1. Further empirical evaluation would strengthen this work, as the authors note.\n2. The proposed moment-matching algorithm scales poorly with moment order $k$ and dimension $m$ (via $\\binom{m+k}{k}$), which limits immediate practical effects despite the asymptotic guarantees.\n3. The theoretical claim of polylogarithmic compression yielding a stretched-exponential scaling $\\text{exp} (- \\sqrt[m]{d})$ is not supported with evidence. The numerical experiments in Section 6 demonstrate how the scaling laws can be improved only for quadratic compression.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oaCo1YCmRM", "reviewer": "Reviewer_LiWj", "summary": "The paper studies how neural networks and datasets can be compressed by exploiting permutation symmetries. The authors show that symmetric functions can be represented using fewer variables, which implies that both the model and the data can be reduced to polylogarithmic size without significantly changing the loss. This leads to what the authors call a dynamical lottery ticket hypothesis and stronger scaling laws.", "questions": "- Could you provide a concrete description of the compression algorithm? How are the compressed parameters and datasets obtained from the original ones?\n- How does your method compare, both in compression ratio and performance, with Iterative Magnitude Pruning or other sparse training techniques?\n- Can you explicitly state the trade-off between compression and approximation error, and how it compares with previous results (e.g. to those for the Strong LTH such as Pensia et al., 2020)?\n- What exactly does the function $f$ represent in Theorem 5? You didn't define it. Can you clarify the notation?\n- Can you argue that the bound $|f' - f| = \\omega(d)$ is not vacuous?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper presents an interesting idea: using permutation symmetry to achieve strong compression of both networks and datasets.\nThe theoretical argument (that symmetric functions can be represented with fewer variables), is promising. The results aim to connect model compression, scaling laws, and the lottery ticket hypothesis in a unified framework.", "weaknesses": "The paper proposes a theoretical link between symmetry, compression, and scaling laws. However, the lack of clear algorithmic formulation and the absence of fair experimental baselines limit its current practical relevance.\n\nThe main limitation of the paper is the lack of rigor and clarity. The compression process is described only at a high level. It is not clear how one would actually construct the compressed network or dataset in practice. The paper does not include pseudocode or complexity estimates, making it hard to evaluate the tractability of the proposed methods. \n\nThe experimental comparison is incomplete. The proposed compressed network is compared with both the original network and a random sparse network. However, it is already known that random sparse networks perform poorly, while sparse networks obtained with *Iterative Magnitude Pruning* (IMP, Frankle & Carbin 2019) can match the performance of dense ones. A fair comparison should therefore include IMP or other modern sparse training methods.\n\nThe compression-error trade-off is not clearly quantified. The claim that a network with (d) parameters can be reduced to polylogarithmic size should be expressed as a function of the error, and possibly compared to existing theoretical bounds.\nFinally, some parts of the theoretical presentation are unclear. The meaning of the function $f$ in Theorem 5 is not explained, and the notation $|f' - f| = \\omega(d)$ is confusing, since $ \\omega(d)$ can mean any function that grows faster than $d$, but such a bound would be vacuous.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)