Collaborative Research: AF: Medium: Foundations of Structured Optimization

合作研究：AF：媒介：结构化优化的基础

• 批准号: 1955039
• 负责人: Aaron Sidford
• 金额: $ 63万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1955039&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Medium; Foundations

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.

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

项目成果

The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood

低秩矩阵的 Bethe 和 Sinkhorn 常量及其对轮廓最大似然的影响

• 发表时间: 2021
• 期刊: Proceedings of Machine Learning Research
• 作者: Anari, Nima;Charikar, Moses;Shiragur, Kirankumar;Sidford, Aaron
• 通讯作者: Sidford, Aaron

Semi-Random Sparse Recovery in Nearly-Linear Time

近线性时间的半随机稀疏恢复

• 发表时间: 2023
• 期刊: Proceedings of Thirty Sixth Conference on Learning Theory (COLT 2023
• 作者: Kelner, Jonathan;Li, Jerry;Liu, Allen X.;Sidford, Aaron;Tian, Kevin
• 通讯作者: Tian, Kevin

Large-Scale Methods for Distributionally Robust Optimization

用于分布式鲁棒优化的大规模方法

• 发表时间: 2020
• 期刊: NeurIPS 2020
• 作者: Levy, Daniel;Carmon, Yair;Duchi, John C.;Sidford, Aaron
• 通讯作者: Sidford, Aaron

Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

• 发表时间: 2021-05
• 作者: Y. Carmon;A. Jambulapati;Yujia Jin;Aaron Sidford

ReSQueing Parallel and Private Stochastic Convex Optimization

• DOI: 10.1109/focs57990.2023.00124
• 发表时间: 2023-01
• 期刊: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Y. Carmon;A. Jambulapati;Yujia Jin;Y. Lee;Daogao Liu;Aaron Sidford;Kevin Tian