Aulas: Seg 9-12, sala 510 ou 511 (confirmar). Zoom link
Trabalho 1 (entrega 3 de outubro)
Trabalho 2 (entrega 7 de novembro)
Novembro 28 |
Fabio: Load-Balancing on related and unrelated machines Luiz Fernando: Sample Average Approximation Marcos: Teaching blackbox learners Matheus Levi: Learn to prune Pedro: Learning DNNs online |
Dezembro 5 |
Antonio Carlos: Inverse Optimization Antonio Moreira: Active Learning Felipe: Bandits and mechanism design Flavio: Random order model for online algorithms Matheus Waga: Universal portfolio with transaction costs Vinicius: Markov Decision Processes |
Outubro 3 | Entrega Trabalho 1 Entrega proposta de projeto final |
Novembro 7 | Entrega Trabalho 2 |
Novembro 28, Dezembro 5 | Apresentacoes projeto final |
Scribe notes are not edited
Topico | Material | Notas | ||
---|---|---|---|---|
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 via Primal-Dual] |
[scribe] | |
Aula 2 | Algoritmos online: Paging |
"Online Computation and Competitive Analysis" (Borodin, El-Yaniv): Cap 3, 4. [Modelos mais realistas paging] |
||
Aula 3 | Algoritmos online: AdWords (anuncios Google) |
[Artigo AdWords] [AdWords chapter] [Monografia Primal-Dual] [Modelo estocastico] [Convex analysis perspective on PD algos] |
[old whiteboard] | |
Aula 4 | Online Learning: Prediction with experts advice. Halving algorithm, Weighted Majority |
[Madry's notes] [AHK MWU Survey] |
[old whiteboard] | |
Aula 5 | Online Learning: Multiplicative Weights Update. Abstract prediction with experts. |
[Madry's notes] [AHK MWU Survey] |
[old whiteboard] | |
Aula 6 | Online Learning: Application of MWU: Percepton (classificacao linear), Boosting |
[AHK MWU Survey] [Boosting book] [Video boosting IAS] [Original Tracking Regret] [Cesa-Bianchi et al.] [Adamskiy et al.] [Daniely et al.] |
[old scribe] [old whiteboard] |
|
Aula 7 | Online Learning: Online Convex Optimization: Convexidade. OCO e exemplo. Follow the Leader, e problema de estabilidade. Follow the Regularized Leader. |
[Hazan's OCO book] [McMahan lec1] [McMahan lec 2] [McMahan survey] [OCO Tutorial] [Stability in learning] |
[old scribe] [whiteboard] |
|
Aula 8 | Online Learning: Aplicacoes: SVM e regressao online |
[Online SVM] |
[old scribe] [old whiteboard] |
|
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 10 | 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] |
[old scribe] [old whiteboard] |
|
Aula 11 | 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] |
[old scribe] [old whiteboard] |
|
Aula 12 | PAC Learning: VC dimension and complexity of concept class. Generalization bounds based on VC dimensions. Generalization bounds for Boosting and SVM. |
[Learning book] |
[old whiteboard] | |
Aula 13 | Stochastic Programming: Sample Average Approximation |
[Livro Stoch Programming] [Luedtke-Ahmed SAA] |
[old whiteboard] | |
Aula 14 | Bandits: Adversarial model, EXP3 |
[Bandits book]
[Bubeck/Cesa-Bianchi mono] |
[old whiteboard] |
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 análise de algoritmos tradicional (equivalente ao curso de pós-graduação ``Projeto e Análise de Algoritmos''), e probabilidade discreta (independência, valor esperado, etc.)
Ementa: