Projeto final


O projeto tem que ser relevante à disciplina e pode ser:
  • Apresentar de um tema ou artigo
  • Aplicar e implementar algo visto em aula ou relacionado ao seu problema, + apresentar resultados
  • Trabalho teórico: por exemplo, extensão de resultado visto em aula ou relacionado, + relatorio

Multiplos alunos podem dividir um artigo/tema (apresentacoes e relatorios individuais). Com isso podemos fazer mini-aulas consistindo em 2 ou 3 apresentacoes consecutivas.

Apresentações

As apresentacoes sao individuais, com 30 minutos de duracao

O objetivo principal é que as apresentações sejam interessantes para os outros alunos. Para isso, tem que ser auto-contida, didática, e muito bem estruturada. Pense como uma micro-aula, ensinando pra quem nao nunca viu o problema/modelo (fora o visto em aula). Espera-se que a apresentacao contenha o seguinte:

  • Descricao clara do problema/modelo estudado
  • Exemplo de aplicação concreta ou situação que pode ser modelada com tal modelo
  • Enunciado auto-contido de pelo menos um dos resultados sobre o problema/modelo contidos no artigo/capitulo/etc.
  • Ideia ou passos principais para o obter resultado, comunicados de forma inteligivel
  • (Caso queira, alguma demonstracao)

Dicas para uma boa apresentacao:

  • Tente encontrar uma aula (lecture notes) ou palestra no seu tema (ou baseie seu tema em tal); assim voce tem as coisas o mais estruturado e mastigado possivel.
  • Se a notacao/setup for complexo, simplifique considerando um caso especial ilustrativo
  • Se atenha as ideias principais. "Detalhes" (e.g, como implementar, hipoteses podem nao ser verdadeiras na pratica, etc.) devem ser deferidos aos ultimos 5 min

Proposta de projeto

Até o dia XX (veja na página principal) voce devera entregar a proposta do seu projeto. Esse é um documento de aproximadamente 2 paginas contendo uma breve descricao do tema e um plano tentativo da sua apresentacao ou trabalho cumprindo os items indicados nas secoes anteriores. Para apresentacoes esse plano deve conter o cronograma estimado de cada parte.

Veja um exemplo de plano (com tempo de apresentação de 45 min ao invés de 30 min)

Escolha do tema

Alguns pontos de partida para a escolha do tema:

  • Artigos das conferencias COLT, ICML, NIPS, SODA
  • Material colocado como referencia às aulas (veja tambem as edicoes anteriores do curso)
  • Cursos relacionados, como os do Nikhil Bansal, Kamesh Munagala, e Nikhil Devanur e Anna Karlin
  • Busca por topicos explorados apenas superficialmente no curso (basicamente todos)
  • Alguns topicos nao cobertos no curso: (otimos para mini-aulas, veja acima):
    • Stochastic Optimization from a Computer Science perspective (veja o curso do Kamesh Munagala e sua palestra)
    • Stochastic Programming (em particular Sample Average Approximation)
    • Machine Teaching (por exemplo, artigo mais limpo no tópico, video do grupo de Machine Teaching da Microsoft)
    • Desenho de algoritmos online via programacao linear, 2 apresentações:
      • Apresentação 1: Definição de programação linear, exemplo de problemas (offline) modelados como prog lin (Secao 4.1 da aula do Nikhil), dualidade fraca (aula do Nikhil ou survey), extra
      • Apresentação 2: Algoritmo para ski rental usando programacao-linear (Secao 3 do survey), sketch de algoritmo para Online Set Cover (Secao 4.4 da aula do Nikhil).
    • Online Random Order (or Secretary) Model (survey)
    • Prophet Inequalities (inicio slides + motivacao e aplicacoes)
    • Markov Decision Processes
    • Reinforcement Learning (continuacao do topico acima)
    • Active Learning (slides do Dasgupta e Langford)

Alguns artigos relacionados ao curso: (atualizados periodicamente)

  • Learning to Prune: Speeding up Repeated Computations
  • Oracle-Based Robust Optimization via Online Learning
  • An Online-Learning Approach to Inverse Optimization
  • Unified Algorithms for Online Learning and Competitive Analysis
  • Efficiency Through Procrastination: Approximately Optimal Algorithm Configuration with Runtime Guarantees
  • What You See May Not Be What You Get:UCB Bandit Algorithms Robust to eps-Contamination
  • Exploiting easy data in online optimization
  • Robust Multi-objective Learning with Mentor Feedback
  • Two Faces of Active Learning
  • A Complete Characterization of Statistical Query Learning with Applications to Evolvability
  • Approximations to Stochastic Dynamic Programs via Information Relaxation Duality