Algorithmic Guarantees for Distilling Supervised and Offline RL Datasets
Authors: Aaryan Gupta
Rishi Saket
Aravindan Raghuveer
Venue: ICLR 2026 Poster (2026)
Keywords: dataset distillation
supervised learning
offline RL
learning theory
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: Algorithms and performance guarantees for supervised and offline RL dataset distillation along with experimental validation.

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 approximately 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 $\Omega(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. We show similar guarantees: 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 extensive experiments to validate our theoretical guarantees and observe performance gains on real-world RL environments with offline training datasets and supervised regression datasets.

ALGORITHMIC GUARANTEES FOR DISTILLING SUPERVISED AND OFFLINE RL DATASETS
Aaryan Gupta
Rishi Saket
Google DeepMind India aa Syyanngppagggseee aeooolgoolll.oooo com
Google DeepMind India
r rishisa serrisaketttooogo com
Aravindan Raghuveer
Google DeepMind India eraghuverr@ooggee.com
ABSTRACT
Given training dataset, the goal of dataset distillation is to derive synthetic dataset such that models trained on the latter perform as well as those trained on the training dataset. In this work, develop and analyze an efficient dataset distillation algorithm for supervised learning, specifically regression in IR 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 (d?) sampled regressors to derive synthetic dataset on which the MSE loss of any bounded linear model is approximately 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 well the model optimized on the latter. Complementing this, we also prove a matching lower bound of l 2(d2) 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 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. We show similar guarantees: our algorithm generates syn- thetic dataset whose Bellman loss with respect any linear action-value predictor is close the latter's 's Bellman loss on the offline RL training dataset. Therefore, policy associated with an action-value predictor optimized on the synthetic dataset performs nearly well as that derived from the one optimized on the training data. We conduct extensive experiments to validate our theoretical guarantees and observe performance gains on real-world RL environments with offline training datasets and supervised regression datasets.
INTRODUCTION
Reinforcement learning (RL) which is increasingly used to train very large machine learning models has two training paradigms: online and offline. While in online RL a policy model trained while interacting with the environment, offline RI. trains a model on data points collected from multiple trajectories of interactions with the environment and external entities (e.g. g. humans, Al agents). In many applications online RL is either not possible, very expensive not scalable due the requirement key benefit of offline RL is its ability ingest large amounts of diverse training data (Fu et al.) 2021). and consequently, offline RL has become popular for training large models for tasks in for e.g. natural language processing, computer vision, robotics etc. (Levine et al. 2020).
of a dedicated agent interacting with the environment for the duration of model training.
However, the use large scale datasets presents challenges related to their storage, management well the computational expense incurred in their use for training multiple models with different

---

hyperparameters and architectures. One way mitigate this issue is to create smaller synthetic dataset derived from the training dataset i.., a distillation of the latter. Dataset distillation (DD) for
supervised learning has been extensively studied in previous works (e.g. (Wang et al. 2018 Sachdeval & McAuley 2023 Lei & Too 2024)) which have developed a variety of methods based on matching the loss gradients or feature-embedding between the training and synthetic datasets by optimizing the latter. This is done either with respect to networks being trained simultancously using bi-level optimization, or fixed collection of sampled networks. Distinct from sampling, coreset or random projection methods, DD techniques generate synthetic data via optimization with respect to networks which may also be trained in the process. These DD techniques have been shown to perform well on real-world supervised datasets in terms of the quality as well as the size of the generated syntheic dataset as the latter is explicitly optimized.
While some works (e.g. (Nguyen et al., 2021 Chen et al., 2024) have also provided theoretical performance guarantees, most DD techniques are heuristics albeit with empirically observed gains.
For offline RL, few recent works have proposed methods using behavioral cloning (BC) for distilling an offline training dataset comprising trajectories of (state, action)-pairs. In (Lei et al. 2024), the
authors propose optimizing the synthetic dataset using policy-based BC loss leveraging action-value weights learnt from offline RL. On the other hand, the method proposed by [ight et al. (2024) extends the matching loss gradients approach to offline RL. In particular, it optimizes a synthetie dataset to match the BC loss gradients on the offline and synthetic data, where the gradients are with respect to the parameters of sampled action predictor networks.
As can be seen, the state of research into offline RL dataset distillation, while nascent, is also unsatisfying. Firstly, the BC does not leverage the observed reward that is usually available in offline RL datasets, and typically only perform well when the training dataset is generated by expert policies. Secondly, there is a sparsity of theoretical performance guarantees for the DD techniques for offline RL as well as supervised learning DD. For linear regression, the work Chen et al. (2024) proves efficiency guarantees assuming however that a trained model is available, while the work of Nguyen ett al. (202T)- while not training model proves convergence only of the synthetic feature- vectors for given synthetic labels. For offline RL, the work Lf et al. (2024) provides analytical guarantees, while requiring trained policy model on the given training dataset. To the best of our knowledge, there are no provably efficient DD algorithms known without model training for either supervised learning or offline RL.
Our Contributions, In this work we make progress towards bridging the above gaps in our under- standing through the following contributions:
Dataset Distillation in supervised regression. We propose an algorithm minimizing the squared difference of MSE losses between the training and the synthetic datasets with respect to a fixed set of randomly sampled models. While our algorithm is along the line of previous DD approaches using loss, gradient loss or embedding matching techniques, our contribution is to prove that it admits efficiency and performance guarantees for linear regression. In particular, we prove that the optimization objective is convex and tractable, and in d-dimensions optimizing the synthetic dataset w.r.t. Ödd)) randomly sampled regressors suffices to guarantee that any bounded linear regressor has approximately the same MSE loss on the training and synthetic datasets. Therefore, the optimum linear regressor on the synthetic dataset is close that on the training dataset. This the first performance and efficiency guarantee for supervised DD without model training.
We also prove lower bound of (dd2) on the number of randomly sampled linear regressors obtain a good quality synthetic dataset. This result shows the tightness of our algorithmic guarantees.
Dataset Distillation in offline RL. We extend the above approach for dataset distillation in supervised regression to offline RL DD by matching the Bellman loss on the training and synthetic datasets w.r.t a collection of randomly sampled linear Q-value predictors over IRd, The performance guarantees are in similar vein as the supervised regression case, though more involved due to the max term in the Bellman Loss formulation.
Nevertheless, we obtain a performance guarantee showing that minimizing to small value the differ- ence of the Bellman Losses with respect to exp(O(dlop d)) randomly sampled Q-value predictors (without model training) generates a synthetic dataset whose Bellman Loss w.r.t. any linear bounded
I hides polylogarithmic factors
2

---

Q-value predictor is close approximation to that on the training dataset. Consequently, the Bellman Loss minimizer Q-value predictor on the synthetic dataset is close to optimal on the training dataset.
Offline RL with decomposable feature-maps. We consider natural setting where the state-action feature-map is the sum of individual feature-maps of the state and action. In this scenario, we prove that our method requires only (d²) sampled linear Q-value predictions, instead of the exponentially many required in the general case. Additionally, we show that the finding the synthetic dataset is tractable convex optimization when the state and action feature-maps are linear.
Empirical Evaluations. We conduct experiments supervised regression and offline RI datasets to validate our proposed algorithms, showing that our techniques obtain improved performance over standard baselines, both in terms of quality and size of the generated datasets. Notably, our experiments demonstrate the effectiveness of our algorithms using very few sampled models in both supervised regression and offline RL settings. Although the guarantees are proven for linear models, we show that our algorithms work well in practice with non-linear neural networks.
2 PREVIOUS RELATED WORK
Dataset Distillation. The work of Wang et al. (2018) introduced the problem of distilling a dataset into a representative (and smaller) synthetic dataset, in the setting of supervised learning. This and other works e.g. (Deng & Russakovsky (022) use a bi-level optimization formulation in which the model is optimized on the training dataset while the synthetic dataset is optimized on the trained model. A related set of methods rely matching various properties of the synthetic dataset with the training dataset. In particular, the work of Zhao et al. (2021): Zhao & Bilen (202)) matches the model's 's loss gradients on the training and synthetic datasets the model is alternately optimized over the training dataset. In a similar vein, the work of Wang et al.)
optimization over the latter, while
(2022) aligns the feature distribution of the two datasets in a dynamic bi-level optimization approach, while the works of Cazenavette et al. (2022); Cui et al. (2023) match the training trajectory of an initial model optimized on the training dataset with its training trajectory on the synthetic dataset, by optimizing on the latter. Unlike the mentioned works optimizing model along with the synthetic dataset, the work of Zhao & Bilen (2023) instead matched the cnature-distribution on the training and synthetic datasets with respect to tixed collection of randomly sampled networks. For linear ridge regression, the work of Nguyen et al. (202T) implicitly matched the regression losses by minimizing a surrogate objective, while proving convergence of synthetic feature-vectors given the synthetic labels. More recently, CCen et al. (2024) analytically gave an efficient synthetic dataset generation algorithm for linear ridge regression, requiring however access to the optimal regression model for the training dataset.
Closely related to DD for linear regression is matrix sketching which provides a principled way to reduce the dimensionality (or size) of training data. By applying randomized projections (e.g.. the Mainsssn-iiddsttrauuss transform (Johnson & Lindenstrauss 1984 Sarlós (006)) or leverage-score sampling (Drineas et al.) 2006;; Mahoney] 2011). one can construct a much smaller sketch of the original data while provably preserving the solution quality of least-squares regression.
However, these guarantees are largely limited to linear and convex models. In contrast, DD methods can be applied neural networks, albeit without comparable theoretical guarantees. Additionally, DD techniques optimize the synthetic dataset, and have been shown to to work well in practice on real data in terms of size compression and quality preservation.
Offline RL. A key advantage is that offline RL is adaptable to data generated by sub-optimal policies (Levine et al. 2020) Fu al.) [021). while also being scalable to large datasets (Lange et al.] 2012). On the other hand. the lack of online exploration can lead to less generalizable policies being trained due to distributional shifts. To address this, several techniques based on constraining the policy (Fujimoto & Gul 2021 Tarasov et al., (023) or regularization of Q-value predictors have been developed (Kumar et al. 2020 Kostrikov et al. 2022). A major practical consideration is the exponential growth in dataset sizes, along with which the associated challenges of storage, transfer and training on datasets as well as maintaining privacy controls have only multiplied. Dataset distillation has been proposed to tackle these problems, with existing works developing behavioral cloning methods for distilling an offline training dataset comprising trajectories of (state, action) pairs. While Lupu et al. (2024) propose behavior distillation for online RI., the work of Lei et al. 2024)
3

---

