Statistical sparse online regression: A diffusion approximation perspective

Jianqing Fan, Wenyan Gong, Chris Junchi Li, Qiang Sun

Research output: Contribution to conferencePaper

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages1017-1026
Number of pages10
StatePublished - Jan 1 2018
Event21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018 - Playa Blanca, Lanzarote, Canary Islands, Spain
Duration: Apr 9 2018Apr 11 2018

Conference

Conference21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018
CountrySpain
CityPlaya Blanca, Lanzarote, Canary Islands
Period4/9/184/11/18

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Statistical sparse online regression: A diffusion approximation perspective'. Together they form a unique fingerprint.

  • Cite this

    Fan, J., Gong, W., Li, C. J., & Sun, Q. (2018). Statistical sparse online regression: A diffusion approximation perspective. 1017-1026. Paper presented at 21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018, Playa Blanca, Lanzarote, Canary Islands, Spain.