Convex optimization for data science : continuous-time Lyapunov analyses, geometry dependent matching pursuit and concentration inequalities

Overview & Synopsis

Convex optimization is a cornerstone of data science, providing efficient tools for optimizing convex functions over convex sets. It serves as the foundation for numerous machine learning algorithms, enabling robust solutions for tasks such as regression, classification, and clustering. It is also crucial for deriving (approximation to) concentration inequalities, which provide probabilistic bounds that help understand the behavior and performance of algorithms on large datasets. This thesis offers comprehensive and principled methodologies for studying continuous-time optimization models, approaching concentration inequalities, as well as enhancing the understanding and development of greedy algorithms. The first part of the manuscript focuses on studying convergence guarantees of ordinary differential equations arising from first-order methods, using Lyapunov functions. We provide a systematic approach to finding and verifying Lyapunov functions for various ordinary and stochastic differential equations, yielding convergence results with fewer assumptions. This functionality is integrated into the PEPit python package. The second part investigates greedy first-order methods, such as steepest coordinate descent and matching pursuit, which has become popular due to their natural tendency to propose sparse solutions. We propose a principled approach to generating (regularized) matching pursuit adapted to problem geometry at hand, along with their refined convergence guarantees. In the last part, we introduce a constructive approach to concentration inequalities for independent random variables. We propose on the one hand a variational approach that extends the classical approach via moment generating function and is particularly suited to first-order moment assumptions. On the other hand, we propose a polynomial approach, based on a hierarchy of sums-of-squares approximations, suited to higher-order moment conditions.