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.

AduC_057_Legendre_(L.,_1756-1797)

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!

 

 

Advertisements

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.

20180612_142435

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!

20180909_153659

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.

constraints

candidates

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.