Contributions to Performance Estimation Problems for the Analysis and Design of First-Order Optimization Methods
(2025)
Files
Thesis2025YassineKamri.pdf
Open Access - Adobe PDF
- 2.01 MB
Details
- Authors
- Supervisors
- Abstract
- Performance Estimation Problems (PEPs) deal with the worst-case convergence analysis of fixed-step first-order optimization algorithms. This thesis extends PEPs to analyze different classical convex optimization settings, for which they can be framed and solved as convex optimization problems. First, we construct a convex PEP formulation for block coordinate-wise algorithms over the class of coordinate-wise smooth convex functions. We use this tool to analyze several popular algorithms such as cyclic coordinate descent and alternating minimization, and provide tighter numerical convergence rates compared to those available in the literature. We also give new insights about the behavior of these algorithms, notably by characterizing the dependence of the worst-case of cyclic coordinate descent on the number of blocks, estimating numerically optimal constant step sizes for cyclic coordinate descent, and analyzing the efficiency of deterministic variants of random accelerated coordinate descent algorithms. Secondly, we extend the PEP framework for the analysis of gradient descent over Hölder-smooth convex functions, propose a fixed step-size strategy in this context, demonstrate the convergence of the algorithm and compare its convergence rate to the one of universal gradient methods. Finally, we extend the PEP framework for the automatic design of optimized fixed-step first-order algorithms. We propose several methods for the numerical design of fixed-step first-order algorithms, and test them in different convex optimization settings, including those previously considered in this thesis. This leads to numerically optimized algorithms that are frequently displaying faster convergence rates compared to the classical algorithms.
- Affiliations
UCLouvain SST/ICTM/INMA - Pôle en ingénierie mathématique
Citations
Kamri, Y. (2025). Contributions to Performance Estimation Problems for the Analysis and Design of First-Order Optimization Methods. https://hdl.handle.net/2078.5/275045