FOCS 2021

A (very) preliminary call for papers for FOCS 2021 now available:…


This year, the submission deadline has been delayed to early June. This is in order to maximize the chances of a physical conference (sometime in early 2022).

Algorithms for Convex Optimization Book

I am excited to announce that a pre-publication draft of my book Algorithms for Convex Optimization (to be published by Cambridge University Press) is now available for download here:

Algorithms for Convex Optimization Book

The goal of this book is to enable a reader to gain an in-depth understanding of algorithms for convex optimization. The emphasis is to derive key algorithms for convex optimization from first principles and to establish precise running time bounds in terms of the input length.

The intended audience includes advanced undergraduate students, graduate students and researches from theoretical computer science, discrete optimization, and machine learning.

The book has four parts:

  1. Chapters 3,4, and 5: Introduction to convexity, models of computation and notions of efficiency in convex optimization, Lagrangian duality, Legendre-Fenchel duality, and KKT conditions.
  2. Chapters 6,7, and 8: First-order methods such as gradient descent, mirror descent and the multiplicative weights update method, and accelerated gradient descent.
  3. Chapters 9,10, and 11: Newton’s method, path-following interior point methods for linear programming, and self-concordant barrier functions.
  4. Chapter 11 and 12: Cutting plane methods such as the ellipsoid method for linear and general convex programs.

Chapter 1 summarizes the book via a brief history of the interplay between continuous and discrete optimization: how the search for fast algorithms for discrete problems is leading to improvements in algorithms for convex optimization.

Many chapters contain applications ranging from finding maximum flows, minimum cuts, and perfect matchings in graphs, to linear optimization over 0-1-polytopes, to submodular function minimization, to computing maximum entropy distributions over combinatorial polytopes.

The book is self-contained and starts with a review of calculus, linear algebra, geometry, dynamical systems, and graph theory in Chapter 2. Exercises posed in this book not only play an important role in checking one’s understanding, but sometimes important methods and concepts are introduced and developed entirely through them. Examples include the Frank-Wolfe method, coordinate descent, stochastic gradient descent, online convex optimization, the min-max theorem for zero-sum games, the Winnow algorithm for classification, the conjugate gradient method, primal-dual interior point method, and matrix scaling.

Feedback, corrections, and comments are welcome.

The dynamics of Lagrange and Hamilton

In 1788, Lagrange presented a set of equations of motion that, unlike Newtonian mechanics, are independent of the choice of coordinates of the physical system, and ultimately led to the formulation of general relativity. Hamilton came up with a different set of equations of motion in 1833 that arguably led to the development of quantum mechanics. Remarkably, in classical mechanics, these sets of equations turn out to be equivalent via a beautiful duality due to Legendre.


A portrait of Legendre by H. Rousseau, E. Thomas, Augustin Challamel, and Desire Lacroix via Wikimedia Commons

Lagrangian and Hamiltonian dynamics have inspired several promising optimization and sampling algorithms such as first-order methods in optimizationHamiltonian Monte Carlo (see also this paper that will appear in NIPS 2018). Legendre duality also appears in convex optimization as Fenchel dualityThis note, written primarily for optimization folks, introduces Lagrangian dynamics, Hamiltonian dynamics, and proves the duality that connects them.

I hope that these fundamental ideas inspire you as well to think about optimization from a physics perspective!



Fair Elections

Elisa Celis and Nisheeth Vishnoi

Elections are the nervous system of a democracy and, hence, issues related to their transparency and fairness are central to healthy societies. However, the number of controversial elections has exploded since 2000, and the more recent ones involve the use of the Internet and algorithms — a good excuse for computer scientists to get involved in elections to save democracy!

Last year, the two of us and Lingxao Huang revisited the question of fairness in multi-winner elections. A multi-winner election is one where the objective is to select a committee from a set of candidates based on voter preferences. However, election systems for multi-winner elections have been shown to be biased against minorities by giving preference to committees that under-represent their already-small numbers. When the candidates have certain sensitive attributes (such as gender), and different types (e.g., male, female and non-binary) we may instead wish to impose additional requirement so that the winning committee is fair. We considered the problem of finding the committee with the maximum number of votes, subject to such additional fairness requirements.

