Utility Boundary of Dataset Distillation: Scaling and Coverage Laws

Abstract

Dataset distillation (DD) aims to replace a full training set with a tiny synthetic one, yet current theories neither explain why heterogeneous matching objectives (gradient, distribution, trajectory) work nor provide a quantitative boundary for robustness under configuration changes (optimizer, architecture, augmentation). We propose **configuration-dynamics-error (CDE) analysis** for a broad class of matching-based DD methods, a unified generalization framework that treats a training configuration as an update operator inducing optimization dynamics and measures distillation robustness by the test-risk gap between models trained on distilled versus full data. Within this framework, gradient, distribution, and trajectory matching reduce the same dynamics-induced risk gap, explaining why these heterogeneous objectives can all support dataset distillation. CDE yields two predictive laws: within a fixed configuration, the gap decays as $\mathcal{O}(k^{-1/2})$ with the distilled set size $k$ until a configuration-dependent floor, explaining IPC saturation and indicating when reducing the floor is more valuable than enlarging $k$. Across configurations, an order-tight coverage law formalizes the utility boundary: the required $k$ grows linearly with the configuration diversity captured by covering-number complexity. Experiments with representative DD methods and configuration changes exhibit predictive behavior consistent with both laws.