Fetching the paper…
Reading the bibliography…
Despite its important applications in Machine Learning, min-max optimization of nonconvex-nonconcave objectives remains elusive.
Zur Theorie der Gesellschaftsspiele
John von Neumann · 1928
Earlier work this paper cites.
A proof of the equivalence of the programming problem and the game problem
George B. Dantzig · 1951
Earlier work this paper cites.
An analog of the minimax theorem for vector payoffs
David Blackwell · 1956
Earlier work this paper cites.
Existence and uniqueness of equilibrium points for concave n-person games
J Ben Rosen · 1965
Earlier work this paper cites.
Problems and results on 3-chromatic hypergraphs and some related questions
Paul Erdős and László Lovász · 1973
Earlier work this paper cites.
Fast multiple-precision evaluation of elementary functions
Richard P Brent · 1976
Earlier work this paper cites.
The extragradient method for finding saddle points and other problems
GM Korpelevich · 1976
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
Arkadiĭ Semenovich Nemirovsky and David Borisovich Yudin · 1983
Earlier work this paper cites.
How easy is local search?
David S Johnson, Christos H Papadimitriou, and Mihalis Yannakakis · 1988
Earlier work this paper cites.
Exponential lower bounds for finding brouwer fixed points
M. D. Hirsch, C. H. Papadimitriou, and S. A. Vavasis · 1989
Earlier work this paper cites.
A note on total functions, existence theorems, and computational complexity
N Meggido and CH Papadimitriou · 1989
Earlier work this paper cites.
Simple local search problems that are hard to solve
Alejandro A. Schäffer and Mihalis Yannakakis · 1991
Earlier work this paper cites.
Computational Complexity
C Papadimitriou · 1994
Earlier work this paper cites.
On the complexity of the parity argument and other inefficient proofs of existence
Christos H Papadimitriou · 1994
Earlier work this paper cites.
The relative complexity of NP search problems
Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi · 1995
Earlier work this paper cites.
The complexity of pure nash equilibria
Alex Fabrikant, Christos H. Papadimitriou, and Kunal Talwar · 2004
Earlier work this paper cites.
Interior point polynomial time methods in convex programming
Arkadi Nemirovski · 2004
Earlier work this paper cites.
Prediction, Learning, and Games
Nikolo Cesa-Bianchi and Gabor Lugosi · 2006
Earlier work this paper cites.
Finite-dimensional variational inequalities and complementarity problems
Francisco Facchinei and Jong-Shi Pang · 2007
Earlier work this paper cites.
Settling the complexity of computing two-player nash equilibria
Xi Chen, Xiaotie Deng, and Shang-Hua Teng · 2009
Earlier work this paper cites.
The complexity of computing a nash equilibrium
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou · 2009
Earlier work this paper cites.
A constructive proof of the lovász local lemma
Robin A Moser · 2009
Earlier work this paper cites.
On the complexity of nash equilibria and other fixed points
Kousha Etessami and Mihalis Yannakakis · 2010
Earlier work this paper cites.
A constructive proof of the general lovász local lemma
Robin A Moser and Gábor Tardos · 2010
Earlier work this paper cites.
Adaptive subgradient methods for online learning and stochastic optimization
John Duchi, Elad Hazan, and Yoram Singer · 2011
Earlier work this paper cites.
Continuous local search
Constantinos Daskalakis and Christos Papadimitriou · 2011
Earlier work this paper cites.
Market equilibrium under separable, piecewise-linear, concave utilities
Vijay V. Vazirani and Mihalis Yannakakis · 2011
Earlier work this paper cites.
Regret analysis of stochastic and nonstochastic multi-armed bandit problems
Sébastien Bubeck and Nicolo Cesa-Bianchi · 2012
Earlier work this paper cites.
Online learning and online convex optimization
Shai Shalev-Shwartz · 2012
Earlier work this paper cites.
The equivalence of linear programs and zero-sum games
Ilan Adler · 2013
Earlier work this paper cites.
On the complexity of approximating a nash equilibrium
Constantinos Daskalakis · 2013
Cited alongside, same era.
Generative Adversarial Nets
Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio · 2014
Cited alongside, same era.
Adam: A method for stochastic optimization
Diederik P Kingma and Jimmy Ba · 2014
Cited alongside, same era.
Constant rank bimatrix games are ppad-hard
Ruta Mehta · 2014
Cited alongside, same era.
Understanding machine learning: From theory to algorithms
Shai Shalev-Shwartz and Shai Ben-David · 2014
Cited alongside, same era.
On the cryptographic hardness of finding a nash equilibrium
Nir Bitansky, Omer Paneth, and Alon Rosen · 2015
Cited alongside, same era.
Ppp-completeness with connections to cryptography
Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis · 2018
Later among the works it cites.
Local saddle point optimization: A curvature exploitation approach
Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann · 2019
Later among the works it cites.
Accelerated methods for composite non-bilinear saddle point problem
Mohammad Alkousa, Darina Dvinskikh, Fedor Stonyakin, and Alexander Gasnikov · 2019
Later among the works it cites.
Last-iterate convergence rates for min-max optimization
Jacob Abernethy, Kevin A Lai, and Andre Wibisono · 2019
Later among the works it cites.
Last-iterate convergence: Zero-sum games and constrained min-max optimization
Constantinos Daskalakis and Ioannis Panageas · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Inapproximability of nash equilibrium
Aviad Rubinstein · 2015
Cited alongside, same era.
Nips 2016 tutorial: Generative adversarial networks
Ian Goodfellow · 2016
Cited alongside, same era.
Introduction to online convex optimization
Elad Hazan · 2016
Cited alongside, same era.
Integer factoring and modular square roots
Emil Jeřábek · 2016
Cited alongside, same era.
Unrolled generative adversarial networks
Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein · 2016
Cited alongside, same era.
Settling the complexity of computing approximate two-player nash equilibria
Aviad Rubinstein · 2016
Cited alongside, same era.
The complexity of splitting necklaces and bisecting ham sandwiches
Aris Filos-Ratsikas and Paul W. Goldberg · 2019
Later among the works it cites.
The hairy ball problem is ppad-complete
Paul W. Goldberg and Alexandros Hollender · 2019
Later among the works it cites.
Negative momentum for improved game dynamics
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julien, and Ioannis Mitliagkas · 2019
Later among the works it cites.
On the complexity of modulo-q arguments and the chevalley-warning theorem
Mika Göös, Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis · 2019
Later among the works it cites.
What is local optimality in nonconvex-nonconcave minimax optimization?
Chi Jin, Praneeth Netrapalli, and Michael I Jordan · 2019
Later among the works it cites.
An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
Weiwei Kong and Renato DC Monteiro · 2019
Later among the works it cites.
On gradient descent ascent for nonconvex-concave minimax problems
Tianyi Lin, Chi Jin, and Michael I Jordan · 2019
Later among the works it cites.
First-order methods almost always avoid strict saddle points
Jason D. Lee, Ioannis Panageas, Georgios Piliouras, Max Simchowitz, Michael I. Jordan, and Benjamin Recht · 2019
Later among the works it cites.
Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks
Tengyuan Liang and James Stokes · 2019
Later among the works it cites.
Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen · 2019
Later among the works it cites.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil · 2019
Later among the works it cites.
Solving a class of non-convex min-max games using iterative first order methods
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn · 2019
Later among the works it cites.
Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
Yuyuan Ouyang and Yangyang Xu · 2019
Later among the works it cites.
Efficient algorithms for smooth minimax optimization
Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh · 2019
Later among the works it cites.
On solving minimax optimization locally: A follow-the-ridge approach
Yuanhao Wang, Guodong Zhang, and Jimmy Ba · 2019
Later among the works it cites.
Optimal algorithms for stochastic three-composite convex-concave saddle point problems
Renbo Zhao · 2019
Later among the works it cites.
A tight and unified analysis of extragradient for a whole spectrum of differentiable games
Waïss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel · 2020
Closest in time.
Tree polymatrix games are ppad-hard
Argyrios Deligkas, John Fearnley, and Rahul Savani · 2020
Closest in time.
Consenus-halving: Does it ever get easier?
Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, and Manolis Zampetakis · 2020
Closest in time.
A topological characterization of modulo-p arguments and implications for necklace splitting
Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, and Manolis Zampetakis · 2020
Closest in time.
Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman E. Ozdaglar · 2020
Closest in time.
Near-optimal algorithms for minimax optimization
Tianyi Lin, Chi Jin, and Michael Jordan · 2020
Closest in time.
A provably convergent and practical algorithm for min-max optimization with applications to gans
Oren Mangoubi, Sushant Sachdeva, and Nisheeth K Vishnoi · 2020
Closest in time.
A second-order equilibrium in nonconvex-nonconcave min-max optimization: Existence and algorithm
Oren Mangoubi and Nisheeth K Vishnoi · 2020
Closest in time.