課程資訊

Prediction, Learning, and Games

108-2

CSIE5002

922 U4550

3.0

Theory course, requiring math maturity.

*This is an advanced course in learning theory.*

The probably approximately correct (PAC) theory has been the standard framework of machine learning for decades, but its underlying “i.i.d. data” assumption results in a significant theory-practice gap. This course introduces online learning theory, whose probability-free nature naturally avoids the aforementioned theory-practice gap. The main focuses are:
- PAC learning theory
- Individual sequence prediction.
- Learning with expert advice and the aggregating algorithm.
- Advanced decision theoretic online learning.
The tentative schedule can be found below.

The exact contents of this course may change with respect to the latest advances
in learning theory.

Course website: https://cool.ntu.edu.tw/courses/752

● Be able to read state-of-the literature on learning theory.
● Be able to analyze basic online (learning) algorithms.
● Be able to work on online learning research topics.
● Be able to think beyond the statistical and PAC learning frameworks.

Prerequisites: Calculus, linear algebra, and probability.

Knowledge in convex optimization, machine learning, and/or statistics can be helpful but not necessary.

Office Hours

1. N. Cesa-Bianchi and G. Lugosi. 2006. Prediction, Learning, and Games.
2. S. Shalev-Shwartz. 2011. Online Learning and Online Convex Optimization.
3. S. Bubeck. 2011. Introduction to Online Optimization.
4. V. V. V’yugin. 2012. Lecture Notes on Machine Learning and Prediction.
5. S. Hart and A. Mas-Colell. 2013. Simple Adaptive Strategies.
6. A. Rakhlin and K. Sridharan. 2014. Statistical Learning and Sequential Prediction.
7. E. Hazan. 2015. Introduction to Online Convex Optimization.
8. A. Slivkins. 2019. Introduction to multi-armed bandits.
9. T. Lattimore and C. Szepesvari. 2019. Bandit Algorithms.

(僅供參考)

 No. 項目 百分比 說明 1. Homework 60% Four assignments. 15% each. 2. Final project 40% Report (and oral presentation if time allowed). Find a paper that is not entirely correct and discuss the paper's significance and how to fix the errors.

 課程進度
 週次 日期 單元主題 第1週 3/02 Course organization. PAC learning. 第2週 3/09 More complexity measures in PAC learning 第3週 3/16 PAC-Bayes analysis 第4週 3/23 Individual sequence prediction 第5週 3/30 Individual sequence prediction 第6週 4/06 Individual sequence prediction 第7週 4/13 Individual sequence prediction 第8週 4/20 Aggregating algorithm 第9週 4/27 Aggregating algorithm 第10週 5/04 No class. 第11週 5/11 Midterm. 第12週 5/18 Online gradient descent. 第13週 5/25 Decision theoretic online learning. 第14週 6/01 Quantile bounds. 第15週 6/08 Second-order and adaptive bounds. 第16週 6/15 Final project presentations. 第17週 6/22 Final project. 第18週 6/29 Final project.