Informacoes basicas

Aulas: Seg 9-12, sala 510 ou 511 (confirmar). Zoom link


Avaliacao




Agenda apresentações (TBD)



Datas importantes

Outubro 3 Entrega Trabalho 1
Entrega proposta de projeto final
Novembro 7 Entrega Trabalho 2
Novembro 28, Dezembro 5 Apresentacoes projeto final


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]
[scribe]
Aula 2 Algoritmos online: Paging

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

[Nikhil's lec on Paging]
[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]


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