But what does it mean to be fair?

Is a committee fair when types are equally represented? Or proportionally represented? These questions have received more than a century’s worth of attention in social choice theory and are deeply entangled with culture and politics. In short, fairness means different things in different contexts and rather than addressing a specific instance of this question, we asked ourselves — can we provide a framework in which a user can specify fairness constraints according to their needs and design algorithms that can compute the winning committee accordingly?

Because such a framework must handle general classes of constraints, the algorithmic task became more challenging than the usual unconstrained case. If you are interested in understanding our algorithmic and complexity results, they appear in our recent paper that was presented at IJCAI-ECAI this year.

Clearly, however, there are real merits to providing such generality — earlier this year, our paper caught the eye of members of a people’s movement from the Valais canton in Switzerland, who were in the process of rethinking elections in their region. They were happy to know that we had solved the exact problem they needed for a primary election and asked us if we would be willing to help them conduct their elections. We were, of course, thrilled!

After an intense collaboration for more than four months, 8 elections that used our framework concluded on September 9, 2018. For us, there were several eye-opening aspects of taking our algorithmic framework from theory to practice. Perhaps the most interesting one was coming up with an answer to:

Who decides what is fair?

In this case, it was the voters! Before voting on the committee, a vote to determine the fairness constraints was conducted in each of the eight districts. This vote was in mid-June and also checked if the voters agree to use our algorithmic framework. Since transparency was the key motivation, prior to this vote,  we were invited to a press conference to educate the people about the whole process that resulted in coverage in newspapers Le Temps,  Le Nouvelliste, TV channel Canal 9, and radio channels Rhone FM and  Radio Chablais.


An image from the press conference in Sion on June 12, 2018. Elisa Celis (center), accompanied by members of Appel Citoyen.

In the end, the voters decided to place constraints on the gender balance, age demographics, and regions. While all districts approved these same three attributes, the specific constraints varied by district according to their demographics and pre-defined regions. This was a truly open and democratic way to determine the criteria by which the committee was to be balanced. The constraints not only ensured that the outcome would be fair (as defined by the voters) but also encouraged many more women to run for election than the party originally anticipated — in fact, in several districts there were more women than men contesting the election!


Computing the winning committees in Sion on September 9, 2018. From L to R: Lingxiao Huang, Vijay Keswani, Elisa Celis, Florian Evequoz, Bernadette Morand-Aymon.

Everything about these elections, from votes, candidates, constraints, and code, to the output, is open for all to verify. We have also made available a demo with pre-loaded constraints, candidate information, and votes for anyone to test and compute the results. To know more about the use of our algorithm in these elections, take a look at this video. A few links to the coverage of these elections can be found here: Canal 9,  Le Temps, Le Nouvelliste.

We feel fortunate that we were given this unique opportunity to take tools from computer science to the heart of a democratic process. It was an unparalleled learning experience for all of us and something that we increasingly look forward to in the future.



You can also use our demo to design your own elections and play around with our algorithms. This demo was developed with the help of Abhibhav Garg and Vijay Keswani and has limited functionality. If you are interested in using our full framework and/or working with us,  please feel free to contact us.



An Exposition on Geodesic Convexity

I arrived at the Institute for Advanced Study to attend a workshop on Optimization, Complexity and Invariant Theory organized by Avi Wigderson. The workshop has an incredibly diverse agenda, also reflected in the participants.

I will talk about Geodesic Convexity: Sometimes, functions that are non-convex in the Euclidean space turn out to be convex if one introduces a suitable metric (or differential structure) and redefines convexity with respect to the induced straight lines — geodesics. Such a function is called geodesically convex. Unlike standard convexity,  when does a function have this property and how to optimize it, is not well-understood. My talk will focus on introducing geodesic convexity and show that the problem of computing the Brascamp-Lieb constant has a succinct geodesically convex formulation.

And, accompanying my talk are these self-contained and expository notes on differentiation on manifolds, geodesics, and geodesic convexity that are prepared with the help of my student Ozan Yildiz.