?
A Superlinearly-Convergent Proximal Newton-Type Method for the Optimization of Finite Sums
Journal of Machine Learning Research. 2016. Vol. 48. P. 2597–2605.
Родоманов А. О., Kropotov D.
We consider the problem of optimizing the strongly convex sum of a finite number of convex functions. Standard algorithms for solving this problem in the class of incremental/stochastic methods have at most a linear convergence rate. We propose a new incremental method whose convergence rate is superlinear – the Newton-type incremental method (NIM). The idea of the method is to introduce a model of the objective with the same sum-of-functions structure and further update a single component of the model per iteration. We prove that NIM has a superlinear local convergence rate and linear global convergence rate. Experiments show that the method is very effective for problems with a large number of functions and a small number of variables.
Научное направление:
Математика
Приоритетные направления:
компьютерно-математическое
Язык:
английский