TL;DR
This paper establishes the first unified theoretical foundation for dataset distillation by introducing a "configuration–dynamics–error" framework. It proves two fundamental laws: a scaling law ($\Delta \le \mathcal{O}(1/\sqrt{k}) + \epsilon_{\text{bound}}$) explaining why accuracy saturates as distilled dataset size $k$ grows, and a tight coverage law showing that $k$ must scale linearly with configuration diversity ($\mathcal{H}_{\text{cov}}$) to remain effective across different architectures, optimizers, and augmentations.
What Problem Does This Paper Address?
Dataset distillation (DD) compresses massive datasets into a small number of synthetic samples that can train models from scratch with minimal performance loss. Despite impressive empirical progress, two core questions remain unanswered:
- Fragmented Theory: The three dominant distillation paradigms—Gradient Matching (GM), Distribution Matching (DM), and Trajectory Matching (TM)—rely on disjoint heuristics and mathematical assumptions. There has been no unified theory explaining why all three work or how they relate.
- Brittle Transferability (The Utility Boundary): Distilled datasets are notoriously sensitive to setup changes. A synthetic dataset optimized for a simple ConvNet trained via SGD often degrades drastically when evaluated on modern architectures (e.g., ResNet) or different optimizers (e.g., Adam). Additionally, practitioners regularly hit a "saturation wall" where increasing images-per-class (IPC) ceases to improve performance.
Methods
The authors introduce the configuration–dynamics–error framework, formalizing training configurations, optimization dynamics, and generalization risk into an end-to-end analytical pipeline:
- Configuration Metric Space: A configuration $a \in \mathcal{A}$ encapsulates the model architecture, optimizer, hyperparameters, and data augmentations. The difference between two configurations is quantified by a distance metric $d_{\mathcal{A}}(a, a')$, defined by the maximum drift in their parameter update fields on real data. Configuration diversity is measured by the metric covering entropy $\mathcal{H}_{\text{cov}}(\mathcal{A}, r) = \log \mathcal{N}(\mathcal{A}, d_{\mathcal{A}}, r)$.
- Matching Discrepancy ($\Delta_a$): Captures how differently synthetic and real data drive parameter updates under configuration $a$.
- Surrogate Unification: The authors prove that DM (Wasserstein-1 or MMD), GM (anchor gradient matching), and TM (unrolled trajectory matching) are interchangeable surrogates in an outer–inner bi-level optimization loop that contract the exact same matching discrepancy $\Delta_a$, governed by $\mathcal{B}_{\text{TM}} = \mathcal{O}(\mathcal{B}_{\text{GM}})$ and $\mathcal{B}_{\text{GM}} = \mathcal{O}(\mathcal{B}_{\text{DM}})$.
- Theoretical Bounds: Under Polyak–Łojasiewicz (PL) contraction and Lipschitz regularity:
- Single-Configuration Scaling Law: $\Delta \le \mathcal{O}(1/\sqrt{k}) + \epsilon_{\text{bound}}$.
- Cross-Configuration Coverage Law: Average risk scales as $\mathcal{O}(\sqrt{\mathcal{H}_{\text{cov}}/k} + \mathcal{H}_{\text{cov}}/k)$, and worst-case risk scales as $\Theta(\sqrt{\mathcal{H}_{\text{cov}}/k})$, backed by a matching minimax lower bound.
Datasets
The theoretical predictions were validated across standard distillation benchmarks:
- MNIST
- CIFAR-10 and CIFAR-100
- ImageNette (a 10-class subset of ImageNet)
No new benchmarks were introduced; existing public datasets and official open-source baseline implementations were used.
Key Insights and Ideas
- Explaining IPC Saturation: The scaling law proves that generalization error cannot drop to zero; it hits an irreducible floor $\epsilon_{\text{bound}}$ determined by optimization residuals and intrinsic representation limits of $k$ prototypes. Once $k$ is moderately large, shrinking $\epsilon_{\text{bound}}$ (via better surrogates or training dynamics) is more impactful than blindly increasing sample budget $k$.
- The Cost of Portability: Distillation does not transfer "for free." To maintain target accuracy across a family of deployment configurations, the required distilled size must satisfy $k = \Omega(\mathcal{H}_{\text{cov}}(\mathcal{A}, r))$. Doubling the configuration diversity essentially doubles the required number of synthetic samples.
- Exchangeability of Distillation Paradigms: DM, GM, and TM are not distinct competing philosophies, but rather surrogate approximations of the same dynamical matching discrepancy with different trade-offs:
- GM achieves lower error within a fixed configuration but degrades quickly under configuration shifts.
- DM provides higher robustness to configuration shifts but exhibits higher sample variance (demands larger $k$).
- TM faithfully tracks optimization paths but suffers the greatest variance and sensitivity to unrolling instability.
Key Results
- Scaling Law Verification ($1/\sqrt{k}$ decay): Across MNIST, CIFAR-10/100, and ImageNette, regressing generalization error $\Delta$ against $1/\sqrt{k}$ produced linear fits with $R^2$ values frequently between $0.85$ and $0.99$ (e.g., DC, DSA, and DM on MNIST scored $R^2 = 0.90\text{--}0.99$; on CIFAR-10, $R^2 = 0.86\text{--}0.96$). The linear trend also extended to diffusion-based distillation (MGD$^3$ on ImageNette with $R^2 = 0.87\text{--}0.92$).
- Coverage Law Verification ($\Delta \propto \sqrt{\log M/k}$): Testing across subsets of $M$ configurations (spanning combinations of ConvNet, LeNet, ResNet-18, AlexNet, MLP, VGG11, SGD, Adam, and DSA augmentations) yielded linear correlations between empirical error and $\sqrt{\log M}/\sqrt{k}$ (e.g., on MNIST, $R^2 = 0.88\text{--}0.92$). Slopes quantitatively confirmed the sensitivity rankings predicted by theory ($\text{slope}_{\text{TM}} > \text{slope}_{\text{GM}} > \text{slope}_{\text{DM}}$).
Limitations and Future Work
- Optimization Assumptions: Theoretical guarantees rely on Polyak–Łojasiewicz (PL) contraction and Lipschitz-smooth update fields, which can fail under non-smooth activations, large-batch regimes, or non-convex/adversarial landscapes.
- Complexity Estimation: In experiments, covering entropy $\mathcal{H}_{\text{cov}}$ was approximated using $\log M$ (where $M$ is the number of candidate configurations). Developing efficient, principled geometric estimators for $d_{\mathcal{A}}$-clustering remains an open direction.
- Algorithmic vs. Semantic Shifts: The coverage law models diversity in algorithmic training parameters (architectures, optimizers, augmentations) but does not account for data distribution shifts (e.g., domain adaptation from CIFAR-10 to STL-10). Extending $d_{\mathcal{A}}$ to incorporate distribution distances is suggested for future work.
Summary updated