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:
- Lecture: Setting up AI/ML problems as optimization
[Slides] [Annotated]
Wed., Jan. 16:
- Lecture: Linear programs - problem statement and geometry of LPs
[Slides] [Annotated]
Wed., Jan. 23:
- Lecture: Linear program geometry
[Slides] [Annotated]
Mon., Jan. 28:
- Lecture: Quadratic programs
[Slides] [Annotated]
Wed., Jan. 30:
- Lecture: Duality of LPs and QPs
[Slides] [Annotated]
Mon., Feb. 4:
- Lecture: SVMs and Duality;
[SVM and Duality Slides] [SVM and Duality Annotated]
Wed., Feb. 6:
- Lecture: SVMs and Duality continued
[SVM and Duality Slides] [SVM and Duality Annotated]
Mon., Feb. 11:
- Lecture: Semi-infinite (or just big) programs: Constraint Generation
[Constraint Generation Slides] [Constraint Generation Annotated Slides]
Wed., Feb. 13:
- Lecture: Column Generation
Constraint Generation for Maximum Margin Markov Networks
[Column Generation Slides] [Column Generation Annotated]
[M3Ns Slides] [M3Ns Annotated Slides]
Mon., Feb. 18:
- Lecture:
Constraint Generation for Maximum Margin Markov Networks (continued)
[M3Ns (cont.) Slides] [M3Ns (cont.) Annotated Slides]
Ellipsoid and subgradient algorithms
[Ellipsoid slides] [Ellipsoid annotated slides]
Wed., Feb. 20:
- Ellipsoid and subgradient algorithms
[Slides] [Annotated]
[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:
- Lecture: Convex sets and subgradient algorithm
[Convex sets slides] [Subgradient slides] [Convex sets annotated] [Subgradient annotated]
Wed., Feb. 27:
- Lecture: Convex sets, convex functions [Slides] [Annotated]
Mon., Mar. 3:
- Lecture: Convex functions [Slides] [Annotated]
Wed., Mar. 5:
- Lecture: Convex functions, Convex programs [Convex fns slides] [Convex programs slides] [Convex fns Annotated] [Convex programs annotated]
Mon., Mar. 17:
- Lecture: Convex programs [Slides] [Annotated]
Wed., Mar. 19:
- Lecture: Convex programs [Slides] [Annotated]
Mon., Mar. 24:
- Lecture: Convex programs and duality [Slides] [Annotated]
Wed., Mar. 26:
- Lecture: Convex programs and duality [Slides] [Annotated]
Mon., Mar. 31:
- Lecture: Convex programs and duality [Slides] [Annotated]
Wed., Apr. 2:
- Lecture: Convex programs and duality [Slides] [Annotated]
Mon., Apr. 7:
- Lecture: Convex programs and duality [Slides] [Annotated]
Wed., Apr. 9:
- Lecture: Solving convex problems [Slides] [Annotated]
Mon., Apr. 14:
- Lecture: Solving convex programs [Annotated]
[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:
- Intro to integer programs
[Slides] [Annotated]
Mon., Apr. 21:
- Lecture: Integer programs continued; Approximation algorithms; Rounding
[IP Slides] [IP Annotated] [Rounding Slides] [Annotated]
Wed., Apr. 23:
- Lecture: rounding, continued [Rounding Slides] [Annotated]
Mon., Apr. 28:
- Lecture: Submodularity [Slides] [Annotated]
Wed., Apr. 30:
- Lecture: Submodularity, cont. [Slides] [Corrected Annotated]
[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]