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

点击翻译按钮获取中文摘要

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.