91125\
    `florian.schaefer@caltech.edu` Anima Anandkumar\
    Computing and Mathematical Sciences\
    California Institute of Technology\
    Pasadena, CA 91125\
    `anima@caltech.edu`
bibliography:
- 'refs.bib'
title: Competitive Gradient Descent
---

\[section\] \[theorem\] \[theorem\][Lemma]{} \[theorem\][Remark]{}

Introduction
============

**Competitive optimization:** Whereas traditional optimization is concerned with a single agent trying to optimize a cost function, competitive optimization extends this problem to the setting of multiple agents each trying to minimize their own cost function, which in general depends on the actions of all agents. The present work deals with the case of two such agents: $$\begin{aligned}
    \label{eqn:game}
    &\min_{x \in {\mathbb{R}}^m} f(x,y),\ \ \ \min_{y \in {\mathbb{R}}^n} g(x,y)\end{aligned}$$ for two functions $f,g:{\mathbb{R}}^m \times {\mathbb{R}}^n \longrightarrow {\mathbb{R}}$.\
In single agent optimization, the solution of the problem consists of the minimizer of the cost function. In competitive optimization, the right definition of *solution* is less obvious, but often one is interested in computing Nash– or strategic equilibria: Pairs of strategies, such that no player can decrease their costs by unilaterally changing their strategies. If $f$ and $g$ are not convex, finding a global Nash equilibrium is typically impossible and instead we hope to find a “good” local Nash equilibrium.

**The benefits of competition:** While competitive optimization problems arise naturally in mathematical 