Collaborative Research: AF: Medium: Foundations of Structured Optimization

在过去的十年中，如何处理大规模优化问题发生了巨大的变化。无论是训练复杂的机器学习模型，在海量数据集中寻找模式，还是调整推荐系统中的参数，越来越多的数据科学家应用简单的迭代方法来解决复杂的优化问题。这些流行的方法，例如梯度下降的变体，经常忽略问题结构，而需要额外的昂贵的时间，能量和调整资源。然而，广泛的结构类别经常渗透到现代优化问题中，无论是流行的机器学习模型的网络结构，数据集的稀疏性，还是学习问题的低维结构。该项目的主要目标是提供新的数学和算法工具，以利用基础和普遍的优化问题中的广泛的结构类别。该项目将开发用于解决结构化优化问题的新技术，解决算法设计中长期存在的理论问题，并提供各种研究，教育和推广活动，旨在使这些技术广泛可用并易于应用。最终，该项目将为更有效的结构化优化和大规模数据分析奠定基础。该项目将专注于提供优化理论的重大数学和算法进步，以及解决突出结构化优化问题的有效算法设计。研究人员将开发一套广泛的通用结构感知算法和数学技术，以改善普适优化和机器学习问题的运行时间。本项目考虑的优化问题，包括线性规划、随机优化、线性系统求解、非凸优化以及本项目考虑的优化工具，如邻域点法、非线性共轭梯度法、L-BFGS等，是理论计算机科学、运筹学、科学计算、数值分析和机器学习中一些最大的开放问题的核心。因此，为了实现这些结果，PI将联合收割机技术跨越这个广泛的算法思想社区，并推进凸分析，谱图理论，迭代方法，和数值分析，最终获得一个新的强大的工具包，解决大规模的，该奖项反映了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.