Gabriele Farina - Teaching

Course material & Lecture notes

■ Nonlinear Optimization (MIT 6.7220 / 15.084; Spring 2025, 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 materials (Spring 2025)

2025-02-04 html \| pdf	[L01] Introduction Overview of the course material; goals and applications; general form of an optimization problem; Weierstrass's theorem; computational considerations.
2025-02-06 html \| pdf	[L02] First-order optimality conditions First-order necessary optimality conditions; the unconstrained case; halfspace constraints.
2025-02-11 html \| pdf	[L03] More on normal cones, and a first taste of duality The connection between normal cones and Lagrange multipliers; linear programming duality as a straightforward consequence of normal cones.
2025-02-13 html \| pdf	[L04] Convex functions and sufficiency of normal cones Definition of convexity for functions; local optimality implies global optimality; sufficiency of first-order optimality conditions; how to recognize a convex function.
2025-02-20 html \| pdf	[L05] The driver of duality: Separation Feasibility as minimization of distance from the feasible set; how separation implies the normal cone to the intersection of halfspaces.
2025-02-25 html \| pdf	[L06] Separation as a proof system Primer on computational complexity; the class NP $\cap$ coNP and its significance; certificate of infeasibility and Farkas lemma.
2025-02-27 html \| pdf	[L07] Functional constraints, 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).
2025-03-04 html \| pdf	[L08] Lagrangian duality Lagrangian function; connections with KKT conditions; dual problem; examples.
2025-03-06 html \| pdf	[L09] Conic constraints Conic programs and notable cases: linear programs, second order cone programs, semidefinite programs; selected applications.
2025-03-11 html \| pdf	[L10] Polynomial optimization Polynomial optimization problems; connection between polynomial optimization and semidefinite programming; the sum of squares decomposition.
2025-03-13 html \| pdf	[L11] Polarity and oracle equivalence Duality between optimization and separation; polar and bipolar.
2025-04-01 html \| pdf	[L12] 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.
2025-04-03 html \| pdf	[L13] Acceleration and momentum The idea of momentum; Nesterovs accelerated gradient descent; Allen-Zhu and Orecchia's accelerated gradient descent; practical considerations.
2025-04-08 html \| pdf	[L14] Projected gradient descent and mirror descent 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.
2025-04-15 html \| pdf	[L15] Stochastic gradient descent and empirical risk minimization 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.
2025-04-17 html \| pdf	[L16] 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.
2025-04-22 html \| pdf	[L17] Hessians, preconditioning, and Newtons method Local quadratic approximation of objectives; Newtons method; local quadratic convergence rate; global convergence for certain classes of functions; practical considerations.
2025-04-24 html \| pdf	[L18] 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.
2025-04-29 html \| pdf	[L19] Self-concordant functions Limitations of the classic analysis of Newtons method; desiderata and self-concordant functions; properties and examples.
2025-05-06 html \| pdf	[L20] Central path and interior-point methods Central path; barriers and their complexity parameter; the short-step barrier method; proof sketch.

Course Homepage (Spring 2025)