tackles the offline RL case by first training action-value value predictor and using action-value weighted BC to optimize the synthetic dataset. On the other hand, the method proposed by [iihht et al. (2024) extends the matching loss gradients approach to offline RL. In particular, it optimizes a synthetic dataset to match the behavioral cloning loss gradients on the offline and synthetic data, where the gradients are with respect the parameters of sampled action predictor networks.
3 PROBLEM DEFINITION
We will use B(t,r) = fx E IR || r) to denote the b2-ball in R' centered at 0 of radius r. Supervised Learning Dataset Distillation. We consider regression tasks over d-dimensional real- vectors and real-valued labels. For an n-point dataset 1) E (RR x RR), and predictor f: IR - R, the mean squared error (MSE) of f on D m DD f) == (1/m) Σ ((x.))D(V - f(x))² We assume that the training datapoints are norm bounded by and labels have magnitude at most b for some parameters B and b, and impose the same restriction on the synthetic dataset. Let Deam = {(x, y.) E Bid, B) x b be an n-sized training dataset, while we denote an m-sized synthetic dataset by Day coordinate to feature-vectors we can omit the constant offset and restrict ourselves to linear regressors of the form v as prediction for the label y. We impose ||v||2 I 1 as bound the norm, and let Fo denote the class of such regressors. We define the supervised regression dataset distillation problem as: for a parameter E, given Duup
{(z,. ūt) B(d, B) x [-b, b] 1 f=1 By appending 1-valued
rain compute Dsyn such that
etr miss
Dsup
f) = (Lmse (Dum syn
train: f) Lusse (Dsup syn f)) SE, for all f E Fo-
(1)
train
Offline RL Dataset Distillation. Consider a Markov Decision Process (MDP) given by (S, A, P, 7), where (i) S is the set of states, (ii) A is the set of actions, (iii) P is the transition prob- ability i... P(s') s,a) denotes the probability of transitioning to state s' from state s on action a, (iv) R is the reward function, where R(s, a) [0, Rmax] the reward obtained on action at state s. and (v) is the discount factor. A policy ı is a mapping from states to action, and the goal is to maximize
at each state its value function: Ug (s) = Ex, ? so = s] where Rg is the reward at step t under the policy starting from state 8. The action-value function is the expected sum of discounted reward starting from a state and a specific action i.e., 9- (s, E,, Ei 7 so s, s, = On the other hand, given an action value function predictor f A I. the corresponding greedy policy n' given by x' (s) a a) always yields at least much expected discounted reward starting from any state æ. In offline RL, a dataset Derl consists of collection of state, action, reward and next state tuples of the form (s, a, r, s'), with generated by some (non-optimal) policies. The goal is to learn policy from this dataset which maximizes the value function. We cast this problem as deriving a action-value predictor from Dorl and taking the greedy policy with respect it. Under reasonable assumptions the MDP and Dor the performance of action-value predictor f is measured by the Bellman loss (see Appendix G.I for details) given by:
(f(s.o)-T-> max f(s',a)) d'E
LBan( Dord f) (ssaa,ns') Dad
max
(2)
Feature Map and linear action-value predictors. We assume that S,A S B(do, Bo), and that Φ B(do, B0)² + Rd is given feature-map s.t. [|os(s, a)lla < B for any (8,a) in its domain, for some parameters Bo, do and B. An action-value predictor I given by f(x := =v (Tx( (ss,)) a), for (s, a) E B(do, 2. and restrict ourselves to the class of such predictors Qo satisfying [ S 1. Datasets. The training dataset is Dor = {(8,, at, Fi, $ C x A x [0, Rmax x S of state. action, reward and next state tuples. Since S A could either be discrete non-convex, for tractable optimization the synthetic dataset Dod is allowed to consist of tuples {(,; â, f, 8)) E
:=v
Bidg, Bo) x B(dg, Bo) x [0, Rmax] B(dg Bo). With this, LBa is can defined for Dorl and any f Qo as:
syn: f) = -E Del (1ts,0) - - max f(8', ",,dd) -
LBen ( (Dor
(3)
a'EA
4

---

Note that in the above, the maximization inside the loss is taken over the original set of actions, consistent with the definition of the Bellman loss. With the above setup, we define the offline RL dataset distillation problem as follows: For parameter e, given D compute D such that
en (Dmi Bell tain: D f) == (L (Diin f) LBou (D sy: f))² S
for all f E Qo-
(4)
4 OUR RESULTS
Supervised Learning Dataset Distillation. For convenience, we shall employ a homogeneous
formulation i.c., with 0 label, using the concatenation < Fd x R + Rd+ given by <(x, y)
(Z1...., Tdd y) where x = (Z1...., Za). Observe that r r' y) = v y = f(x)
where
r= (U1, (U1,.... Cd, -1), and f E Fo s.t. f(x) v'x. Further, if ||v||2 be the class regressors with target label 0 where each E F is given by 1((x, y) == r [(x, y)
then
||r||2 2. Let
where < ||r||2 < 2. One can thus extend the notion of the MSE loss Lmse to F. by letting Luse (D.h) = ())))) [h(x,, v) We also define G to be distribution over regressors where random g G is given by sampling r (0, 1/(d + 1))d+1 u.a.r. and letting g(x, y) = r [(x y). With this setup, we prove the following theorem.
Theorem 4.1. Let Duup the training dataset as described above. For any A > and 8 > 0, let 91.....3 9b be iid regressors sampled from for some k O (d2 log(d( + b))A) log(1/6)). Then, with probability 8 over the choice of , if there exists Dayp s.t.
Σ
Lon ( (Deup Dsup 93 S A'
(5)
then, for all h E F, L spu Dayp, h) I A, where A' Ak/O(d),, in particular this holds also for all f E Fu.
It can be seen that L (Duup urain Dagn g) is convex function over the points of Dayo (see Appendix G.2 for an explanation) and therefore the LHS of equation[]is is also convex and can be minimized efficiently. Based on this we provide the corresponding Algorithm
Algorithm 1: Supervised Regression Dataset Distillation
Input: k. m E Z Suup E (B(d, B) (-b, 1. Sample iid at random II..... from G.
2. Output
ang (B(
Dj=1 Ler
SD urain: - -y))
Lower Bound. Complementing the above algorithmic result, we prove the following matching (up to logarithmic factors) lower bound on the number of sampled regressors.
Theorem 4.2. For any positive integer d, there exists Duup of q (d + 1) points of the form
(x, u) E R2 where x E IR y E R, each of Euclidean norm ||/|2 < 2 such that for any choice
of homogeneous (i.e., target label 0) regressors {fe : RR + f((z) = vi where Vi E RRYT where T q(q + 1), there exists:
Dey of q points in IR9 each of Euclidean norm S 2, and
a regressor fo R2 + R. given by fo(z) == vo z for a unit vector Vo E IR!
satisfying
L Len
D
Duup fi) 0, Vt {1.... .1. T} train
and
L L (Dsup Duup fu) 2 1/(4g²).
(6)
Informally, the above theorem constructs a training dataset such that for any set of less than q 1)/2 linear regressors one choose a synthetic dataset which each of the linear regressors have the same loss as on the training dataset, while there exists a regressor that has significantly different losses. This implies lower bound of ((d?) for in Theorem 4.1
Note that Theorem 4. states that as long as there exists any Daye of size m such that 5 is satisfied, the implications of the theorem hold i.e. Doup is good distilled synthetic dataset. There is no
5

---

restriction as long 55) is satisfied and Theorem 4.1 does not explicitly impose any lower bound on m. However, depending on Doup it may not always be possible to satisfy (5) for small values of Specifically, we show in Appendix D lower bound on based on the spectral properties of the gram matrix of Suu In the worst case, we show a lower bound m 2 d + and show that possible to achieve this lower bound implying its tightness.
Offline RL Dataset Distillation, For convenience, we define the following modified Bellman loss which incorporates scale factor I& for the reward in the usual Bellman loss:
[ (F(e..o)
27
LBen (D, f. ((sass)))
- (((s.0))\r- Dr
mmx f a'EA
max f(s', ,
(7)
To state our result, we need the pseudo-dimension Pdim (see Appendix A.1 of the above loss restricted to single points. In particular, U be class of mappings
(dd, Bu) x B(do. Bo) x
[0, Rmax] x B B(do, Bo) + R where each 24 is defined by u(s, a, r,s) == LBau( {[s, (ss,a,, a, r, s' f. 1]. Let p == Pdim(lf). Further, we assume that Φ is L-Lipschitz. We
for some f E 2o and [-1,1]
also define:
Bell (Der Duain Dort A) = (Lee (D J, Lee S. ()))
(8)
We define distribution (o)) over (predictor, scalar) pairs in which random (f, is sampled by independently choosing r ~ [(,,, o² and ~ NO0, o²) and defining f [s, a) == r ((s a). For simplicity we define H == (1) Using this, we have the following theorem.
Theorem 4.3. Let Ded the offline RL training dataset as described above. For any A > O and 6 > let (J1,)1),.... (Sk, Au) be iid samples from H. for some k (ld do (p(log(1/v)
log( Bo LBLLBB. Rmax)) 1og(1/5), where u A/(B+ Rmax)* Then, with probability 6, if there exists Dert s.t.
Leel (Drd Deel fz, A5) SA'
(9)
then, for all f E Qo. Lien (Der
syn f) S A. where A' = (L)O(1)).
train
The following is the distillation algorithm whose guarantees follow directly from Theorem 4.3
Algorithm 2: Offline RL Dataset Distillation
Input: d, i. m Z+, feature-map d. Dorl E (S A [0, Rmax] x SS)" 1. Sample iid at random (J1, .... (Jk, AR) from H.
Output argmin Det E(B(do. XBd,, Bo) (0. Bo)o Σラ L Rell (Drrl Dorl fār Az)
tain
Offline RL with decomposable feat We consider the natural case when ø is decomposable ie.. o(s, a) == (s) + Φ2(a) e Rd for all E S, e for some mappings ò1, d2 B(dd, Bu) Rdd Further, we say that & is linear and decomposable if ói and Φ2 are linear maps.
Theorem 4.4. Consider the case when & is decomposable as defined above and let Der the offline RL training dataset. For any A > and > O, let (fi, A.).... (fk, 2x) be iid samples from (1/ + for some O (d2 log(d(B + (m) there exists Darl s.I.
Then, with probubility 1 if
i mell pod Derl Jú, A,) A A'
Dort
(10)
satisfying
E E (()1(s), (2 (2)))))))))))))))))) (n (s())) = E (2(())
(11)
then, for all Qn. ge i Dort f) A, where A' = (k/O(d))
DDer

---

In particular, the above theorem shows that the optimization in Algoritbm22consrrinndd by equation in the case of decomposable feature-mat map o, requires only O(d²) sampled action- valuue predictors. Further, when @ is linear and decomposable i.c., Φ1 and @2 are linear maps, then equation [I lis a linear constraint in the points Dog and it can be shown (see Appendix F for details) that the optimization in Algorithm 2 constrained by equation
11 is convex.
Discussion of Our Results. Theorem 4.1 and Algorithm togetherr provide an efficient supervised dataset distillation algorithm (for linear regression) with performance guarantees. Specifically, we show that with high probability over ((d)) sampled regressors, optimizing a convex objective over Diyn to minimize the sum of Imme for the sampled regressors, is sufficient to obtain high quality synthetic dataset. While our method adapts the model-trainine free approach of Zhao & Bilen (2023) to loss matching, our theoretical guarantees are qualitatively different from those Nguyen et al. (202I) which showed convergence of synthetic features assuming the synthetic labels are given, and of Chen et al.] (2024) who assumed the availability of the optimal trained model. We show that our analysis is tight (upto polylogarithmic factors) by proving ((d2) lower bound on the number of sampled regressors in Theorem 4.2 In addition, we also provide a lower bound of (dd) on the size of the synthetic dataset needed (in Appendix D). We note that Theorem 4.1 shows that the randomness (or sample complexity) required is proportional to log (1/A /) where A is the error, which is quantitatively better than sample size proportional to 1 A achieved by matrix sketching techniques (see Garg et al. (2024), Wang et al. 2017). Clarkson & Woodruft (2009). Our theoretical analysis of the supervised regression relies anti- monccnnnenttatioon of Like with respect to random linear regressors, and can be applied to any class of non-linear regressors that admit similar anti-concentration properties. Our theoretical analysis of the supervised regression setting can be carried out for any class of non-linear predictors that admit anti-concentration of I. over the choice of the predictor's random weights. In the linear setting, L a degree polynomial in the weights of the linear predictor and we use the Carbery-Wright inequality for polynomials (Theorem A.3) to get anti-concentration Lemma C. If some class of neural networks can be approximated by polynomials of bounded degree (as suggested by Frances et al. (2022)) in the weights of the neural network which can be sampled randomly, our techniques could be applied. However, proving such anti-concentration for general neural networks is beyond the scope of this paper and we defer this line of work to the future.
For offline RL. Theorem 4.3 and Algorithm give the first dataset distillation algorithm with rigorous performance bounds, without model training. Our novel approach based on matching the Bellman loss w.r.t. sampled Q-value predictors differs from the previous behavioral cloning (BC) based methods of Light et al] (2024) which matches the loss gradients of the BC objective and Lei et al.] (2024) which optimizes the synthetic dataset using an action-value weighted BC loss requiring trained action-value predictor.
However, the Bellman Loss involves max term and thus cannot be well represented as a low degree polynomial in the weights of the predictor. Due to this, polynomial anti-concentration (used in the supervised regression case) cannot be applied and the proof is via a conditioning argument. In effect, our algorithm requires sampling exp(O(d log d) predictors in the worst case where d is the output dimension of the feature-map. We note that a brute force approach would be to choose a net over the predictors Qo instead of sampling. However, that would necessarily require exp(d) such predictors, while in practice a smaller number of randomly sampled predictors suffices, as demonstrated in our experimental evaluations.
While the bound in Theorem 4.3 is indeed less efficient than Ö(d) sample complexity of the super- vised setting, in practice the features are mapped into smaller dimension than the input mitigating this to some extent. Further, in Theorem 4.4. we prove similar ( in the case of decomposable feature-map d and show that the optimization is convex when & is linear and decomposable. This a natural assumption and is the default feature map in applied RL for most value based deep RI. approaches. For example, the highly cited work of (Lillicrap et al. 2016) explicitly describes con- catenating the action and state embeddings. A common trick used in practice and in our experiments is to one-hot encode the actions and concatenate them with the state embedding to obtain the feature map. Additive feature maps are also explicitly studied in (Zhang et al.) 2020) and (Yang & Wang 2019). Our analysis uses a conditioning argument which leverages the linearity of the predictor for using Gaussian anti-concentration. The anti-concentration is used to show that the sampled linear predictors lie in an appropriate subset with non-trivial probability. We believe Theorem 4.4 provides
7

---

evidence that proving appropriate Lipschitzness and anti-concentration of non-linear predictor's output w.n.t its weights, can be used to extend our arguments to such predictors, e.g. neural networks. We however, defer more detailed study of the non non-linear predictor case for the future.
and 4.4 are included in Appendices C D.2 E. and F Prespectively. In the next section however, we provide informal description of the proof techniques. A subset the experimental evaluations are included in Section 6 while additional experiments and further details are deferred to Appendix H
Organization of the Paper. The proofs of Theorems 4.1
OVERVIEW OF OUR TECHNIQUES
Proof Outline of Theorem 4.1. The proof proceeds by contradiction: suppose there is some h E F and Dayn T. (Dira Deyn h) > A. Letting g be random sample from G, show using algebraic manipulations and properties of the Gaussian distribution that T. (Dean Dagn g) is degree-4 polynomial x² in Gaussian variables, such that E[a²] > A/)(d). This can be used along with the Garbery-Wright
moteennncento bound for Gaussian polynomials to show that Pr[u² > A 2 1/3, Since { are iid samples from G, using Chernoff Bound, the probability that there exists (2k) many j E [K] satisfying T (D
train Deyn ; > (/O(d²) is at least 1 - exp R((k) To complete the argument, we require union bound of this error probability over all h E F and Dyyn, which we do by constructing finegrained nets as follows.
Net over all h E F: Since h E is given by some r E Rd+1 where 1 S ||r||2 S 2, one can take a E-net w.r.t to Euclidean metric over all such vectors whose size at most ((de)) (see Appendix ..2 for a small enough so that L is essentially unaffected when h is replaced by (or vice versa) corresponding to the nearest vector in the net. For our purpose can be ((A)). Net over all D For this we first observe that Dayn can always replaced by a subset of size d using Lemma D.2 so that Luse remains lower bounded by A Thus, it suffices to consider the net (N)* over all s-sized datasets where N is e'nnet over the set of all possible datapoints, so that L is approximately preserved by the nearest dataset in (NV
The size of (AV)* is (BB + b) (ssd), and the product of the sizes of the nets constructed above is exponential in O (df log(d(( + b)/ Thus, to obtain the statement of the theorem via a union bound, the number of sampled regressors required is k = O (d log(d( (d B + b) log(1/))).
The proof of the lower bound of 2(dd) on the sampled linear regressors relies on the fact that the set of symmetric g x q matrices, where q = d 1, is a g(9 1)/2- dimensional linear space. Thus, for a choice of less than q(q + 1)/2 homogeneous linear regressors, there is non-zero symmetric matrix A for which (vv A) = 0 where v is any one of the chosen regression vectors. Here, A can be scaled so that its operator norm is exactly 1/2. Thus, one can choose (up to appropriate scaling) Duup so that E xx T| = which is independent of the mue
Proof Outline of Theorem 4.2
1 = I+ A which is psd. It can be that each chosen regressor has the same MSE loss on sup and Diyn, while due to A + 0, there is a train regressor which has different losses on Duu and Daya
chosen regressors. Diye is then chosen that Eze [xx
Due to lack of space we defer the proof outlines Theorems
and to Appendix B
EXPERIMENTAL EVALUATIONS
We generate synthetic datasets, Dayn of sizes much smaller than the original training dataset using Algorithms [ aadn for supervised regression and offline RI. respectively. We evaluate the models trained on them, over the test split of the original dataset in case of supervised regression or the derived policy in the RL environment.
Baselines. The following baseline datasets are included as part of our experiments. Full Original: model trained on the entire original training dataset Duain- and Random: model trained on a random sub-sample (of same size the synthetic dataset) of the original dataset, Drand- In addition, for supervised regression, Leveraged: model trained on a leverage score subsample (of same size as the synthetic dataset) of the original dataset, Daev (see Drineas al. 2006)).
8

---

Red Wine Quality
White Wine Quality
Boston Housing
3.0
D_train
D_train
+ D_train
2.5
D_rend
2.0
D_rand
D Derend
1 D
D_lev
D_lev
D lev
Test
1.0
1.0
0.3
20
40
60
8C
100
20
40
60
80
100
20
40
60
100
N_syn
N_syn
N_syn
Figure I: MSE Test losses for Homogeneous Linear Regression on the following supervised datasets: red wine quality, white wine quality, Boston Housing.
Supervised Regression Datset Distillation. We evaluate Aggortthm[aaooo with the above mentioned baselines the Wine Quality (Cortez et al. (2009) ODbL 1.0 License). specifically the included red wine and white wine quality datasets, and the Boston Housing Dataset (Harrison & Rubinfeld 1978).
The sizes of the synthetic dataset Noya we consider are (20, 50. 100). The size of Drand and Diev the same as Dyn, and is subsampled randomly from D Dusin- We initialise the convex optimisation of Day with the initial value Drand- We take l 100 random homogeneous linear regressors in Algorithm I to find Day and then train homogenous linear model (f(x) = r²xx on the four datasets.
The mean test loss of models trained on respective datasets (over 10 trials) are plotted in Figure] 1
Further details of the model training, hyperparameter search are included in Appendix H. and
Appendix H.2 Experiments on larger datasets are also included in Appendix H.3
We observe that the homogenous linear models trained on Dayn performs almost as well as ones trained on Drain far better than ones trained on Drand, and better on par with the models trained on Die.. This demonstrates the efficacy of our synthetic data generation technique for supervised learning datasets and empirically verifies Theorem 4.1 We also observe that we perform better than the classical data- reductedutioon technique of leverage score subsampling for homogenous linear regressors.
Offline RL Experiments. We test Algorithm 2 for offline RI. DD by evaluating a policy trained on our synthetic dataset using Fitted-Q Iteration (Frnst et al., 2005). classical offline RI. algorithm. along with the Full Original and Random baselines on the Cartpole environment (Towers et al.) 2024 (MIT License), Mountain Car MDP (Moore (I990). Towers et al. (2024) MIT License), and the the Acrobot Environment (Sutton (1955), Towers al. (2024) MIT License). Refer to Appendices H.4 H.7 further details on the datasets. Since linear Q-value predictors are known to perform poorly with Fitted-Q iteration even when trained Duain. use 2-layer neural networks for training and generating the synthetic data which are randomly sampled by sampling the model weights independently from standard Gaussian distribution.
We do not use Diev as a baseline because leverage score subsampling is only defined for linear regression and has no analog in neural network regression. To generate Dinin. we sample from transitions from random(or nearly random) policies. We sample k: = 20 random models with random normal weights for the data distillation procedure. The size of Drant and Dayo is denoted by Neya We generate D once and we train all three datasets with the Fitted-Q iteration algorithm to get the trained policies. We evaluate these trained policies in the environment 10 times and plot our results in Figure 2 D is sampled 10 times and each sample is evaluated once. Further experiments are conducted with more values of l and can be found Appendices H.4 H.6 H.7 along with more experimental details.
We observe that a model trained on Day is significantly better than one trained on Drand- We also see that Nom increases, the model trained on Deyn performs even better par than one trained on Duain for the Cartpole and Acrobot environments. This demonstrates the efficacy of our synthetic data generation technique for offline RL datasets for non-line non-linear predictors. Additional discussions and experimental evaluations such as comparisons of our method against behavior cloning distillation baselines (Light et al. 2024) are included in Appendix H

---

Cartpole
Mountain Car
Acrabot
500
-100
Expected Retur
Expested Return
-100
400
-125
-200
r_nand
D rand
Expected
D_syn
-150
D_ayn
-175
4400
D_rand
D_sym
-200
Nyyyn
N_sym
N_syn
Figure 2: Max Evaluation Return with two-layer neural networks the offline RL datasets created by the following environments: Cartpole, Mountain Car, Acrobot.
Limitations. Despite the success found the toy sequential decision problems above, our algorithm does not yield similar performance established offline RL benchmarks such D4RL. The D4RL benchmark is created to distinguish between standard offline RL algorithms like Fitted-Q iteration (FQI) which does iterative Bellman Loss minimization, and recent advanced algorithms like conservative Q-learning (CQL) (see Kumar et al. (2020) and page 2 of (Fu et al. 2020). While we propose novel offline RL dataset distillation algorithm based Bellman Loss matching, since D4RL is unsuited for Bellman Loss base algorithms, one would need to adapt dataset distillation to more complicated loss functions like that used in CQL. These generalizations our techniques, their analysis and evaluations on D4RL benchmarks are beyond the scope of this paper and are deferred to future work.
Experimental Code. The experimental code is available at https: /ttsps://gitule wwg.t.th...... com/ google-deepnn nd/loss nd/loss_matching aataaaun__aaaeeettssttllaaaaalaa cerr__dsssilaaiioo of the algorithms in this paper are in python using the TensorFlow library. Our experiments were run on a system with standard 8-core CPU, 64GB of memory with one 16 GB RAM GPU.
The implementations
CONCLUSIONS
We propose loss matching based algorithm for supervised dataset distillation, which given training dataset the synthetic dataset is optimized with respect to a fixed set of randomly sampled models. For linear regression in IRd we prove rigorous theoretical guarantees, showing that optimizing convex loss matching objective for only (dd)) sampled regressors, without any model training, suffices to obtain high quality synthetic dataset. We prove matching lower bound of ((d?) many sampled regressors, showing the tightness of our analysis. We extend our approach to offline RL to provide algorithm for dataset distillation matching Bellman Loss using sampled Q-value predictors, while showing similar performance bounds, albeit requiring exp(O log d)) sampled predictors in the worst case. However, under natural decomposability assumption d-dimensional state-action embeddings, we improve the upper bound (dd)). Our experiments show that our algorithms yield performance gains on real datasets, both in terms of the size and quality of the synthetic dataset, even with small number of sampled predictors.
An interesting yet challenging future direction in to extend our theoretical results in the supervised setting to neural networks, and to obtain provably efficient offline RL dataset distillation algorithms for more general classes of state-action embeddings, perhaps leveraging specific geometric properties of the associated MDPs.
10

---

REFERENCES
Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 2009.
A. Carbery and J. Wright. Distributional and 19 norm inequalities for polynomials over convex bodies in r", Mathematical Research Letters, 8:233-248, 2001.
George Cazenavette, Tongzhou Wang, Antonio Torralba, Alexci A. Efros, and Jun- Yan Zhu. Dataset distillation by matching training trajectories. In Proc. CVPR, pp. 11708-107177 2022.
Yilan Chen, Wei Huang, and Tsui- Wei Weng. Provable and efficient dataset distillation kernel ridge regression. In Proc. NeurIPS, 2024. BRR.httss:/ /ttp:://ppeeeeveee ew. net. www.et/forumt d=
WI2VpcBdndl
Kenneth L Clarkson and David P Woodruff. Numerical linear algebra in the streaming model. In Proc. STOC, pp. 205-214. ACM, 2009. URL htt.htts:://// .ac. wtt.a///g////....11111111 11155/131..14515131111 1536445|
Paulo Cortez, António Cerdeira, Fernando Almeida, Telmo Matos, and José Reis. Modeling wine
preferences by data mining from physicochemical properties. Decision support systems, 47 (4):547-553, 2009. URL https: /www: kaggle. com
wi ine-quality
Justin Cui, Ruochen Wang, Si Si, and Cho-Jui Hsieh. Scaling up dataset distillation imagenet- 1k with constant memory. In Proc. ICML. JMLR.org, 2023.
Zhiwei Deng and Olga Russakovsky. Remember the past: Distilling datasets into addressable memories for neural networks. In Proc.NeurIPS, 2022. URLAttps.//ppeneeeeee.cc
Forum?id=RYZy wwgfa
Petros Drineas, Ravi Kannan, and Michael Mahoney. Fast monte carlo algorithms for matrices ii:
Computing low-rank approximation to matrix. SIAM Journal Computing, 36( 36(1))158-11)) 2006.
Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforce- ment learning. Proc. ICMI,, 2021. URL htt.tttt//oooceeeeeiieeee wwt..m..e......33333.3 duan21a a a/dpan22a.... pdE
m
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychome- trika, 1(3):211-218) 1936.
Damien Emst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. J. Mach. Learn. Res., 6:503-556, December 2005. ISSN 1532-4435.
Zhu Frances, Jing Dongheng, Leve Frederick, and Ferrari Silvia. Nn-poly: Approximating common neural networks with taylor polynomials to imbue dynamical system constraints. In Frontiers in Robotics and AI, 2022.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprini arXiv:2004.07219, 2020.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine D4rl: Datasets for deep
data-driven reinforcement learning,
Scott Fujimoto and Shixiang Gu. A minimalist approach offline reinforcement learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Proc. NeurlPS, 2021. URL
net wwwoormmddgg20/eee0
Sachin Garg, Kevin Tan, and Michal Dereziński. Distributed least squares in small space via sketching and bias reduction. In Proc.NeurIPS. 2024. URL
www.:eeddin...eeie..eee..see http://flllsslsaaeeeaeaaeaaaaeae https://procedings ottpr//rrrr.reeaaao..ooo.////a/a

---

D. Harrison and D.L. Rubinfeld. Hedonic prices and the demand for clean air. J. Environ. Economies & Management, 2881-02--48, 1978.
William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984.
Ilya Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with im-
plicit q-learning. In Proc. ICLR, 2022. URL https:://ppeereee....eeeeeteette for.ffoummeeetmemm
68.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. In Proc. NIPS, 2020.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch Reinforcement Leariigg, pp. 45-73. Springer Berlin Heidelberg, Berlin. Heidelberg, 2012. ISBN 978-3-644--77645-3 doi: 10.1007/ 1-.---42-276455 2. URL
Shiye Lei and Dacheng Tao. A Comprehensive Survey of Dataset Distillation. IEEE Transactions on Pattern Analysis & Machine Intelligence, 46(01):17-32, 2024. ISSN 1939-3539.
Shiye Lei, Sen Zhang, and Dacheng Tao. Offline behavior distillation. In Proc. NeurIPS, 2024. URL net htt.://wweeerfooom22o//999999///
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems, 2020.
0164
Jonathan Light, Yuanzhe Liu, and Ziniu Hu. Dataset distillation for offline reinforcement learning, 2024. URL/attps://arx. wtwp:l/wwwrg/////aa/aaaea// 24007./224...0 240./2299
Timothy P. Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Proc. ICLR, 2016. URL https:
httpttps::/ /ttp:v////avvv.a/aa/ ottp:////gppppp///////p /tr.///ppp///aa......r//////////
02971
Andrei Lupu, Chris Lu, Jarek Luca Liesen, Robert Tjarko Lange, and Jakob Nicolaus Foerster. Behaviour distillation. In Proc. ICLR, 2024. URL https: Tlttps://openzeete /ttp/////eeee/eeeee/e//e/ www.:errttofummooeoo Ldd=uu9xD&@mi
Michael W Mahoney. Randomized algorithms for matrices and data. Foundations and Trends in Machine Learning, 3(2):123-224, 2011.
Andrew William. Moore. Efficient memory-based learning for robot control. Technical report, 1990.
Timothy Nguyen, Zhourong Chen, and Jachoon Lee. Dataset meta-learning from kernel
ridge-regression. In Proc. ICLR, 2021. URL
1- 1-PrzOrKCOR
R. K. Pace and R. Barry, Sparse spatial autoregressionss. In Statistics & Probability Letters, pp. 291-297, 1997. URL /ttt:::://bl..ogg1101111///////
(96) 00140-0
Noveen Sachdeva and Julian McAuley. Data distillation: A survey. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL https::/openzeviee.. wwtp:/iwwwwww.....eeeeeeeeee
[d=1mXMMPP- T4T0 Survey Certification.
Tamás Sarlós. Improved approximation algorithms for large matrices via random projections. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 143-152, IEEE, 2006.
GW Stewart. On the early history of the singular value decomposition, volume 35. SIAM, 1993.
Richard S Sutton. Generalization in reinforcement learning: Successful examples us- ing sparse coarse coding. In D. Touretzky, M.C. Mozer, and M. Hasselmo (eds.), Advances in Neural Information Processing Systems, volume 8. MIT Press, 1995. URL httpp::/ppcceeeeiiigeee neuripg cct ccppaper htteeerfiieeeeeeee/eeee/ H1r2555fdk222bb000000000ooocooon
12

---

Denis Tarasov, Vladislav Kurenkov, Alexander Nikulin, and Sergey Kolesnikov. Revisiting the minimalist approach to offline reinforcement learning. In Proc. NeurIPS, 2023. URL https
Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U. Balis, Gianluca De Cola, Tristan Deleu,
Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, Rodrigo Perez- VrrentVicente Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Hannah Tan, and Omar G. Younis. Gymna- sium: A standard interface for reinforcement learning environments, 2024. URL https
//gymnas um farama .tr.aaaoorrr/// .org/
Roman Vershynin, Nigh--Dmensional Probubility: An Introduction with Applications Data Science. Cambridge University Press, 2018.
Kai Wang, Bo Zhao, Xiangyu Peng, Zheng Zhu, Shuo Yang, Shuo Wang, Guan Huang, Hakan Bilen, Xinchao Wang, and Yang You. Cafe: Learning to condense dataset by aligning features. In Proc. CVPR, pp. 12186-12195, 2022.
Shusen Wang, Alex Gittens, and Michael W. Mahoney. Sketched ridge regression: Optimization perspective, statistical perspective, and model averaging. In Proc. ICML, 2017. URL https
mir /rgp://ceosssstttlo..ee//e/////n
pdf
Tongzhou Wang. Jun- Yan Zhu, Antonio Toralla, and Alexei A. Efros. Dataset distillation. CoRR,
abs/1811.10959, 2018. URL.htt.://arxww..or/////. 1811. 10959
Lin Yang and Mengdi Wang. Gample-optimal qleaming using linearly additive features. In In Proc. ICML, 2019. URL https:: mlr www...tw....ep....mmmmm..m...l.t evpesssvv97. pwwpss/////aaggg/ 9b/
yang19b.pd.
Zhang, L.. Ma, K. Leung, Poularakis, and M. Srivatsa. State action separable reinforcement learning. In In Proc. IEEE International Conference Big Data (Big Data), 2020.
Bo Zhao and Hakan Bilen. Dataset condensation with differentiable siamese augmentation. In Proc. ICML, 2021.
Bo Zhao and Hakan Bilen. Dataset condensation with distribution matching. In Proic. WACV, pp. 6503-6512, 2023.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In Proc. ICLR, 2021.
13

---

A PRELIMINARIES FOR APPENDIX
A. FUNCTION CLASSES AND PSEUDO-DIMENSION DIMENSION
We will consider class FF of real-valued functions (regressors) mapping E to 1-1,1]. The pseudo- dimension of the function class Pdim(F) is defined as the minimum cardinality subset of R which pseudo-shatern shattered. It is formally defined Definition 11.2 of (Anthony Bartlett 2009).
For X C Rd where X N. set Cp(E. F. X)) ) to be minimum sized &p ép-metric ç-cover of F over smallest subset of such that for any f E F, there exists f E Cp(E:F,
X. i.. Cp(E,F,X))
s.t. (BxEx (x) (x) 1/2 = for [1, oo), and maxxex lff((x) f(x) 1 g for p co.
The largest size of such a cover over all choices of X C R s.t. | = N is defined to be F,NE
The pseudo-dimension of F. (F) (see Sec. 10.4 and 12.3 of (Anthony & Bartlett 2009 can be used bound the size of covers for F as follows:
(1, S (E. = (eN/Ep)²
(12)
where p Pdim(F) and N d. By normalizing, the above bounds be adapted to functions which map to 1 B, B] for > 0.
The following theorem follows from Theorem 11.4 from (Anthony & Bartlett 2009).
Theorem A.1. The class of linear regressors over Rd given by r x for E IR has pseudo-dimension
A.2 COVER OVER B(d,r)
Let T(d, =) be the smallest subset of the Euclidean ball of radius in d-dimensions B(d,r) r) such that for all r E B(d,r) r) there exists i E (dd, s.t. ||r - +|12 I e. The following lemma follows from Corollary 4.2.13 of (Vershynin 2018).
Lemma A.2. T(d,r, r,E) < (1 2r
A.3 CARBERY- WRIGHT
BOUND
The following non-trivial anti-concentration of polynomials over Gaussian variables was proved by (Carbery & Wright 2001).
Theorem A.3 (Theorem 8 from (Carbery & Wright 2001 ). There is an absolute constant C > 0
such that if f is any degree-d polynomial over iid ((0, variables, then Pr [lf] S <E[[]]]] < // for all
A.4 LIPSCHITZNESS OF FEATURE- MAP Ó
For the our results on offline RL dataset distillation, mentioned in Sec. we assume that the feature- map 6 is L-Lipschitz, specifically w.r.t. the E2 me-tici.. In other words, for any (81 Q1), (82, a2) e B(do, Bo) B(do, Bo).
(1)()))11) 6(32, 02) L[(s,, 01) (82, a2)12 =L ||sı s2113 || 02l1
L ([|sı - s2l12 1 ||01 az a2)12)
A.5 Low RANK APPROXIMATION
kev ingredient our lower bound is the classical Mokkart-Youg--iisse theorem (Eckart & Young 1936 Stewart 1993), which states that for any symmetric positive semidefinite matrix A E ga with cigenvalues \ 2 A 2 ... 2 Ad. the best rank-m approximation in spectral norm is obtained by truncating the eigendecooppsiitio of A, and the approximation error is exactly
min rank(B)sm
|| A
BlI
Am+1-
(13)
14

---

This immediately implies that if Am-1 E, then any rank-m factorization B ZZ with Z Rdxm must incur spectral error at least
A.6
CHERNOFF BOUND
We also the following well known concentration bound.
Theorem A.4 (Chernoff Bound). Let X Xn be iid {0, 1) 1]-valued random variables and let
=
Σ 1= Xi). Then for any 5 > 0,
Pr Σ
S1 d)p s exp (-82p/2)
B PROOF OUTLINES CONTD.
Proof Outline of Theorem 4.3 The main complication compared to the supervised regres- sion case is the presence of the max term in the Bellman loss, which we circumvent using conditioning argument. Specifically, consider some action-value predictor (s. = r (ss a) such that Ben (Dri.. Dagh 1) > E, for some syn- Assume for ease of exposition that ||||| 1. Now, f H corresponds
Qu given by
vector f = + Ju where N(, 1), (00, 1)d-1 and is a d x (d (2-10 1) matrix with columns being a completion of to an orthonormal basis. It is easy to that with probability least exp(-O d)), ||ul]|2 < 1 and therefore ||Jull2 < 1. Conditioning on this event and the positivity of a allows us to use max.' f(((' ,a)) R max [(0('', (')ss,'))) This, along with conditioning À 2 1 and some algebraic manipulations yields that Î Ler, (Darl bain Dert f) a A, which directly yields probabilistic lower bound of ((A) on Lee Dedd Ded f). The rest of the net based arguments are analogous to the supervised case but with notable differences. In particular,
observe that Dor can always be replaced by a subset of size O(d/ A log (1/A)) so that L remains lower bounded by O(A). In addition, use more broadly applicable generalization error bound for the the Bellman loss using its pseudo-dimension and the Lipschitzness of Φ. However, due to the (s log d)) the conditioning, success probability for single sample (ff A) is also exp( Od d)) and therefore the number of predictors be sampled is exp(O(d log d)).
Proof outline of Theorem 4.4 We observe that when & is decomposable, for Q-value predictor f( = v TTo(s, a), we have that m [(s', (')
o (5') + max.'eA v (2 Here == ma v (2(aa) depends only on v and is independent of the dataset. This allows for cancellations of terms between Deri and Dor in L and using the constraint in equation 11
obtain a linear regression formulation in the embedding space Fd. Thus, one can essentially follow the proof of Theorem 4.1 Further, it is easy to see that if Φ1 and Φ are linear then the constraint in resulting convex optimization.
equation 11 linear in the points of Dorl
syn
C PROOF OF THEOREM
D.uup ((x;, y/) E ((d, B) 1- bi the given training dataset consisting of feature- and real-valued label pairs for regression task. For ease of notation in the proof of this theorem we shall drop the concatenation operator and instead use vectors to denote
data point with the that
feature-vector and label concatenated. Further, we let == d + represent the dimensionality the domain F IRy With this notation, map = {x, E B(g - 1, B) x (-b,b) is the given analogous notation for the datapoints of the synthetic datasets in the
training dataset. We analysis below.
C. BOUNDS FOR FIXED h AND FIXED SYNTHETIC DATASET D
We begin by fixing (i) h E F s.t.
h(x) àu for some IR9 s.t. ||u||2 and à E [1,2]
(14)
15

---

and, D {2: E B(q - B) [bb,b]
for some = Using this, have
2
n
mse
sup train?
D. -
x,) )2 (éu' (uit2,) 2;
(15)
The following lemma provides key probabilisticc lower bound.
Lemma C.1. Let T we have
(Derai train"
D. h) 2 A. Then, for randomly chosen g G(F) s.t. g(x) = =r'x,
Pr
(
[.mms
sup D,g) 2
A Cuq?
A (11r112 - 10) z 30
7
for some absolute constant Co > O.
Proof. We first lower bound the expectation E <mme Diiiin D.9)] Sampling a random g G corresponds to sampling r (0, 1/g)" u.a.r. and letting g(x) r for x E RR. Letting == u, we can find unit vectors -2.-... Fr such that ri...., Fg is an orthonormal basis. Writing r :: aiti + + Ug we obtain that aty is iid N N(0, 1/4) for each j E q.
Therefore,
(Duup D.g) = mse train
a
a 21
(16)
1=1
Define 3; Ei=2 for i E [n] and similarly 7j = that both {8. fr are independent of a1. We now rewrite the squared loss in terms of (3.) ii to obtain:
uu-2a,rJ2, for i [s]. Note
@Dapp D.9)= =
(a1r + B.)2
1
E(arrTa +1033)
mse
[i
xxx;)
Σ (rT2,))
i=1
i=1
1 n
2
+ 20n
-
Bar x4
Σ
url TT 25
+
Σ
3
7
(17)
At this point, we let K =
1 Σi= (r]x,)
Ei= (rl 2.
w=
E
and À = 2 ( Σ Brix X;
1 Σラ 7/1 [2.). Note that Ki, are independent of a1 Substituting
these into equation we obtain
L
DDup
Irain D.g) = (a + a1 + +w²
=a a²\² + w 2at2x + 2a + 2a
Taking the expectation over 01 yields,
Eay
eir
sup
D.g)] =E [o x² +E a2 X2 + w² 2E [ail An + 2E [an] Aw + 2E [| =(3/4²) + (2/g)/)
train
=(2/g²) (w/g))/((//+)/)))/ X2/9
222
1
(r x2)
Σ
(rT 22))
q2
2
n
=2
Céu T
xx
(éu 2,)
qē
72
1
A
I T
(D
2
(18)
qc
29
16

---

where we used equation 14 and equation 15 along with the fact that 01 (0, 1/9). Observe that T (Dium D.g) g) is degree-4 square polynomial in {az} and hence is always positive. Observe that the lower bound in equation 18 is independent of {az}}=2 and is thus an lower bound for the
expectation over {ay})=ı Applying Theorem
A.3 (see Appendix A.3 to equation 18 we obtain
1
Pr
I mse (Drip train D,g)
2
(19)
72
2q
Further, since ||[[||3]] = 1, by Markov's inequality, Pr[[|=||3 > 10] < 1/100. This along with the equation 19 and taking Co (1/2)) completes the proof.
The following is a straightforward implication of Lemma (Theorem A.4).
C.1 along with the Chernoff Bound
Lemma C.2. Let Line (Doup D) A. Then, for itd random 91. .I...., 9k G(F), 9,(x) :=
have
Pr
[k]:
(L (LaTe(D (Duup train
D,95) 2
A (1lv S 100
7k
2 1 exp
-7k
Cog
60
240
C.2 NET OVER REGRESSORS AND SYNTHETIC DATASETS DAyR
First we shall construct a net over regressors h E F, where h(x) := x for some r E B(g, 2). Thus, we can consider the cover T(4, 2, 2)) (see Appendix A.2) and let F = {h 3f E T(q, 2) s.t. h(x) == x), for some parameter E 10 1) to be chosen later. The following is a simple approximation lemma.
Lemma C.3. For any Dam and D as defined in the previous subsection, for any h E F 2h E F s.t.
Lone Duain h)
(Daup L (D Drain
D,h) S 65E(B
(20)
Proof. Let h(x) = xx, where ().. Choose f E (gg,2, s.t. ||| +|12 < and
define h be h(x) = T'x. Thus, for every x; E suup
(r x,) xx)x, < ((r f) xx, 2
triin
2 2 - f) r x, S (E(B + b))3 + 4E(B B + b)2 S 5 + 6)² since & < 1. Using this, along
with equation 15 we have that L sup D. =
L er mise
Sup train
D h) + where e E R s.t.
|u| < 5
Therefore, Lew (Daup train
train Dhh) < 2/ L (D (Dirin train D, h) + |u|2 It is easy to see using the norm bounds on the regressor vectors and the data points along with equation th
D,h) - ( (Duup
/ Len (Duu D, D,h)= < bb) Thus, 2/u/ v L (Dsup D, h) + |ul < ( + 25 Irain
train
6)2 < 65 b) which completes the proof.
We now show that the synthetic data D can be approximated with much smaller dataset D whose points are from an appropriate Euclidean net.
Lemma C.4. Fix (0, For any Doup there exists dataset ò of size from Euclidean net T(g, ( bb), + b)/2) such that for any h E F,
whose points are
Law
SDuup train D, h)
L ( train Duup h) < 65vg 2 (B + b)*
(Duup
(21)
Proof. Let us first take D (bounded in a ball of radius ( ( + b)) to be the dataset of size from Lemma such that
mscc traim?
Sup D. h) T, e Duu train
Dsup
(22)
17

---

Then create D by replacing each point in D with the closest point in T(g, // + b), vQu(B b). Using arguments analogous to those in the proof of Lemma C.3 we obtain,
ett
(Duup Iruin
D. h))
car Fmse
(Dra D, n)) s 65vg + b)
(23)
Combining the above two inequality and equation completes the proof.
Note that in In Lemma C.4 we replace the m-sized synthetic dataset Dayn with a dataset π of size q = d + with points from an appropriate net. This allows to take union bound over all possible q- g-sized D. The value of m unrestricted, and need not depend on d. There no restriction on = D either, and we in any case do not require a net argument for Duap Due to this net train"
argument which replaces Diya with g-sized D (albeit with possibly larger norms), the analysis is made independent of m and thus e and ô are also independent of m.
C.3 UNION BOUND OVER NET AND COMPLETING THE PROOF
To use the analysis in Sec. C.2 let us set 5 A (B and v (B Applying Lemma C.4 and followed by Lemma C.3 directly yields the following combined net for the regressors h and the synthetic dataset.
Lemma C.5. For any h E F and Diyn, there exist h E F and D E (B
such that
L (Dap D, h) Lime (Dman Days h) -
(24)
where: s = for some constant C1 and f {h 3 T 2.5) s.t. h(x) i'x].
Observe that
$ x
( 3 1
6 9
= -exp (0(1²log log q(B +b)
(122og
S
Thus, one can apply Lemma C.2 with k = O q² log
g(B+b)
log (1) and take a union bound
over F. (gg, ( (B ( b)/ to obtain the following: with probability (1 5)) over
train iid random 9I....,9h Ik ~ G, if L DDuu D, h) > A then there exist 7k/60 distinct j E [k] s.t.,
L (Doup train
D Z Cog
A (1Ivg-113 < 10)
(25)
Now, since 1|v I 10, ög, E FF for some ē 2 2/ VO. And since L (D D, gj-)) is proportional to ||v 112 applying Lemma C.4 to L (Duup train D, 0,āg;-) yields that
Lat
Drup
Dsup g5-) 2Cog
which implies,
7kA
L EIT
D Sup
Duup 93)
120Coq
completing the proof of Theorem
4.1
D LOWER BOUNDS FOR SUPERVISED LEARNING DATASET DISTILLATION
train ((x,, v:) B(d, B) x [-b, bJj is the given training dataset consisting of feature- vector and veluev label pairs for regression task and our goal is to find the synthetic dataset Deyp = {Zz, g.) E B(d,B) x [-b, b]] For ease notation in the proof of this theorem we shall drop the concatenation operator and instead use vectors to denote the data point with the feature-vector and label concatenated. Further, we let == d + 1 represent the dimensionality so that
the domain of F is R9. With this notation, Duup {x; E B(g 1, B) x [-b, b) b) is the given
18

---

training dataset. We analogous notation for the datapoints of the synthetic datasets in the analysis below.
We begin by fixing f E F s.t.
[(x) êuix x for some IR s.t. ||ul|2 and à E [1,2]
and, Day {z, Biq 1, B) x (-b, b] for some 8 Zt. Further, let us also define X = [11, X2,..... ,,, E R2xn and Z [21, Z2..... Zml E Raxm
Using this, we have
2
Lar ( mse
train
Duup f)
syn:
=
Σ
(éu
Taxx,,] x,)²
Σ 1=1
cu
2;)²
17
m
1=1
1
m
x
u
T 2,2;
11
m
1
1
-4
u
XiXi
u
u
Σ
Zizi
T
71
i=1
i=1
Σ
T
u
x;X!
i=1
1=1
XXT
T
ZZ
2
u1
11
(26)
m
Lemma D.1. Let Z E RRaxm have columns Vj (uz,8} 8j) with u2 RR-1, 83 E R, satisfying
l2 S B and |sy| S for j. Let Z E R2x4 have columns (vi, t.) and satisfy 1 zz
'Z Then for all |V:l12 S /q B and [t.l S /qb.
-A
A c
Proof. Write the block decomposition 1 Zz
q 1ZZ
with A = 1 Ej= 4
and Σm=1 ot Let V E R(0-1xxg have columns V.. Then VVT = A, V <
q tr A) S qB", giving ||vll2 I /q B, for all = 1, .,.... q. Similarly, for t = (fq...., tq) we have Σ L = a < 12, giving |4] S /7b, b, for all i 1.
As zzt= E <RT4 is a positive semi-definii matrix, we observe that by using the Cholesky factorization the synthetic data D Day (corresponding to Z Raxm) can always be replaced by another dataset
D (corresponding to Z E IR9x9) of size y such that zzT //m zz' /g without any change in the loss. Together with the norm bounds on the data points of D from the lemma above, this leads to the following lemma which we use in Appendix C
Lemma D.2. For any Duup E (B(d, B) x (b,,))) and Doup
(B(d, B) [-b, 6)))",
there exists a dataset D E (B(d, Bvd+ [-bvd+1, 1, of size d + 1 such that T DDuup Dayn f) I, ( (Daup D,
f) for any f F.
D.1 LOWER BOUND ON THE SIZE OF SYNTHETIC DATA
Given parameter and dataset D (corresponding to X R9x*), the objective of the supervised trai
learning dataset distillation problem to find synthetic dataset D (corresponding to Z RR*x such that eer DDuup
train Deyp f) < e for all f E F. as stated in 1p.
This means that in 24 (uT corresponding to synthetic dataset Z should satisfy || Xx_ zz 1l ye g.
equation 26)..
we need to have L muse
D SaP f)
train
XXX zz
2 < for all unit vectors E R7. This implies that the matrix
u
n
19

---

Using the low rank approximation theorem stated in (3) can say that needs to be least the number of eigenvalues of xx' larger than e² or more formally the size of the synthetic dataset <//4 m (X L = (X) - J. where # denotes the size of a and X, a denote
the eigenvalues and singular values of matrix.
In the worst case choice of D (corresponding X E Ro*"), we get lower bound of m 2 q
d + 1 on the size of Dayn when all d + 1 singular values of ((Dmin) ) are larger than s//4
D.2 PROOF OF THEOREM
We begin with the following lemma.
Lemma D.3. Let d 2 1, 9 d 1.1. For any vi....; VT E R with T dl+t1) 2
there exists
non-zero symmetric matrix A TRaxa that satisfies
Av, =0
for I....,T.
(27)
Proof. Note that Av = AV, viv!). Further, the set of x q symmetric matrices is q(q + 1)/2 dimensional linear subspace of Rex4, Since T < q/q + 1)/2, there exists a non-zero symmetric
matrix in the orthogonal complement of the linear span of {v.v.] Jtml which can be taken be the required matrix A.
L
To complete the proof of Theorem 4.2 we first choose Dupp = fei,...,,ey eq where e, the vector with in the ith coordinate and zero otherwise i.e., it is the äth coordinate basis vector. It is easy to see that
Lase ( train f) (1/g)v Iv (1/4)llv12.
(28)
when fzz vTz for all v Rd. Now, let fi..... fr be the regressors as in the statement of Theorem 4.2 Applying Lemma D.3 we obtain the symmetric matrix A which, by scaling, can be assumed to have largest magnitude eigenvalue i.e., its operator norm be 1/2.
We now construct Diyn follows. Consider the B (I A). Since the operator norm of A is 1/2, B psd with maximum eigenvalue at most 3/2 and minimum eigenvalue at least 1 1/2. The eggen-dccomposition of B implies that
B
(VAu))(AAu))
(29)
i=1
where max:=1,... A S 3/2, min:=1,.... A 1/2, and ||u,||2 1 for 1,...... d. We take Dayn == ( so that its points have Fuclidean norm at most / /3/2 < 2. Using equation 27 have that,
Lmse (Dsup fe) ( Bv, = (1/ + Avv),, = (1/4) v; 1
t I..... (30)
The first condition equation didirectly follows from equation 28 and equation 30 To see the second
@quattonnddirretlly condition, choose vo to be the cigenvector of A corresponding to its maximum magnitude eigenvalue which is 1/2. Then,
L (Daup, fo) = 01 (1/o) vv
(31)
which along with equation
28 implies that
Sup msse tramn syn fo) = ((1/g) - (1/2) v3 -163))))== 1/(4g2).
proving the second condition of equation 6 as well.
E PROOF OF THEOREM
For of notation, will use O() notation absorb absolute constants in the proof below. For convenience, like the case supervised regression case, we shall homogenize the Bellman loss follows. Let us define ((8, r) (h,,...,aa (., where dis, a) (l1,-.. ... la). Note that
20

---

since Ø [dd,, Bb) B(dg. Bo) (dd, B). have Ç B(do, Bb) x [cg.. Bu) x [0. Rmax
Bgg, B R. We also define a class of functions Q mapping Bido, Bu) x Bidy. Bu) x [0, Rmax to R where each h E Q is given by h(s,a,r) == r ((s, r) for some R+ Let Q1 be the restricted class where ||||| $
Note that for any f E Qo given by f(s,a) v (T taking (U1,.... vd -X) yields that E Q and h(s, r) = f(, a) - dr, and f(8', a²) = h(s', a', 0). Thus, we define another version of the Bellman loss as:
Bell h) == B(Oann)) [ (M(s.ar)) - max max M('',
27
(32)
o'EA
Using this we can see that, for f - Qo where f(s,a) == wTsss taking r = (VI,..., Cd -1) and h(s, a) = r a() we obtain that Q1 and
Lean( () (D,
(33)
Further, for some (S) E H, where [8, a) == v vTo(s, letting r (vi,..., Ud, Ud, -A) and a(s,a,r) :=
: r- a,, we obtain that h E and
Lee (D, LBee( h).
(34)
Thus, by abuse of notation, we think of h pling r E N(0, 1)d+1. We shall use to denote d + in the rest of this sec- the given training dataset, and for D
being chosen randomly by sam-
tion. We fix Dort {(st, Ti, < {(8;, àe, Pi, 8)) B(da, Bo) B(do, Bo) [0, Rmax] B(do, Ba) define:
Bell (Drd D,h) (T-nen( (Dort Prain:
h) - Imaan (Tan((()))))) hi)
(35)
It is easy to using the norm bounds and equation 32
equation
35| that for any h E Q1. D, 256 + Rmax)*
Teaa D, h), Tueal Dod h) 16(B B Rmux)² and īer Dort train:
E. PROBABILISTIC LOWER BOUND FOR FIXED h AND I
We fix for this subsection h Q1 and Ó as above. First we prove the following lemma.
Lemma E.1. If Law (Darl trin: D,h) 2 A, then over the choice of g E H, s.t. g(s, a. = r
Pr ( fig
(Dad
(Ded ani D.g) A/8) (|]rl12 s <2)> (Vd(B B + R )4))
A
(eid)
(36)
where 0j > 0 a constant.
Proof. Let correspond to the vector er E gd-1 where || = and < 2. Thus, random E (0, 1)d+1 corresponds of Hr where NO0, 1) and (0, 1)d are independently sampled and H is a (d + 1) x d matrix of unit norm columns which are a completion of to orthonormal basis. From the above upper bound, we have that Lev (D train D, h) 256(B B + Rmax)*
and therefore, < 256(B + Rmax).
Let us condition on the event that ||o (coA/(Vd(B + Rmax)*)) and a E (1.3.2]. Firstly,
since (cnA/(VV(B Rmmx) O(1), by the properties of the standard Gaussian distribution, one obtains that
A
oid
Pr[E] >
(37)
Vd(B + Rmax) )4)
21

---

for some ej depending eu only. Now, & implies that |Hr] 2 for which we choose co > 0 small enough. Since a > under this implies that
(cAA/(B - Rmax)
0.1
g(ss a.r) - max g(s' ((s',d',))
d'EA
(at Hon++H))oa
max HF) c(s',,' (())(aff)))(((6.d0
d'EA
af'((s,a,r) - max af d's','', Qu(( + Remas)
a'EA
2
at [at"<(s, - ary m <(s' a', O(v(B + Rmmxs)
a'EA
ar ((s, ary
ony maxi m + Olv(B + Rmax))
d'Ed
(38)
where we used the upper bound on a. Thus, using analysis similar to the proof of Lemma C.3 we obtain that for some choice of Go >> small enough, & implies that
Ler (Dod D.g) - a LBe (Dod D, (h(ha))
< A/64
(39)
and since a and and è S 2, we have a Lee (Derl train D, (h/2)) 2 A/16. Thus,
Lem Dori train D.g) 2 3/2
(40)
Moreover, since |Hi]l 0.1 and 3/2], obtain that |||||2 S 2, which completes the proof.
The following amplified version of the previous lemma a direct implication.
Lemma E.2. Let Len (Dorl
D, h) 2 A. Then, for iid random . 99t ~ H. s.1. g,(s,,r))
r ((,,,,)) we have
Pr
V
((
[ eI Bell
DDor
train
D,9,) 2 A/8) A (11rl11 (11r)lla=21
22) 21-(11-
(Vd(B + Rmax) ())
A
(oid)
E.2 NET OVER PREDICTORS AND SYNTHETIC DATASETS Dord
First we shall construct net over predictors h E Q1, where 1(x) = ((x a. for some B(g,2), 2). Thus,
consider the Euclidean net T(g, 2, {)) and let Q (n Q 38 T(g, 2. 2) s.t. fi(x, r) == FT((s, r) for some parameter ç (0, 1) to be chosen later. The
proof of the following simple approximation lemma is exactly along the lines of the proof of Lemma
and the analysis the previous subsection accounting for the error in the max term of equation 32
which is handled similarly.
Lemma E.3. For any Dert and D as defined in the previous subsection, for any h E Q1 3h Ộ
s.f.
Lggn (Dert D, h) Lignt
(Dort train D. < 300g + Rmmx)*
(41)
The argument for net over the synthetic dataset is similar we show that the synthetic data Dor can be approximated with a much smaller dataset Ò whose points are from discrete set.
Lemma E.4. Fix a T,V E 10. For any Dorl there exists a dataset ò of size s (where p is the pseudo-dimensian in Sec. 4) whose points (8, à, P, 8') are s.I. s. a, 8' are from the Euclidean net T ((do. Bu, vl Rmax) Rmax)/(10L) and & E T(1, Rmaxs v(B B Rmax)) such that for any h E 21.
igg Dert D))) igg (Dod Dorl 1i) s O(TTB + Rmax) + v(B + Rmax) (42)
22

---

Proof. Since p is the pseudo-dimentn is defined in Sec. 4. it is also the pseudo -eeunn-dimensoon on the class of functions V given by LBe (ss. a, r, )) h) for h E Q1. Thus, Let first define D
probabilistically to be a set of := ((pp ((pp/²2) (g((1))) points independently and u.a.r. sampled from Dort Using the upper bound on A (r/16, V, 21) from Chapters 10.4 and 12.3, and Theorem 17.1 of [Anthony-Bate Barttettt 2009], we get that for any E 21.
Lnall (2,)) Tn (D h) s 16r(B (B+ Rmax)*
(43)
with probability at least O. Thus, using the above and arguments similar to those used earlier in this and the previous sections we obtain that there exists D of size s.t.
Lar (Darl frain h) L (Drdl iainn Dert h) - O + Rmax)*)
(44)
Lastly, to get D we replace each (8, (,, in D with the nearest point in the net Ti
T(do, vo, v Rmax)/ (m0L) x T(dg, Bo, PBB (mmx)((00)) x T(1, Rmax, D(Bx,,(BB (B Rmax) ))) X T(d. Bo, ((B + Rmax) (10L)). Using the Lipschitzness bound of L on ø and the analysis used in the proof of Lemma
C.4. we obtain that,
Ten (Dodl h)
Rell Irain D. s 5(v(lB + Rmax)")
DDod
(45)
Rell Irain
Combining the above inequalities completes the proof.
E.3 UNION BOUND AND PROOF OF THEOREM 4.3
We take T and to be O + Rmax)*), so that applying Lemmas E.4 and E.3 yields, Lemma E.5. For any 21 and Deel there exist h E 21 and D (Ti)² such that
ien (Dod Dod h) - Lgen (Dad minn D, h) = C'A
(46)
where C' > O is small enough constant and : as defined in the previous subsection.
// some constant C1 and Q
Now, the size of the net bounded follows:
() E
G.
dot
@ x TT 6
v(B + Rmax)
=exp (q logolo( + Romax) / /A) loplog(( (B + Rmm))/A) =: (47)
(-cid)
Now, using the above, we take k (+d(B+RRmn)) 1T) union bound over the net (along the lines the proof in Sec. C.3). get back the lower bound with Dar we apply Lemma E.4 to 9, such that Ir,1 < 2 i.. gj E Q1 This completes the proof.
A
(log(1/0) in Lemma E.2 and apply
F PROOF OF THEOREM 4.4
We can use elementary manipulation of Ter based on (TT) and the additive state-action embedding to essentially remove the max term and the subsequent proof is along the same lines as that of Theorem
have ((8 vo a) = v (s) (zz(a)) as defined, so notice that
fax a') T (1(5')) + maxv 62(a') d'EA
max
(48)
o' e'E.A
In 488.. m voz(aa))) is a constant independent of the training and synthetic dataset and depends only v, define a(v) = max.'eA v Φ22(a)). Expanding within the outer square,
23

---

canceling and zeroing using mild linear condition 11 and equation 48
obtain
Ball (Dui
train
syn ()
= -(M(saraa) min
[f(s, () Ar max [(5 a²))²] a'EA
((s.nss)) Dmm
(f(s,a) -Ar mmx f(s', 2²))
= (B.aann'))) man
01(() + v v' - Ar 7v x1'))(s)) >a(v))
((s,,, Deal
( - dr ()))) ))()))3
(B.,.. Del
Ar 7a(v))
((( Dell [(v (di(s) 701(5)) Ar 22)
= -IE (s.,,,,,))) De man
(01(s) -
=rr
((s.a,,;))) [(v (b) 701(6)) 02 Ar)
+ (( 1m
[v²a((v]] - [
2E (s,a,,,,))) Dec
ha(vv(v 7701(8)) 02())) - Ar]]
+ 2E (s,, Dm
hv(v)(v
(01(s') + Φ2(a)) Ar)))²
( Pi
(v -701555)) o2(a)) Ar)
-B(ss.,,,s') Ded [[v (0)(s) (5) o2(a)) 11)
(49)
Now notice that the loss term 49) looks exactly like the linear supervised regression loss Let We can concatenate v and À to get regression vector r. In addition, we take the feature vectors x to be simply (1(() - 701 (s') + (a and the regression label y to be Note that x S O and lvl S Rmaxx
We can sample regressors (O, 1/ 1)) u.a.r. and use the concatenation trick before. The nets will be taken over the embeddings of states and actions instead of the states and actions themselves. Thus, via analysis similar the linear regression case (Theorem O (de log ((( B + Rmax)/ / A) log(1/8)) upper bound on the number of sampled predictors, given that the synthetic dataset satisfies the mild linear condition above.
we obtain
F.1 CONVEXITY OF THE OBJECTIVE
As seen above, eer reduces to the supervised regression case with )) ( + Φ2(a) as the regression point with regression label r, corresponding to (s, a, optimization objective in the supervised regression case is convex in the synthetic data regression points and labels.
r, s'). From Appendix G.2 the
Therefore, if Φ1 and de are linear in (,,,,,,s) then the pen is also convex in the points of Dort Further, the condition equation 11 is also an affine linear constraint on the points of Dorl and therefore the optimization is convex.
syn
G USEFUL TECHNICAL DETAILS
G.1 BELLMAN LOSS RISK BOUNDS
The value gap i.c., the difference between the true and estimated value functions for a policy corresponding to Q-value predictor can be estimated by the latter's empirical Bellman Loss on offline data. This holds under under a certain concentrability assumption informally it states that the dataset should contain all state-action pairs which reachable from the starting state with significant probability, should also be present with sufficient probability in the dataset. We refer the reader to Assumption and Lemma 3.2 of (Duan al. 2021) for more details.
24

---

Table I: Homogeneous Linear Regression MSE loss over white and red wine quality data
wine color
N syn
D rnin
Dayn 0.85 + 0.20
D
Diev
20
1.82 + 1.22
1.21 + 0.45
red
50
0.65 0.04
0.65 0.07
0.97 = 0.22
0.80 0.08
100
0.67 + 0.05
0.81 + 0.16
0.73 + 0.07
20
1.00 = 0.21
1,81 = 0.44
1.31 0.30
white
50
0.74 + 0.04
0.82 0.17
1.04 + 0.19
0.90 + 0.11
100
0.75 0.02
0.83 + 0.05
0.84 + 0.05
G.2 CONVEXITY OF L mso (Drpp Irain: Dayn J)
train f') is constant w.r.t. Dayn and the dependent part is Timse (Dayp f)- The latter is the mean squared error loss which is the average of squares of linear functions of the points of Deyn and is therefore convex in the points of D Since L m (Dimp Days f) is convex in LrsseDDyv) syn f). it is also convex in the points of D
From equation| Tensse Dup
Lisse (Daup,
Now, if Φ is linear in (s, a) (the concatenation of and a), then ( syn: f, A) (from equation
is sum of squares of terms which are each the difference of (i) linear function in the points of Ded syn and, (ii) the maximum over a A of linear functions of the points of D Since max (over fixed number of arguments) is convex function over its vector of arguments, this implies that Be Ded f A) is convex and therefore î. Bel DDol Dort J, A) is also convex.
main
H ADDITIONAL EXPERIMENTS
H.1 ADDITIONAL EXPERIMENTAL DETAILS FOR THE WINE QUALITY DATASET
The red wine dataset has 1599 wine samples and the white wine dataset has 4898 wine samples. For both red and white wines, we use the feature QUALITY the label and regress on the remaining 11 features. We pre-process the data by standardizing each feature column and label. We randomly shuffle the samples into an 80/20 split into training and test data.
We use a linear homogeneous model (i.e. f(x) = rrx x) for regression on the label. We sample 100 linear regressors from the standard normal distribution as well Neval 100 another regressors from the same distribution. Using a fixed learning rate of 0.01 on the Adam optimiser and at most 5000 steps, we optimize the randomly initialised synthetic data until the objective has minimum value on the Neval 100 regressors. The model is then trained on the four datasets using Adam optimizer with a learning rate of 0.001 and the mean loss is reported Table [
We observe that model trained on Dayn performs better than ones trained on both Drand and Drev- We also observe that the test loss of a model trained on Dayn decreases, as expected.
H.2 ADDITIONAL EXPERIMENTAL DETAILS FOR THE THE BOSTON HOUSING DATASET
The Boston Housing dataset has 506 samples. We use the feature MEDV (Median value of owner- occupied homes in 1000's) as the label and regress on the remaining 13 features. We preprocess the data by standardising each feature column and label. We randomly shuffle the samples into an 80/20 split into training and test data. The sizes of the synthetic dataset N we consider are {20, 50, 100).
We take A 100 random homogencous linear regressors in Algorithm 1. Using fixed learning rate of 0.01 on the Adam optimiser and at most 5000 steps, we optimise the randomly initialised synthetic data until the objective has minimum value the Neval 100 randomly sampled regressors. The model is then trained on the four datasets using the Adam optimiser with a learning rate of 0.001. The mean test loss of models trained on respective datasets (over 10 trials) are included in Table
We observe that a model trained on D Dayn performs better than one trained on Drand and on par with Diev- We also observe that the test loss of model trained on Dan decreases, expected.
25

---

Table 2: Homogeneous Linear Regression MSE loss over Boston Housing data
N syn
D train
Dyyn
Drand 1.77 + 1.71
Diev
20
0.57 + 0.23
0.57 = 0.20
50
0.27 + 0.05
0.40 0.14
0.44 0.16
0.38 = 0.08
100
0.29 + 0.07
0.29 + 0.08
0.36 + 0.09
Table Homogeneous Linear Regression MSE loss over California Housing data
N Nyyn
Drrain
Dayn 1.11 = 0.27
Drand
10
0.99 + 0.05
20
1.13 0.33
0
50
0.56 + 0.05
1.16 + 0.30
0.73 + 0.06
100
1.16 + 0.71
0.73 + 0.07
200
0.94 = 0.38
0.69 = 0.02
H.3 ADDITIONAL EXPERIMENTS ON THE CALIFORNIA HOUSING DATASET
For the supervised case we propose to add experiments on the California Housing dataset (Pace Barry 1997) which has around 20K points and 9 features. The dataset distillation is done using linear models, while the training and evaluation is done using a (10, 10) two hidden layer ReLU based neural network, demonstrating that our synthetic data generation process can in practice be used with different model architectures for evaluation. We sample k = 100 random linear models for distillation.
We see from Table 3 that our distillation technique significantly outperforms random sampling and achieves 200-factor compression, even on large datasets like California Housing.
H.4 ADDITIONAL EXPERIMENTS AND DETAILS FOR THE CARTPOLE ENVIRONMENT
In this environment, pole attached by an un-actuated joint cart, which moves along a frictionless track. The pendulum is placed upright on the cart and the goal is to balance the pole by applying forces in the left and right direction on the cart. The action indicates the direction of the fixed force the cart is pushed with and can take two discrete values. The observation is an array with shape (4,) with the values corresponding to the positions and velocities. The episode terminates the pole angle position goes beyond certain range and is artificially truncated after 500 time-steps.
Since the goal is to keep the pole upright for as long as possible, by default, a reward +1 given for every step taken, including the termination step.
We sample n = 10000 steps of completely random policies in this environment to get D which contains both terminated and non-terminated states. We separate them into D Duain-terminatee and Dmain nnterrinnterm We have to do this in our implementation as the theoretical result only analyzes infinite horizon MDP's. In practice, the q-value function for the terminated states does not have any max term as the trajectory ends there, i.c. for a terminated state Sterm. the q-value is simply the reward, so we use f (Sterm, a) r. We use our data distillation routine to get a distilled version of each of these datasets separately and combine them together to get D Deyn-eenteeee + D Dyy sen-teemminttedd = Dayn- Note that the ratio of the terminated and non non-terminated states Dayn and Darain is artificially kept the same and we take the total size of the synthetic dataset Day to be Nayn-
Our model architecture for this experiment fixed 2-layer (10,10) ReLU based neural network. For the synthetic data generation, we sample & models and we use the Adam optimiser and perform search over the learning rate among (3e-1, 1e-1, 1, 3e-2, 1e-2, 3e-3, 1e-3, 3e-4, 1e-4) for the distillation processes of both the terminated and -entmmmminteed states and report the synthetic dataset that performs the best on evaluation.
We train the three datasets using the Fitted-Q iteration algorithm that iteratively optimises the Bellman loss to get a v-value predictor. We test the optimal policy corresponding to the v-value predictor on the real environment and report the returns. We report extensive evaluation with multiple values of k, Nayn in Table We observe that on average, policies trained on our generated synthetic data perform better than both real and random data. As expected, we see that the size of Dayn
26

---

increases (i.e. Nyn increases), the model trained on it performs better. Surprisingly, increasing the number of randomly sampled action-value predictors &t does not seem to have a discemnble impact on performace.
Table 4: Extended Evaluation for the Cartpole Environment with (10, 10) -lyyer NN.
Nyyn
Dirain
Drand
D
10
339.10 = 132.07
13.50 = 0.67
500.00 = 0.00
10
10
332.70 129.18
13.90 = 0.54
500.00 0.00
20
10
416.30 = -33.773
13.50 = 0.50
455.40
+ 133.80
50
10
343.10 129.38
13,40 0.66
181.00 21.87
100
10
368.20 + 116.77
13.30 = 1.19
464.00 108.00
20
332.10 + 117.26
135.20 - 41.38
500.00 0.00
10
20
377.20 122.43
148.20 = 43.15
240.50
212.56
20
20
348.50 = 144.20
141.30 = 70.23
500.00 0.00
50
20
325.80 139.27
146.60 = 36.67
500.00 0.00
100
20
324.60 + 124.09
145.30 = 48.06
450.00 + 130.99
50
339.80 139.34
174.60 = 11.71
500.00 = 0.00
10
50
346.70 = 128.98
174.50 = 12.89
500.00 = 0.00
20
50
341.80 = 123.77
172.40 = 19.69
500.00 0.00
50
50
330.10 = 120.47
177.80 = 10.39
500.00 = 0.00
100
50
326.00 + 151.14
178. 10 17.01
500.00 0.00
100
337.70 115.30
135.90 = 76.44
500.00 0.00
10
100
329.00 + 122.08
148.40 + 104.72
500.00 + 0.00
20
100
328.90 124.00
124.10 = 47.61
500.00 0.00
50
100
332.20 = 123.10
129.50 = 61.10
500.00 + 0.00
100
100
386.40
132.20
136.30 = 93.81
500.00 0.00
200
354.00
126.69
158.40
53.20
500.00
0.00
10
200
331.90 + 130.53
169.90 + 93.20
500.00 0.00
20
200
371.20
133.87
176.60 = 81.36
500.00
0.00
50
200
332.80 = 125.28
175.60 = 62.60
500.00 - 0,00
100
200
340.60 144.32
199.20 97.88
500.00 0.00
H.5 COMPARISION AGAINST BEHAVIOR CLONING DISTILLATION
Behavior cloning (BC) based approaches (like those of Lei al. (024)) Light et al. (2024) do work well on datasets generated by non-expert policy. On the other hand, the Cartpole dataset used our paper was generated by a completely random policy. Nevertheless, we propose to demonstrate this empirically by adding the following experiments comparing the performance of our method with the BC loss based distillation from (Light et al. 2024). We observe that BC on the full training data well as the synthetic dataset created using the algorithm from (Light et al. 2024) perform much worse than our techniques as the former do not take rewards into consideration. This demonstrates the dependence data quality of BC based distillation approaches and the effectiveness of our method.
Evaluation on the Cartpole Random Dataset of 10K transitions, comparing against BC and BC on synthetic data generated by (Light et al. 2024 with k = 100 sampled models is shown in Table
Table 5: Cartpole Random Dataset, comparing against BC on full training data and BC Light et al. 2024)
Nsy
Derain
D D
Day
BC
BC
368.20 +: 116.77
13.30 + 1.19
464.00 + 108.00
17.50 + 5.46
13.30 + 1.68
20
324.60 + 124.09
145.30 + 48.06
450.00 + 130.99
19.30 9.17
13.50 + 5.14
50
326.00 = 151.14
178.10 : 17.01
500.00 0.00
28.30 - 14.95
17.10 12.86
100
386.40
+ 132.20
136.30
1.300::0 93.81
500.00 + 0.00
26.00 + 13.51
14.20 + 4.02
200
340.60
+ 144.32
199.20 + 97.88
500.00 0.00
17.60 + 6.87
22.90 + 8.46
27

---

H.6 ADDITIONAL EXPERIMENTS AND DETAILS FOR THE MOUNTAIN CAR ENVIRONMENT
The Mountain Car MDP (Moore 1990), Towers et al. (2024) MIT License) is a deterministic MDP that consists of a placed stochastically the bottom of sinusoidal valley, with the only possible actions being the accelerations that can be applied to the car in either direction. The observation space continuous with two dimensions and there are three discrete actions possible. The goal is to reach the flag placed on top of the right hill as quickly as possible, as such the agent is penalised with a reward of 1 for each timestep. The episode truncates after 200 timesteps and is also terminated the position of the car goes beyond a certain range.
To generate the offline data, we sample 5000 samples through a uniformly random policy and another 5000 samples through an expert policy trained using tabular g-learning on a discretized state space.
We use the same learning rate search method as mentioned Appendix H.4 and optimizers to get the synthetic data, partitioned into terminated and non-terminated samples. We use neural network with two hidden layers with 64 neurons and ReLU activations for the g-value predictor with the Fitted-Q iteration algorithm for training. Policies trained on the three datasets are evaluated in the environment and the average returns over 10 trials are reported in Table We observe that the policies trained on the random datasets not able to reach the top of the hill and are all truncated. Policies trained on the synthetic data are on average able to reach the top of the hill, albeit slower than ones trained on the full offline dataset. As in the Cartpole environment, increasing Nayn increases our performance, but increasing k as no impact on performance.
Table 6: Evaluation for Mountain Car with (64, 64) NN.
Nay
D
Drand
Dayn -200.00 = 0.00
5
10
-111.40 + 13.16
-200.00 + 0.00
10
10
-109.80 + 27.92
-200.00
0.00
-200.00 = 0.00
20
10
= =
-200.00 + 0.00
-157.70 2.28
50
10
1
-200.00 + 0.00
-200.00
= 0.00
100
10
1
-200.00 + 0.00
-195.90
+ 8.28
5
50
100.30 + 15.49
-00.000 + 0.00
-183.90
+ 24.61
10
-104.80 15.14
-20..00 0.00
-200.00
0.00
20
50
104.50 + 13.97
-200.00 + 0.00
-129.50 30.31
50
50
-00.990 + 16.26
-200.00 + 0.00
-162.60
17.24
100
50
106.90 = 14.45
-20..00 + 0.00
1.59000
5
200
-109,80 + 16.02
-200.00 + 0.00
-149.60 25.39
10
200
-108.50 = 18.70
-200.00 + 0.00
20
200
-105.40 = 14.71
-200.00 + 0.00
-121.90 37.87
50
200
-112.60
= 14.99
-200.00
= 0.00
-132.00 23.00
100
200
105.30 + 14.16
-200.00 + 0.00
-162.90 + 32.98
H.7
ADDITIONAL EXPERIMENTS AND DETAILS FOR THE ACROBOT ENVIRONMENT
The Acrobot Environment (Suttonn 1995), Towers et al. 2024) MIT License) consists two links connected linearly to form a chain, with one end of the chain fixed. The joint between the two links is actuated. The goal is to apply torques on the actuated joint to swing the free end of the linear chain above given height while starting from the initial state of hanging downwards. The action space is discrete with three possible actions and the state space is continuous with 6 dimensions. The goal is have the free end reach a designated target height in as few steps as possible, and as such all steps that do not reach the goal incur a reward of -1. Achieving the target height results in termination with a reward of 0. Episodes are artificially truncated after 500 timesteps.
To generate the offline data, we sample 10000 transitions through a uniformly random policy. We use the same learning rate search method and optimizers as mentioned in Appendix H.4 to get the synthetic data, partitioned into terminated and non-terminated samples. We use neural network with two hidden layers with 64 neurons and ReLU activations for the value predictor with the Fitted-Q iteration algorithm for training. Policies trained on the three datasets evaluated in the environment and the average returns over 10 trials are reported in Table 7 We observe that polices trained on the synthetic data give higher returns average than policies trained on the full offline dataset and
28

---

randomly subsampled smaller dataset. As in the Cartpole environment, increasing Nyn increases performance, but increasing k as no impact on performance.
Table 7: Evaluation for Acrobot with (64, 64)- NN.
k
Ng
Drain -84.20 + 10.82
Drnnd -500.00 + 0.00
Dayn
5
10
-74.10 7.49
10
10
-82.30 + 12.04
-500.00 + 0.00
-74.60 9.65
20
10
-81.30 + 4.86
-500.00 + 0.00
+
50
10
-84.60 + 11.88
-500.00 + 0.00
-72.70
100
-84.20 16.61
-500.00 = 0.00
-74.40
5
50
-85.10
10.97
.779.00
-75.00
10
50
-83,40 + 11.24
4
-77.40
20
50
-82.60 8.85
-4.1.50
-9.480
50
50
-85.50 9.45
+
7 8.80
100
50
-83.30 + 13.24
484.70 30.60
-75.00 10.24
5
200
-85.60 = 7.23
103.30
-89.10
10
200
-33.00 11.07
.99.00
10.74
-86.90 20.87
20
200
-82.40 8.97
+
18.20
50
200
-86.90 5.26
-102.50 4.20
+
100
200
8.5.
-102.30 + 9.96
-84.50 13.40
29


Reviews:
[{"review_id": "rDb425zHej", "reviewer": "Reviewer_3Mno", "summary": "The paper tackles supervised regression and offline RL settings by constructing synthetic datasets that preserve the original objective of training with original training dataset. It introduces a loss-matching method using randomly sampled linear regressors/Q-value predictors achieving Õ(d^2) sampling guarantees for regression (alongside a matching Ω(d^2) lower bound) and exp(O(d log d)) in offline RL (furthermore relaxed Õ(d^2) under decomposable feature maps). The approach shows solid empirical performance on standard regression datasets and classic offline RL benchmarks, and offers a timely theory-first approach for distillation.", "questions": "- na -", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The use of loss-matching method using randomly sampled linear regressors/Q-value predictors is particularly important tool that is used in RL literature. \n- Two results for each setting look comprehensive as contributions to the learning community.\n- Experiments demonstrate that small synthetic sets and few sampled models can perform competitively on standard regression datasets and classic offline RL benchmarks.", "weaknesses": "- Even though experiments demonstrate that small synthetic sets match the performance when trained with entire training dataset, some issues pop up:\n- - This phenomena cannot be explained by the current theory. The distillation problem is only interesting for the case $n>>m$. This is also the focus of the literature (Light et al. 25, Lei et al. 24) cited by this work.\n- - Lemma C.4 does provide net arguments for the choice of synthetic dataset size. But it seems that both $m$ and $n$ are proportional to $d$, whereas the dependence on $\\epsilon$ for $m$ is unclear.\n- - The training size for toy sequential decision problems are high. I suggest authors to really use established benchmarks like D4RL to demonstrate their distillation behavior.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ToQIoagaiQ", "reviewer": "Reviewer_Ham7", "summary": "This paper introduces a dataset distillation method for supervised regression and offline RL that matches the loss on the original and synthetic datasets with respect to a fixed set of randomly sampled models, avoiding bi-level optimization. The key contribution is a theoretical guarantee that only $O(d^{²})$ sampled linear regressors are needed for the supervised case, with a matching lower bound. The experiments demonstrate its effectiveness.", "questions": "1. Could the authors discuss potential pathways for extending the theoretical guarantees to non-linear function approximators, such as neural networks? Note that I'm not asking for additional experimental results, just want to have a discussion, since making a more constructive theoretical analysis on non-linear functions is more feasible and practical for most real-world cases.\n2. For the offline RL setting, how restrictive is the decomposable feature map assumption in practice?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides theoretical guarantees for dataset distillation, an area where such analysis is often lacking. The upper and matching lower bounds for the supervised case are particularly compelling.\n2. The experiments adequately support the theoretical claims, showing that the method works well in practice, even with non-linear neural networks, and outperforms baseline approaches like random subsampling.", "weaknesses": "1. The empirical evaluation is limited to relatively small-scale datasets and standard RL benchmarks. A more extensive evaluation on larger-scale or more complex datasets would strengthen the claims of practical efficacy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VHEo2HqECK", "reviewer": "Reviewer_4Kx3", "summary": "This paper proposes a dataset distillation algorithm by matching the losses between training and synthetic datasets without introducing extra model training. The authors develop and analyze a method for supervised learning and offline reinforcement learning, where only $\\hat{\\mathcal{O}}(d^2)$ regressors are sufficient to ensure the MSE loss of any bounded linear model is approximately preserved. They also provide a matching lower bound of  $\\Omega (d^2)$, establishing tightness. Furthermore, the authors extend the algorithm beyond supervised learning, i.e., offline RL, by leveraging the next state and reward information in the dataset to match the Bellman loss rather than the behavior cloning loss. Extensive theoretical analysis and supplementary experiments prove that the proposed method efficiently distills the synthetic dataset from the training dataset without relying on auxiliary techniques-additional classifier training.", "questions": "- What would be the major bottleneck when extending the proposed method to a non-linear function approximator (i.e., neural network) with offline RL?", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well structured and addresses comprehensive details.\n- Extensive theoretical proofs concretely support the main claim.\n- Experiments demonstrate that the proposed method shows a clear margin compared to other baselines, recovering near-optimal or even outperforming performance.", "weaknesses": "- The experimental section appears relatively narrow, focusing on small regression settings with Gym control tasks. Comparing with other baselines (Lei et al. 2024, Light et al. 2024) for generating synthetic datasets would improve the soundness of the suggested method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)