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. 14:

Wed., Jan. 16:

Wed., Jan. 23:

Mon., Jan. 28:

Wed., Jan. 30:

Mon., Feb. 4:

Wed., Feb. 6:

Mon., Feb. 11:

Wed., Feb. 13:

Mon., Feb. 18:

Wed., Feb. 20:

[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

Mon., Feb. 25:

Wed., Feb. 27:

Mon., Mar. 3:

Wed., Mar. 5:

Mon., Mar. 17:

Wed., Mar. 19:

Mon., Mar. 24:

Wed., Mar. 26:

Mon., Mar. 31:

Wed., Apr. 2:

Mon., Apr. 7:

Wed., Apr. 9:

Mon., Apr. 14:

[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. 16:

Mon., Apr. 21:

Wed., Apr. 23:

Mon., Apr. 28:

Wed., Apr. 30:

[Top]

Project Poster Session

3-6pm, Thursday, May 1

NSH Atrium

[Top]

Project Paper Due

May 5th by 3pm by email to the instructors list

[Top]

Final Exam

Out: Monday, May 5
Due: Friday, May 9, Noon

[Top]