Approches constructives pour l'analyse de pire cas des méthodes de gradient en optimisation convexe : contributions, éléments de compréhension, et nouveaux résultats.
Baptiste Goujaud · theses.fr (ABES) · 2024
In the current era marked by an unprecedented surge in available data and computational prowess, the field of machine learning, and more specifically deep learning, has witnessed an extraordinary evolution.Machine learning algorithms heavily rely on optimization techniques to tune their parameters and enhance predictive accuracy.Amidst the myriad of optimization approaches, the first-order optimization methods have emerged as stalwarts, demonstrating a remarkable balance between efficacy and computational efficiency.Crucially, the development of strong optimization theory is pivotal in unraveling the full potential of first-order optimization.Theoretical underpinnings not only deepen our understanding of optimization landscapes but also pave the way for the design of novel algorithms.The momentum-based algorithms have proven their mettle by significantly accelerating convergence in optimization problems.The conceptual foundation provided by optimization theory has enabled the formulation of momentum, turning theoretical insights into a powerful and widely adopted practical optimization tool.The role of this thesis is to pursue and accelerate the effort to develop a strong theoretical foundation of first-order optimization.We proved various results, exploiting the general structures of the certificate proofs.(i) We used the link between quadratic optimization and polynomial theory to explain empirically observed phenomena.(ii) We implemented a Python package to support the emph{Performance estimation} framework.(iii) We wrote a tutorial to explain how to derive natural proofs in optimization based on this framework.(iv) We applied this methodology, with the help of our python package, to derive a complete first-order optimization theory on a very large class of functions.(v) We complemented the theoretical emph{Performance estimation} framework to disprove the convergence of a specific family of methods and applied it to the famous Heavy-ball method to provably disprove an acceleration over the class of smooth and strongly convex functions.