Games in Machine Learning
Advanced lecture, winter 2023/2024
CISPA & Saarland University

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 high-performing 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 min-max objective. In this approach, two models, or players, are trained jointly. Each player has a different real-valued 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 two-player games using iterative, gradient-based methods to find the Nash Equilibrium solution. Moreover, many problems in machine learning inherently involve multiple players. Examples include Generative Adversarial Networks, multi-agent 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 (single-player games). In addition to a brief introduction to game theory, this course focuses on:

• Variational Inequalities and classes of VIs,
• Gradient-based 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 (single-player), Sebastian Stich

• Lecture 4: Two Player Games, Tatjana Chavdarova

  • Slides • Annotated
  Covers:
  • Two-Player Games: normal form games, zero-sum and general-sum games
  • Minimax Theorem
  • Methods for Solving Two-Player 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 Zero-sum Two-Player 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, Non-expansive, (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 • Code-demo
  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 Continious-time , Tatjana Chavdarova

  • Slides • Annotated • Exercises • Solutions
  Covers:
  • Continious-time Dynamics
  • From a Discrete Method to a Continuous-Time Dynamics
  • Case study: bilinear games
  • Lyapunov sability
  

• Lecture 11: Mirror Descent & Mirror Prox , Tatjana Chavdarova

  • Slides • Annotated
  Covers:
  • Motivation
  • Variable-Metric Methods
  • Mirror Descent: Mirror maps, Bregman divergence, MD algorithm
  • Mirror Prox
  

Guest Lecture: The Complexity of Constrained Min-Max Optimization — Manolis Zampetakis

February 6th, 2024

• Abstract. Despite its important applications in Machine Learning, min-max optimization of objective functions that are nonconvex-nonconcave remains elusive. We show that an approximate local min-max point of large enough approximation is guaranteed to exist, but finding one such point is PPAD-complete. 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 Nemirovsky-Yudin oracle optimization model. In particular, we show that, given oracle access to some function and its gradient, every algorithm that finds an approximate local min-max 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 post-doctoral 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 multi-agent environments, and convergence properties of popular heuristic methods.
  
• Paper: https://arxiv.org/abs/2009.09623

Resources & References

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.