Combinatorial Algorithms and Continuous Optimization

I am seeking motivated students and interns who want to work with me in Theoretical Computer Science or Machine Learning. The broad themes I am interested in involve combinatorial algorithms and continuous optimization. A solid mathematical background is necessary.

The goal is to develop fast and practical solutions for fundamental algorithmic problems. This involves designing faster algorithms for classical problems in combinatorial optimization (involving graphs, matchings, submodular functions, matroids, etc.), and developing new theory relevant to modern machine learning (with a focus on deep learning). The mathematical toolkit is based on modern techniques from continuous optimization, and interferes with other interesting theory from convex geometry, probability and numerical linear algebra.

I will supervise several projects on the following topics:

Fast computation of optimal matchings, paths, flows.

Develop fast graph algorithms using a mix of continuous and combinatorial optimization. This approach has led to amazing breakthroughs, such as maximum flow in almost linear time. This paradigm is extremely promising for a series of open problems in algorithmic graph theory.

Related publications:

Faster Sparse Minimum Cost Flow by Electrical Flow Localization	Axiotis, Madry, Vladu	FOCS 2021	[arXiv]
Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs	Axiotis, Madry, Vladu	FOCS 2020	[arXiv]
Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in $\tilde{O}(m^{10/7} \log W)$ Time	Cohen, Madry, Sankowski, Vladu	SODA 2017	[arXiv]

Optimization for submodular functions.

Submodular functions are fundamental combinatorial objects. We intend to study efficient algorithms for minimizing submodular functions or improved approximations for submodular maximization.

Related publications:

Decomposable Submodular Function Minimization via Maximum Flow	Axiotis, Karczmarz, Mukherjee, Sankowski, Vladu	ICML 2021	[arXiv]
Submodular Maximization with Matroid and Packing Constraints in Parallel	Ene, Nguyen, Vladu	STOC 2019	[arXiv]

Efficient numerical methods.

How fast can you solve general linear programs or regression problems? What about simpler tasks such as solving a linear system $Ax=b$? These questions are intimately connected to each other. Many recent breakthroughs in algorithmic graph theory have had an impact on these more general tasks.

Related publications:

Interior Point Methods with a Gradient Oracle	Vladu	STOC 2023	[arXiv]
Improved Convergence for $\ell_\infty$ and $\ell_1$ Regression via Iteratively Reweighted Least Squares	Ene, Vladu	ICML 2019	[arXiv]
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods	Cohen, Madry, Tsipras, Vladu	FOCS 2017	[arXiv]

Discrepancy Theory.

Discrepancy theory is a subfield of combinatorics which has branched in Computer Science due to several connections it has to geometric problems, randomized algorithms and complexity theory. A landmark result in the field is Spencer’s celebrated Six standard deviations suffice. In its simplest form, Spencer’s paper considers a set system $S$ of cardinality $n$ over a ground set of $n$ elements. The problem is to color each element of the ground set in red or blue, such that all the sets in the system are balanced in the sense that no set contains many more red than blue elements or vice-versa. The maximum imbalance of a set induced by this coloring is called the discrepancy of the coloring.

Spencer’s result offers an important insight into the limitations of the tools we generally employ to prove the existence of mathematical objects. A standard method to show that there always exists a low discrepancy coloring is to prove that a random coloring produces one with nonzero probability. To this end, one shows that for each set in $S$, a random coloring will have small discrepancy, with high probability. Applying a union bound turns this into a guarantee for all sets in $S$. This standard approach shows that one can always produce a coloring which achieves discrepancy $O(\sqrt{n \log n})$. Howeverm this approach misses even better colorings. Using a difficult nonconstructive argument Spencer proves that in fact colorings with discrepancy $6\sqrt{n}$ exist. This result is tight up to constant factors, and exhibits an example where correlations between different sets in $S$ can be exploited in order to overcome the limitations of the union bound technique, which essentially tries to ignore them.

It turns out that techniques from continuous optimization are very well suited to attacking discrepancy problems, and we intend to use them to make further progress on several open problems in the field.

Related publications:

Discrepancy Minimization via Regularization	Pesenti, Vladu	SODA 2023	[arXiv]

Efficient Optimization for Machine Learning.

How fast can we train machine learning models? How to make them stable? Why do they generalize well? Present day deep learning models require training millions (or billions) of parameters, which is very slow and expensive. Can we make this process more efficient?

We use tools from optimization, convex geometry and probability to provide algorithms with provable guarantees, and develop new techniques that will have an impact in practice.

Related publications:

CrAM: A Compression-Aware Minimizer	Peste, Vladu, Kurtic, Lampert, Alistarh		[arXiv]
AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks	Peste, Iofinova, Vladu, Alistarh	NeurIPS 2021	[arXiv]
Adaptive Gradient Methods for Constrained Convex Optimization	Ene, Nguyen, Vladu	AAAI 2021	[arXiv]
Towards Deep Learning Models Resistant to Adversarial Attacks	Madry, Makelov, Schmidt, Tsipras, Vladu	ICLR 2018	[arXiv]