Second-order stochastic optimization for machine learning in linear time

Naman Agarwal, Brian Bullins, Elad Hazan

Research output: Contribution to journalArticlepeer-review

120 Scopus citations


First-order stochastic methods are the state-of-the-art in large-scale machine learning optimization owing to efficient per-iteration complexity. Second-order methods, while able to provide faster convergence, have been much less explored due to the high cost of computing the second-order information. In this paper we develop second-order stochastic methods for optimization problems in machine learning that match the per-iteration cost of gradient based methods, and in certain settings improve upon the overall running time over popular first-order methods. Furthermore, our algorithm has the desirable property of being implementable in time linear in the sparsity of the input data.

Original languageEnglish (US)
Pages (from-to)1-40
Number of pages40
JournalJournal of Machine Learning Research
StatePublished - Nov 1 2017

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence
  • Control and Systems Engineering
  • Statistics and Probability


  • Convex optimization
  • Regression
  • Second-order optimization


Dive into the research topics of 'Second-order stochastic optimization for machine learning in linear time'. Together they form a unique fingerprint.

Cite this