Course material & Lecture notes
■ Nonlinear Optimization (MIT 6.7220 / 15.084, Spring 2024)
Introduction to the fundamentals of nonlinear optimization theory and algorithms. When applicable, emphasis is put on modern applications, especially within machine learning and its sub-branches, including online learning, computational decision-making, and nonconvex applications in deep learning.Course material
2024-02-06
html | pdf |
[L01]
Introduction
Overview of the course material; goals and applications; general form of an optimization problem; Weierstrass's theorem; computational considerations.
|
2024-02-08
html | pdf |
[L02]
First-order optimality conditions
First-order necessary optimality conditions; the unconstrained case; halfspace constraints; a first taste of Lagrange multipliers and duality.
|
2024-02-13
html | pdf |
[L03]
The special case of convex functions
Definition of convexity for functions; local optimality implies global optimality; sufficiency of first-order optimality conditions; how to recognize a convex function.
|
2024-02-15
html | pdf |
[L04A]
Feasibility, optimization, and separation (Part A)
Feasibility as minimization of distance from the feasible set; the computational equivalence between separation and optimization: the ellipsoid algorithm.
|
2024-02-22
html | pdf |
[L04B]
Feasibility, optimization, and separation (Part B)
Primer on computational complexity; linear programming as a problem in NP intersection coNP; certificate of infeasibility (Farkas lemma).
|
2024-02-27
html | pdf |
[L05]
Lagrange multipliers and KKT conditions
Optimization problems with functional constraints; Lagrangian function and Lagrange multipliers; constraint qualifications (linear independence of constraint gradients, Slater's condition).
|
2024-02-29
html | pdf |
[L06]
Conic optimization
Conic programs and notable cases: linear programs, second order cone programs, semidefinite programs; selected applications.
|
2024-03-05
html | pdf |
[L07]
Gradient descent and descent lemmas
Gradient descent algorithm; smoothness and the gradient descent lemma; computation of a point with small gradient in general (non-convex) functions; descent in function value for convex functions: the Euclidean mirror descent lemma.
|
2024-03-07
html | pdf |
[L08]
Acceleration and momentum
The idea of momentum; Nesterov's accelerated gradient descent; Allen-Zhu and Orecchia's accelerated gradient descent; practical considerations.
|
2024-03-12
html | pdf |
[L09A]
Projected gradient descent and mirror descent (Part A)
The projected gradient descent (PGD) algorithm; distance-generating functions and Bregman divergences; proximal steps and their properties; the mirror descent algorithm; descent lemmas for mirror descent.
|
2024-03-14
html | pdf |
[L09B]
Projected gradient descent and mirror descent (Part B)
The projected gradient descent (PGD) algorithm; distance-generating functions and Bregman divergences; proximal steps and their properties; the mirror descent algorithm; descent lemmas for mirror descent.
|
2024-04-02
html | pdf |
[L10]
Stochastic gradient descent
Practical importance of stochastic gradient descent with momentum in tranining deep learning models; empirical risk minimization problems; minibatches; stochastic gradient descent lemmas; the effect of variance.
|
2024-04-04
html | pdf |
[L11]
Distributed optimization and ADMM
The setting of distributed optimization; the alternating direction method of multipliers (ADMM) algorithm; convergence analysis of ADMM in the case of convex functions.
|
2024-04-09
html | pdf |
[L12]
Hessians, preconditioning, and Newton's method
Local quadratic approximation of objectives; Newton's method; local quadratic convergence rate; global convergence for certain classes of functions; practical considerations.
|
2024-04-11
html | pdf |
[L13]
Adaptive preconditioning: AdaGrad and ADAM
Adaptive construction of diagonal preconditioning matrices; the AdaGrad algorithm; the convergence rate of AdaGrad; proof sketch; AdaGrad with momentum: the popular ADAM algorithm.
|
2024-04-16
html | pdf |
[L14A]
Self-concordant functions (Part A)
Limitations of the classic analysis of Newton's method; desiderata and self- concordant functions; properties and examples.
|
2024-04-18
html | pdf |
[L14B]
Self-concordant functions (Part B)
Limitations of the classic analysis of Newton's method; desiderata and self- concordant functions; properties and examples.
|
2024-04-23
html | pdf |
[L15]
Central path and interior-point methods
Central path; barriers and their complexity parameter; the short-step barrier method; proof sketch.
|
2024-04-25
html | pdf |
[L16]
Bayesian optimization
Zeroth order optimization; conceptual differences between Bayesian optimization and first-order methods; function distribution and the acquisition function; Gaussian process regression.
|
2024-04-30
html | pdf |
[L17]
Online optimization and regret
From offline to online optimization; a model for online decision-making; definition of regret.
|
2024-05-02
html | pdf |
[L18]
Online mirror descent
Online generalization of the mirror descent algorithm; analysis of regret; notable instances: online projected gradient descent, and multiplicative weights update algorithm.
|
■ Topics in Multiagent Learning (MIT 6.S890, Fall 2023)
This new graduate course, co-developed with Costis Daskalakis, presents the foundations of multi-agent systems from a combined game-theoretic, optimization and learning-theoretic perspective, building from matrix games (such as rock-paper-scissors) to stochastic games, imperfect information games, and games with non-concave utilities. We present manifestations of these models in machine learning applications, from solving Go to multi-agent reinforcement learning, adversarial learning and broader multi-agent deep learning applications. We discuss aspects of equilibrium computation and learning as well as the computational complexity of equilibria. We also discuss how the different models and methods have allowed several recent breakthroughs in AI, including human- and superhuman-level agents for established games such as Go, Poker, Diplomacy, and Stratego.Course material
2023-09-19
html | pdf |
[L04]
Learning in games: Foundations
Regret and hindsight rationality. Phi-regret minimization and special cases. Connections with equilibrium computation and saddle-point optimization.
|
2023-09-21
html | pdf |
[L05]
Learning in games: Algorithms
Regret matching, regret matching plus, FTRL and multiplicative weights update.
|
2023-10-24
html | slides |
[L12]
Foundations of imperfect-information extensive-form games
Complete versus imperfect information. Kuhn's theorem. Normal-form and sequence-form strategies. Similarities and differences with normal-form games.
|
2023-10-26
html | slides |
[L13]
Linear programming for Nash equilibrium in two-player zero-sum extensive-form games
Formulation and implementation details.
|
2023-10-31
html | slides |
[L14]
Learning in imperfect-information extensive-form games (Part I)
Construction of learning algorithms for extensive-form games.
|
2023-11-02
html | slides |
[L15]
Learning in imperfect-information extensive-form games (Part II) and sequential irrationality
Proof of Counterfactual Regret Minimization (CFR). Introduction to sequential irrationality.
|
2023-11-07
html | slides |
[L16]
Equilibrium refinements and team coordination
Extensive-form perfect equilibria and quasi-perfect equilibrium.
|
2023-11-09
html | slides |
Course Homepage
■ Computational Game Solving (CMU 15-888, Fall 2021)
This new graduate course, co-developed with Tuomas Sandholm at CMU, focuses on multi-step imperfect-information games. Imperfect-information games are significantly more complex than perfect-information games like chess and Go, and see emergence of signaling and deception at equilibrium. There has been tremendous progress in the AI community on solving such games since around 2003. The course covers the fundamentals and the state of the art of solving such games.Course material
2021-09-09
html | pdf |
[L02]
Representation of strategies in tree-form decision spaces
Behavioral and sequence-form representation of a strategy. Computation of expected utilities given the sequence-form representation (multilinearity of expected utilities). Kuhn's theorem: relationship between normal-form and sequence-form strategies. Bottom-up decomposition of the sequence-form polytope.
|
2021-09-14
html | pdf |
[L03]
Hindsight rationality and regret minimization
Phi-regret minimization. Special cases: external regret minimization, internal regret minimization, swap regret. Solution to convex-concave saddle-point problems via regret minimization. Applications to bilinear saddle-point problems such as Nash equilibrium, optimal correlation, etc.
|
2021-09-16
html | pdf |
[L04]
Blackwell approachability and regret minimization on simplex domains
Blackwell game approach and construction of regret matching (RM), RM+.
|
2021-09-21
html | pdf |
[L05]
Regret circuits and the Counterfactual Regret Minimization (CFR) paradigm
Treeplex case: regret circuits for Cartesian products and for convex hull. Construction of CFR and pseudocode; proof of correctness and convergence speed.
|
2021-09-28
html | pdf |
[L07]
Optimistic/predictive regret minimization via online optimization
Online projected gradient descent. Distance-generating functions. Predictive follow-the-regularized-leader (FTRL), predictive online mirror descent (OMD), and RVU bounds. Notable instantiations, e.g., optimistic hedge / multiplicative weights update. Accelerated convergence to bilinear saddle points. Dilatable global entropy.
|
2021-09-30
html | pdf |
[L08]
Predictive Blackwell approachability
Blackwell approachability on conic domains. Using regret minimization to solve a Blackwell approachability game. Abernethy et al.’s construction. Predictive Blackwell approachability.
|
2021-10-05
html | pdf |
[L09]
Predictive regret matching and predictive regret matching plus
Connections between follow-the-regularized-leader / online mirror descent and regret matching / regret matching plus. Construction of predictive regret matching and predictive regret matching plus.
|
2021-10-07
html | pdf |
[L10]
Monte-Carlo CFR and offline optimization techniques
Regret minimization with unbiased estimators of the utilities. Game-theoretic utility estimators (external sampling, outcome sampling). Offline optimization methods for two-player zero-sum games. Accelerated first-order saddle-point solvers (excessive gap technique, mirror prox). Linear programming formulation of Nash equilibrium strategies. Payoff matrix sparsification technique.
|
2021-11-11
html | pdf |
[L19]
Sequential irrationality and Nash equilibrium refinements
Sequential irrationality. Trembling-hand equilibrium refinements: quasi-perfect equilibrium (QPE) and extensive-form perfect equilibrium (EFPE). Relationships among refinements. Computational complexity. Trembling-hand linear program formulation of QPE and EFPE. Scalable exact algorithms for QPE, and EFPE.
|
2021-11-16
html | pdf |
[L20]
Correlated strategies and team coordination
Team maxmin equilibrium and TMECor; why the latter is often significantly better. Realization polytope: low dimensional but only the vertices are known and not the constraints.
|
Course Homepage
Handouts
2024-04-19
html | pdf |
Near-optimal learning in imperfect-information sequential games
(and other combinatorial convex settings)
|
Reports of typos are always welcome! Please reach out at gfarina AT mit.edu
.