Population Risk Bounds for Kolmogorov-Arnold Networks Trained by DP-SGD with Correlated Noise

Resumo Técnico: Limites de Risco Populacional para Redes Kolmogorov–Arnold Treinadas por DP-SGD com Ruído Correlacionado

1. Formulação do Problema

O artigo aborda uma lacuna crítica na compreensão teórica das Redes Kolmogorov–Arnold (KANs), uma alternativa estruturada aos Perceptrons de Múltiplas Camadas (MLPs) que parametriza interações por meio de funções univariadas aprendíveis. Embora as KANs tenham demonstrado forte desempenho empírico em domínios científicos e de engenharia envolvendo dados sensíveis, as garantias teóricas existentes para sua generalização (risco populacional) são limitadas.

Especificamente, trabalhos anteriores [60] estabeleceram limites de risco populacional para KANs apenas sob Descida de Gradiente (GD) em Lote Completo e Privacidade Diferencial (DP) com ruído independente. Isso deixa dois regimes práticos significativos não analisados:

1. Descida de Gradiente Estocástica (SGD) em Mini-lotes com Recorte de Gradiente: A receita de treinamento padrão para redes neurais modernas, que altera fundamentalmente a dinâmica de otimização em comparação com a GD em lote completo.
2. Mecanismos de DP com Ruído Correlacionado: Mecanismos recentes (por exemplo, DP-$\lambda$CGD [28]) introduzem correlações temporais no ruído ($\xi_t = \kappa(Z_t - \lambda Z_{t-1})$) para melhorar o compromisso entre privacidade e utilidade. A teoria DP padrão assume ruído independente, e não existem limites de risco populacional para treinamento com ruído correlacionado em configurações não convexas como as KANs.

O desafio central é que a dependência temporal no ruído rompe a estrutura de "centralização condicional" essencial para a análise padrão de SGD de um passo, enquanto as etapas de projeção usadas para garantir estabilidade na otimização não convexa obstruem a cancelamento parcial de perturbações correlacionadas.

2. Metodologia e Abordagem Técnica

Os autores estabelecem limites de risco populacional decompondo o risco em risco de otimização (convergência para o mínimo empírico) e lacuna de generalização (diferença entre risco empírico e risco populacional).

A. Análise de Otimização (Não Convexa, Ruído Correlacionado)
Para lidar com o ruído correlacionado em um regime não convexo, os autores desenvolvem um novo quadro de prova que contorna as limitações dos argumentos padrão de SGD projetado:

1. Dinâmica Auxiliar Não Projetada: Eles introduzem uma trajetória auxiliar $\{\tilde{W}_t\}$ que evolui sem projeção, mas utiliza os mesmos mini-lotes e ruído. Isso permite que a análise se concentre na estrutura do ruído sem a obstrução do operador de projeção.
2. Iterado Deslocado: Para abordar a falta de centralização condicional no ruído correlacionado (onde $E[\xi_t | \mathcal{F}_{t-1}] \neq 0$), eles definem um iterado deslocado $U_t = \tilde{W}_t + \eta c_{priv} Z_t$. Essa transformação absorve a perturbação gaussiana atual, revelando uma estrutura de cancelamento onde o termo correlacionado principal se reduz a um resíduo proporcional a $(1-\lambda)$.
3. Bootstrap de Alta Probabilidade: Eles empregam uma análise "parada" para certificar que a trajetória auxiliar permanece dentro de uma região localizada onde estimativas de curvatura específicas de KAN (baseadas na margem do Kernel Tangente Neural) se mantêm. Isso envolve provar que a projeção está inativa com alta probabilidade, equiparando assim os iterados projetados $W_t$ aos iterados auxiliares não projetados $\tilde{W}_t$.

B. Análise de Generalização
A lacuna de generalização é limitada usando estabilidade algorítmica. Ao acoplar duas execuções do algoritmo em conjuntos de dados vizinhos (usando a mesma inicialização, mini-lotes e sequência de ruído), os autores mostram que os termos de ruído aditivos se cancelam na diferença dos iterados. O limite de estabilidade depende do risco de otimização derivado no passo anterior.

