CS Machine Learning Seminar: Equilibrium Complexity and Deep Learning

Thursday, October 6, 2022
3:30 p.m.
Online presentation
Soheil Feizi

Computer Science Department Machine Learning Seminar

Equilibrium Complexity and Deep Learning

Constantinos Daskalakis
Avanessians Professor of Electrical Engineering and Computer Science

Zoom link
Password: 828w

Deep learning has recently made significant progress in learning challenges such as speech and image recognition, automatic translation, and text generation, much of that progress being fueled by the success of gradient descent-based optimization methods in computing local optima of non-convex objectives. From robustifying machine learning models against adversarial attacks to causal inference, training generative models, multi-robot interactions, and learning in strategic environments, many outstanding challenges in Machine Learning lie at its interface with Game Theory. On this front, however, Deep Learning has been less successful. Here, the role of single-objective optimization is played by equilibrium computation, but gradient-descent based methods fail to find equilibria, and even computing local equilibria -- the analog of computing local optima in single-agent settings -- has remained elusive.

We shed light on these challenges through a combination of learning-theoretic, complexity-theoretic, and game-theoretic techniques, presenting obstacles and opportunities for Machine Learning and Game Theory going forward, including recent progress on multi-agent reinforcement learning.

(I will assume no deep learning, game theory, or complexity theory background for this talk and present results from joint works with Noah Golowich, Stratis Skoulakis, Manolis Zampetakis, and Kaiqing Zhang.)

References: - The Complexity of Constrained Min-Max Optimization: https://arxiv.org/abs/2009.09623

- The Complexity of Markov Equilibrium in Stochastic Games: https://arxiv.org/abs/2204.03991

Constantinos "Costis" Daskalakis is the Avanessians Professor of Electrical Engineering and Computer Science at MIT. He holds a Diploma in Electrical and Computer Engineering from the National Technical University of Athens, and a PhD in Electrical Engineering and Computer Science from UC Berkeley. He works on Computation Theory and its interface with Game Theory, Economics, Probability Theory, Machine Learning and Statistics. He has resolved long-standing open problems about the computational complexity of Nash equilibrium, and the mathematical structure and computational complexity of multi-item auctions. His current work focuses on multi-agent learning, high-dimensional statistics, learning from biased and dependent data, causal inference and econometrics. He has been honored with the ACM Doctoral Dissertation Award, the Kalai Prize from the Game Theory Society, the Sloan Fellowship in Computer Science, the SIAM Outstanding Paper Prize, the Microsoft Research Faculty Fellowship, the Simons Investigator Award, the Rolf Nevanlinna Prize from the International Mathematical Union, the ACM Grace Murray Hopper Award, the Bodossaki Foundation Distinguished Young Scientists Award, and the ACM SIGECOM Test of Time Award.

remind we with google calendar


December 2022

27 28 29 30 1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
1 2 3 4 5 6 7
Submit an Event