Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 6, 2020 | Submitted
Report Open

Competitive Mirror Descent


Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. This is a highly expressive modeling language that subsumes most of modern machine learning. In this work we propose competitive mirror descent (CMD): a general method for solving such problems based on first order information that can be obtained by automatic differentiation. First, by adding Lagrange multipliers, we obtain a simplified constraint set with an associated Bregman potential. At each iteration, we then solve for the Nash equilibrium of a regularized bilinear approximation of the full problem to obtain a direction of movement of the agents. Finally, we obtain the next iterate by following this direction according to the dual geometry induced by the Bregman potential. By using the dual geometry we obtain feasible iterates despite only solving a linear system at each iteration, eliminating the need for projection steps while still accounting for the global nonlinear structure of the constraint set. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.

Additional Information

AA is supported in part by Bren endowed chair, DARPA PAIHR00111890035, LwLL grants, Raytheon, BMW, Microsoft, Google, Adobe faculty fellowships, and DE Logi grant. FS gratefully acknowledges support by the Ronald and Maxine Linde Institute of Economic and Management Sciences at Caltech. FS and HO gratefully acknowledge support by the Air Force Office of Scientific Research under award number FA9550-18-1-0271 (Games for Computation and Learning) and the Office of Naval Research under award number N00014-18-1-2363.

Attached Files

Submitted - 2006.10179.pdf


Files (2.0 MB)
Name Size Download all
2.0 MB Preview Download

Additional details

August 19, 2023
October 20, 2023