acceptodds
Under review as a conference paper at ICLR 2027

Dynamic Sketching for Efficient SGD via Kernel Mean Approximation with Random Features

Abstract

Large-scale deep learning is often trained on highly redundant datasets, where many examples provide similar learning signals. This raises a natural question: can we reduce training compute by replacing full-data SGD with a small coreset that adapts as the model representation evolves? We propose DySk (Dynamic Sketching), a weighted dynamic coreset method based on loss-aware kernel mean approximation. At periodic refresh steps, DySk computes current representations and losses, builds a loss-weighted random Fourier feature sketch of the representation distribution, and selects a compact support by greedy residual matching. It then fits nonnegative simplex weights on the selected support and trains on the resulting weighted coreset until the next refresh. This yields a forward-pass-only refresh mechanism that tracks the evolving training distribution without requiring per-example backward gradients for selection. Empirically, DySk preserves accuracy while substantially reducing the amount of data processed by SGD, yielding a favorable accuracy–runtime trade-off against gradient-matching and other coreset baselines. We further provide ablations and a conditional sketch-to-gradient analysis supporting the empirical and theoretical behavior of DySk.

Primary area:
optimization
Keywords:
Coreset Selection, Training Acceleration, Random Fourier Features

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_ozhZOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Dynamic Sketching (DySk), a dynamic weighted coreset method for efficient neural network training. DySk periodically constructs a compact representation of the full dataset using random Fourier features, selects representative samples through greedy residual matching, and optimizes their sampling weights to approximate the full-data feature distribution. The selection process requires only forward passes, avoiding expensive per-example gradient computations. The authors provide a conditional theoretical analysis connecting sketch approximation to gradient approximation. Experiments on CIFAR-10/100 demonstrate improved accuracy and efficiency over existing coreset methods at matched subset budgets, while additional ImageNet-1k and Transformer pretraining experiments suggest broader applicability.

Critical strengths
  • The proposed method combines kernel mean approximation with dynamic subset selection, preserving representation-space coverage without requiring per-example backward gradients. This provides a computationally motivated alternative to gradient-based coreset methods while adapting to evolving representations during training.

  • DySk consistently outperforms the evaluated coreset baselines across multiple subset budgets on CIFAR-10/100, with particularly substantial gains at small budgets. These results provide meaningful empirical support for the proposed selection strategy.

Critical weaknesses
  • Figure 1, which presents the main experimental results, reports accuracy against nominal coreset fractions rather than actual computational cost. Since DySk dynamically refreshes its subset during training, the overhead of repeated full-dataset forward passes and subset selection is essential to evaluating its efficiency. Although Table 17 provides end-to-end runtimes, it reveals less favorable comparisons at matched computational budgets: on CIFAR-10, Random 20% outperforms DySk 5% at nearly identical runtime (92.07% vs. 90.74%), while on CIFAR-100, Random 20% is both faster and slightly more accurate than DySk 10% (71.29% vs. 70.99%). A more rigorous accuracy–runtime comparison across different subset budgets should be presented in the main paper. Furthermore, complete training-time measurements are provided only for CIFAR, leaving the claimed efficiency benefits on ImageNet and LLM pretraining insufficiently validated.

  • On ImageNet-1k, DySk-Core applies the proposed sketch-based selection to only 256 examples, while the remaining subset is constructed through class-balanced uniform sampling and trained with uniform weights. Despite this substantial simplification, DySk-Core slightly outperforms DySk-Direct, which implements the full weighted selection procedure. This raises concerns about the proposed greedy selection and weighting mechanisms at scale. In particular, the experiments do not sufficiently isolate how much of the improvement comes from kernel sketch matching versus class-balanced random sampling. Additional controlled ablations are needed to establish the contribution of the proposed components.

  • The LLM experiment evaluates only a relatively small 286M-parameter Transformer, without reporting full-data training performance or end-to-end runtime. Moreover, several essential implementation details are missing, including the training corpus, total token count, Transformer layer used to extract representations, and aggregation of token-level hidden states into sequence-level features. The results are also reported from a single run per configuration. These omissions limit reproducibility and make it difficult to assess whether the proposed approach generalizes to realistic large-scale LLM pretraining.

  • The theoretical analysis relies on the assumption that full parameter gradients can be approximated by a linear transformation of random Fourier features derived from penultimate-layer representations. However, the paper provides limited intuition or empirical evidence supporting this relationship for deep neural networks, where gradients also depend on labels and the Jacobians of earlier layers. Without characterizing the gradient-prediction residual or directly measuring gradient approximation errors, it remains unclear whether the theoretical bound provides a meaningful explanation for the observed performance.

