CaltechAUTHORS
  A Caltech Library Service

Competitive Mirror Descent

Schäfer, Florian and Anandkumar, Anima and Owhadi, Houman (2020) Competitive Mirror Descent. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20201106-120218966

[img] PDF - Submitted Version
See Usage Policy.

1949Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20201106-120218966

Abstract

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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/2006.10179arXivDiscussion Paper
ORCID:
AuthorORCID
Owhadi, Houman0000-0002-5677-1600
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.
Funders:
Funding AgencyGrant Number
Bren Professor of Computing and Mathematical SciencesUNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)HR00111890035
Learning with Less Labels (LwLL)UNSPECIFIED
BMWUNSPECIFIED
Microsoft Faculty FellowshipUNSPECIFIED
Google Faculty Research AwardUNSPECIFIED
AdobeUNSPECIFIED
Caltech De Logi FundUNSPECIFIED
Linde Institute of Economic and Management ScienceUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0271
Office of Naval Research (ONR)N00014-18-1-2363
Record Number:CaltechAUTHORS:20201106-120218966
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20201106-120218966
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106491
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:06 Nov 2020 22:52
Last Modified:06 Nov 2020 22:52

Repository Staff Only: item control page