Professor Yurii Nesterov (CORE/INMA, UCLouvain, Belgium) is a guest of Corvinus Institute for Advanced Studies (CIAS), Corvinus University of Budapest in February. As part of his visit, a minicourse given by Yurii Nesterov and a workshop will be organized.
The Corvinus Center for Operations Research (CCOR) invites you to Modern Theory of Second-Order Methods Mini-course. It is organized in a hybrid way. (You can ask Zoom links via email marianna dot eisenberg-nagy at uni-corvinus dot hu.)
Venue: Corvinus University, Building E, Room: E.338
Dates:
February 8, 9.30-11.00
February 9, 10.00-11.30
February 14, 10.00-11.30
In this course we present the latest achievements in the theory of the second-order schemes. We start from the global complexity estimates for the new second-order methods, based on the cubic regularization of quadratic model of the objective function. We consider several complexity bounds for different classes of nonconvex functions. Next topic is the accelerated second-order methods for convex functions and the lower complexity bounds. We finish the course with the universal second order schemes.
Lecture 1: Global complexity bounds for 2nd-order methods. Systems of nonlinear equations.
Historical remarks
Trust region methods
Cubic regularization of second-order model
Local and global convergence
Solving the system of nonlinear equations
Numerical experiments
Lecture 2: Accelerated second-order methods. Lower complexity bounds.
Composite convex optimization problem
Composite Cubic Newton Method
Complexity bound
Non-degeneracy for 2nd-order methods
Estimating sequences
Accelerated Cubic Newton
Lecture 3: Universal 2nd-order methods.
Problem formulation
Holder classes for second derivative
Main inequalities
Regularized methods for particular Holder class
Accelerated method
Universal accelerated method
References
- Yu. Nesterov, B. Polyak. Cubic regularization of Newton’s method and its global performance. Mathematical Programming, 108(1), 177-205 (2006).
- Yu. Nesterov. Accelerating the cubic regularization of Newton’s method on convex problems. Mathematical Programming, 112(1) 159-181 (2008)
- Yu. Nesterov. Modified Gauss-Newton scheme with worst-case guarantees for its global performance. Optimization Methods and Software, 22(3) 469-483 (2007)
- Yu. Nesterov. Complexity bounds for primal-dual methods minimizing the model of objective function. Mathematical Programming, 171, 311-330 (2018)
- G.N. Grapiglia, Yu. Nesterov. Regularized Newton methods for minimizing functions with Holder continuous Hessians. SIOPT, 27(1), 478-506 (2017).
- Yu. Nesterov. Superfast 2nd-order methods for unconstrained convex optimization. JOTA, 191, 1-30 (2021).
OR (instead of 1-5): sections 4.1-4.4, and section 6.4.6 of
Yu. Nesterov. Lecture notes on Convex Optimization. Springer (2018).