This is the public, feature-limited version of the conference webpage. After Registration and login please visit the full version.

Convex optimization based on global lower second-order models

Nikita Doikov, Yurii Nesterov

Oral presentation: Orals & Spotlights Track 21: Optimization
on 2020-12-09T06:45:00-08:00 - 2020-12-09T07:00:00-08:00
Poster Session 4 (more posters)
on 2020-12-09T09:00:00-08:00 - 2020-12-09T11:00:00-08:00
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/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 $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.

Preview Video and Chat

To see video, interact with the author and ask questions please use registration and login.