Many recent machine learning tools rely on differentiable game formulations.
While several numerical methods have been proposed for these types of games,
most of the work has been on convergence proofs or on upper bounds for the rate
of convergence of those methods. In this work, we approach the question of
fundamental iteration complexity by providing lower bounds. We generalise
Nesterov's argument -- used in single-objective optimisation to derive a lower
bound for a class of first-order black box optimisation algorithms -- to games.
Moreover, we extend to games the p-SCLI framework used to derive spectral lower
bounds for a large class of derivative-based single-objective optimisers.
Finally, we propose a definition of the condition number arising from our lower
bound analysis that matches the conditioning observed in upper bounds. Our
condition number is more expressive than previously used definitions, as it
covers a wide range of games, including bilinear games that lack strong
convex-concavity.
Description
[1906.07300] Lower Bounds and Conditioning of Differentiable Games
%0 Journal Article
%1 ibrahim2019lower
%A Ibrahim, Adam
%A Azizian, Waïss
%A Gidel, Gauthier
%A Mitliagkas, Ioannis
%D 2019
%K bounds game-theory
%T Lower Bounds and Conditioning of Differentiable Games
%U http://arxiv.org/abs/1906.07300
%X Many recent machine learning tools rely on differentiable game formulations.
While several numerical methods have been proposed for these types of games,
most of the work has been on convergence proofs or on upper bounds for the rate
of convergence of those methods. In this work, we approach the question of
fundamental iteration complexity by providing lower bounds. We generalise
Nesterov's argument -- used in single-objective optimisation to derive a lower
bound for a class of first-order black box optimisation algorithms -- to games.
Moreover, we extend to games the p-SCLI framework used to derive spectral lower
bounds for a large class of derivative-based single-objective optimisers.
Finally, we propose a definition of the condition number arising from our lower
bound analysis that matches the conditioning observed in upper bounds. Our
condition number is more expressive than previously used definitions, as it
covers a wide range of games, including bilinear games that lack strong
convex-concavity.
@article{ibrahim2019lower,
abstract = {Many recent machine learning tools rely on differentiable game formulations.
While several numerical methods have been proposed for these types of games,
most of the work has been on convergence proofs or on upper bounds for the rate
of convergence of those methods. In this work, we approach the question of
fundamental iteration complexity by providing lower bounds. We generalise
Nesterov's argument -- used in single-objective optimisation to derive a lower
bound for a class of first-order black box optimisation algorithms -- to games.
Moreover, we extend to games the p-SCLI framework used to derive spectral lower
bounds for a large class of derivative-based single-objective optimisers.
Finally, we propose a definition of the condition number arising from our lower
bound analysis that matches the conditioning observed in upper bounds. Our
condition number is more expressive than previously used definitions, as it
covers a wide range of games, including bilinear games that lack strong
convex-concavity.},
added-at = {2019-09-04T15:55:19.000+0200},
author = {Ibrahim, Adam and Azizian, Waïss and Gidel, Gauthier and Mitliagkas, Ioannis},
biburl = {https://www.bibsonomy.org/bibtex/2094cdda3321aef00e5f5d16ac536bc42/kirk86},
description = {[1906.07300] Lower Bounds and Conditioning of Differentiable Games},
interhash = {8ae9013551350fb7b5e12930162c142c},
intrahash = {094cdda3321aef00e5f5d16ac536bc42},
keywords = {bounds game-theory},
note = {cite arxiv:1906.07300Comment: Submitted to NeurIPS 2019},
timestamp = {2019-09-04T15:55:19.000+0200},
title = {Lower Bounds and Conditioning of Differentiable Games},
url = {http://arxiv.org/abs/1906.07300},
year = 2019
}