Design of Efficient Saddle Point Algorithms for Large-scale/Complex Geometry Convex Optimization

该奖项为新算法的理论和软件开发提供资金，用于处理信号处理，医学图像重建，机器学习和高维统计推断中出现的大规模优化模型，其中大量且稳定增长的底层数据导致需要处理具有数十万个变量和约束的优化问题。此外，一些应用，如低秩矩阵近似，导致困难的几何问题，这大大放大了纯粹的问题大小所带来的挑战。这些挑战将通过利用最先进的方法开发具有廉价迭代的算法来解决，主要是感兴趣问题的双线性鞍点重构，结合基于对偶的处理困难几何和通过各种类型的随机化加速算法。理论和算法的发展将被调整到几个通用的应用程序（稀疏和低秩定向信号处理和机器学习，基于总变分的图像处理的扩展等），并将旨在开发具有良好理论性能保证和可见实际潜力的优化技术;后者将通过模拟和真实的生活问题的广泛数值实验来验证。2如果成功，该研究将通过丰富其处理大规模/复杂几何问题的能力来推进优化的理论和实践，从而对信号处理，图像重建，机器学习和其他一些学科领域。作为一个副产品，这项研究将有助于最近的趋势，桥梁相应的研究社区，具有明显的互利。此外，本研究的成果可作为新博士学位的基础。水平优化课程。

This award provides funding for theoretical and software development of novel algorithms for processing large-scale optimization models arising in Signal Processing,Medical Image Reconstruction, Machine Learning, and high-dimensional Statistical inference, where huge and steadily growing amounts of underlying data result in thenecessity to process optimization problems with hundreds of thousands of variables and constraints. In addition, some of applications, such as low rank matrixapproximations, lead to problems with difficult geometry, which amplifies significantly the challenges caused by sheer problem sizes. These challenges will bemet via developing algorithms with cheap iterations utilizing state-of-the-art approaches, primarily bilinear saddle point reformulation of the problem of interestcombined with duality-based handling difficult geometry and accelerating algorithms via various types of randomization. Theoretical and algorithmic developmentswill be adjusted to several generic applications (sparsity- and low-rank oriented Signal Processing and Machine Learning, extensions of total variation-based Imageprocessing, and some others) and will be aimed at developing optimization techniques with good theoretical performance guarantees and visible practical potential;the latter will be validated by extensive numerical experimentation with both simulated and real life problems.If successful, the research will advance theory and practice of optimization by enriching its abilities to process large-scale/complex geometry problems and thus willcontribute significantly to the computational toolboxes in Signal Processing, Image Reconstruction, Machine Learning, and some other subject domains. As a byproduct,the research will contribute to recent tendency of bridging the corresponding research communities, with clear mutual benefits. In addition, the results ofthe research could form the base of new Ph.D.-level optimization courses.