Who thought the algorithm behind machine learning would have cool complexity implications?
Let's unpack these classes, subclasses of TFNP, where for every input we know there is an easily verifiable solution and we are looking at the complexity of finding it. PPAD is the class famous for having finding a Nash Equilibrium as a complete set, see this post for details.
PLS is the class of problems where we look for a local minimum. Finding a global minimum is NP-complete--think vertex cover. Finding a local minimum is often easier but still could be hard if you are optimizing over an exponential set of values.
CLS is a bit trickier to define, basically you are finding an approximate local minimum of a function mapping three real variables to one real value.
The authors show that gradient descent is complete for PPAD ∩ PLS even if you only use two input variables. Since gradient descent is in CLS, the equality follows.
More in my 2021 post. On that post author Paul Goldberg commented
The paper is a fine example of the humorous stereotype of complexity theorists proving a problem "hard" when meanwhile the problem is being routinely solved in practice in the real world.
Nevertheless it's a neat complexity result and now officially one of my favorite theorems.
A follow up paper by Goos et. al, Further Collapses in TFNP, is also quite nice! They give a simplified proof of CLS = PPAD ∩ PLS and further show CLS = EOPL. They also show SOPL = PLS ∩ PPADS.
ReplyDeleteThis is indeed a beautiful paper. But if you post about it in 2024, it's worth noting that it is effectively obsolete: this follow-up paper showed an even stronger collapse with a *much* simpler proof!
ReplyDeleteMika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao:
"Further Collapses in TFNP"
https://arxiv.org/abs/2202.07761
On the topic of further work, there are CLS-completeness results for some interesting and important problems. Mainly, mixed-strategy equilibria of congestion games (Settling the complexity of Nash equilibrium in congestion games, by Babichenko and Rubinstein), and KKT solutions of quadratic programs (The Complexity of Computing KKT Solutions of Quadratic Programs, by Fearnley, myself, Hollender, and Savani).
ReplyDelete