Questions for authors
  • Could the authors provide accuracy–runtime curves comparing DySk with baseline methods across different subset budgets, including all warm-up, forward-pass, and selection overhead? In particular, how does DySk compare against random selection at matched wall-clock budgets? Could the authors also report complete end-to-end training times for ImageNet and LLM experiments?

  • Since DySk-Core selects only 256 examples through sketch matching on ImageNet and fills the remaining subset using class-balanced uniform sampling, how much of its improvement is attributable to the proposed sketch-based selection? Could the authors compare against a class-balanced random baseline under the same training protocol? Additionally, why does DySk-Core consistently outperform the full DySk-Direct method?

  • What training corpus, total number of tokens, sequence length, and validation dataset are used in the LLM experiment? Which Transformer layer provides the feature representations, and how are token-level hidden states aggregated? Could the authors provide end-to-end training-time measurements to substantiate the efficiency and scalability claims?

  • What motivates the assumption that random Fourier features of penultimate-layer representations can linearly approximate full parameter gradients? Could the authors empirically measure the gradient approximation error and investigate whether reducing sketch mismatch actually leads to better gradient matching throughout training?

Reviewer_TA9BOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes a method called DySk for training neural networks using a small subset of the training data: the contribution is it's selection and update without computing gradients for individual examples. Examples that represent the full dataset are selected using current representations, losses, random Fourier features.

The authors provide theory. Under assumptions these representations can help approximate the full gradient. They evaluate DySk on CIFAR-10, CIFAR-100, ImageNet, and language model pretraining. The results show improvements over random selection and several existing methods. The authors also study the effect of different components of the method.

Critical strengths

DySk achieves better accuracy than random selection and several existing methods on CIFAR-10 and CIFAR-100, especially on small subsets. The ablation studies also show that DySk performs better than a simpler method that selects examples based only on their losses.

Critical weaknesses

The main experiments compare methods at the same coreset sizes, but this does not necessarily mean the same computational cost. When comparing actual training time, random selection can achieve similar or even better accuracy. For example, on CIFAR-100, random selection with a 20% budget achieves 71.29% accuracy in 0.195 hours, while DySk with a 10% budget achieves 70.99% in 0.219 hours (Table 17). Since computational efficiency is the main motivation of the paper, I think stronger comparisons at the same runtime are necessary. The ImageNet and language model experiments also do not clearly demonstrate end-to-end runtime improvements.

The main theoretical result assumes that gradients can be approximated using sketch features, but the authors do not test whether this assumption holds in practice. The convergence analysis does not directly cover the default loss-weighted version of DySk without an additional bias term. The theoretical results also do not show that the proposed greedy selection procedure achieves a sufficiently small approximation error. I think the theory relies on strong assumptions and does not provide enough justification for the practical performance of the method.

Questions for authors

I do not have specific clarification questions. My main concerns are about the computational efficiency claims and the gap between the theoretical analysis and the proposed method.

Reviewer_pwmWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Dynamic Sketching, which is a forward-pass-only refresh procedure that matches a random-feature representation sketch. DySk is evaluated across image classification and language-model pretraining settings, and empirically preserves accuracy while substantially reducing the amount of data processed by SGD.

Critical strengths
  1. DySk demonstrates promising empirical performance with consistent improvements over the evaluated coreset baselines. DySk achieves higher accuracy with significantly lower reported runtimes.

  2. Controlled experiments in B.2 are really informative. The mechanism ablation demonstrates whether DySk's gains stem from representation-space coverage or forward-pass difficulty scoring and loss weighting

Critical weaknesses
  1. The evaluation on ImageNet-1K and Transformer pretraining lacks end-to-end wall-clock runtime comparisons against the baselines. This omission is notable given the substantial scoring overhead reported in Appendix E.3, where evaluating candidate batches required ~147–150 minutes per refresh. To substantiate the claimed computational efficiency at scale, authors should provide accuracy-versus-runtime curves for both ImageNet and Transformer experiments.
Questions for authors
  1. In Section 5.3, DySk-CORE completes the support by class-balanced uniform sampling. Does the baseline method Random-Warm use the same class balancing?

  2. Theorem 4.2 states that the gradient error can be bounded above by the sketch mismatch. Can the authors validate empirically by showing lower sketch mismatch corresponds to lower gradient error, so that the tightness of the bound can be established?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.