CAREER: Discrete Convexity in Algorithm Design

职业：算法设计中的离散凸性

• 批准号: 2045354
• 负责人: Nima Anari
• 金额: $ 50.71万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-02-01 至 2026-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2045354&HistoricalAwards=false
• 关键词: CAREER; Discrete; Convexity; Algorithm; Design

Algorithm design is the study of techniques for efficient computation on large-scale problems. Modern industries rely on computational problems ranging from statistical analysis of massive amounts of data to optimization problems that improve their ongoing operations. As such, general-purpose frameworks for designing fast and reliable algorithms are very valuable. Linear and convex programming is one such framework, studied since the 1830s by mathematicians, and since the 1940s as a tool for solving computational problems. Modern applications of convex programming can be found everywhere; for example, power companies optimize their pricing and sourcing of electricity, and companies like Uber and Amazon optimize their logistics, using convex programming. More recently, convexity has played an important role in statistical and probabilistic analysis; there is an increasing amount of interest in these problems due to their intimate connection with and uses in machine learning. While convexity and convex programming have had many successes, they are only suited for continuous problems, leaving a large gap to address discrete phenomena. Discrete phenomena can be found everywhere: statistical models of diseases and symptoms in medicine, categorical predictions in machine-learning models, and value-optimization problems involving bundling of items in retail industries. The goal of this project is to develop a foundational framework for fast and reliable statistical-analysis and optimization algorithms based on discrete notions of convexity for discrete problems. This project incorporates a synergistic education plan that includes curriculum development for undergraduate and graduate students at Stanford university aimed at students from a diverse set of areas: computer science, statistics, mathematics, and operations research.This project will develop a discrete convexity framework for algorithm design through three fronts. First, the project will study combinatorics of convex polytopes encapsulating discrete objects and relate them to algorithmic efficiency. The project will explore generalization of matroids, objects widely used in combinatorial optimization because of their theoretical guarantees in greedy algorithms. The expected outcome will be an understanding of when local search, an optimization technique that operates by changing small parts of the solution at a time, succeeds. Second, the project will explore randomized algorithms such as Markov Chain Monte Carlo and Gibbs Sampling on discrete objects, producing an understanding of when local algorithms are successful in sampling from discrete distributions and in statistical analysis. One goal of this project is connecting the effectiveness of local search for optimization problems and local algorithms for sampling from probability distributions. Finally, the project will explore variational techniques for statistical analysis, a category of convex-programming-based algorithms that are typically much faster than Markov Chain Monte Carlo, but sometimes come with worse theoretical guarantees; however, variational techniques are widely used with success in practice, and this project will aim at shedding light on their effectiveness through the lens of discrete convexity. This project is interdisciplinary and will provide connections between computer science and other fields, most notably statistics, combinatorics, algebraic geometry.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.

算法设计是对大规模问题的有效计算技术的研究。现代工业依赖于计算问题，从大量数据的统计分析到改善其持续运营的优化问题。因此，用于设计快速可靠算法的通用框架非常有价值。线性和凸规划就是这样一个框架，自19世纪30年代以来被数学家研究，并自20世纪40年代以来作为解决计算问题的工具。凸规划的现代应用随处可见;例如，电力公司优化其定价和电力采购，Uber和亚马逊等公司使用凸规划优化其物流。最近，凸性在统计和概率分析中发挥了重要作用;由于它们与机器学习的密切联系和用途，对这些问题的兴趣越来越大。虽然凸性和凸规划已经取得了许多成功，但它们只适用于连续问题，留下了很大的空白来解决离散现象。离散现象随处可见：医学中疾病和症状的统计模型，机器学习模型中的分类预测，以及零售业中涉及捆绑商品的价值优化问题。这个项目的目标是开发一个快速可靠的数学分析和优化算法的基础框架，基于离散问题的离散凸性概念。该项目包含了一个协同教育计划，其中包括针对斯坦福大学的本科生和研究生的课程开发，目标是来自不同领域的学生：计算机科学，统计学，数学和运筹学。该项目将通过三个方面开发算法设计的离散凸性框架。首先，这个项目将研究凸多面体封装离散对象的组合学，并将它们与算法效率联系起来。该项目将探讨拟阵的推广，广泛用于组合优化的对象，因为它们在贪婪算法的理论保证。预期的结果将是理解局部搜索（一种通过每次改变解决方案的一小部分来操作的优化技术）何时成功。其次，该项目将探讨随机算法，如马尔可夫链蒙特卡罗和吉布斯抽样离散对象，产生的局部算法是成功的离散分布和统计分析抽样的理解。这个项目的一个目标是连接局部搜索的优化问题和局部算法的概率分布抽样的有效性。最后，该项目将探讨变分技术的统计分析，一类凸规划为基础的算法，通常比马尔可夫链蒙特卡洛快得多，但有时会带来更差的理论保证;然而，变分技术被广泛使用，在实践中取得了成功，本项目将旨在通过离散凸性的透镜阐明其有效性。该项目是跨学科的，将提供计算机科学和其他领域之间的联系，最显着的是统计学，组合学，代数几何。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

项目成果

Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence

通过平均情况熵独立的生成树和行列式点过程的最优次线性采样

• DOI: 10.1109/focs54457.2022.00019
• 发表时间: 2022
• 期刊: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS
• 作者: Anari, Nima;Liu, Yang P.;Vuong, Thuy-Duong
• 通讯作者: Vuong, Thuy-Duong

Fractionally log-concave and sector-stable polynomials: counting planar matchings and more

• DOI: 10.1145/3406325.3451123
• 发表时间: 2021-02
• 期刊: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Yeganeh Alimohammadi;Nima Anari;Kirankumar Shiragur;T. Vuong

From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization

• 发表时间: 2021-02
• 作者: Nima Anari;T. Vuong

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

Entropic independence: optimal mixing of down-up random walks

• DOI: 10.1145/3519935.3520048
• 发表时间: 2022-06
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Nima Anari;Vishesh Jain;Frederic Koehler;H. Pham;T. Vuong