Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model

In the context of statistical supervised learning, the noiseless linear model\nassumes that there exists a deterministic linear relation $Y = \\langle\n\\theta_*, X \\rangle$ between the random output $Y$ and the random feature\nvector $\\Phi(U)$, a potentially non-linear transformation of the inputs $U$. We\nanalyze the convergence of single-pass, fixed step-size stochastic gradient\ndescent on the least-square risk under this model. The convergence of the\niterates to the optimum $\\theta_*$ and the decay of the generalization error\nfollow polynomial convergence rates with exponents that both depend on the\nregularities of the optimum $\\theta_*$ and of the feature vectors $\\Phi(u)$. We\ninterpret our result in the reproducing kernel Hilbert space framework. As a\nspecial case, we analyze an online algorithm for estimating a real function on\nthe unit interval from the noiseless observation of its value at randomly\nsampled points; the convergence depends on the Sobolev smoothness of the\nfunction and of a chosen kernel. Finally, we apply our analysis beyond the\nsupervised learning setting to obtain convergence rates for the averaging\nprocess (a.k.a. gossip algorithm) on a graph depending on its spectral\ndimension.\n