195. Second-order interpolation conditions for univariate functions, towards a tight analysis of second-order optimization methods
Invited abstract in session WE-2: Recent advances in computer-aided analyses of optimization algorithms I, stream Conic optimization: theory, algorithms and applications.
Wednesday, 14:10 - 15:50Room: M:O
Authors (first author is the speaker)
| 1. | Anne Rubbens
|
| ICTEAM, UCLouvain | |
| 2. | Nizar Bousselmi
|
| ICTEAM, UCLouvain | |
| 3. | Julien Hendrickx
|
| ICTEAM | |
| 4. | François Glineur
|
| ICTEAM/INMA & CORE, Université catholique de Louvain (UCLouvain) |
Abstract
We focus in this work on the derivation of interpolation constraints for given function classes, that is necessary and sufficient conditions that a data set must satisfy to ensure the existence of a function of the class of interest, defined on the whole space and interpolating the data.
Interpolation constraints allow to manipulate only data sets instead of continuous functions, and are essential to obtain tight guarantees on the worst-case performance of optimization methods on given function classes, where one manipulates a finite set of iterates (and associated evaluations of a function and its derivatives). While interpolation constraints are available for a wide range of first-order function classes (smooth, convex,..), allowing to tightly analyze first-order method, this is not the case for second-order function classes. We thus propose interpolation conditions for (convex) univariate function with Lipschitz second derivative, with the objective of tightly analyzing second-order methods.
Keywords
- Complexity and efficiency of optimization algorithms
- Analysis and engineering of optimization algorithms
Status: accepted
Back to the list of papers