Course materials (Spring 2024)

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 ﬁrst taste of Lagrange multipliers and duality.
2024-02-13 html \| pdf	[L03] The special case of convex functions Deﬁnition of convexity for functions; local optimality implies global optimality; suﬃciency of ﬁrst-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; certiﬁcate 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 qualiﬁcations (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, semideﬁnite 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	[L09] 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	[L09] 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 eﬀect 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	[L14] 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	[L14] 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 diﬀerences between Bayesian optimization and ﬁrst-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.

Course page

■ Topics in Multiagent Learning (MIT 6.7980; Fall 2026, 2025, 2024, 2023)

This graduate course, co-developed with Costis Daskalakis, studies multiagent systems through game theory, optimization, and learning theory. We cover Nash equilibria, regret minimization, learning dynamics, and extensive-form games, alongside multiagent deep reinforcement learning, information and mechanism design, team and hidden-role games, alignment, high-dimensional and kernelized learning, nonconvex games, calibration, and the complexity of finding equilibria. Applications and open research questions connect the theory to multiagent AI.

Course materials (Fall 2026)

2026-09-15 html \| pdf	[L01] Setting and equilibria: the Nash equilibrium Nash's existence theorem and its connection to fixed-point theorems.
2026-09-17 html \| pdf	[L02] Brouwer and Sperner Sperner's lemma, Brouwer's theorem, and combinatorial proofs of equilibrium existence.
2026-09-22 html \| pdf	[L03] Properties of Nash equilibrium Topological and computational properties. Zero-sum games and linear programming. Correlated and coarse correlated equilibria.
2026-09-24 html \| pdf	[L04] Learning in games: Foundations Regret and hindsight rationality. Regret minimization and its relationships with equilibrium concepts.
2026-09-29 html \| pdf	[L05] Learning in games: Algorithms General principles for learning algorithms. Follow-the-leader, regret matching, multiplicative weights, and online mirror descent.
2026-10-01 html \| pdf	[L06] Learning with bandit feedback Partial feedback and exploration. From multiplicative weights to Exp3; regret guarantees.
2026-10-06 html \| pdf	[L07] Modeling extensive-form games Perfect and imperfect information. Kuhn's theorem. Normal-form and sequence-form strategies.
2026-10-08 html \| pdf	[L08] Learning in extensive-form games No-regret learning, counterfactual utilities, and counterfactual regret minimization (CFR).
2026-11-19 html \| pdf	[L19] PPAD-hardness of Nash equilibrium Reductions and the computational hardness of finding Nash equilibria.
html \| pdf	[S1] A second look at the minimax theorem
html \| pdf	[S2] Centralized algorithms for Nash equilibrium computation
html \| pdf	[S3] Learning algorithms (II)
html \| pdf	[S4] Sequential irrationality and perfect equilibria
html \| pdf	[S5] Markov (aka stochastic) games
html \| pdf	[S6] Phi-regret minimization

Course Homepage (Fall 2026)

Course materials (Fall 2024)

2024-09-05 html \| slides	[L01] Introduction Introduction to the course and logistics.
2024-09-10 html \| pdf	[L02] Setting and equilibria: the Nash equilibrium Definition of normal-form games. Solution concepts and Nash equilibrium. Nash equilibrium existence theorem.
2024-09-12 html \| pdf	[L03] Setting and equilibria: the correlated equilibrium Topological and computational properties of the set of Nash equilibria in normal-form games. Connections with linear programming. Definition of correlated and coarse correlated equilibria; relationships with Nash equilibria.
2024-09-17 html \| pdf	[L04] Learning in Games: Foundations Regret and hindsight rationality. Definition of regret minimization and relationships with equilibrium concepts.
2024-09-19 html \| pdf	[L05] Learning in Games: Algorithms (Part I) General principles in the design of learning algorithms. Follow-the-leader, regret matching, multiplicative weights update, online mirror descent.
2024-09-24 html \| pdf	[L06] Learning in Games: Algorithms (Part II) Optimistic mirror descent and optimistic follow-the-regularized-leader. Accelerated computation of approximate equilibria.
2024-09-26 html \| pdf	[L07] Learning in Games: Bandit feedback From multiplicative weights to Exp3. General principles. Obtaining high-probability bounds.
2024-10-01 html \| pdf	[L08] Learning in Games: $\Phi$-regret minimization Blum-Mansour construction of a swap regret minimizer. Gordon, Greenwald, and Marks general construction for $\Phi$-regret minimizers.
2024-10-03 html \| pdf	[L09] Foundations of extensive-form games Complete versus imperfect information. Kuhn's theorem. Normal-form and sequence-form strategies. Similiarities and differences with normal-form games.
2024-10-08 html \| pdf	[L10] Learning in extensive-form games No-regret algorithms for extensive-form games. Counterfactual utilities and counterfactual regret minimization (CFR).
2024-10-10 html \| pdf	[L11] Equilibrium refinements Sequential irrationality. Extensive-form perfect equilibria nad quasi-perfect equilibria.
2024-10-29 html \| slides	[L12] Deep reinforcement learning for large-scale games (Guest lecture by Samuel Sokota) Sequential irrationality. Extensive-form perfect equilibria nad quasi-perfect equilibria.
2024-10-31 html \| slides	[L13] Deep reinforcement learning for large-scale games (Guest lecture by Samuel Sokota) Public belief states. Applications to poker, Hanabi. Team games.
2024-11-05 html \| pdf	[L14] Combinatorial games and Kernelized MWU (Part I) Example of combinatorial games. Kernelized multiplicative weights update algorithm.
2024-11-07 html \| pdf	[L14] Combinatorial games and Kernelized MWU (Part II) Example of combinatorial games. Kernelized multiplicative weights update algorithm.
2024-11-12 html \| pdf	[L15] Computation of exact equilibria A second look at the minimax theorem. Hart and Schmeidler's proof of existence of correlated equilibria. Ellipsoid against hope algorithm.
2024-11-14 html \| pdf	[L16] Markov (aka stochastic) games Setting and taxonomy of equilibria. Stationary Markov Nash equilibria in inifinite-horizon games. Shapley's minimax theorem.
2024-11-19 html \| pdf	[L17] PPAD-completeness of Nash equilibria (part I) Sperner's lemma. The PPAD complexity class. Nash ∈ PPAD.
2024-11-21 html \| pdf	[L18] PPAD-completeness of Nash equilibria (part II) Arithmetic circuit SAT. PPAD-hardness of Nash equilibria.

Course Homepage (Fall 2024)

Course materials (Fall 2023)

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	[L17] Scalability-enhancing techniques Techniques to further scalability of EFG solving.

Course Homepage (Fall 2023)

Learning dynamics shown as a vector field over a colored strategy space

Course page

■ 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 materials (Fall 2021)

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 (Fall 2021)

A face-down playing card, an ace of spades, and poker chips

Course page

Tutorials

■ Learning and Computation of Φ-Equilibria (ACM EC’26 Tutorial)

This ACM EC’26 tutorial, presented jointly with Ioannis Anagnostides and Brian Hu Zhang on June 15, 2026, explores Φ-regret minimization and the computation of Φ-equilibria. Topics include the Gordon–Greenwald–Marks reduction, expected fixed points, semi-separation, ellipsoid methods, multicalibration, TreeSwap, and profile swap regret.

Tutorial notes & slides

2026-06-15 html \| pdf	[1] Introduction Online learning and regret; correlated equilibria; the Gordon–Greenwald–Marks framework.
2026-06-15 html \| pdf	[2] Beyond Normal Form Expected fixed points and semi-separation for regret minimization over richer strategy spaces.
2026-06-15 html \| pdf	[3] Ellipsoid Against Hope Ellipsoid methods for computing correlated and Φ-equilibria to high precision.
2026-06-15 html \| pdf	[4] Φ-Regret and Multicalibration Forecasting and multicalibration as a route to Φ-regret minimization.
2026-06-15 html \| pdf	[5] TreeSwap: Efficient Swap Regret Minimization The TreeSwap reduction and swap-regret minimization for large action spaces.
2026-06-15 html \| pdf	[6] Profile Swap Regret, Manipulability, and Response-Based Approachability Profile swap regret, guarantees against manipulation, and algorithms based on approachability.
2026-06-15 slides	Tutorial slides

A strategy x and its deviation φ(x) on the probability simplex

Tutorial page

Handouts

2024-04-19 html \| pdf	Near-optimal learning in imperfect-information sequential games (and other combinatorial convex settings) MIT Theory Reading Group (3h whiteboard talk)
2016-10-20 html	Approachability in Two-Player Games Blackwell approachability is a celebrated concept regarding two-player games with vector payoffs. Blackwell's theorem provides a way of computing approximated Nash equilibria in large-scale games.

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