Linear Lower Bounds and Conditioning of Differentiable Games
  Recent successes of game-theoretic formulations in ML have caused a
resurgence of research interest in differentiable games. Overwhelmingly, that
research focuses on methods and upper bounds on their speed of convergence. In
this work, we approach the question of fundamental iteration complexity by
providing lower bounds to complement the linear (i.e. geometric) upper bounds
observed in the literature on a wide class of problems. We cast saddle-point
and min-max problems as 2-player games. We leverage tools from single-objective
convex optimisation to propose new linear lower bounds for convex-concave
games. Notably, we give a linear lower bound for $n$-player differentiable
games, by using the spectral properties of the update operator. We then propose
a new definition of the condition number arising from our lower bound analysis.
Unlike past definitions, our condition number captures the fact that linear
rates are possible in games, even in the absence of strong convexity or strong
concavity in the variables.
