Collaborative Research: AF: Medium: Foundations of Structured Optimization

在过去的十年里，解决大规模优化问题的方式发生了戏剧性的转变。无论是训练复杂的机器学习模型，还是在海量数据集中发现模式，还是在推荐系统中调整参数，数据科学家都越来越多地使用简单的迭代方法来解决复杂的优化问题。这些流行的方法，例如梯度下降的变体，通常忽略问题结构，而倾向于需要额外昂贵的时间、精力和调优资源。然而，广泛的结构类往往渗透到现代优化问题中，无论是流行的机器学习模型的网络结构，数据集的稀疏性，还是学习问题的低维结构。这个项目的主要目标是提供新的数学和算法工具，以开发基本和普遍的优化问题中的广泛结构类。该项目将开发解决结构化优化问题的新技术，解决算法设计中长期存在的理论问题，并提供各种研究、教育和推广活动，旨在使这些技术能够广泛获得和易于应用。最终，该项目将为更高效的结构优化和大规模数据分析奠定基础。该项目将专注于在优化理论和为解决突出的结构优化问题设计高效算法方面取得重大的数学和算法进步。研究人员将开发一套广泛的通用结构感知算法和数学技术，以改善普适优化和机器学习问题的运行时间。这个项目中考虑的优化问题，包括线性规划、随机优化、线性系统求解、非凸优化以及本项目中考虑的优化工具，如内点法、非线性共轭梯度法、L-BFGS等，是理论计算机科学、运筹学、科学计算、数值分析和机器学习中一些最大的开放问题的核心。因此，为了实现这些结果，PIS将结合这些广泛的算法思维社区的技术，并在凸分析、谱图理论、迭代方法和数值分析方面推进最先进的理论，最终获得解决大规模结构化优化问题的新的健壮工具包。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Over the past decade there has been a dramatic shift in how large-scale optimization problems are tackled. Whether training sophisticated machine-learning models, finding patterns in massive data sets, or tuning parameters in recommendation systems, increasingly data scientists apply simple iterative methods to solve complex optimization problems. These popular methods, e.g. variants of gradient descent, often ignore problem structure in favor of requiring additional expensive resources of time, energy, and tuning. However, broad classes of structure often permeate modern optimization problems, whether it be network structure of popular machine-learning models, the sparsity of datasets, or the low-dimensional structure of learning problems. The primary goal of this project is to provide new mathematical and algorithmic tools to exploit broad classes of structure in fundamental and prevalent optimization problems. This project will develop new techniques for solving structured optimization problems, address long-standing theoretical questions in algorithm design, and provide varied research, educational, and outreach activities designed to make these techniques broadly accessible and easily applied. Ultimately, this project will lay the foundations for more efficient structured optimization and large-scale data analysis.This project will focus on providing significant mathematical and algorithmic advances in the theory of optimization and the design of efficient algorithms for solving prominent structured optimization problems. The investigators will develop a broad set of general structure-aware algorithmic and mathematical techniques to obtain improved running times for pervasive optimization and machine-learning problems. The optimization problems considered in this project, including linear programming, stochastic optimization, linear system solving, nonconvex optimization and the optimization tools considered in this project, such as interior-point methods, nonlinear conjugate gradient, L-BFGS, etc., lie at the heart of some of the largest open problems in theoretical computer science, operations research, scientific computing, numerical analysis, and machine learning. Consequently, to achieve these results the PIs will combine techniques across this broad spectrum of algorithmically-minded communities and advance the state-of-the-art theory in convex analysis, spectral graph theory, iterative methods, and numerical analysis to ultimately attain a new robust toolkit for solving massive-scale structured optimization problems.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.