mlsanityData to 7 Oct 2026

Learning with SGD and Random Features

arXiv 1807.06343 ↗First posted 17 Jul 2018stat.ML cs.LGcited by 33

Not on the map. Why?

Abstract (arXiv)

Sketching and stochastic gradient methods are arguably the most common techniques to derive efficient large scale learning algorithms. In this paper, we investigate their application in the context of nonparametric statistical learning. More precisely, we study the estimator defined by stochastic gradient with mini batches and random features. The latter can be seen as form of nonlinear sketching and used to define approximate kernel methods. The considered estimator is not explicitly penalized/constrained and regularization is implicit. Indeed, our study highlights how different parameters, such as number of features, iterations, step-size and mini-batch size control the learning properties of the solutions. We do this by deriving optimal finite sample bounds, under standard assumptions. The obtained results are corroborated and illustrated by numerical experiments.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). First posted on arXiv 17 Jul 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 2; 2023: 6; 2024: 7; 2025: 6; 2026: 4.

33 papers.

Sort:

  1. 2024Scaling Laws in Linear Regression: Compute, Parameters, and Datacited by 54
  2. 2021Random feature neural networks learn Black-Scholes type PDEs without curse of dimensionalitycited by 34
  3. 2021Kernel Continual Learningcited by 27
  4. 2023Universal approximation property of Banach space-valued random feature models including random neural networkscited by 12
  5. 2023Non-Parametric Representation Learning with Kernelscited by 11
  6. 2023How many Neurons do we need? A refined Analysis for Shallow Networks trained with Gradient Descentcited by 10
  7. 2023Random Fourier Signature Featurescited by 9
  8. 2025Kernel ridge regression under power-law data: spectrum and generalizationcited by 8
  9. 2021A spectral-based analysis of the separation between two-layer neural networks and linear methodscited by 7
  10. 2024Random features models: a way to study the success of naive imputationcited by 7
  11. 2025Two-Point Deterministic Equivalence for Stochastic Gradient Dynamics in Linear Modelscited by 6
  12. 2021ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitionscited by 5
21 more
  1. 2021On the Double Descent of Random Features Models Trained with SGDcited by 5
  2. 2023Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalizationcited by 5
  3. 2021Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learningcited by 4
  4. 2024Universal randomised signatures for generative time series modellingcited by 4
  5. 2024Generalization Analysis of Online Stochastic Gradient Descent for Overparameterized Two-Layer Neural Networkscited by 4
  6. 2024Optimal Kernel Quantile Learning with Random Featurescited by 4
  7. 2025Random Feature Representation Boostingcited by 4
  8. 2024RandNet-Parareal: a time-parallel PDE solver using Random Neural Networkscited by 3
  9. 2025Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Datacited by 3
  10. 2021MetaKernel: Learning Variational Random Features with Limited Labelscited by 2
  11. 2022Coefficient-based Regularized Distribution Regressioncited by 2
  12. 2025Random feature approximation for general spectral methodscited by 2
  13. 2025SchoenbAt: Rethinking Attention with Polynomial basiscited by 1
  14. 2021Shallow Representation is Deep: Learning Uncertainty-aware and Worst-case Random Feature Dynamicscited by 0
  15. 2022Ridgeless Regression with Random Featurescited by 0
  16. 2023Random feature approximation for general spectral methodscited by 0
  17. 2024Macformer: Transformer with Random Maclaurin Feature Attentioncited by 0
  18. 2026Random Neural Network Expressivity for Non-Linear Partial Differential Equationscited by 0
  19. 2026Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networkscited by 0
  20. 2026Minimax-Optimal Generalization Bounds for Smooth Deep Neural Networks Trained by (Stochastic) Gradient Descentcited by 0
  21. 2026Stochastic gradient descent with initial regularizationcited by 0