Informacoes basicas

Aulas: Qua 13-16, Zoom link
Piazza (duvidas e discussoes)


Avaliacao



Trabalhos

Trabalho 1 (entrega 14 de outubro)
Trabalho 2 (entrega 18 de novembro)


Agenda apresentações (TBD)

Dezembro 2 Moises: Markov Decision Processes
Luiz Carlos: Monte Carlo Tree Search
Andre: Bandit Online Convex Optimization
Felipe: Active Learning
Dezembro 9 David: Learning to Prune: Speeding up Repeated Computations (Alabi et al.)
Pietro: Learning to Play Sequential Gamesversus Unknown Opponents (Sessa et al.)
Rafael: Online Search/One Way Trading
Arthur: Random Order Model for Online Algorithms


Datas importantes

Outubro 14 Entrega Trabalho 1
Entrega proposta de projeto final
Novembro 18 Entrega Trabalho 2
Dezembro 2, 9 Apresentacoes projeto final
Dezembro 9 Entrega relatorio (caso faça)


Topicos

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] 		[whiteboard]
Aula 2 Algoritmos online: Lower bounds algoritmos aleatorizados, Yao's minimax. Paging

"Online Computation and Competitive Analysis" (Borodin, El-Yaniv): Cap 3, 4.

[Nikhil's lec on Paging]
[Modelos mais realistas paging]
 [whiteboard]
Aula 3 Algoritmos online: AdWords (anuncios Google) [Artigo AdWords]
[AdWords chapter]
[Monografia Primal-Dual]
[Modelo estocastico]
[Convex analysis perspective on PD algos] 		[whiteboard]
Aula 4 Online Learning: Prediction with experts advice. Halving algorithm, Weighted Majority [Madry's notes]
[AHK MWU Survey]
 [whiteboard]
Aula 5 Online Learning: Multiplicative Weights Update. Abstract prediction with experts. [Madry's notes]
[AHK MWU Survey]
 [whiteboard]
Aula 6 Online Learning: Application of MWU: Boosting [AHK MWU Survey]
[Boosting book]
[Video boosting IAS]
[Original Tracking Regret]
[Cesa-Bianchi et al.]
[Adamskiy et al.]
[Daniely et al.]
 [old scribe]
[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]
[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]
[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]
[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]
 [whiteboard]
Aula 13 Stochastic Programming: Sample Average Approximation [Livro Stoch Programming]
[Luedtke-Ahmed SAA] 		[whiteboard]
Aula 14 Bandits: Adversarial model, EXP3 [Bandits book]
[Bubeck/Cesa-Bianchi mono] 		[whiteboard]
Aula 15 Bandits: Stochastic model, UCB [Bandits book]
[Bubeck/Cesa-Bianchi mono] 		[whiteboard][prova UCB]


Descricao do curso

O objetivo deste curso é apresentar diferentes metodologias para se raciocinar sobre tomada de decisão na presença de incerteza. Por exemplo:

  • Como decidir quais informações devem ser mantidas em cache, sem saber quais serão acessadas num futuro próximo, de forma a otimizar sua utilização (Paging problem)?
  • Como o Google utiliza previsão de buscas futuras para otimizar a alocação de anúncios (AdWords Problem)?
  • Se tivermos acesso a experts, será possível fazer previsões quase tão boas quanto o melhor expert sem saber a priori quem é o melhor expert (Online Learning)?
  • Existem problemas de aprendizado de máquina mais difíceis que outros? Quantos exemplos são necessários para aprendizado? Como podemos formalizar a ideia de generalização em aprendizado? Podemos justificar analiticamente o bom funcionamento de alguns métodos, por exemplo SVM? (PAC learning)

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:

  1. Algoritmos online. Aplicações: Paging, AdWords
  2. Online Learning: predição com experts, método Multiplicative Weights Update, aplicações (e.g. boosting)
  3. Online Learning 2: Online Convex Optimization (OCO). Aplicações: escolha de portfólio de ativos, SVM
  4. Ferramentas de probabilidade: desigualdades de Markov, Chebychev, e Chernoff, e union bound
  5. Programação Estocástica: Sample Average Approximation. Aproximação baseada em programação linear, SDDP
  6. Statistical Learning: PAC learning, quantidade de dados suficientes/necessários pra aprendizado baseado em dimensao VC; justificação SVM; conexões com OCO
  7. Modelos bandit: adversario e estocástico. Aplicações: alocacao de recursos de marketing