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

基于信息的鞍点结构优化的复杂性分析和优化方法

基本信息

批准号：
2053493
负责人：
Yangyang Xu
金额：
$ 25万
依托单位：
Rensselaer Polytechnic Institute
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-06-01 至 2024-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2053493&HistoricalAwards=false
关键词：
Information Based Complexity Analysis Optimal

项目摘要

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.

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