Stochastic Gradient Descent for Nonparametric Regression
This work addresses computational efficiency in nonparametric regression for data analysis, presenting an incremental improvement with specific theoretical guarantees.
The paper tackles nonparametric regression by introducing a stochastic gradient descent algorithm for additive models, achieving minimax optimal risk with careful learning rate scheduling across three training stages.
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 the dimensionality of the data and the size of the training sample. We also provide polynomial convergence rates even when the covariates do not have full support on their domain.