C. Contabilidade de Privacidade
O artigo fornece uma garantia de privacidade para o mecanismo de ruído correlacionado (DP-$\lambda$CGD) sob subamostragem uniforme sem reposição. Ele deriva um limite superior analítico para o multiplicador de ruído $\kappa$ necessário para satisfazer a DP $(\epsilon, \delta)$, utilizando pares dominantes e divergência de hockey-stick para contabilizar a estrutura de correlação.

3. Contribuições Principais

O artigo faz as seguintes contribuições específicas:

• Primeiros Limites de Risco Populacional para KANs em Regimes Práticos: Estabelece os primeiros limites de risco populacional para KANs de duas camadas treinadas por SGD em mini-lotes com recorte, cobrindo tanto configurações não privadas quanto DP. Isso move a teoria das KANs além do cenário de GD em lote completo de [60].
• Primeira Análise de DP com Ruído Correlacionado Não Convexo: Até onde se sabe, esta é a primeira análise de risco populacional para um mecanismo de ruído correlacionado em um cenário não convexo. Ele instancia isso para KANs treinadas com DP-SGD em mini-lotes com recorte.
• Especializações Precisas: Os resultados recuperam e melhoram os limites existentes:
  • Para SGD em mini-lotes não privado, os limites produzem um risco de otimização e populacional da ordem $O(1/n)$ no regime de largura polilogarítmica, suprimindo fatores logarítmicos e a dependência da margem NTK $\gamma$.
  • Para DP-SGD com ruído independente ($\lambda=0$), os limites correspondem ao limite inferior de DP-SCO convexo de [7] até fatores logarítmicos e melhoram os resultados de DP-GD em lote completo de [60] reduzindo a largura de rede necessária e a dependência da margem NTK.
  • Para DP-SGD com ruído correlacionado, a análise identifica como o parâmetro de correlação $\lambda$ influencia o risco de otimização, embora a taxa final de risco populacional (sob calibração de privacidade conservadora) corresponda assintoticamente à taxa de ruído independente.

4. Resultados Principais

Sob regimes de parâmetros representativos (largura polilogarítmica $m \asymp \text{polylog}(n)$), o artigo deriva as seguintes taxas de risco populacional para os iterados médios:

• SGD em Mini-lotes Não Privado:
  $$\text{Risco} \lesssim \frac{1}{n}$$
  Isso melhora a taxa $O(1/(\gamma^4 n))$ para GD em lote completo em [60], alcançando $O(1/(\gamma^2 n))$ com uma largura necessária menor.

• Privacidade Diferencial (Ruído Independente e Correlacionado):
  Sob DP $(\epsilon, \delta)$, tanto os mecanismos de ruído independente quanto correlacionado atingem a taxa:
  $$\text{Risco} \lesssim \frac{1}{\gamma \sqrt{n}} + \frac{\sqrt{d}}{\gamma^4 n \epsilon}$$
  (até fatores polilogarítmicos).
  A análise mostra que, embora a correlação temporal melhore o termo de erro de otimização (escalando com $1-\lambda$), a calibração de privacidade conservadora de forma fechada necessária para a garantia teórica compensa esse ganho no limite final de risco populacional. Os autores observam que uma contabilidade de privacidade mais precisa pode revelar taxas dependentes de $\lambda$ melhoradas.

5. Significado e Alegações

O artigo afirma fornecer a primeira análise de risco de otimização e populacional de um mecanismo de ruído correlacionado para treinamento DP além da aprendizagem convexa, especificamente para redes neurais (KANs).

• Novidade Teórica: O núcleo técnico — combinando dinâmica auxiliar não projetada, iterados deslocados e bootstrap de alta probabilidade — oferece uma nova rota para analisar o treinamento DP com ruído correlacionado em regimes não convexos, o que pode ser de interesse independente além das KANs.
• Relevância Prática: Ao cobrir SGD em mini-lotes e ruído correlacionado, os resultados preenchem a lacuna entre garantias teóricas e a "receita padrão" usada em sistemas modernos de aprendizado profundo e aprendizado federado.
• Limitações: Os autores modestamente reconhecem que a taxa final de risco populacional para ruído correlacionado corresponde à taxa de ruído independente assintoticamente sob sua calibração de privacidade conservadora atual. Eles identificam uma contabilidade de privacidade mais precisa como uma questão em aberto que poderia potencialmente desbloquear os benefícios teóricos da correlação nos limites finais de risco. Além disso, a análise está atualmente restrita a KANs de duas camadas com coeficientes da segunda camada fixos.