Interpolation conditions for exact computer-aided analysis of optimization methods
(2025)
Files
Thèse_Anne_Rubbens.pdf
Open Access - Adobe PDF
- 3.42 MB
Details
- Authors
- Supervisors
- Hendrickx, Julien
- Abstract
- This thesis considers the tight performance analysis of optimization methods. It first aims at better understanding interpolation conditions for classes of functions or operators, that is, conditions ensuring consistency of datasets with a function or operator in the class. Combined with computer-aided approaches as, e.g., the Performance Estimation Problem (PEP) framework, these allow for exact performance analysis of given methods on these classes. It then extends the PEP framework to enable the analysis of broader optimization settings. The thesis is structured in three parts. The first part introduces an algebraic approach to function and operator interpolation, and uses it to refine existing descriptions of a few function and operator classes, including weakly convex functions, smooth functions satisfying a Lojasiewicz condition, blockwise smooth functions, and Lipschitz monotone operators. The second part focuses on second-order optimization. It derives interpolation conditions for univariate function classes with second-order properties, such as self-concordance and Lipschitz continuity of the Hessian. These conditions are used to obtain exact worst-case performance bounds on second-order methods in the univariate setting. Finally, the third part extends the PEP framework to the tight analysis of stochastic optimization methods. Given a stochastic first-order method, a function class, and a noise model with specified expectation and variance, it proposes a family of semidefinite formulations that yield increasingly strong convergence guarantees on the problem, at the expense of an increasing complexity. The largest formulations, whose size grow exponentially with the number of iterations, provide tight guarantees.
- Affiliations
UCLouvain SST/ICTM/INMA - Pôle en ingénierie mathématique
Citations
Rubbens, A. (2025). Interpolation conditions for exact computer-aided analysis of optimization methods. https://hdl.handle.net/2078.5/258618