Introduction to Online Optimization/Learning (Fall 2022)

Instructor: Haipeng Luo
TA: Tiancheng Jin (email: first_name.last_name@usc.edu)
When: Thursday 3:30pm-6:50pm
Where: GFS 118 (note the location change!)

Office hours (instructor): Thursday 2:00pm-3:00pm at SAL 216
Office hours (TA): Wednesday 2:00pm-4:00pm at PHE 328 and zoom

Overview

This course focuses on the foundation and advances of the theory and algorithms of online learning/online convex optimization/sequential decision making, a topic that has been playing a crucial role in machine learning and many real-life applications. The main theme of the course is to study algorithms whose goal is to minimize “regret” when facing against a possibly adversarial environment, and to understand their theoretical guarantees. Special attention will be paid to adaptive, robust, and practical algorithms. Connections to other topics such as game theory and reinforcement learning will also be covered. A concrete schedule can be found here.

Learning Objectives

At a high-level, through this course you will have a concrete idea of what online learning is about, what the state-of-the-art is, and what the open problems are. Specifically, you will learn about classical algorithms such as Hedge/exponential weights, follow the regularized leader, online mirror descent, UCB, EXP3, and others, as well as general techniques for proving regret upper and lower bounds. The more general objective is to train you to think about machine learning in a more rigorous and principled way so you will be able to design provable and practical machine learning algorithms after this course. In addition, through this course you will also obtain training on some basic but important research skills, such as writing in LaTeX, collaboration, and presentation.

Prerequisites

Familiarity with probability, convex analysis, calculus, linear algebra, and analysis of algorithms. Some basic understanding of machine learning would be very helpful.

Requirements

Communications

The main communication tool for this course is Piazza. Please sign up via this link. All announcements of this course will be made there, so you have to sign up. You are also encouraged to ask and/or answer questions on Piazza.

Readings

There are no official textbooks for this course. In addition to the lecture notes, the following books/surveys are all good resources for extra reading.