This outline is still very preliminary, and is subject to change.  We'll put the latest updates to the syllabus here when they become available.  There are 29 lectures total.

Linear & Quadratic Programming [9 Lectures]

  • Intro: setting up AI/ML problems as optimization [1]
    • ex: maximum likelihood
    • ex: most likely explanation in an HMM or MRF
    • ex: misclassification error + structural risk for classification
    • ex: propositional planning
  • linear programs and QPs [2]
    • 2d LP Applet
    • ex: value of a shortest path MDP
    • ex: QP: SVM
    • ex: QP: LASSO
    • ex: minimax equilibria in matrix games; regret
  • duality of LPs and QPs [2]
  • Lagrange multipliers
    • ex: value/policy of a shortest path MDP
    • ex: QP: SVM
    • ex: mincut, maxflow
  • semi-infinite (or just big) programs [1]
    • constraint generation, column generation, separation oracles
    • ex: constraining largest singular value <= 1 by adding linear constraints
    • ex: finding support vectors in SVMs
  • combining dynamic programming and LPs [1]
    • ex: Viterbi, max-product for maximum margin Markov networks
  • ellipsoid algorithm [1]
    • Blackwell's theorem
  • gradient and subgradient descent [1]
    • ex: structured margin/ maximum margin Markov nets

Mon., Jan. 11:

Wed., Jan. 13:

  • Lecture: Linear programs - problem statement and geometry of LPs (Geoff)
    [Slides] [Annotated]
  • Relevant readings: B&V p1-7 (optimization and LPs), p21-42 (convexity)

Wed., Jan. 20:

  • Lecture: Linear program geometry, the simplex algorithm (Geoff)
    [Slides] [Annotated]
  • Relevant readings: Bertsimas and Tsitsiklis - Chapter 2 and 3

Mon., Jan. 25:

  • Lecture: Geometry of LP solutions, convex sets (Carlos)
    [Slides] [Annotated]
  • Relevant readings: BV 2.1 - 2.3

Wed., Jan. 27:

Mon., Feb. 1:

  • Lecture: Quadratic programs (Geoff)
    [Slides] [Annotated]
  • Relevant readings: Readings - BV 4.4 and BV 8.6 (SVMs)

Wed., Feb. 3:

Mon., Feb. 8:

  • Lecture canceled due to snow!

Wed., Feb. 10:

  • Lecture canceled due to snow!

Thu., Feb. 11 (special make-up lecture: 5PM in Hammerschlag B103):

Mon., Feb. 15:

Wed., Feb. 17:

Mon., Feb. 22:

Wed., Feb. 24:

Mon., Mar. 1:

Wed., Mar. 3:

Mon., Mar. 15:

[Top]

Convex Optimization [10 Lectures]

  • convex sets, functions and programs [4]
    • ex: piecewise linear object functions
    • ex: approximating convex functions by piecewise linear functions
    • ex: Logistic regression
    • ex: SDP: largest/smallest eigenvalue
    • ex: SDP: semidefinite embedding
    • ex: equilibria and regret in convex games
    • ex: experimental design
    • ex: transformation-invariant SVMs
  • duality of functions and sets [1]
    • norms, support functions
  • convex programs and duality of CPs [2]
    • ex: maxent vs MLE in Gibbs
    • ex: SOCP: LP with uncertain constraints, bounded probability of failure
    • ex: SDP: largest/smallest eigenvalue
    • ex: SDP: finding the fastest-mixing policy in an MDP
    • ex: SDP: semidefinite embedding
  • Newton's method [1]
    • ex: finding analytic center of polyhedron
  • interior-point methods for solving CPs [1]
    • barriers, self-concordance
    • central path
    • poly-time algorithms for CPs
  • online optimization [1]
    • online convex programs
    • online regret
    • no-regret algorithms
    • ex: adaptive data structures
    • ex: margin perceptron

Wed., Mar. 17:

Mon., Mar. 22:

Wed., Mar. 24:

Mon., Mar. 29:

Wed., Mar. 31:

Mon., Apr. 5:

Wed., Apr. 7:

  • Lecture: Second-order (Newton's) solver for convex problems (cont.)
  • Analysis, equality constraints, general constrained optimization [Slides] [Annotated]

Mon., Apr. 12:

[Top]

Combinatorial and Mixed Optimization [9 Lectures]

  • Mixed integer linear programs [1.5]
    • review of complexity classes
    • Totally Unimodular Problems
    • ex: finding optimal tours / Hamiltonian paths / coverings with tours or paths
    • ex: scheduling
    • ex: task assignment / matching
    • ex: set cover
    • ex: clearing combinatorial exchanges
    • ex: stochastic programs with recourse (e.g., Steiner)
  • stochastic hillclimbing [1.5]
    • dist'n over neighborhood, exploring v. increasing moves
    • random restarts
    • example: MaxSAT search (MaxWalkSAT)
  • cutting planes, branch & bound, branch & cut [1]
  • approximation algorithms [2.5]
    • rounding & duality
    • ex: simple randomized rounding for 0/1 SVMs
    • ex: Goemans/Williamson randomized rounding for MAXSAT and mincuts
    • ex: minimum balanced cut for image segmentation
  • submodularity [2.5]
    • ex: set partition based on mutual information
    • ex: most informative observations
    • ex: information cascades
    • ex: minimax Kriging, robust experimental design

Wed., Apr. 14:

Mon., Apr. 19:

Wed., Apr. 21:

Mon., Apr. 26:

Wed., Apr. 28:

[Top]

Additional Topics

  • Use of bounds in optimization
  • coordinate ascent
  • EM algorithm
    • ex: k-means, Baum-Welch
  • variational bounding
    • ex: tree-reweighted BP
  • Fisher scoring
  • games and equilibria as optimization problems
    • ex: equilibria in extensive-form games; sequence form
    • ex: equilibria in convex games; transformation regret
    • ex: finding Nash equilibria in matrix games

[Top]