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
- Nociones básicas: capítulos 1 y 2 de IT (semanas 1 y 2)
- Desigualdades de concentración: capítulo 3 de IT (lectura personal: Sección 3.1)
- Generalización y estabilidad: capútulo 4 de IT
- Cotas minimax para estimación: capítulos 7 y 8 de IT
- Estimación con restricciones: capítulo 11 de IT
Privacidad Diferencial
- Ataques de privacidad: Exposed! A survey of attacks on private data, The Power of Linear Reconstruction Attacks
- Privacidad Diferencial: 1 y 2 de CDP, y capítulo 3 de AFDP
- Privacidad Diferencial Local: Capítulo 6 de IT
- Alternativas a sensitividad global y generación sintética de datos (capítulos 3 y 4 de CDP), y capítulo 4 de AFDP
- 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
- 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
- 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
- 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:
- (IT) Information Theory and Statistics: http://web.stanford.edu/class/stats311/lecture-notes.pdf
- (AFDP) The Algorithmic Foundations of Differential Privacy: https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf
- (CDP) The Complexity of Differential Privacy: https://privacytools.seas.harvard.edu/files/privacytools/files/complexityprivacy_1_01.pdf
Otros artículos y referencias relevantes serán agregadas para cada capítulo
Información de Interés
- Survey sobre las motivaciones prácticas y conceptuales de privacidad: https://privacytools.seas.harvard.edu/files/privacytools/files/pdf_02.pdf
- Resumen de Apple sobre su utilización de privacidad diferencial: https://www.apple.com/privacy/docs/Differential_Privacy_Overview.pdf