548. Tight Analysis of Second-Order Optimization Methods via Interpolation of generalized Hessian Lipschitz Univariate Functions
Invited abstract in session MC-8: Systematic and computer-aided analyses II: Systematic algorithmic design approaches, stream Systematic and computer-aided analyses of optimization algorithms.
Monday, 14:00-16:00Room: B100/7007
Authors (first author is the speaker)
| 1. | François Glineur
|
| ICTEAM/INMA & CORE, Université catholique de Louvain (UCLouvain) | |
| 2. | Nizar Bousselmi
|
| ICTEAM, UCLouvain | |
| 3. | Julien Hendrickx
|
| ICTEAM | |
| 4. | Anne Rubbens
|
| ICTEAM, UCLouvain |
Abstract
We show how to compute exact worst-case guarantees on the performance of second-order optimization methods on a wide range of univariate function classes. These classes include Hessian Lipschitz, self-concordant, and quasi-self-concordant functions, which we unify within a class of generalized Lipschitz functions.
Our results rely on the development of interpolation conditions for all classes of interest, for which we present a standard derivation procedure, combined with the Performance Estimation framework which we generalize to include second-order quantities. Use those, we improve or, in some cases, prove tightness of known rates of convergence of Newton's method and its regularized variants on the above-mentioned classes of univariate functions.
Keywords
- Computer-aided algorithm analysis
- Second- and higher-order optimization
- Computer-aided algorithm analysis
Status: accepted
Back to the list of papers