Statistical sparse online regression: A diffusion approximation perspective

In this paper we adopt the diffusion approximation perspective to investigate Stochastic Gradient Descent (SGD) for least squares, which allows us to characterize the exact dynamics of the online regression process. As a consequence, we show that SGD achieves the optimal rate of convergence, up to a logarithmic factor. We further show SGD combined with the trajectory average achieves a faster rate, by eliminating the logarithmic factor. We extend SGD to the high dimensional setting by proposing a two-step algorithm: a burn-in step using offline learning and a refinement step using a variant of truncated stochastic gradient descent. Under appropriate assumptions, we show the proposed algorithm produces near optimal sparse estimators. Numerical experiments lend further support to our obtained theory.