Seminar Details
2023-05-09 (14h) : Convex Analysis and Synthesis of Accelerated Gradient Algorithms
At Euler building (room A.002)
Organized by Mathematical Engineering
Speaker :
Carsten Sherer (University of Stuttgart, Department of Mathematics)
Abstract :
Gradient descent is a well-established technique for solving optimization problems in the current era of big data and machine learning. Recent years have witnessed a strong interest in so-called accelerated gradient algorithms which have superior convergence properties if compared to standard gradient descent applied to convex optimization problems. It has been known for a long time that such algorithms can be viewed as a linear time-invariant discrete-time system in feedback with the gradient of the to-be-minimized function as a nonlinearity. This point-of-view provides an immediate link to the so-called absolute stability problem for Lur’e systems in control. It opens up the possibility to apply advanced tools from robust control in order to compute the convergence rate of a given accelerated gradient algorithm by semi-definite programming.
A much more challenging task is the direct computational design of algorithms in order to achieve optimal convergence rates. This questions falls into the area of robust feed- back controller synthesis. In this talk we survey how to analyze and synthesize algorithms by robust control techniques. A particular emphasis will be laid on highlighting the key structural aspects that enable the construction of suitable small-sized semi-definite pro- grams to determine optimal algorithms. As a distinguishing feature, we reveal that our techniques seamlessly extend to extremum control, with the goal to design controllers that drive the output of a general linear system to the minimum of a convex function with an optimal rate of convergence.