Randomized Algorithms for Extreme Convex Optimization

The field of mathematical optimization experienced a paradigm shift in the last decade: while the 20 years prior to about year 2005 were dominated by the development of interior-point methods, research activity since has almost entirely been focused on first-order methods. This was caused by several factors. Most notably, there has been a surge in the demand from practitioners, in fields such as machine learning, signal processing and data science, for new methods able to cope with new large scale problems. Moreover, an important role in the transition was played by the fact that accuracy requirements in many modern applications (such as classification and image denoising) were only moderate or low, which was in sharp contrast with the preceding focus on applications in classical domains such as engineering and physics where accuracy requirements were typically high. The paradigm shift would not have been possible, however, were it not for the development and success of modern gradient methods, the complexity of which improved upon classical results by an order of magnitude, using sophisticated tools such as the estimate sequence method and smoothing. At the moment, mathematical optimization is experiencing yet another revolution, related to the introduction of randomization as an algorithmic design and analysis tool, much in the same way that probabilistic reasoning has recently begun to transform several other "continuous" fields, including numerical linear algebra and control theory. The import of randomization is at least twofold: it makes it possible to design new algorithms which scale to extreme dimensions, and at the same time it often leads to improved theoretical complexity bounds. This project focuses on the design, complexity analysis and high-performing implementations of efficient randomized algorithms suitable for extreme convex optimization.