Resumen Técnico: Verificación Pública Eficiente de ML Privado mediante Regularización

Planteamiento del Problema

La Privacidad Diferencial (DP, por sus siglas en inglés) es el marco estándar para proteger la información sensible en el entrenamiento de modelos de aprendizaje automático, garantizando que los usuarios del modelo no puedan inferir puntos de datos específicos. Sin embargo, existe una brecha crítica: los proveedores de datos y el público carecen de métodos eficientes para verificar si un modelo publicado fue realmente entrenado bajo garantías de DP.

Los métodos de verificación actuales enfrentan dos limitaciones primarias:

1. Auditoría de Caja Negra: Los enfoques que consultan a un entrenador de modelos con diferentes conjuntos de datos son estadísticamente insuficientes. El artículo demuestra que, bajo la suposición de firmas digitales, un entrenador malicioso puede implantar una puerta trasera "computacionalmente indetectable". Esta puerta trasera permanece latente durante las auditorías estándar, pero permite al entrenador filtrar el conjunto de datos a entidades específicas, invalidando la privacidad del algoritmo a pesar de haber pasado cualquier verificación de caja negra.
2. Costos de Verificación Interactiva: Los protocolos de verificación interactiva existentes para DP (por ejemplo, verificar DP-SGD) requieren que el verificador vuelva a computar casi todos los pasos de entrenamiento. Por ejemplo, verificar DP en el conjunto de datos MNIST anteriormente requería aproximadamente 100 horas de computación, escalando con el costo de entrenamiento. Esto hace que la verificación pública sea poco práctica para conjuntos de datos grandes.

El artículo aborda el desafío de diseñar un algoritmo de DP donde el costo de verificación sea estrictamente menor que el costo de entrenamiento, específicamente para la Optimización Convexa Estocástica (DP-SCO).

Metodología

1. Fundamento Teórico: Puertas Traseras Indetectables

Los autores primero formalizan la insuficiencia de la auditoría de caja negra. Construyen un algoritmo de entrenamiento con puerta trasera $T'$ que es computacionalmente indistinguible de un algoritmo de DP legítimo $T$ para cualquier auditor de tiempo polinomial.

• Mecanismo: El algoritmo incorpora un paso de verificación de firma digital en los datos de entrenamiento. Si una entrada específica contiene una firma válida (que solo el entrenador malicioso posee), el algoritmo devuelve el conjunto de datos de entrenamiento bruto en lugar del modelo.
• Implicación: Esto demuestra que sin protocolos interactivos, ningún auditor público puede garantizar la privacidad de un modelo, lo que requiere un cambio hacia la certificación interactiva.

2. Algoritmo Central: ERM por Fases Modificado

Para lograr una verificación eficiente, los autores proponen una modificación del algoritmo de Minimización del Riesgo Empírico (ERM) por Fases (Feldman et al., 2020).

• ERM por Fases Estándar: Resuelve una serie de objetivos regularizados sobre subconjuntos disjuntos de datos, aumentando la fuerza de la regularización a través de fases. Se basa en la composición paralela de presupuestos de privacidad para lograr garantías ajustadas. Sin embargo, verificar la composición paralela es costoso porque el verificador debe confirmar que cada fase utilizó un subconjunto de datos específico y disjunto.
• La Modificación: Los autores alteran los criterios de parada para los aproximadores de mínimos en cada fase.
  • En lugar de requerir que el exceso de pérdida sea pequeño, requieren que la norma del gradiente sea pequeña ($\|\nabla F_i(\tilde{w}_i)\|_2 \leq \frac{2}{n_i} L$).
  • Ajustan el presupuesto de privacidad $\delta$ para cada fase a $\delta / \lceil \log_2(n) \rceil$.
• Beneficio Resultante: Esta modificación permite al algoritmo derivar compromisos de privacidad-utilidad casi óptimos utilizando únicamente la composición secuencial estándar en lugar de la composición paralela. La composición estándar es significativamente más fácil de verificar porque no requiere probar la disjuntividad de los subconjuntos de datos, solo que el ruido se añadió correctamente y que las normas de los gradientes se cumplieron.

3. Protocolo de Verificación

El protocolo propuesto (Algoritmo 2) involucra una prueba interactiva entre un Probador (entrenador) y un Verificador (público):

