TL;DR
Dataset distillation compresses large datasets into tiny synthetic ones, but combining these "mini-datasets" from different sources leads to a surprising composition gap. This paper proves that even perfectly distilled individual sets fail to represent their collective whole because the math of compression doesn't play nice with the math of mixing data.
What Problem Does This Paper Address?
Imagine several hospitals each distill their private patient data into a few representative images to share with a central researcher. The researcher then combines these synthetic sets to train a global model. Intuitively, we expect the union of these distilled sets to behave like the union of the original datasets.
However, this paper reveals a fundamental flaw: compression and mixing do not commute. As shown in Figure 1, distilling each source separately and then mixing them (the "independent" path) leads to a different result than mixing the real data first and then distilling the union (the "joint" path). This "composition gap" means that even if every hospital does a perfect job distilling their own data, the combined result might still be a poor proxy for the total real-world data.
Methods
The authors tackle this using a mix of rigorous theory and empirical network testing:
- Quadratic Analysis: They start with quadratic loss functions, where they can derive exact formulas. They prove a Structural Composition Law (Theorem 4.2), showing that the error depends on the variance of the source Hessians (the "curvature" of the data).
- Local Nonlinearity: For complex neural networks, they use a "frozen quadratic" proxy at the start of training. This allows them to predict local training behavior using Hessian-vector products without needing to compute full, massive Hessian matrices.
- Error Decomposition: They break down the total observed error into a "structural" term (the inherent math gap) and a "source residual" (how well the individual sets were distilled in the first place).
Datasets
The researchers validated their findings on standard computer vision benchmarks:
- CIFAR-10: Used for the main grid of experiments, including different levels of data heterogeneity (IID vs. label skew).
- SVHN: Used to replicate findings on a different domain (digit recognition).
- CIFAR-100: Used to test the scalability of the observations to more classes.
Key Insights and Ideas
- Curvature is Key: The gap isn't just about the data points themselves, but their "shape" in the loss landscape. If two datasets have very different curvature ellipses (as shown in Figure 2), their separately distilled versions will point the model in the wrong direction when combined.
- The "Jensen Gap" for Data: The failure is essentially a matrix-version of Jensen's inequality. Because the map from real data to a distilled set is nonlinear, the "average of the functions" is not the "function of the average."
- Label Skew Exacerbates the Gap: When data is split by class (e.g., one hospital has only dogs, another only cats), the Hessians differ wildly, making the composition gap much larger than in a random (IID) split.
- Fidelity $\neq$ Accuracy: A synthetic set can be "faithful" (reproducing the exact training endpoint of its source) but still result in poor downstream accuracy when mixed. Training fidelity and final model performance are distinct requirements.
Key Results
- Accuracy Gains from Joint Distillation: Distilling the union of data directly consistently yields better models. On CIFAR-10, joint distillation improved accuracy by 5.3 to 5.9 percentage points over simply unioning independent distillates.
- Predictive Power: Their theoretical quadratic prediction captured the local endpoint discrepancy on real networks with high precision (cosine similarity of 1.000 at small step sizes).
- The Skew Effect: As label skew increases, the "excess endpoint error" grows significantly. In Figure 4, you can see how the error for the unioned set (red) rises sharply compared to the joint set (blue) as the data becomes less IID.
Limitations and Future Work
- Optimizer Scope: The exact theoretical results currently apply to fixed-step gradient descent. Extending this to adaptive optimizers like Adam, where the step depends on the entire history, remains an open challenge.
- Long Horizons: The "local" analysis works best for short training trajectories. Over long training runs, the model moves through different curvature regimes, potentially complicating the gap.
- Scaling Up: While tested on CIFAR-100, the authors note that exploring this dissociation at the scale of ImageNet is a vital next step.
- Mitigation: The paper identifies the problem but doesn't offer a "magic bullet" fix for independent distillates. Future work could involve "composition-aware" distillation objectives that penalize this gap during the initial compression phase.
Summary updated