%0 Journal Article %1 agarwal2016secondorder %A Agarwal, Naman %A Bullins, Brian %A Hazan, Elad %D 2016 %K optimization %T Second-Order Stochastic Optimization for Machine Learning in Linear Time %U http://arxiv.org/abs/1602.03943 %X 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.

@article{agarwal2016secondorder, abstract = {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.}, added-at = {2019-06-07T18:03:08.000+0200}, author = {Agarwal, Naman and Bullins, Brian and Hazan, Elad}, biburl = {https://www.bibsonomy.org/bibtex/271c9c6529175cc53348c2498c35692ea/kirk86}, description = {[1602.03943] Second-Order Stochastic Optimization for Machine Learning in Linear Time}, interhash = {6e34ffca72feb5a13a1ebf94dc69cad1}, intrahash = {71c9c6529175cc53348c2498c35692ea}, keywords = {optimization}, note = {cite arxiv:1602.03943}, timestamp = {2019-06-07T18:03:08.000+0200}, title = {Second-Order Stochastic Optimization for Machine Learning in Linear Time}, url = {http://arxiv.org/abs/1602.03943}, year = 2016 }