Stochastic first-order methods for differentially private machine learning

Stochastic first-order methods for differentially private machine learning

Optimización estocástica

Privacidad diferencial

Problemas de puntos silla

620

Ingeniería

Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2023

En esta tesis estudiamos, desde un punto de vista teórico, dos problemas relevantes en los campos de aprendizaje automático y análisis de datos con restricciones de privacidad: la aproximación de puntos estacionarios en optimización estocástica bajo privacidad diferencial y la aproximación de puntos de silla estocásticos (SSP) bajo privacidad diferencial. Introducimos nuevos algoritmos diferencialmente privados y probamos formalmente garantías teóricas de convergencia y de privacidad. Un punto x se llama ⇥-punto estacionario de una función F : Rd R si ⇥⇤F(x)⇥ ⌅ ⇥. Proponemos un nuevo algoritmo diferencialmente privado basado en SPIDER (Fang et al., 2018) que supera a la mejor tasa conocida anteriormente para aproximar puntos estacionarios del error de generalización. Nuestro algoritmo encuentra un O˜ 1 n1/3 + ⇥ d n ⇤1/2⌅ - punto estacionario del error de generalización en tiempo lineal en n. SSP son las soluciones a problemas de la forma minx⇥X maxy⇥Y F(x, y) para F dada como una esperanza con respecto a una distribución desconocida o difícil (un escenario común en el aprendizaje automático). Para un par (x⇤, y⇤) medimos la cercanía a un SSP con su gap de dualidad Gap(x⇤, y⇤) = EA,S [maxv⇥X,w⇥Y (F(x⇤, w) ⇧ F(v, y⇤))]. Presentamos un nuevo algoritmo para aproximar SSP de forma privada bajo algunos supuestos geométricos. Si F es cuadrática en (x, y) y además se cumplen los supuestos geométricos, nuestro algoritmo es el primer método diferencialmente privado en evitar la maldición de la dimensionalidad al encontrar de manera privada un par (x⇤, y⇤) con Gap(x⇤, y⇤) independiente de las dimensiones ambiente de x e y. Finalmente, mostramos que una pequeña modificación de nuestro algoritmo logra las tasas óptimas para el problema de generar datos sintéticos de forma privada.

González Lara, Tomás

2023-08-17T21:08:00Z

2023-08-17T21:08:00Z

2023

Guzmán Paredes, Cristóbal

Pontificia Universidad Católica de Chile. Escuela de Ingeniería

acceso abierto

xi, 68 páginas

application/pdf

en

tesis de maestría

10.7764/tesisUC/ING/74424

https://doi.org/10.7764/tesisUC/ING/74424

https://repositorio.uc.cl/handle/11534/74424