Aulas: Ter 9-12, Sala RDC510
Trabalho 1 (entrega 9 de outubro)
Trabalho 2 (entrega 13 de novembro)
Novembro 6 | Lucas, Matheus, Leonardo Oliveira |
Novembro 13 | Andrew, Guilherme, Jordana |
Novembro 27 | Georges, Eduardo, Tomas |
Dezembro 4 | Thiago, Luisa, Toni |
Dezembro 11 | Alessandro, Leonardo Moraes, Luis Felipe, Mauricio |
Outubro 9 | Entrega Trabalho 1 Entrega proposta projeto final |
Novembro 13 | Entrega Trabalho 2 |
Novembro (6), 13, 27, dezembro 4, 11 | Apresentacoes projeto final |
Dezembro 4 | Entrega relatorio do projeto final |
Scribe notes are not edited.
Topico | Material | Scribe notes | ||
---|---|---|---|---|
Intro | ||||
Aula 1 | Algoritmos online: Modelo, competitive ratio. Problema Ski Rental. Algoritmos deterministicos e lower bounds. Algoritmos aleatorizados. | [Anupam and Avrim's notes] [Karlin et al. Ski Rental paper] [Optimal algo from Primal-Dual] |
scribe notes | |
Aula 2 | Algoritmos online: Yao's minimax principle e lower bound para algoritmos aleatorizados. Paging (inicio) |
"Online Computation and Competitive Analysis" (Borodin, El-Yaniv): Cap 3, 4. |
scribe notes | |
Aula 3 | Algoritmos online: Paging: Algoritmos deterministicos, lower bound deterministicos; algo. aleatorizados. AdWords (anuncios Google). Notas: framework Primal-Dual. |
[Modelos mais realistas paging] [Artigo AdWords] [AdWords Chapter] [Monografia Primal-Dual] [Convex analysis perspective on PD algos] |
scribe notes | |
Aula 4 | Online Learning: Prediction with experts advice. Halving algorithm, Weighted Majority, Multiplicative Weights Update |
[Madry's notes] [AHK MWU Survey] |
scribe notes | |
Aula 5 | Online Learning: Applications of MWU: Boosting. Fast algorithms for offline problems (linear classification) |
[Madry's notes] [AHK WMU Survey] [Boosting book] |
scribe notes | |
Aula 6 | Online Learning: Other metrics: Tracking and Strongly Adaptive Regret. Online Convex Optimization |
[Original Tracking Regret] [Cesa-Bianchi et al.] [Adamskiy et al.] [Daniely et al.] [Hazan's OCO book] |
scribe notes | |
Aula 7 | Online Learning: Online Convex Optimization: Follow the Leader, and stability problem. Follow the Regularized Leader. Online Gradient Descent. |
[Hazan's OCO book] [McMahan lec1] [McMahan lec 2] [McMahan survey] [OCO Tutorial] [Stability in learning] |
scribe notes | |
Aula 8 | Online Learning: Online Gradient Descent. Online SVM and regression |
[OGD paper] [Online SVM] [Follow the Perturbed Leader] |
scribe notes | |
Pre Aula | Revisao probabilidade | Livro "Probability and Computing" (Mitzenmacher and Upfal): Cap 1, Cap 2 (menos 2.1.2, 2.4, 2.5), Sec 3.2. | ||
Opcao mais prolixa: notas do O'Donnell, Lec 2, Lec 3 (Sec 1, 2), Lec 5, Lec 6 (Sec 1, 2.1), Lec 8 (Sec 1, 3, 5), Lec 23 (Sec 4) | ||||
Aula 9 | Probabilidade: Desigualdades dos 3 "Russos": Markov, Chebychev, Chernoff. Chernoff + union bound: Balls-in-bins. |
[Matousek-Vondrak's notes] [Concentration Inequalities book] [van Handel's notes] |
scribe notes | |
Aula 10 | PAC Learning: PAC learning as formalization of what it means to learn; examples. Empirical Risk Minimization, and cases it fails. Generalization guarantees for finite concept classes |
[Learning book] [Guestrin's slides] |
||
Aula 11 | PAC Learning: Generalization guarantees for finite concept classes. VC dimension and "size" of concept class. Sauer-Shelah Lemma. Generalization bounds based on VC dimensions. |
[Learning book] |
scribe notes | |
Aula 12 | PAC Learning: Generalization bounds for Boosting and SVM. Connection between PAC learning and Online Learning: online-to-batch conversion. Stochastic Bandits: Model. Explore then Commit algorithm. UCB. |
[Learning book] [Bandits book] [Bubeck/Cesa-Bianchi mono] |
O objetivo deste curso é apresentar diferentes metodologias para se raciocinar sobre tomada de decisão na presença de incerteza. Por exemplo:
Durante o curso apresentaremos modelos para formular essas e outras questões, discutindo suas motivações, hipóteses, limitações, e conexões; veremos estratégias algorítmicas para tomada de decisão; e apresentaremos provas de garantia de qualidade dos algoritmos, provendo sua fundamentação teórica.
N.B.: Este curso é baseado na minha participação no programa de pesquisa "Algorithms and Uncertainty" no Simons Institute em UC Berkeley durante o semestre 2016.2.
Pre-requisitos: Conforto com analises de algoritmos tradicionais (equivalente ao curso de pós-graduação ``Projeto e Análise de Algoritmos''), e probabilidade discreta (independência, valor esperado, etc.)
Ementa: