Convex optimization based on global lower second-order models
(2021) Advances in Neural Information Processing Systems 33 : 34th Conference on Neural Information Processing Systems (NeurIPS 2020) — ISBN: [9781713829546], published
Files
CORE_RP_3311.pdf
Open Access - Adobe PDF
- 1.96 MB
Details
- Authors
- Abstract
- In this work, 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 O(1/k2)O(1/k2) global rate of convergence in functional residual, where k k is the iteration counter, minimizing convex functions with Lipschitz continuous Hessian. This significantly improves the previously known bound O(1/k)O(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. (2021). Convex optimization based on global lower second-order models. In ed. by H. Larochelle, e.a. (ed.), Advances in Neural Information Processing Systems 33 : 34th Conference on Neural Information Processing Systems (NeurIPS 2020). NeurIPS. https://hdl.handle.net/2078.5/233927