Informacoes basicas

Aulas: Ter 9-12, Sala RDC510


Avaliacao



Trabalhos

Trabalho 1 (entrega 9 de outubro)
Trabalho 2 (entrega 13 de novembro)


Agenda apresentações

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


Datas importantes

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


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]
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.

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


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; aplicações: Paging, balanceamento de carga
  2. Online Learning: predição com experts, método Multiplicative Weights Update, aplicações (e.g. boosting); conexão com Modelo de Ordem Aleatória
  3. Online Learning 2: Online Convex Optimization (OCO). Aplicações: escolha de portfólio de ativos, SVM
  4. Ferramentas de probabilidade: desigualdade de Markov, desigualdade de Chernoff, union bound
  5. Statistical Learning: PAC learning, quantidade de dados suficientes/necessários pra aprendizado baseado em dimensao VC; justificação SVM; conexões com OCO
  6. Modelo de Ordem Aleatória: Secretary Problem, alocação de anúncio na Google (adWords Problem). Conexão PAC learning, OCO.