Week 1
| Mon 01/25 | Introduction: Basic terminology, examples: linear regression, LASSO, sparse regression | [pdf] |
| Wed 01/27 | Elements of convex geometry: Convex sets, convex functions, separating hyperplanes, linear classification, perceptron, neural networks | [pdf] |
| Wed 01/27 | Section 1 | [pdf] |
Week 2
| Mon 02/01 | Linear programming: Definition, canonical and standard form, modelization examples | [pdf] |
| Wed 02/03 | Duality theory: Farkas lemma, weak duality, strong duality | [pdf] |
| Wed 02/03 | Section 2 | [pdf] |
Week 3
| Mon 02/08 | Applications of duality: Game theory, Nash equilibrium, minimax theorem | [pdf] |
| Wed 02/10 | Applications of duality: Learning theory, boosting | [pdf] |
| Wed 02/10 | Section 3 | [pdf] |
Week 4
| Mon 02/15 | Presidents' day: no class | |
| Wed 02/19 | Simplex method: Extreme points, basic feasible solutions, simplex method | [pdf] |
| Wed 02/19 | Section 4 | [pdf] |
Week 5
| Mon 02/22 | Convexity and multivariate analysis: Taylor expansions, properties of convex functions, necessary and sufficient conditions for optimality | [pdf] |
| Wed 02/24 | Gradient descent algorithm: Strong convexity, analysis of convergence | [pdf] |
| Wed 02/24 | Section 5 | [pdf] |
Week 6
| Mon 02/29 | Steepest descent and Newton's method: steepest descent, coordinate descent, Newton's method | [pdf] |
| Wed 03/02 | Online convex optimization: prediction from experts, weighted majority (aka multiplicative weights) algorithm, online convex optimization, online learning, online gradient descent | [pdf] |
| Wed 03/02 | Section 6 | [pdf] |
Week 7
| Mon 03/07 | Duality: Lagrangian duality, Slater's condition | [pdf] |
| Wed 03/09 | Application of Lagrangian duality: Support Vector Machines | [pdf] |
| Wed 03/09 | Section 7 | [pdf] |
Week 8
| Mon 03/14 | Spring break: no class | |
| Wed 03/16 | Spring break: no class | |
| Wed 03/16 | Spring break: no section |
Week 9
| Mon 03/21 | Strong duality: Duality gap, complimentary slackness, KKT conditions | [pdf] |
| Wed 03/23 | Optimization with erroneous oracles: Absolute and relative erroneous oracles, approximation algorithms, value oracles, probabilistic constructions, Chernoff bounds | [pdf] |
| Wed 03/23 | Section 8 | [pdf] |
Week 10
| Mon 03/28 | Discrete optimization: Maximum matching, minimum spanning trees, greedy algorithms | |
| Wed 03/30 | Knapsack: Approximation algorithms, the greedy algorithm, LP relaxation, dynamic programming, FPTAS | [pdf] |
| Wed 03/30 | Section 9 | [pdf] |
Week 11
| Mon 04/04 | Submodularity: Maximum-cover, the greedy algorithm, properties of submodular functions, maximizing influence in social networks | [pdf] |
| Wed 04/06 | Submodularity under matroid constraints: Matroids, the greedy algorithm, combinatorial auctions | |
| Wed 04/06 | Section 10 | [pdf] |
Week 12
| Mon 04/11 | Non-monotone submodularity: Examples of submodular maximization, Max-Cut problem, local search algorithm, randomized algorithm for non-monotone maximization | [pdf] |
| Wed 04/13 | Rounding techniques: Minimum-Set Cover, greedy algorithm, randomized rounding, simple rounding | [pdf] |
| Wed 04/13 | Section 11 |
Week 13
| Mon 04/18 | Pipage rounding: randomized and concave relaxations of Max-Cover, pipage rounding | [pdf] |
| Wed 04/20 | Relaxations of submodular functions: Multilinear relaxations, concave and convex closures, submodular minimization, matroid polytopes | |
| Wed 04/20 | Section 12 |
Week 14
| Mon 04/25 | The continuos greedy algorithm | [pdf] |
| Wed 04/27 | Poster session |