Not All Learnable Distribution Classes are Privately Learnable

Resumen Técnico: "No todas las clases de distribuciones aprendibles son aprendibles de forma privada"

Planteamiento del Problema
El artículo aborda una pregunta fundamental en la intersección de la teoría del aprendizaje estadístico y la privacidad diferencial (DP): ¿Es toda clase de distribuciones que es aprendible en el escenario estándar (no privado) también aprendible bajo las restricciones de la privacidad diferencial $(\varepsilon, \delta)$?

Si bien está establecido que la privacidad diferencial pura ($\varepsilon$-DP, donde $\delta=0$) impone separaciones estrictas entre clases aprendibles y clases aprendibles de forma privada (a menudo caracterizadas por números de recubrimiento/empaquetado), el estatus de la privacidad diferencial aproximada ($(\varepsilon, \delta)$-DP) permaneció como una pregunta abierta. La literatura reciente ha producido marcos cada vez más generales para el aprendizaje de distribuciones privadas, lo que llevó a Ashtiani [Ash22] a conjeturar que la respuesta a la pregunta anterior es afirmativa: que toda clase de distribuciones aprendible es aprendible de forma privada.

Metodología y Construcción
Los autores refutan esta conjetura construyendo una clase específica de distribuciones, denotada como $\mathcal{H}_w$, que sirve como contraejemplo. La construcción utiliza un mecanismo de "trampa" que involucra mezclas de distribuciones:

1. La Estructura de la Clase: La clase $\mathcal{H}_{w,d}$ consiste en mezclas sobre $d+1$ componentes que comparten un vector de parámetros común $\mathbf{p} \in [0,1]^d$.
   • El Componente "Clave": Una distribución de producto binaria sobre $\{0,1\}^d$ con peso de mezcla $w$. Una sola muestra de este componente revela información sobre todo el vector de parámetros $\mathbf{p}$.
   • Los Componentes "Difíciles": $d$ componentes adicionales, cada uno soportado en $\{\pm j\}$ para $j \in \{1, \dots, d\}$, con peso de mezcla $(1-w)/d$. Una muestra de cualquiera de estos revela información sobre solo una sola coordenada de $\mathbf{p}$.
2. La Trampa: El peso de mezcla $w$ se establece en $1/(2\alpha)$ (donde $\alpha$ es el error objetivo). Esto asegura que los componentes "difíciles" dominen la mezcla (alta probabilidad de muestrearlos), mientras que el componente "clave" es raro.
3. El Truco de la Dimensionalidad: La clase $\mathcal{H}_w$ se define como la unión de estas clases sobre todas las dimensiones $d \ge 2$. La construcción asegura que, aunque la dimensión $d$ no está fijada a priori, la dificultad del aprendizaje escala con $d$.

Resultados y Pruebas Clave
El artículo establece una separación entre la aprendibilidad no privada y la aprendibilidad privada para la clase $\mathcal{H}_w$ con respecto a la distancia de Variación Total (TV):

1. Aprendibilidad No Privada (Muestras Finitas):
   Los autores demuestran que $\mathcal{H}_w$ es aprendible con un número constante de muestras (independiente de $d$) hasta un error constante.

   • Mecanismo: Dado que el componente "clave" aparece con probabilidad $w$, un algoritmo no privado puede recopilar suficientes muestras para observar el componente clave. Una vez observado, la dimensión $d$ se identifica y el vector de parámetros $\mathbf{p}$ puede estimarse mediante la media muestral de la distribución de producto binaria.
   • Complejidad: La complejidad de la muestra es $O(1/\alpha^3 \cdot \log(1/\beta))$, que es constante con respecto a la dimensión $d$.

2. No Aprendibilidad Privada (Se Requieren Muestras Infinitas):
   Los autores prueban que ningún mecanismo $(\varepsilon, \delta)$-DP puede aprender esta clase con la misma garantía de error utilizando un número finito de muestras.

   • Reducción: Construyen una reducción del problema de estimación de densidad en $\mathcal{H}_{w,d}$ al problema de estimación de parámetros $\ell_1$ para distribuciones de producto binaria.
   • Límite Inferior: Aprovechando límites inferiores conocidos para la estimación de medias privadas de distribuciones de producto binaria (específicamente de [KLSU19]), muestran que la complejidad de la muestra para aprender $\mathcal{H}_{w,d}$ bajo DP escala como $\Omega(\sqrt{d}/(\sqrt{\alpha}\varepsilon))$.
   • Contradicción: Dado que la clase $\mathcal{H}_w$ incluye distribuciones para cualquier $d \ge 2$, y el tamaño de muestra requerido crece con $\sqrt{d}$, ningún tamaño de muestra finito $n$ es suficiente para aprender toda la clase $\mathcal{H}_w$ bajo DP. A medida que $d \to \infty$, el tamaño de muestra requerido tiende a infinito.

Contribuciones Clave

• Refutación de la Conjetura: El artículo proporciona un contraejemplo explícito a la conjetura de Ashtiani de que toda clase de distribuciones aprendible es aprendible de forma privada bajo $(\varepsilon, \delta)$-DP.
• Separación de Aprendibilidad: Demuestra una separación estricta donde una clase es aprendible con $O(1)$ muestras de forma no privada, pero requiere un número infinito de muestras para aprenderse de forma privada.
• Construcción de Trampa: Los autores introducen una construcción específica de "trampa" donde un componente raro actúa como clave para un parámetro de alta dimensión, el cual está de otro modo oscurecido por un componente dominante y difícil de aprender. Esta estructura impide que los mecanismos privados accedan a la "clave" sin violar las restricciones de privacidad o requerir tamaños de muestra prohibitivos.

Significado y Afirmaciones
El artículo afirma "refutar débilmente" la conjetura. Los autores notan explícitamente que una "refutación fuerte" requeriría mostrar que la clase es aprendible para cualquier error objetivo (no solo error constante) con muestras finitas de forma no privada, lo cual no prueban. Sin embargo, su resultado es significativo porque muestra que incluso para garantías de error constante, el panorama del aprendizaje de distribuciones privadas es fundamentalmente diferente del aprendizaje no privado.

El trabajo destaca que los marcos generales para el aprendizaje privado no pueden depender simplemente de reducciones de caja negra de aprendices no privados sin suposiciones estructurales adicionales. Establece que la existencia de un componente "clave" que es raro pero esencial para el aprendizaje puede crear una barrera insuperable para los algoritmos privados, incluso cuando el algoritmo no privado es eficiente.

Conclusión
El artículo concluye que la agenda de diseñar algoritmos generales de aprendizaje privado que funcionen para todas las clases de distribuciones aprendibles no puede realizarse plenamente. Existen clases aprendibles donde la restricción de privacidad altera fundamentalmente la complejidad de la muestra de finita a infinita, independientemente de la tolerancia al error específica (dentro del régimen constante considerado).