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

随着现代研究中涉及的数据量不断增加，构建适用于大规模数据集且不需要大量计算时间的新数学和统计工具非常重要。优化算法是各种学科中数据分析的重要计算工具，许多现代应用要求这些优化算法处理非常大规模，高度非线性和非光滑的问题。这些特征以可扩展和高效的方式给计算解决方案带来了巨大的挑战。该项目旨在解决大规模数据分析问题中出现的优化算法的计算困难。本科生和研究生将接受培训并参与该项目。 在大数据时代，可扩展性是设计计算算法的最重要因素之一。这一特点促使最近的快速发展的一阶方法。这个项目的重点是发展和理解的基本限制的新的一阶算法解决鞍点结构优化问题。具体而言，该项目旨在推进适用于大规模数据分析问题的鞍点结构非光滑优化技术。利用一阶方法可以获得的关于结构的问题特定信息，将进行基于信息的复杂性分析，以揭示特定类别问题的内在困难，并设计数值方法。确定性的一阶方法，随机和贪婪的块梯度方法，随机一阶方法，以及它们的异步并行版本足够的多核机器或集群将被开发。对于每一类提出的方法，将建立较低的复杂性界限，并将设计最佳的数值算法，以达到这些bounds.This奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

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.