Quadratic Objective Perturbation: Curvature-Based Differential Privacy

Resumo Técnico: Perturbação Quadrática do Objetivo para ERM com Privacidade Diferencial

Enunciação do Problema
O artigo aborda o desafio de alcançar Privacidade Diferencial (DP) em problemas de Minimização de Risco Empírico (ERM), particularmente em configurações modernas de aprendizado de máquina onde os dados são sensíveis e os modelos são frequentemente superparametrizados. A formulação padrão envolve minimizar a soma de funções de perda convexas mais um regularizador sobre um conjunto de dados $D$. Abordagens existentes, especificamente a Perturbação Linear do Objetivo (LOP), impõem a privacidade adicionando um termo linear aleatório ao objetivo. No entanto, a LOP depende da suposição forte de que os gradientes das funções de perda são uniformemente limitados. Essa suposição é frequentemente violada em aprendizado profundo moderno e sistemas superparametrizados, onde os gradientes podem ser ilimitados, tornando a LOP inaplicável ou exigindo mecanismos de corte irreais que degradam a utilidade.

Metodologia: Perturbação Quadrática do Objetivo (QOP)
Os autores propõem a Perturbação Quadrática do Objetivo (QOP), um mecanismo que perturba a função objetivo com uma forma quadrática aleatória em vez de uma linear. Em vez de resolver o problema original, o mecanismo resolve:
$$\theta_{priv} = \arg\min_{\theta \in C} \left\{ J(\theta; D) + \frac{\sigma^2}{2}(\theta - \tilde{\theta}^*)^T W (\theta - \tilde{\theta}^*) \right\}$$
onde $W$ é uma matriz aleatória extraída de uma distribuição (especificamente um conjunto Wishart) e $\tilde{\theta}^*$ é uma aproximação de um minimizador comum das funções de perda.

Características metodológicas chave incluem:

1. Privacidade Baseada em Curvatura: Diferentemente da LOP, que desloca o minimizador e requer gradientes limitados para controlar a sensibilidade, a QOP modifica a curvatura do objetivo. O termo quadrático aleatório induz forte convexidade, e a sensibilidade da saída é controlada através das propriedades espectrais (autovalores) da matriz aleatória $W$.
2. Regime de Interpolação: A análise assume a existência de um minimizador comum $\theta^*$ para todas as funções de perda individuais (o regime de interpolação), uma condição padrão em aprendizado superparametrizado onde o risco de treinamento zero é alcançável.
3. Soluções Aproximadas: O quadro estende-se a cenários práticos onde o problema perturbado é resolvido aproximadamente (precisão $\tau$) e o ponto de ancoragem $\tilde{\theta}^*$ é uma aproximação (precisão $\eta$) do verdadeiro minimizador comum. O mecanismo adiciona ruído gaussiano à solução aproximada para contabilizar esses erros.
4. Implementação Algorítmica: O problema perturbado resultante retém uma estrutura composta (soma finita suave + regularizador não suave + restrições), permitindo que seja resolvido eficientemente usando esquemas de Divisão de Três Operadores Estocásticos (StoTOS).

Principais Contribuições

1. Novo Mecanismo de Perturbação: Introdução da QOP, que elimina a necessidade da suposição de gradiente limitado requerida por métodos anteriores de perturbação linear.
2. Análise de Privacidade sob Suposições Mais Fracas: Uma prova de privacidade inovadora demonstrando que a privacidade diferencial $(\epsilon, \delta)$ pode ser garantida no regime de interpolação sem assumir gradientes limitados. A prova aproveita as propriedades espectrais da matriz aleatória $W$ para limitar a sensibilidade do minimizador.
3. Robustez à Aproximação: Extensão das garantias de privacidade para configurações envolvendo resoluções inexatas e pontos de ancoragem aproximados, mostrando que a privacidade significativa é preservada apesar dessas imperfeições práticas.
4. Garantias de Utilidade: Derivação de limites sobre o risco empírico excedente, quantificando o trade-off entre parâmetros de privacidade, precisão do solucionador e a distância entre o minimizador verdadeiro e o minimizador comum.

Resultados

• Comparação Teórica: O artigo estabelece que a QOP e a LOP satisfazem leis de escalonamento fundamentalmente diferentes. A análise teórica mostra que o risco da LOP escala com o diâmetro do conjunto de restrições (devido à sua dependência de limites de gradiente), enquanto o risco da QOP permanece estável e independente do diâmetro da restrição.
• Experimentos Numéricos: Resultados empíricos em mínimos quadrados lineares com regressão LASSO confirmam as descobertas teóricas. Em regimes com gradientes ilimitados (grandes diâmetros de restrição), o risco empírico da LOP aumenta significativamente, enquanto a QOP permanece estável. Mesmo em regimes de domínio pequeno, a QOP demonstra menor risco empírico comparada à LOP e à LOP com corte de gradiente.
• Eficiência Algorítmica: O uso de esquemas de divisão estocástica permite que os problemas perturbados sejam resolvidos eficientemente, validando a viabilidade prática da abordagem.

Significado e Alegações
O artigo alega que a QOP fornece uma alternativa natural aos métodos clássicos de perturbação de objetivo, particularmente para configurações modernas de aprendizado de máquina onde suposições fortes de regularidade (como gradientes limitados) raramente são atendidas. Ao deslocar o controle da sensibilidade de limites de gradiente para a curvatura do objetivo via perturbações de matriz aleatória, os autores oferecem um quadro que é teoricamente sólido sob suposições mais fracas e empiricamente superior em estabilidade. O trabalho sugere que perturbações baseadas em curvatura são um mecanismo mais robusto para equilibrar privacidade e utilidade em modelos superparametrizados. Os autores notam que trabalhos futuros poderiam focar em relaxar a suposição de minimizador comum e explorar privacidade diferencial de Rényi para garantias mais apertadas.