Informacoes basicas

Aulas: Seg 9-12, Sala ???


Avaliacao



Trabalhos

Trabalho 1 (entrega 29 de abril)
Trabalho 2 (entrega 3 de junho)


Agenda apresentações (TBD)



Datas importantes

Abril 29 Entrega Trabalho 1
Entrega proposta de projeto final
Junho 3 Entrega Trabalho 2
Junho (10), 17, 24, julho 1 Apresentacoes projeto final
Julho 1 Entrega relatorio do projeto final


Topicos

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]
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): Caso especial Online Matching. Analise guloso em AdWords. [Artigo AdWords]
[AdWords Chapter]
[Monografia Primal-Dual]
[Convex analysis perspective on PD algos]
Aula 4 Online Learning: Prediction with experts advice. Halving algorithm, Weighted Majority [Madry's notes]
[AHK MWU Survey]
Aula 5 Online Learning: Multiplicative Weights Update. Abstract prediction with experts. Start boosting. [Madry's notes]
[AHK MWU Survey]
[Boosting book]
Aula 6 Online Learning: Applications of MWU: Boosting. Fast algorithms for offline problems (linear classification) [AHK WMU Survey]
[Boosting book]
[Original Tracking Regret]
[Cesa-Bianchi et al.]
[Adamskiy et al.]
[Daniely et al.]
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]
Aula 8 Online Learning: Aplicacoes: SVM e regressao online [Online SVM]
Aula 9 Online Learning: Other algorithms: Follow the Perturbed Leader, Online Gradient Descent, Online Frank-Wolfe. Modelo bandit, aplicacoes. Algorithmo EXP3 [Follow the Perturbed Leader]
[Online Gradient Descent]
[Online Frank-Wolfe]
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]
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]
Aula 12 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]
Aula 13 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]


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 (AdWord 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 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:

  1. Algoritmos online: análise competitiva, framework primal-dual. Aplicações: Paging, AdWords, Online Set Cover
  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. Online Learning 3: Modelo bandit. Aplicações: alocacao de recursos de marketing
  5. Ferramentas de probabilidade: desigualdades de Markov, Chebychev, e Chernoff, e union bound
  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. Stochastic bandits