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 subbranches, including online learning, computational decisionmaking, and nonconvex applications in deep learning.Course material
20240206
html  pdf 
[L01]
Introduction
Overview of the course material; goals and applications; general form of an optimization problem; Weierstrass's theorem; computational considerations.

20240208
html  pdf 
[L02]
Firstorder optimality conditions
Firstorder necessary optimality conditions; the unconstrained case; halfspace constraints; a ﬁrst taste of Lagrange multipliers and duality.

20240213
html  pdf 
[L03]
The special case of convex functions
Deﬁnition of convexity for functions; local optimality implies global optimality; suﬃciency of ﬁrstorder optimality conditions; how to recognize a convex function.

20240215
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.

20240222
html  pdf 
[L04B]
Feasibility, optimization, and separation (Part B)
Primer on computational complexity; linear programming as a problem in NP intersection coNP; certiﬁcate of infeasibility (Farkas lemma).

20240227
html  pdf 
[L05]
Lagrange multipliers and KKT conditions
Optimization problems with functional constraints; Lagrangian function and Lagrange multipliers; constraint qualiﬁcations (linear independence of constraint gradients, Slater's condition).

20240229
html  pdf 
[L06]
Conic optimization
Conic programs and notable cases: linear programs, second order cone programs, semideﬁnite programs; selected applications.

20240305
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 (nonconvex) functions; descent in function value for convex functions: the Euclidean mirror descent lemma.

20240307
html  pdf 
[L08]
Acceleration and momentum
The idea of momentum; Nesterov's accelerated gradient descent; AllenZhu and Orecchia's accelerated gradient descent; practical considerations.

20240312
html  pdf 
[L09A]
Projected gradient descent and mirror descent (Part A)
The projected gradient descent (PGD) algorithm; distancegenerating functions and Bregman divergences; proximal steps and their properties; the mirror descent algorithm; descent lemmas for mirror descent.

20240314
html  pdf 
[L09B]
Projected gradient descent and mirror descent (Part B)
The projected gradient descent (PGD) algorithm; distancegenerating functions and Bregman divergences; proximal steps and their properties; the mirror descent algorithm; descent lemmas for mirror descent.

20240402
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 eﬀect of variance.

20240404
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.

20240409
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.

20240411
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.

20240416
html  pdf 
[L14A]
Selfconcordant functions (Part A)
Limitations of the classic analysis of Newton's method; desiderata and self concordant functions; properties and examples.

20240418
html  pdf 
[L14B]
Selfconcordant functions (Part B)
Limitations of the classic analysis of Newton's method; desiderata and self concordant functions; properties and examples.

20240423
html  pdf 
[L15]
Central path and interiorpoint methods
Central path; barriers and their complexity parameter; the shortstep barrier method; proof sketch.

20240425
html  pdf 
[L16]
Bayesian optimization
Zeroth order optimization; conceptual diﬀerences between Bayesian optimization and ﬁrstorder methods; function distribution and the acquisition function; Gaussian process regression.

20240430
html  pdf 
[L17]
Online optimization and regret
From offline to online optimization; a model for online decisionmaking; definition of regret.

20240502
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, codeveloped with Costis Daskalakis, presents the foundations of multiagent systems from a combined gametheoretic, optimization and learningtheoretic perspective, building from matrix games (such as rockpaperscissors) to stochastic games, imperfect information games, and games with nonconcave utilities. We present manifestations of these models in machine learning applications, from solving Go to multiagent reinforcement learning, adversarial learning and broader multiagent 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 superhumanlevel agents for established games such as Go, Poker, Diplomacy, and Stratego.Course material
20230919
html  pdf 
[L04]
Learning in games: Foundations
Regret and hindsight rationality. Phiregret minimization and special cases. Connections with equilibrium computation and saddlepoint optimization.

20230921
html  pdf 
[L05]
Learning in games: Algorithms
Regret matching, regret matching plus, FTRL and multiplicative weights update.

20231024
html  slides 
[L12]
Foundations of imperfectinformation extensiveform games
Complete versus imperfect information. Kuhn's theorem. Normalform and sequenceform strategies. Similarities and differences with normalform games.

20231026
html  slides 
[L13]
Linear programming for Nash equilibrium in twoplayer zerosum extensiveform games
Formulation and implementation details.

20231031
html  slides 
[L14]
Learning in imperfectinformation extensiveform games (Part I)
Construction of learning algorithms for extensiveform games.

20231102
html  slides 
[L15]
Learning in imperfectinformation extensiveform games (Part II) and sequential irrationality
Proof of Counterfactual Regret Minimization (CFR). Introduction to sequential irrationality.

20231107
html  slides 
[L16]
Equilibrium refinements and team coordination
Extensiveform perfect equilibria and quasiperfect equilibrium.

20231109
html  slides 
Course Homepage
■ Computational Game Solving (CMU 15888, Fall 2021)
This new graduate course, codeveloped with Tuomas Sandholm at CMU, focuses on multistep imperfectinformation games. Imperfectinformation games are significantly more complex than perfectinformation 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
20210909
html  pdf 
[L02]
Representation of strategies in treeform decision spaces
Behavioral and sequenceform representation of a strategy. Computation of expected utilities given the sequenceform representation (multilinearity of expected utilities). Kuhn's theorem: relationship between normalform and sequenceform strategies. Bottomup decomposition of the sequenceform polytope.

20210914
html  pdf 
[L03]
Hindsight rationality and regret minimization
Phiregret minimization. Special cases: external regret minimization, internal regret minimization, swap regret. Solution to convexconcave saddlepoint problems via regret minimization. Applications to bilinear saddlepoint problems such as Nash equilibrium, optimal correlation, etc.

20210916
html  pdf 
[L04]
Blackwell approachability and regret minimization on simplex domains
Blackwell game approach and construction of regret matching (RM), RM+.

20210921
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.

20210928
html  pdf 
[L07]
Optimistic/predictive regret minimization via online optimization
Online projected gradient descent. Distancegenerating functions. Predictive followtheregularizedleader (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.

20210930
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.

20211005
html  pdf 
[L09]
Predictive regret matching and predictive regret matching plus
Connections between followtheregularizedleader / online mirror descent and regret matching / regret matching plus. Construction of predictive regret matching and predictive regret matching plus.

20211007
html  pdf 
[L10]
MonteCarlo CFR and offline optimization techniques
Regret minimization with unbiased estimators of the utilities. Gametheoretic utility estimators (external sampling, outcome sampling). Offline optimization methods for twoplayer zerosum games. Accelerated firstorder saddlepoint solvers (excessive gap technique, mirror prox). Linear programming formulation of Nash equilibrium strategies. Payoff matrix sparsification technique.

20211111
html  pdf 
[L19]
Sequential irrationality and Nash equilibrium refinements
Sequential irrationality. Tremblinghand equilibrium refinements: quasiperfect equilibrium (QPE) and extensiveform perfect equilibrium (EFPE). Relationships among refinements. Computational complexity. Tremblinghand linear program formulation of QPE and EFPE. Scalable exact algorithms for QPE, and EFPE.

20211116
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
20240419
html  pdf 
Nearoptimal learning in imperfectinformation sequential games
(and other combinatorial convex settings)

Reports of typos are always welcome! Please reach out at gfarina AT mit.edu
.