Convex optimization based on global lower second-order models

Nikita, Doikov, and Yurii, Nesterov ()
Additional contact information
Nikita, Doikov,: CORE, Université catholique de Louvain
Yurii, Nesterov: CORE, Université catholique de Louvain

No 2020023, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: In this paper, we present new second-order algorithms for composite convex optimization, called Contractindomain 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 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 funcitonal resudial, 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.

Date: 2020-02-11
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2020.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2020023

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().