Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model
This provides theoretical guarantees for SGD in noiseless settings, which is incremental as it extends existing analyses to specific regularity conditions.
The paper tackles the problem of analyzing convergence rates for stochastic gradient descent under a noiseless linear model, showing that convergence to the optimum and generalization error decay follow polynomial rates dependent on the regularity of the optimum and feature vectors, with applications to function estimation and gossip algorithms.
In the context of statistical supervised learning, the noiseless linear model assumes that there exists a deterministic linear relation $Y = \langle θ_*, X \rangle$ between the random output $Y$ and the random feature vector $Φ(U)$, a potentially non-linear transformation of the inputs $U$. We analyze the convergence of single-pass, fixed step-size stochastic gradient descent on the least-square risk under this model. The convergence of the iterates to the optimum $θ_*$ and the decay of the generalization error follow polynomial convergence rates with exponents that both depend on the regularities of the optimum $θ_*$ and of the feature vectors $Φ(u)$. We interpret our result in the reproducing kernel Hilbert space framework. As a special case, we analyze an online algorithm for estimating a real function on the unit interval from the noiseless observation of its value at randomly sampled points; the convergence depends on the Sobolev smoothness of the function and of a chosen kernel. Finally, we apply our analysis beyond the supervised learning setting to obtain convergence rates for the averaging process (a.k.a. gossip algorithm) on a graph depending on its spectral dimension.