Randomized Algorithms for Extreme Convex Optimization

数学优化领域在过去十年中经历了范式转变：虽然2005年之前的20年主要是内点方法的发展，但研究活动几乎完全集中在一阶方法上。这是由几个因素造成的。最值得注意的是，在机器学习、信号处理和数据科学等领域，从业者对能够应对新的大规模问题的新方法的需求激增。此外，许多现代应用（如分类和图像去噪）的精度要求只是中等或较低，这一事实在过渡中发挥了重要作用，这与之前关注工程和物理等经典领域的应用形成鲜明对比，这些领域的精度要求通常很高。然而，如果不是现代梯度方法的发展和成功，范式转变是不可能的。现代梯度方法的复杂性比经典结果提高了一个数量级，使用了诸如估计序列方法和平滑等复杂工具。目前，数学优化正在经历另一场革命，这与随机化作为算法设计和分析工具的引入有关，就像概率推理最近开始改变其他几个“连续”领域一样，包括数值线性代数和控制理论。随机化的重要性至少有两个方面：它使设计新的算法成为可能，这些算法可以扩展到极端的维度，同时它经常导致改进的理论复杂性界限。本项目主要研究适用于极端凸优化的高效随机算法的设计、复杂度分析和高性能实现。

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.