PERFORMANCE ANALYSIS OF OPTIMIZATION ALGORITHMS USING SEMIDEFINITE PROGRAMMING

Abstract

In this thesis, we introduce a new framework for systematizing the performance analysis of first-order black-box optimization algorithms for unconstrained convex minimization problems. Through our method, we derive worst-case upper bounds on the convergence rates of the algorithms, over a fixed class of functions. Our approach is based on sum-of-squares optimization, which allow us to introduce a hierarchy of semidefinite programs that produces tighter convergence bounds at higher levels of the hierarchy. With this framework, we recover in a unified manner known convergence results for four popular first-order algorithms, and derive new convergence bounds for noisy gradient descent with various inexact line search methods. We also present two other existing frameworks that seeks to systematically analyze optimization algorithms: one attributed to Drori and Teboulle (2014) known as the Performance Estimation Problem and another by Lessard et al. drawing upon the concept of Integral Quadratic Constraints, and compare all three approaches.