A universal compression theory: Lottery ticket hypothesis and superpolynomial scaling laws

在训练大规模模型时，其性能通常遵循一个缓慢的幂律规律，随参数数量和数据集规模的增长而提升。一个根本性的理论与实践问题是：是否可以用显著更小的模型和少得多的数据实现相当的性能？在本研究中，我们给出了肯定且具有构造性的回答。我们证明，对于 $d$ 个对象的任意置换不变函数，可以渐近地压缩为仅作用于 $\operatorname{polylog} d$ 个对象的函数，并且误差趋于零。该定理包含两个关键推论：（Ia）一个大型神经网络可被压缩至多对数级别的宽度，同时保持其学习动态不变；（Ib）一个大型数据集可被压缩至多对数级别的规模，同时不改变相应模型的损失景观。（Ia）直接证明了“动态彩票假设”——即任何普通网络都可以被大幅压缩，而其学习过程和最终结果均保持不变；（Ib）表明，形式为 $L\sim d^{-\alpha}$ 的神经缩放律可以被增强为任意快速的幂律衰减，最终甚至可达 $\exp(-\alpha' \sqrt[m]{d})$ 的指数级衰减速率。

论文试图解决大规模模型训练中对巨量参数和大数据集的依赖问题，验证是否可以用显著更小的模型和更少的数据实现相当的性能。这是一个重要且具有挑战性的问题，尤其是在追求高效、可扩展AI系统的背景下，尽管模型压缩和数据效率已有研究，但从理论层面证明可以指数级压缩模型与数据规模仍属新颖。

提出并证明了一个核心定理：任意关于d个对象的置换不变函数可以被渐近压缩为仅涉及polylog(d)个对象的函数，且误差趋近于零。由此导出两个关键推论：(Ia) 神经网络可以在保持学习动态不变的前提下压缩到polylogarithmic宽度；(Ib) 训练数据集可以压缩到polylogarithmic大小而不改变损失景观。这一思路首次从理论上支持了动态彩票假设，并揭示了神经缩放律可通过压缩被加速至超多项式衰减。

论文提供了严格的数学证明而非仅经验验证，增强了结论的普适性。其理论框架适用于所有置换不变函数，涵盖广泛模型结构。实验设计虽未详述，但理论结果暗示可在标准数据集（如ImageNet、语言模型语料）上进行压缩验证。若代码开源将极大促进应用。值得深入的方向包括：如何构造实际的压缩算法、在非置换不变任务中的推广、以及在分布式训练中的应用。

1. Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding 2. The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks 3. Scaling Laws for Neural Language Models 4. Chinchilla: Training Compute-Optimal Large Language Models 5. Data Permutation Equivariance in Neural Networks