%0 Journal Article %1 meng2019furious %A Meng, Si Yi %A Vaswani, Sharan %A Laradji, Issam %A Schmidt, Mark %A Lacoste-Julien, Simon %D 2019 %K computation interpolation optimization %T Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation %U http://arxiv.org/abs/1910.04920 %X We consider stochastic second-order methods for minimizing smooth and strongly-convex functions under an interpolation condition satisfied by over-parameterized models. Under this condition, we show that the regularized subsampled Newton method (R-SSN) achieves global linear convergence with an adaptive step-size and a constant batch-size. By growing the batch size for both the subsampled gradient and Hessian, we show that R-SSN can converge at a quadratic rate in a local neighbourhood of the solution. We also show that R-SSN attains local linear convergence for the family of self-concordant functions. Furthermore, we analyze stochastic BFGS algorithms in the interpolation setting and prove their global linear convergence. We empirically evaluate stochastic L-BFGS and a "Hessian-free" implementation of R-SSN for binary classification on synthetic, linearly-separable datasets and real datasets under a kernel mapping. Our experimental results demonstrate the fast convergence of these methods, both in terms of the number of iterations and wall-clock time.

@article{meng2019furious, abstract = {We consider stochastic second-order methods for minimizing smooth and strongly-convex functions under an interpolation condition satisfied by over-parameterized models. Under this condition, we show that the regularized subsampled Newton method (R-SSN) achieves global linear convergence with an adaptive step-size and a constant batch-size. By growing the batch size for both the subsampled gradient and Hessian, we show that R-SSN can converge at a quadratic rate in a local neighbourhood of the solution. We also show that R-SSN attains local linear convergence for the family of self-concordant functions. Furthermore, we analyze stochastic BFGS algorithms in the interpolation setting and prove their global linear convergence. We empirically evaluate stochastic L-BFGS and a "Hessian-free" implementation of R-SSN for binary classification on synthetic, linearly-separable datasets and real datasets under a kernel mapping. Our experimental results demonstrate the fast convergence of these methods, both in terms of the number of iterations and wall-clock time.}, added-at = {2020-05-03T11:13:39.000+0200}, author = {Meng, Si Yi and Vaswani, Sharan and Laradji, Issam and Schmidt, Mark and Lacoste-Julien, Simon}, biburl = {https://www.bibsonomy.org/bibtex/2d0a6aadc878033abdaa301adc0a3c945/kirk86}, description = {[1910.04920] Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation}, interhash = {2f276aef73856a9d189cb96c6bad2c61}, intrahash = {d0a6aadc878033abdaa301adc0a3c945}, keywords = {computation interpolation optimization}, note = {cite arxiv:1910.04920Comment: AISTATS, 2020}, timestamp = {2020-05-03T11:13:39.000+0200}, title = {Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation}, url = {http://arxiv.org/abs/1910.04920}, year = 2019 }