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.