Information-Based Complexity Analysis and Optimal Methods for Saddle-Point Structured Optimization

With the increasing volumes of data involved in modern-day research, it is important to build new mathematical and statistical tools that are applicable to huge-scale datasets and do not require large computation time. Optimization algorithms are an important computational tool for data analysis in various disciplines, and many modern applications require these optimization algorithms to handle very large-scale, highly nonlinear, and non-smooth problems.

These features bring great challenges to computing solutions in a scalable and efficient way. This project aims at addressing the computational difficulties in optimization algorithms that arise from large-scale data analysis problems. Undergraduate and graduate students will be trained and involved in this project.

In the big data era, scalability is one most important factor in designing computational algorithms. This feature motivates the recent rapid development of first-order methods. This project focuses on the development and the understanding of fundamental limits of novel first-order algorithms for solving saddle-point structured optimization problems.

Specifically, the project aims at advancing saddle-point structured non-smooth optimization techniques applicable to large-scale data analysis problems. With problem-specific information on structure that a first-order method can acquire, information-based complexity analysis will be conducted to reveal the intrinsic difficulty of the specified class of problems, and numerical approaches will be designed.

Deterministic first-order methods, randomized and greedy block gradient methods, stochastic first-order methods, and their asynchronous parallel versions adequate for multi-core machines or clusters will be developed. For each class of proposed methods lower complexity bounds will be established, and optimal numerical algorithms will be designed to reach these bounds.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.