IMT3830: Tópicos Avanzados en Algoritmos, Combinatoria y Optimización

Esta es la página oficial del curso IMT3830, segundo semestre de 2019, ofrecido por la Escuela de Ingeniería de la Pontificia Universidad Católica de Chile

Equipo Docente

  • Profesor: Cristóbal Guzmán
  • Ayudante: Patricio Ulloa

Horario

  • Cátedras: Lunes y Viernes, 10:00-11:20

Descripción del curso

En este curso se presentarán las herramientas básicas de Teoría de la Información, junto con sus aplicaciones en Privacidad Diferencial. La teoría de la información fue introducida por Shannon en 1948, en el contexto de compresión y comunicación de datos, y desde entonces ha encontrado numerosas aplicaciones en contextos tales como estadística, análisis de algoritmos, seguridad, entre otros.

Por otra parte, en situaciones donde información sensible de individuos es utilizada para el análisis de datos, privacidad diferencial permite realizar dichos análisis, con una garantía formal de protección de la privacidad. Varios problemas clásicos en estadística (aprendizaje supervisado, optimización convexa estocástica, etc.) pueden ser resueltos con garantías de privacidad, sin embargo muchas preguntas fundamentales permanecen abiertas.

Contenidos

Teoría de la Información

  1. Nociones básicas: capítulos 1 y 2 de IT (semanas 1 y 2)
  2. Desigualdades de concentración: capítulo 3 de IT (lectura personal: Sección 3.1)
  3. Generalización y estabilidad: capútulo 4 de IT
  4. Cotas minimax para estimación: capítulos 7 y 8 de IT
  5. Estimación con restricciones: capítulo 11 de IT

Privacidad Diferencial

  1. Ataques de privacidad: Exposed! A survey of attacks on private data, The Power of Linear Reconstruction Attacks
  2. Privacidad Diferencial: 1 y 2 de CDP, y capítulo 3 de AFDP
  3. Privacidad Diferencial Local: Capítulo 6 de IT
  4. Alternativas a sensitividad global y generación sintética de datos (capítulos 3 y 4 de CDP), y capítulo 4 de AFDP
  5. Cotas inferiores en privacidad: capítulos 5 y 6 de CDP , The Cost of Privacy: Optimal Rates of Convergence for Parameter Estimation with Differential Privacy

Tópicos Avanzados

  1. Privaciad diferencial en optimización convexa estocástica: Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds, Private Stochastic Optimization with Optimal Rates
  2. Análisis de datos adaptativo: Preserving Statistical Validity in Adaptive Data Analysis, Generalization in Adaptive Data Analysis with Holdout Reuse, Algorithmic Stability for Adaptive Data Analysis
  3. Privacidad diferencial y diseño de mecanismos

Evaluaciones

  • Presentaciones en clases
  • Participación en clases
  • Informe y presentación final. Los tópicos pueden ser elegidos entre los tópicos avanzados, y los alumnos podrán también proponer temas.

Presentaciones

El siguiente archivo servirá para coordinar a quienes presenten cada semana. Iremos actualizando la programación a medida que avanzamos en los contenidos.

Apuntes

Seguiremos los siguientes apuntes y libros:

Otros artículos y referencias relevantes serán agregadas para cada capítulo

Información de Interés