Frontiers in Economics and Computation - UK

This seminar series features research in Economics and Computation, Game Theory, Optimisation in a broad sense

Join Mailing List   -   Twitter

 

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS

  • Abstract. We consider the problem of computing a Gradient Descent solution of a continuously differentiable function f on a bounded convex domain, i.e., finding a "point where Gradient Descent terminates". Equivalently, this corresponds to computing a so-called KKT (Karush-Kuhn-Tucker) stationary point of f. We study this problem in the "white box" model, where the function f is given in the input, e.g., as an arithmetic circuit. By some standard arguments, it follows that the problem lies in the intersection of the complexity classes PPAD and PLS. PPAD is mostly known for capturing the complexity of computing a Nash equilibrium, while PLS has been successful in characterizing the complexity of various local optimization problems, such as Local-Max-Cut. We prove that the Gradient Descent problem is complete for PPAD ∩ PLS. In particular, this implies that the class CLS ("Continuous Local Search") which was previously thought to be a strict subset of PPAD ∩ PLS, is in fact equal to it.
p1

Alexandros Hollender (Oxford)

8 December '21

  • Bio. Alexandros Hollender is a postdoctoral research fellow at All Souls college, University of Oxford. His research interests lie mainly in algorithms and computational complexity, including applications in various fields such as game theory, fair division and optimization. His work focuses on total search problems and the various complexity classes that arise in their study. He recently completed his PhD at the University of Oxford under the supervision of Paul Goldberg. Previously, he studied at the Technical University of Munich (TUM), Ecole polytechnique and Stanford University.

Historical Notes and Further Readings

  • Various problems arising from diverse areas such as game theory, economics, optimization, and cryptography, have the property that a solution is guaranteed to exist (by some mathematical existence argument), but it is unclear how to compute it efficiently. Examples include FACTORING (given a number, compute its prime factors) and NASH (given a game, compute a mixed Nash equilibrium). Formally, these problems lie in the complexity class TFNP of total NP search problems, which was first defined by Megiddo and Papadimitriou [1]. Importantly, Megiddo and Papadimitriou noted that, even though many of them are seemingly hard, TFNP problems cannot be NP-hard unless NP = co-NP. In an attempt to study these problems further and provide some evidence of intractability, various "syntactic" sub-classes of TFNP have been defined, such as PPAD and PLS [2,3]. These sub-classes have complete problems and they have indeed been very successful in exactly capturing the complexity of important problems. The problem of computing a Nash equilibrium, and various other problems in economics have been shown to be PPAD-complete [4,5]. The class PLS is known to characterize the complexity of computing a pure Nash equilibrium in a congestion game [6], or finding a local max-cut in a weighted graph [7]. However, many problems remain unclassified.

    In 2011, Daskalakis and Papadimitriou [8] noted that many of these unclassified problems lie both in PPAD and in PLS and are thus unlikely to be complete for either of the two classes. Examples include the problem of computing a mixed Nash equilibrium of a congestion game, solving simple stochastic games (SSGs), computing the unique fixed point of a contracting map. They also argued that these problems are unlikely to be complete for PPAD ∩ PLS, since this intersection of classes seems to only have artificial complete problems. In order to address this, they defined a more natural sub-class of PPAD ∩ PLS, which they called CLS (Continuous Local Search), and proved that the problems of interest also lie in CLS. In the past 10 years there has been very little progress on proving that any of these problems is CLS-complete. In a surprising paper that received a best-paper award at STOC 2021, Fearnley et al. [9] proved that in fact CLS = PPAD ∩ PLS, and that PPAD ∩ PLS exactly characterizes the complexity of computing a "gradient descent solution". It is expected that these new insights will help to understand the complexity of the other problems of interest in CLS. Indeed, using this connection to gradient descent, Babichenko and Rubinstein [10] were able to show that the problem of computing a mixed Nash equilibrium of a congestion game is PPAD ∩ PLS-complete.
  • Related Work
  1. Nimrod Megiddo and Christos H. Papadimitriou. "On total functions, existence theorems and computational complexity." Theoretical Computer Science 81.2 (1991): 317-324.
  2. Christos H. Papadimitriou. "On the complexity of the parity argument and other inefficient proofs of existence." Journal of Computer and System Sciences 48.3 (1994): 498-532.
  3. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. "How easy is local search?" Journal of Computer and System Sciences 37.1 (1988): 79-100.
  4. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. "The complexity of computing a Nash equilibrium." SIAM Journal on Computing 39.1 (2009): 195-259.
  5. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. "Settling the complexity of computing two-player Nash equilibria." Journal of the ACM 56.3 (2009): 14:1-14:57.
  6. Alex Fabrikant, Christos H. Papadimitriou, and Kunal Talwar. "The complexity of pure Nash equilibria." Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004): 604-612.
  7. Alejandro A. Schäffer. "Simple local search problems that are hard to solve." SIAM journal on Computing 20.1 (1991): 56-87.
  8. Constantinos Daskalakis and Christos H. Papadimitriou. "Continuous local search." Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011): 790-804.
  9. John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani. "The Complexity of Gradient Descent: CLS = PPAD ∩ PLS." Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC 2021): 46-59.
  10. Yakov Babichenko and Aviad Rubinstein. "Settling the complexity of Nash equilibrium in congestion games." Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC 2021): 1426-1437.
Top