Lectures and reading

Files for scribe notes: available in canvas

Lecture 1: Introduction to learning theory, learning from expert advice and the online learning model

Examples of machine learning problems, classification of learning models, learning from expert advice, the weighted majority + RWM algorithms, the online learning model, definition of regret, multiplicative weights algorithm & analysis

Reading:

• Chapter 1 in book 1

• Alan Turing's paper on AI: https://www.csee.umbc.edu/courses/471/papers/turing.pdf

• Scribe notes

Lecture 2: Learning from examples

The statistical learning model and PAC learning, defining generalization, ERM and/or online to batch and concluding learnability of finite hypothesis classes, the computational difficulty of learning hyperplanes and motivating convex optimization. Touch upon learnability of infinite hypothesis classes, and generalization theory for them, via online 2 batch and/or compression arguments.

Reading:

• Chapter 9 in book 1

• Book 2

• scribe notes

Lecture 3: Convex optimization, OCO and online gradient descent

Learning continuous hypothesis classes via convex optimization, NP-hardness of hyperplane learning and convex relaxation with SVM, introduction to convex analysis and mathematical optimization, solution concepts for convex and non-convex optimization, gradient descent and its analysis for both convex and nonconvex optimization, online convex optimization, online gradient descent

Reading:

• Chapter 2,3 in book 1

• lecture notes on optimization for machine learning

• scribe notes

Lecture 4: Non-convex optimization

Wrap up OCO, the differences between OEG and OGD, Mirror Descent
Non-convex optimization in ML: uses and algorithms
GD and SGD with bounds for first order optimality
Reading:

• Chapter 2,3 in book 1

• lecture notes on optimization for machine learning

• Optimization chapter in new book on Deep Learning by Prof. Sanjeev Arora

• scribe notes

Lecture 5: Boosting and ensemble methods

Weak learning vs. strong learning, boosting of weak learners, AdaBoost and its analysis

Reading:

• Chapter 11 in book 1

• Book 4

• scribe notes

Lecture 6: Learning with limited information: bandits

The multi-armed bandit problem, explore-exploit trade-off, EXP3 and its analysis, bandit convex optimization, bandit linear optimization, self-concordant regularizers

Reading:

• Chapter 6 in book 1

• Bandit Algorithms by Lattimore and Szepasvari

• scribe notes

Lecture 7: Games, learning, duality and linear programming

Introduction to the theory of games, linear programming, duality, min-max theorem and its proof using regret

Reading:

• Chapter 8 in book 1

• scribe notes

Lecture 8: Recommender systems, matrix learning and projection-free learning

• Recommender systems and matrix completion, the Frank-Wolfe algorithm, online projection free methods

• Reading:

• Chapter 7 in book 1

• scribe notes

Lecture 9: Reinforcement learning

Learning with state, the MDP model, the Bellman equation and dynamic programming, learning MDPs via value iteration, online learning of MDPs

Reading:

• Book 4

• scribe notes

Lecture 10: Optimal control and linear dynamical systems

The problem of control and its relationship to RL, examples of control problems, the optimal control problem, Linear Dynamical Systems, LQR and its solution via Bellman equation

Reading:

• Tutorial on online and nonstochastic control

• scribe notes

Lecture 11: Special research guest lectures

Lecture 12: Regret minimization in control: Nonstochastic control

The nonstochastic control problem, Disturbance Action Policies, the Gradient Perturbation Controller