CAREER: Discrete Convexity in 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.