# Stochastic Gradient Descent for Nonparametric Additive Regression

arXiv: https://arxiv.org/abs/2401.00691 · HTML: https://mlsanity.com/paper/2401.00691/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 32 references that are in the map.
- First posted on arXiv 1 Jan 2024.

## Builds on (most cited first, 9 of 9)

- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares](https://mlsanity.com/paper/1904.12838/) (2019)
- [Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression](https://mlsanity.com/paper/2110.06198/) (2021)
- [Scalable Kernel Methods via Doubly Stochastic Gradients](https://mlsanity.com/paper/1407.5599/) (2014)
- [The Benefits of Implicit Regularization from SGD in Least Squares Problems](https://mlsanity.com/paper/2108.04552/) (2021)
- [Parsimonious Online Learning with Kernels via Sparse Projections in Function Space](https://mlsanity.com/paper/1612.04111/) (2016)
- [A Sieve Stochastic Gradient Descent Estimator for Online Nonparametric Regression in Sobolev ellipsoids](https://mlsanity.com/paper/2104.00846/) (2021)
- [Optimal One-pass Nonparametric Estimation Under Memory Constraint](https://mlsanity.com/paper/2208.08668/) (2022)
- [Online Estimation with Rolling Validation: Adaptive Nonparametric Estimation with Streaming Data](https://mlsanity.com/paper/2310.12140/) (2023)

## Abstract (arXiv)

This paper introduces an iterative algorithm for training nonparametric additive models that enjoys favorable memory storage and computational requirements. The algorithm can be viewed as the functional counterpart of stochastic gradient descent, applied to the coefficients of a truncated basis expansion of the component functions. We show that the resulting estimator satisfies an oracle inequality that allows for model mis-specification. In the well-specified setting, by choosing the learning rate carefully across three distinct stages of training, we demonstrate that its risk is minimax optimal in terms of the dependence on both the dimensionality of the data and the size of the training sample. Unlike past work, we also provide polynomial convergence rates even when the covariates do not have full support on their domain.