Utility Boundary of Dataset Distillation: Scaling and Configuration-Coverage Laws

Zhengquan Luo, zhiqiang xuSubmission to ICLR 2026 · Rejected

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:

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

Abstract

Dataset distillation (DD) aims to construct compact synthetic datasets that allow models to achieve comparable performance to full-data training while substantially reducing storage and computation. Despite rapid empirical progress, its theoretical foundations remain limited: existing methods (gradient, distribution, trajectory matching) are built on heterogeneous surrogate objectives and optimization assumptions, which makes it difficult to analyze their common principles or provide general guarantees. Moreover, it is still unclear under what conditions distilled data can retain the effectiveness of full datasets when the training configuration, such as optimizer, architecture, or augmentation, changes. To answer these questions, we propose a unified theoretical framework, termed configuration–dynamics–error analysis, which reformulates major DD approaches under a common generalization-error perspective and provides two main results: (i) a scaling law that provides a single-configuration upper bound, characterizing how the error decreases as the distilled sample size increases and explaining the commonly observed performance saturation effect; and (ii) a coverage law showing that the required distilled sample size scales linearly with configuration diversity, with provably matching upper and lower bounds. In addition, our unified analysis reveals that various matching methods are interchangeable surrogates, reducing the same generalization error, clarifying why they can all achieve dataset distillation and providing guidance on how surrogate choices affect sample efficiency and robustness. Experiments across diverse methods and configurations empirically confirm the derived laws, advancing a theoretical foundation for DD and enabling theory-driven design of compact, configuration-robust dataset distillation.
BibTeX
@misc{luo2025utility,
  author = {Zhengquan Luo and zhiqiang xu},
  title = {{Utility Boundary of Dataset Distillation: Scaling and Configuration-Coverage Laws}},
  year = {2025},
  eprint = {2512.05817},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.05817},
}
Figure