Games in Machine Learning Course
Winter semester 2023/2024
Abstract
A typical deep learning (DL) pipeline involves defining a utility or loss function and training a set of parameters to optimize it. However, this approach has its limitations. The specified objective might not effectively capture the desired behavior of the model, leading to highperforming models that struggle with accurate predictions when encountering slightly modified inputs. Additionally, these models may learn irrelevant correlations, resulting in subpar performance. This is often solved through a technique known as robustification, which employs a minmax objective. In this approach, two models, or players, are trained jointly. Each player has a different realvalued objective that depends on the parameters of both players. Consequently, in the field of machine learning, it becomes increasingly imperative to understand how to solve twoplayer games using iterative, gradientbased methods to find the Nash Equilibrium solution. Moreover, many problems in machine learning inherently involve multiple players. Examples include Generative Adversarial Networks, multiagent reinforcement learning, collaborative robots, and competing drones.
This course will use a framework encompassing all these problems called Variational Inequalities (VIs). Due to its generality, our studies also apply to standard minimization (singleplayer games). In addition to a brief introduction to game theory, this course focuses on:
 Variational Inequalities and classes of VIs,
 Gradientbased optimization methods to solve VIs,
 Applications of VIs in machine learning problems.
Lecturers:
 Tatjana Chavdarova is faculty at CISPA, with a research focus on the intersection of game theory and machine learning.
 Sebastian Stich is a faculty at CISPA, with a research focus on optimization for machine learning.
UdS students: visit cms course website.
Course Materials

Lecture 1: Introduction, Tatjana Chavdarova
• Slides
Covers:
• Optimization Intro
• Game Theory Intro
• What Makes a Game? (an ML perspective)
• Motivation to Study Games in ML

Lecture 2 & 3: Convex Optimization (singleplayer), Sebastian Stich

Lecture 4: Two Player Games, Tatjana Chavdarova
• Slides • Annotated
Covers:
• TwoPlayer Games: normal form games, zerosum and generalsum games
• Minimax Theorem
• Methods for Solving TwoPlayer Games: Gradient Descent & Extragradient

Lecture 5: Two Player Games (cont.), Tatjana Chavdarova
• Slides • Annotated • Exercises • Solutions
Covers:
• Minimax Theorem Proof Through Connection to Strong Linear Programming Duality
• Methods for Zerosum TwoPlayer Games (cont.): Proximal Point, Optimistic Gradient Descent, Lookahead
• Proximal Point perspective of ExtraGradient & Optimistic Gradient Descent

Lecture 6: Variational Inequality, Tatjana Chavdarova
• Slides • Annotated • Exercises • Solutions
Covers:
• Variational Inequality (VI)
• Examples: Represent a Problem as a VI, Complementarity Problem, Affine Problems
• Problem Classes: Lipschitz, Contractive, Averaged, Nonexpansive, (strongly) Monotone, Cocoercive, Cyclic

Lecture 7: Variational Inequalities II , Tatjana Chavdarova
• Slides • Annotated • Exercises • Solutions
Covers:
• Spectral Viewpoint on Problem Classes
• Monotone Inclusion
• Fixed Point Iteration
• Convergence of Averaged Operators

Lecture 8: Local Convergence (cont.) & Generative Adversarial Networks, Tatjana Chavdarova
• Slides • Annotated • Codedemo
Covers:
• Proof of Necessary and Sufficient Condition for Local Convergence
• Generative Adversarial Networks: Nash Equilibrium of the Framework & Practical Twist How to Train GANs

Lecture 9: The Resolvent & Operator Splitting , Tatjana Chavdarova
• Slides • Annotated • Exercises • Solutions
Covers:
• Operator Theory (cont.): Maximality, (Reflected) Resolvent
• Operator Splitting: forward↔backward, Douglas–Rachford Splitting
• Solving VIs with Contraints: KKT system of VIs and the ACVI method

Lecture 10: Convergence Analysis in Continioustime , Tatjana Chavdarova
• Slides • Annotated • Exercises • Solutions
Covers:
• Continioustime Dynamics
• From a Discrete Method to a ContinuousTime Dynamics
• Case study: bilinear games
• Lyapunov sability

Lecture 11: Mirror Descent & Mirror Prox , Tatjana Chavdarova
• Slides • Annotated
Covers:
• Motivation
• VariableMetric Methods
• Mirror Descent: Mirror maps, Bregman divergence, MD algorithm
• Mirror Prox
Guest Lecture: The Complexity of Constrained MinMax Optimization — Manolis Zampetakis
February 6th, 2024
» Slides Abstract.
Despite its important applications in Machine Learning, minmax optimization of objective functions that are nonconvexnonconcave remains elusive. We show that an approximate local minmax point of large enough approximation is guaranteed to exist, but finding one such point is PPADcomplete. The same is true of computing an approximate fixed point of the (Projected) Gradient Descent/Ascent update dynamics.
An important byproduct of our proof is to establish an unconditional hardness result in the NemirovskyYudin oracle optimization model. In particular, we show that, given oracle access to some function and its gradient, every algorithm that finds an approximate local minmax point needs to make a number of queries that is exponential in the dimension or the accuracy. This comes in sharp contrast to minimization problems, where finding approximate local minima in the same setting can be done with Projected Gradient Descent polynomially many queries. Our result is the first to show an exponential separation between these two fundamental optimization problems in the oracle model.
Joint work with Constantinos Daskalakis and Stratis Skoulakis.
 Short Bio.
Manolis Zampetakis is currently an Assistant Professor at the Computer Science Department of Yale University. Before that, he was a postdoctoral researcher at the EECS Department of UC Berkeley working with Michael Jordan. He received his PhD from the EECS Department at MIT where he was advised by Constantinos Daskalakis. He has been awarded the Google PhD Fellowship and the ACM SIGEcom Doctoral Dissertation Award. He works on the foundations of machine learning (ML), statistics, and data science, with a focus on statistical analysis from biased data, optimization methods in multiagent environments, and convergence properties of popular heuristic methods.
 Paper: https://arxiv.org/abs/2009.09623
Resources & References
by Ernest Ryu and Wotao Yin; Cambridge University Press 2023
Contact
For typos, remarks, or you'd like to use the latex code of the slides feel free to reach out at: tatjana.chavdarova[at]berkeley[dot]edu.
Thanks!