IMT3830: Tópicos Avanzados en Algoritmos, Combinatoria y Optimización
Esta es la página oficial del curso IMT3830, primer semestre de 2023, ofrecido por el Instituto de Ingeniería Matemática y Computacional de la Pontificia Universidad Católica de Chile
Equipo Docente
Profesor: Cristóbal Guzmán
Ayudante: Juan Pablo Flores
Horario
Cátedras: Martes y Jueves, 14:00-15:20
Hora de consultas: Miércoles, 17:00-18:20
Descripción del curso
En este curso se presentarán las herramientas básicas de Privacidad Diferencial, junto con su aplicación para resolver problemas de Optimización (Convexa) Estocástica con garantías formales de privacidad.
Contenidos
Motivation: privacy risks
(Pure) differential privacy: randomized response, Laplace mechanism, basic properties and interpretation, privacy amplification by subsampling
Basics of information theory: entropy, mutual information and probability distances/divergences
Approximate differential privacy: definition, Gaussian mechanism
Rényi differential privacy
Advanced composition theorem
Stochastic Convex Optimization: definition, examples, empirical risk minimization
Stochastic Gradient Method
Differentially-Private Stochastic Convex Optimization (DP-SCO): phased SGM
DP-SCO with nonsmooth losses: stability and generalization, optimality of noisy SGM
DP stochastic optimization with nonconvex losses: private SPIDER
Differentially-Private Synthetic Data: exponential mechanism and Small-DB, private multiplicative weights method
Evaluaciones
5 tareas (40%)
Informe final (30%)
Presentación final (30%)
Apuntes
Referencias
Seguiremos los siguientes apuntes y libros:
Algorithms for Private Data Analysis: http://www.gautamkamath.com/courses/CS860-fa2022.html
Information Theory and Statistics: http://web.stanford.edu/class/stats311/lecture-notes.pdf
The Algorithmic Foundations of Differential Privacy: https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf
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
Sitio web de difusión sobre privacidad diferencial:
https://differentialprivacy.orgSurvey 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