[2510.00504] A universal compression theory for lottery ticket hypothesis and neural scaling laws

Statistics > Machine Learning arXiv:2510.00504 (stat) [Submitted on 1 Oct 2025 (v1), last revised 2 Mar 2026 (this version, v2)] Title: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 View a PDF of the paper titled A universal compression theory for lottery ticket hypothesis and neural scaling laws, by Hong-Yi Wang and 4 other authors View PDF 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...