CAREER: Discrete Convexity in Algorithm Design

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

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.