Informacoes basicas

  • Aulas: Seg 13-16, Sala 510
  • Avaliacao: Trabalhos e notas de aula (scribing)


Trabalhos

Trabalho 1 (entrega 8 maio)
Trabalho 2 (entrega 19 junho)


Apresentacao de fim de curso

Essa parte da avaliacao consiste em apresentacoes individuais de ~45 minutos. A apresentacao deve ser baseada em um artigo/video relevante ao curso, ou um trabalho de implementacao significativo. Multiplos alunos podem dividir um artigo/tema, com autorizacao previa.

Alguns pontos de partida para escolha do tema:

  • Material colocado como referencia às aulas
  • Videos do Workshop Algorithms and Uncertainty Boot Camp. Voce pode "reapresentar" parte de um video.
  • Material "original" (e.g. aplicação não trivial das técnicas vistas)

Agenda apresentações


Junho 12 David Sotelo, João Brandão
Junho 19 Raphael Sampaio, Matheus Leal, Luiz Romario, Yuri Resende
Junho 26 Gabriel Homsi, Joaquim Garcia, Daniel Specht

Sem data: Daniel Gribel, Charles Kubudi



Datas importantes

Maio 8 Entrega Trabalho 1
Entrega proposta apresentacoes fim de curso
Junho 19 Entrega Trabalho 2
Junho 12, 19 e 26 Apresentacoes de fim de curso

Topicos

Scribe notes are only lightly edited.

Topico Material Scribe notes
Aula 1 Algoritmos online: Modelo, competitive ratio. Problema Ski Rental. Algoritmos deterministicos e lower bounds. Algoritmos aleatorizados. Yao's minimax principle e lower bound para algoritmos aleatorizados. [Anupam and Avrim's note]
[Karlin et al. Ski Rental paper]
Notes
Pre Aula 2 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 2 Algoritmos online: Paging: Algoritmos deterministicos, lower bound deterministicos; algo. aleatorizados, mencao LB; pratica. AdWords (anuncios Google). Notas: k-Server, framework Primal-Dual. Quiz probabilidade.

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

[Nikhil's lec on Paging]
[Artigo AdWords]
[AdWords Chapter]
[Monografia Primal-Dual]
[Convex analysis perspective on PD algos]
Notes
Aula 3 Probabilidade: Desigualdades dos 3 "Russos": Markov, Chebychev, Chernoff. Chernoff + union bound: Balls-in-bins. Random order model. Secretary Problem [Matousek-Vondrak's notes]
[Concentration Inequalities - BLM]
[Kesselheim's note on Sec. Prob.]
Notes
Aula 4 Random-order model: Main algorithmic techniques in Random Order model. K-choice Secretary Problem and technique of "Learning a classifier" [Agrawal-Ye-Wang Packing LPs] [M.-Ravi Packing LPs] Notes
Aula 5 Random-order model: High-level idea of what happened in k-choice Secretary, quick wrap up. AdWords in random-order model (high-level idea) [Devanur-Hayes AdWords]
Online Learning: Halving algorithm, Weighted Majority, Multiplicative Weights Update. Application: Boosting [Madry's notes]
[AHK MWU Survey]
Aula 6 Online Learning: Proof of Weighted Majority. Multilpicative Weights Update method. Application: Boosting [Madry's notes]
[AHK MWU Survey]
[Boosting book]
Notes
Aula 7 Online Learning: Other applications/perspectives on prediction with experts. Minimax Theorem. Fast algorithms via experts: linear classification. Conection with random-order model. Extensions: tracking and adaptive regret. [AHK MWU Survey]
[Load bal random-order] [Agrawal-Devanur random-order] [CesaBianchi-Lugosi book] [Tracking/adaptive regret]
Aula 8 Online Learning: Online convex optimization (OCO). Online linear optimization (OLO) and Follow the Perturbed Leader. [Avrim's lecture]
[Kalai-Vempala's lecture]
[Kalai-Vempala paper]
[Hazan's OCO book]
Aula 9 Online Learning: Importance of stability in learning. Online Gradient Descent. Modeling contexts with OCO. Bandit Experts, EXP3 algorithm. Interesting properties of Online Learning. [Stability in learning]
[Perturbation vs. regularization]
[OCO Tutorial]
[log(T) regret]
[Nikhil's OGD notes]
[Auer et al. Bandit]
[Nikhil's EXP3 lecture]
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. Definition of VC dimension, examples. [Learning book]
[Guestrin's slides]
Aula 11 PAC Learning: VC dimension and "size" of concept class: Sauer-Shelah Lemma. Generalization bounds based on VC dimensions. Application to boosting. Structural Risk Minimization.
Aula 12 PAC Learning: Validation. Connections of PAC learning with Online Random-order model and Online Learning; online-to-batch conversion. Covering numbers and relation to VC dimension. Generalization bounds for SVM.


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 SMV? (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: Básico de algoritmos (equivalente ao curso de pós-graduação ``Projeto e Análise de Algoritmos''), probabilidade discreta (independência, valor esperado, etc.) e cálculo (gradiente)

Ementa:

  1. Algoritmos online: análise competitiva; aplicações: Paging, balanceamento de carga
  2. Ferramentas de probabilidade: desigualdade de Markov, desigualdade de Chernoff, union bound
  3. Modelo de Ordem Aleatória: Secretary Problem, alocação de anúncio na Google (adWords Problem)
  4. Online Learning: predição com experts, método Multiplicative Weights Update, aplicações (e.g. boosting); conexão com Modelo de Ordem Aleatória
  5. Online Learning 2: Online Convex Optimization (OCO). Aplicações: escolha de portfólio de ativos, SVM
  6. Statistical Learning: PAC learning, quantidade de dados suficientes/necessários pra aprendizado baseado em dimensao VC; justificação SVM; conexões com Modelo de Ordem Aleatoria e OCO
  7. Programação inteira estocástica: modelos, Deterministic Equivalent, Sample Average Approximation (e conexão com PAC learning)