Algorithmic Guarantees for Distilling Supervised and Offline RL Datasets

• URL: http://arxiv.org/abs/2512.00536v1
• Date: Sat, 29 Nov 2025 16:04:38 GMT
• Title: Algorithmic Guarantees for Distilling Supervised and Offline RL Datasets
• Authors: Aaryan Gupta, Rishi Saket, Aravindan Raghuveer,
• Abstract summary: We develop and analyze an efficient dataset distillation algorithm for supervised learning.<n>We prove that our algorithm needs only $tildeO(d2)$ sampled regressors to derive a synthetic dataset.<n>We extend our algorithm to offline RL dataset distillation by matching the Bellman loss.
• Score: 16.403657943391188
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a training dataset, the goal of dataset distillation is to derive a synthetic dataset such that models trained on the latter perform as well as those trained on the training dataset. In this work, we develop and analyze an efficient dataset distillation algorithm for supervised learning, specifically regression in $\mathbb{R}^d$, based on matching the losses on the training and synthetic datasets with respect to a fixed set of randomly sampled regressors without any model training. Our first key contribution is a novel performance guarantee proving that our algorithm needs only $\tilde{O}(d^2)$ sampled regressors to derive a synthetic dataset on which the MSE loss of any bounded linear model is nearly the same as its MSE loss on the given training data. In particular, the model optimized on the synthetic data has close to minimum loss on the training data, thus performing nearly as well as the model optimized on the latter. Complementing this, we also prove a matching lower bound of $Ω(d^2)$ for the number of sampled regressors showing the tightness of our analysis. Our second contribution is to extend our algorithm to offline RL dataset distillation by matching the Bellman loss, unlike previous works which used a behavioral cloning objective. This is the first such method which leverages both, the rewards and the next state information, available in offline RL datasets, without any policy model optimization. Our algorithm generates a synthetic dataset whose Bellman loss with respect to any linear action-value predictor is close to the latter's Bellman loss on the offline RL training dataset. Therefore, a policy associated with an action-value predictor optimized on the synthetic dataset performs nearly as well as that derived from the one optimized on the training data. We conduct experiments to validate our theoretical guarantees and observe performance gains.

Related papers

• Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing [58.52119063742121]
  Retraining a model using its own predictions together with the original, potentially noisy labels is a well-known strategy for improving the model performance.<n>This paper addresses the question of how to optimally combine the model's predictions and the provided labels.<n>Our main contribution is the derivation of the Bayes optimal aggregator function to combine the current model's predictions and the given labels.
  arXiv  Detail & Related papers  (2025-05-21T07:16:44Z)
• Less is More: Adaptive Coverage for Synthetic Training Data [20.136698279893857]
  This study introduces a novel sampling algorithm, based on the maximum coverage problem, to select a representative subset from a synthetically generated dataset.<n>Our results demonstrate that training a classifier on this contextually sampled subset achieves superior performance compared to training on the entire dataset.
  arXiv  Detail & Related papers  (2025-04-20T06:45:16Z)
• DUPRE: Data Utility Prediction for Efficient Data Valuation [49.60564885180563]
  Cooperative game theory-based data valuation, such as Data Shapley, requires evaluating the data utility and retraining the ML model for multiple data subsets.<n>Our framework, textttDUPRE, takes an alternative yet complementary approach that reduces the cost per subset evaluation by predicting data utilities instead of evaluating them by model retraining.<n>Specifically, given the evaluated data utilities of some data subsets, textttDUPRE fits a emphGaussian process (GP) regression model to predict the utility of every other data subset.
  arXiv  Detail & Related papers  (2025-02-22T08:53:39Z)
• Provably Efficient Online RLHF with One-Pass Reward Modeling [70.82499103200402]
  Reinforcement Learning from Human Feedback has shown remarkable success in aligning Large Language Models with human preferences.<n>Online RLHF has emerged as a promising direction, enabling iterative data collection and refinement.<n>We propose a one-pass reward modeling method that eliminates the need to store historical data and achieves constant-time updates per iteration.
  arXiv  Detail & Related papers  (2025-02-11T02:36:01Z)
• RL on Incorrect Synthetic Data Scales the Efficiency of LLM Math Reasoning by Eight-Fold [41.28168368547099]
  Training on model-generated synthetic data is a promising approach for finetuning LLMs, but it remains unclear when it helps or hurts. We show that training on per-step negatives can help to unlearn spurious correlations in the positive data.
  arXiv  Detail & Related papers  (2024-06-20T17:45:54Z)
• CondTSF: One-line Plugin of Dataset Condensation for Time Series Forecasting [22.473436770730657]
  The objective of dataset condensation is to ensure that the model trained with the synthetic dataset can perform comparably to the model trained with full datasets. In classification, the synthetic data is considered well-distilled if the model trained with the full dataset and the model trained with the synthetic dataset yield identical labels for the same input. In TS-forecasting, the effectiveness of synthetic data distillation is determined by the distance between predictions of the two models.
  arXiv  Detail & Related papers  (2024-06-04T09:18:20Z)
• Group Distributionally Robust Dataset Distillation with Risk Minimization [17.05513836324578]
  We introduce an algorithm that combines clustering with the minimization of a risk measure on the loss to conduct DD.<n>We provide a theoretical rationale for our approach and demonstrate its effective generalization and robustness across subgroups.
  arXiv  Detail & Related papers  (2024-02-07T09:03:04Z)
• Self-Supervised Dataset Distillation for Transfer Learning [77.4714995131992]
  We propose a novel problem of distilling an unlabeled dataset into a set of small synthetic samples for efficient self-supervised learning (SSL) We first prove that a gradient of synthetic samples with respect to a SSL objective in naive bilevel optimization is textitbiased due to randomness originating from data augmentations or masking. We empirically validate the effectiveness of our method on various applications involving transfer learning.
  arXiv  Detail & Related papers  (2023-10-10T10:48:52Z)
• Dataset Distillation by Matching Training Trajectories [75.9031209877651]
  We propose a new formulation that optimize our distilled data to guide networks to a similar state as those trained on real data. Given a network, we train it for several iterations on our distilled data and optimize the distilled data with respect to the distance between the synthetically trained parameters and the parameters trained on real data. Our method handily outperforms existing methods and also allows us to distill higher-resolution visual data.
  arXiv  Detail & Related papers  (2022-03-22T17:58:59Z)
• BiFair: Training Fair Models with Bilevel Optimization [8.2509884277533]
  We develop a new training algorithm, named BiFair, which jointly minimizes for a utility, and a fairness loss of interest. Our algorithm consistently performs better, i.e., we reach to better values of a given fairness metric under same, or higher accuracy.
  arXiv  Detail & Related papers  (2021-06-03T22:36:17Z)
• AutoSimulate: (Quickly) Learning Synthetic Data Generation [70.82315853981838]
  We propose an efficient alternative for optimal synthetic data generation based on a novel differentiable approximation of the objective. We demonstrate that the proposed method finds the optimal data distribution faster (up to $50times$), with significantly reduced training data generation (up to $30times$) and better accuracy ($+8.7%$) on real-world test datasets than previous methods.
  arXiv  Detail & Related papers  (2020-08-16T11:36:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.