How to sketch a learning algorithm

• URL: http://arxiv.org/abs/2604.07328v1
• Date: Wed, 08 Apr 2026 17:46:06 GMT
• Title: How to sketch a learning algorithm
• Abstract summary: We present a data deletion scheme capable of predicting model outputs with vanishing error $varepsilon$ in the deep learning setting.<n>Our proof is based on an assumption that we call "stability"<n>In contrast to the assumptions made by prior work, stability appears to be fully compatible with learning powerful AI models.
• Score: 3.2654563317952205
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: How does the choice of training data influence an AI model? This question is of central importance to interpretability, privacy, and basic science. At its core is the data deletion problem: after a reasonable amount of precomputation, quickly predict how the model would behave in a given situation if a given subset of training data had been excluded from the learning algorithm. We present a data deletion scheme capable of predicting model outputs with vanishing error $\varepsilon$ in the deep learning setting. Our precomputation and prediction algorithms are only $\mathrm{poly}(1/\varepsilon)$ factors slower than regular training and inference, respectively. The storage requirements are those of $\mathrm{poly}(1/\varepsilon)$ models. Our proof is based on an assumption that we call "stability." In contrast to the assumptions made by prior work, stability appears to be fully compatible with learning powerful AI models. In support of this, we show that stability is satisfied in a minimal set of experiments with microgpt. Our code is available at https://github.com/SamSpo1/microgpt-sketch. At a technical level, our work is based on a new method for locally sketching an arithmetic circuit by computing higher-order derivatives in random complex directions. Forward-mode automatic differentiation allows cheap computation of these derivatives.

Related papers

• Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model [12.775038922010452]
  Modern machine learning models are optimized by optimizing high-dimensional non-dimensional empirical risk functions.<n>Within a simple supervised learning setting, we develop a precise picture of the empirical risk landscape.<n>We propose an approximate incremental message passing (ImAMP) algorithm and precisely characterize it.
  arXiv  Detail & Related papers  (2026-06-26T19:57:08Z)
• Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model [53.6316818897326]
  We propose a gradient-based algorithm for training a two-layer neural network in time.<n>We show that our algorithm learns a sparse representation that strongly aligns with the unknown signal $star$.<n>We extend our approach to the setting where $star$ is $k$-sparse for $k = o(sqrtd)$ by introducing a novel weight technique.
  arXiv  Detail & Related papers  (2026-06-13T09:34:39Z)
• Efficiently Learning Drifting Halfspaces with Massart Noise [50.4331323695175]
  We study the problem of learning a drifting concept in the presence of Massart noise.<n>In this framework, an online learner has access to a history of independent samples.<n>The goal is to output, in each round, a hypothesis with small prediction error.
  arXiv  Detail & Related papers  (2026-06-09T17:35:18Z)
• Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses [12.206530775105962]
  Machine unlearning is motivated by legal and user-facing requirements to remove the influence of individuals' data from trained models.<n>We prove upper and lower bounds on the excess population risk of approximate $varepsilon$-unlearning.<n>Our algorithm offers an exponential accuracy improvement over retraining the model from scratch.
  arXiv  Detail & Related papers  (2026-06-01T01:19:04Z)
• Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification [50.717692060500696]
  Next-token prediction with the logarithmic loss is a cornerstone of autoregressive sequence modeling.<n>Next-token prediction can be made robust so as to achieve $C=tilde O(H)$, representing moderate error amplification.<n>No computationally efficient algorithm can achieve sub-polynomial approximation factor $C=e(log H)1-Omega(1)$.
  arXiv  Detail & Related papers  (2025-02-18T02:52:00Z)
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Data Debugging is NP-hard for Classifiers Trained with SGD [8.449687092741604]
  We investigate the computational complexity of the problem named Debuggable. If the loss function and the dimension of the model are not fixed, Debuggable is NP-complete regardless of the training order.
  arXiv  Detail & Related papers  (2024-08-02T16:17:59Z)
• Aligning Model Properties via Conformal Risk Control [4.710921988115686]
  Post-training alignment via human feedback shows promise, but is often limited to generative AI settings. In traditional non-generative settings with numerical or categorical outputs, detecting misalignment through single-sample outputs remains challenging. We propose interpreting model alignment through property testing, defining an aligned model $f$ as one belonging to a subset $mathcalP$ of functions.
  arXiv  Detail & Related papers  (2024-06-26T22:24:46Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• Remember What You Want to Forget: Algorithms for Machine Unlearning [37.656345901739506]
  We study the problem of forgetting datapoints from a learnt model. We provide an unlearning algorithm that can delete up to $O(n/d1/4)$ samples.
  arXiv  Detail & Related papers  (2021-03-04T19:28:57Z)
• Learning to extrapolate using continued fractions: Predicting the critical temperature of superconductor materials [5.905364646955811]
  In the field of Artificial Intelligence (AI) and Machine Learning (ML), the approximation of unknown target functions $y=f(mathbfx)$ is a common objective. We refer to $S$ as the training set and aim to identify a low-complexity mathematical model that can effectively approximate this target function for new instances $mathbfx$.
  arXiv  Detail & Related papers  (2020-11-27T04:57:40Z)
• An Algorithm for Learning Smaller Representations of Models With Scarce Data [0.0]
  We present an algorithm for solving binary classification problems when the dataset is not fully representative of the problem being solved.<n>Our algorithm works by reconstructing up to homology the manifold on which lies the support of the underlying distribution.
  arXiv  Detail & Related papers  (2020-10-15T19:17:51Z)

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

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