Quadratic Objective Perturbation: Curvature-Based Differential Privacy

Resumen Técnico: Perturbación Cuadrática del Objetivo para ERM con Privacidad Diferencial

Planteamiento del Problema
El artículo aborda el desafío de lograr Privacidad Diferencial (DP) en problemas de Minimización de Riesgo Empírico (ERM), particularmente en entornos de aprendizaje automático modernos donde los datos son sensibles y los modelos suelen estar sobreparametrizados. La formulación estándar implica minimizar una suma de funciones de pérdida convexas más un regularizador sobre un conjunto de datos $D$. Los enfoques existentes, específicamente la Perturbación Lineal del Objetivo (LOP), imponen privacidad añadiendo un término lineal aleatorio al objetivo. Sin embargo, LOP depende de la fuerte suposición de que los gradientes de las funciones de pérdida están acotados uniformemente. Esta suposición se viola frecuentemente en el aprendizaje profundo moderno y en sistemas sobreparametrizados, donde los gradientes pueden ser ilimitados, haciendo que LOP sea inaplicable o requiera mecanismos de recorte poco realistas que degradan la utilidad.

Metodología: Perturbación Cuadrática del Objetivo (QOP)
Los autores proponen la Perturbación Cuadrática del Objetivo (QOP), un mecanismo que perturba la función objetivo con una forma cuadrática aleatoria en lugar de una lineal. En lugar de resolver el problema original, el mecanismo resuelve:
$$\theta_{priv} = \arg\min_{\theta \in C} \left\{ J(\theta; D) + \frac{\sigma^2}{2}(\theta - \tilde{\theta}^*)^T W (\theta - \tilde{\theta}^*) \right\}$$
donde $W$ es una matriz aleatoria extraída de una distribución (específicamente un ensamble de Wishart) y $\tilde{\theta}^*$ es una aproximación de un minimizador común de las funciones de pérdida.

Las características metodológicas clave incluyen:

1. Privacidad Basada en Curvatura: A diferencia de LOP, que desplaza el minimizador y requiere gradientes acotados para controlar la sensibilidad, QOP modifica la curvatura del objetivo. El término cuadrático aleatorio induce convexidad fuerte, y la sensibilidad de la salida se controla a través de las propiedades espectrales (valores propios) de la matriz aleatoria $W$.
2. Régimen de Interpolación: El análisis asume la existencia de un minimizador común $\theta^*$ para todas las funciones de pérdida individuales (el régimen de interpolación), una condición estándar en el aprendizaje sobreparametrizado donde es posible lograr una pérdida de entrenamiento cero.
3. Soluciones Aproximadas: El marco se extiende a escenarios prácticos donde el problema perturbado se resuelve de manera aproximada (precisión $\tau$) y el punto de anclaje $\tilde{\theta}^*$ es una aproximación (precisión $\eta$) del verdadero minimizador común. El mecanismo añade ruido gaussiano a la solución aproximada para contabilizar estos errores.
4. Implementación Algorítmica: El problema perturbado resultante conserva una estructura compuesta (suma finita suave + regularizador no suave + restricciones), lo que permite resolverlo eficientemente utilizando esquemas de División de Tres Operadores Estocásticos (StoTOS).

Contribuciones Clave

1. Nuevo Mecanismo de Perturbación: Introducción de QOP, que elimina la necesidad de la suposición de gradiente acotado requerida por los métodos anteriores de perturbación lineal.
2. Análisis de Privacidad bajo Suposiciones Más Débiles: Una prueba de privacidad novedosa que demuestra que se puede garantizar la privacidad diferencial $(\epsilon, \delta)$ en el régimen de interpolación sin asumir gradientes acotados. La prueba aprovecha las propiedades espectrales de la matriz aleatoria $W$ para acotar la sensibilidad del minimizador.
3. Robustez ante Aproximaciones: Extensión de las garantías de privacidad a entornos que involucran resoluciones inexactas y puntos de anclaje aproximados, mostrando que se preserva una privacidad significativa a pesar de estas imperfecciones prácticas.
4. Garantías de Utilidad: Derivación de límites sobre el riesgo empírico excedente, cuantificando la compensación entre los parámetros de privacidad, la precisión del solucionador y la distancia entre el minimizador verdadero y el minimizador común.

Resultados

• Comparación Teórica: El artículo establece que QOP y LOP satisfacen leyes de escalado fundamentalmente diferentes. El análisis teórico muestra que el riesgo de LOP escala con el diámetro del conjunto de restricciones (debido a su dependencia de los límites de gradiente), mientras que el riesgo de QOP permanece estable e independiente del diámetro de la restricción.
• Experimentos Numéricos: Los resultados empíricos en mínimos cuadrados lineales con regresión LASSO confirman los hallazgos teóricos. En regímenes con gradientes ilimitados (diámetros de restricción grandes), el riesgo empírico de LOP aumenta significativamente, mientras que QOP permanece estable. Incluso en regímenes de dominio pequeño, QOP demuestra un riesgo empírico inferior en comparación con LOP y LOP con recorte de gradiente.
• Eficiencia Algorítmica: El uso de esquemas de división estocástica permite resolver los problemas perturbados de manera eficiente, validando la viabilidad práctica del enfoque.

Significado y Afirmaciones
El artículo afirma que QOP proporciona una alternativa natural a los métodos clásicos de perturbación del objetivo, particularmente para entornos de aprendizaje automático modernos donde las suposiciones de regularidad fuerte (como gradientes acotados) rara vez se cumplen. Al desplazar el control de la sensibilidad de los límites de gradiente a la curvatura del objetivo mediante perturbaciones de matrices aleatorias, los autores ofrecen un marco que es tanto teóricamente sólido bajo suposiciones más débiles como empíricamente superior en estabilidad. El trabajo sugiere que las perturbaciones basadas en curvatura son un mecanismo más robusto para equilibrar la privacidad y la utilidad en modelos sobreparametrizados. Los autores señalan que el trabajo futuro podría centrarse en relajar la suposición de minimizador común y explorar la privacidad diferencial de Rényi para garantías más ajustadas.