Convex optimization based on global lower second-order models
(2020) , 22 pages
Files
COREDP2020_23web.pdf
Open Access - Adobe PDF
- 2.73 MB
Details
- Authors
- Abstract
- In this paper, we present new second-order algorithms for composite convex optimization, called Contracting-domain Newton methods. These algorithms are affine-invariant and based on global second-order lower approximation for the smooth component of the objective. Our approach has an interpretation both as a second-order generalization of the conditional gradient method, or as a variant of trust-region scheme. Under the assumption, that the problem domain is bounded, we prove ${\Os}(1/k^2)$ global rate of convergence in functional residual, where $k$ is the iteration counter, minimizing convex functions with Lipschitz continuous Hessian. This significantly improves the previously known bound ${\Os}(1/k)$ for this type of algorithms. Additionally, we propose a stochastic extension of our method, and present computational results for solving empirical risk minimization problem.
- Affiliations
Citations
Doikov, N., & Nesterov, Y. (2020). Convex optimization based on global lower second-order models (CORE Discussion Papers 2020/23). https://hdl.handle.net/2078.5/168446