1. Compromiso (Commitment): El Probador establece un compromiso con el conjunto de datos y los pesos del modelo en cada fase.
2. Verificación de Gradiente: Utilizando Pruebas de Conocimiento Cero (ZKP), el Verificador comprueba que la norma del gradiente del aproximador de mínimo está por debajo del umbral requerido.
3. Verificación de Ruido: El Verificador comprueba que se añadió ruido Gaussiano a los pesos utilizando un esquema de compromiso de Gaussiano discreto.
4. Complejidad: La verificación requiere verificar $n$ gradientes (donde $n$ es el tamaño del conjunto de datos) y $d \cdot \lceil \log_2(n) \rceil$ compromisos de variables aleatorias Gaussianas (donde $d$ es la dimensión).

4. Extensión al Desaprendizaje de Máquina (Machine Unlearning)

Los autores extienden estas técnicas al Desaprendizaje de Máquina Aproximado para pérdidas fuertemente convexas. Aprovechando la estabilidad de las funciones fuertemente convexas, demuestran que el desaprendizaje puede certificarse verificando los gradientes en el conjunto de datos de retención ($D'$) en lugar del conjunto completo, requiriendo solo $|D'|$ comprobaciones de gradiente y $d$ compromisos de ruido.

Resultados Clave

Garantías Teóricas

• Compromiso Privacidad-Utilidad: El algoritmo modificado logra un exceso de riesgo poblacional de $\tilde{O}(L D (\frac{1}{\sqrt{n}} + \frac{\sqrt{d \ln(1/\delta)}}{\epsilon n}))$, lo cual es casi óptimo (coincidiendo con los límites inferiores conocidos hasta factores de $\log \log(n)$).
• Eficiencia de Verificación: La certificación requiere verificar solo $n$ gradientes y $d \cdot \lceil \log(n) \rceil$ variables aleatorias Gaussianas.
  • Comparado con los algoritmos de entrenamiento más rápidos conocidos para DP-SCO, que requieren $\tilde{\Omega}(\min(n^{1.5}, n^2/\sqrt{d}))$ gradientes, el costo de verificación es significativamente menor (al menos una mejora de $O(\sqrt{n})$ en entornos no suaves).
  • En entornos suaves, la reducción en las comprobaciones de variables aleatorias Gaussianas (de $\Omega(dn)$ a $d \log n$) proporciona una ventaja sustancial en el tiempo de ejecución.

Evaluación Empírica

Los autores implementaron el protocolo utilizando el toolkit EMP para regresión logística binaria en el conjunto de datos MNIST ($n=60,000, d=784$).

• Comparación de Tiempo de Ejecución:
  • Enfoque Previo (Verificación de DP-SGD): ~100 horas.
  • Enfoque Propuesto: ~3 horas en una CPU de laptop.
• Análisis de Cuellos de Botella:
  • Verificación de Gradiente: Domina el tiempo de ejecución. El número de gradientes a verificar se redujo en más de 4 veces en comparación con métodos anteriores.
  • Verificación de Ruido: El tiempo para verificar variables aleatorias Gaussianas cayó drásticamente (de ser el costo dominante a ser insignificante, tomando menos tiempo que una sola verificación de gradiente).
  • Comunicación: Se encontró que la sobrecarga de red (LAN/WAN) es insignificante comparada con la computación.
  • Entrenamiento: El tiempo de entrenamiento fue insignificante (segundos) porque no requiere cifrado homomórfico, a diferencia de su proceso de verificación.

Significado y Reivindicaciones

El artículo afirma presentar el primer algoritmo de DP-SCO conocido donde la verificación de DP escala mejor que el costo de entrenamiento.

• Cambio de Paradigma: Mueve el campo de la "auditoría de caja negra" (que es demostrablemente insuficiente contra adversarios computacionalmente limitados) hacia la "verificación pública eficiente" mediante pruebas interactivas.
• Practicidad: Al reducir el tiempo de verificación de ~100 horas a ~3 horas en hardware estándar para datos de escala MNIST, el artículo argumenta que la certificación pública de ML privado se está volviendo factible.
• Limitaciones: Los autores señalan modestamente que el enfoque actual se limita a entornos convexos y no se aplica directamente a redes neuronales profundas (aunque podría aplicarse al ajuste fino de la última capa). También reconocen que para conjuntos de datos muy grandes, la escala lineal con $n$ aún puede ser poco práctica, y que se necesita trabajo futuro para manejar gradientes estocásticos de manera más eficiente (por ejemplo, mediante suavizado aleatorizado).

En resumen, el artículo establece que, al aprovechar la regularización para estabilizar la optimización y modificar los criterios de verificación para centrarse en las normas de los gradientes en lugar del exceso de pérdida, es posible construir algoritmos de DP que sean tanto casi óptimos en utilidad como eficientemente verificables por el público.