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

Riepilogo Tecnico: Limiti del Rischio di Popolazione per le Reti di Kolmogorov–Arnold Addestrate con DP-SGD e Rumore Correlato

1. Enunciato del Problema

Il lavoro affronta una lacuna critica nella comprensione teorica delle Reti di Kolmogorov–Arnold (KAN), un'alternativa strutturata ai Perceptron a Strati Multipli (MLP) che parametrizza le interazioni tramite funzioni univariate apprendibili. Sebbene le KAN abbiano dimostrato prestazioni empiriche solide in domini scientifici e ingegneristici che coinvolgono dati sensibili, le garanzie teoriche esistenti per la loro generalizzazione (rischio di popolazione) sono limitate.

Nello specifico, lavori precedenti [60] hanno stabilito limiti del rischio di popolazione per le KAN solo sotto Gradient Descent (GD) in full-batch e Differential Privacy (DP) con rumore indipendente. Ciò lascia due regimi pratici significativi non analizzati:

1. Stochastic Gradient Descent (SGD) in mini-batch con Gradient Clipping: La ricetta di addestramento standard per le reti neurali moderne, che altera fondamentalmente le dinamiche di ottimizzazione rispetto al GD in full-batch.
2. Meccanismi DP a Rumore Correlato: Meccanismi recenti (ad es. DP-$\lambda$CGD [28]) introducono correlazioni temporali nel rumore ($\xi_t = \kappa(Z_t - \lambda Z_{t-1})$) per migliorare il compromesso privacy-utilità. La teoria DP standard assume rumore indipendente e non esistono limiti del rischio di popolazione per l'addestramento con rumore correlato in contesti non convessi come le KAN.

La sfida centrale è che la dipendenza temporale nel rumore rompe la struttura di "centratura condizionale" essenziale per l'analisi standard dell'SGD a un passo, mentre le fasi di proiezione utilizzate per garantire la stabilità nell'ottimizzazione non convessa ostacolano la cancellazione parziale delle perturbazioni correlate.

2. Metodologia e Approccio Tecnico

Gli autori stabiliscono limiti del rischio di popolazione decomponendo il rischio in rischio di ottimizzazione (convergenza verso il minimo empirico) e gap di generalizzazione (differenza tra rischio empirico e rischio di popolazione).

A. Analisi dell'Ottimizzazione (Non Convessa, Rumore Correlato)
Per gestire il rumore correlato in un regime non convesso, gli autori sviluppano un nuovo quadro dimostrativo che supera i limiti degli argomenti standard dell'SGD proiettato:

1. Dinamiche Ausiliarie Non Proiettate: Introducono una traiettoria ausiliaria $\{\tilde{W}_t\}$ che evolve senza proiezione ma utilizza gli stessi mini-batch e lo stesso rumore. Ciò permette di focalizzare l'analisi sulla struttura del rumore senza l'ostacolo dell'operatore di proiezione.
2. Iterata Spostata: Per affrontare la mancanza di centratura condizionale nel rumore correlato (dove $E[\xi_t | \mathcal{F}_{t-1}] \neq 0$), definiscono un'iterata spostata $U_t = \tilde{W}_t + \eta c_{priv} Z_t$. Questa trasformazione assorbe la perturbazione gaussiana corrente, rivelando una struttura di cancellazione in cui il termine correlato principale si riduce a un residuo proporzionale a $(1-\lambda)$.
3. Bootstrap ad Alta Probabilità: Impiegano un'analisi "fermata" per certificare che la traiettoria ausiliaria rimanga all'interno di una regione localizzata dove valgono stime di curvatura specifiche per le KAN (basate sul margine del Neural Tangent Kernel). Ciò comporta dimostrare che la proiezione è inattiva con alta probabilità, equiparando così le iterazioni proiettate $W_t$ alle iterazioni ausiliarie non proiettate $\tilde{W}_t$.

B. Analisi della Generalizzazione
Il gap di generalizzazione è limitato utilizzando la stabilità algoritmica. Accoppiando due esecuzioni dell'algoritmo su dataset adiacenti (utilizzando la stessa inizializzazione, gli stessi mini-batch e la stessa sequenza di rumore), gli autori mostrano che i termini di rumore additivi si cancellano nella differenza delle iterazioni. Il limite di stabilità dipende dal rischio di ottimizzazione derivato nel passaggio precedente.

C. Contabilità della Privacy
Il lavoro fornisce una garanzia di privacy per il meccanismo a rumore correlato (DP-$\lambda$CGD) sotto campionamento uniforme senza sostituzione. Deriva un limite superiore analitico sul moltiplicatore del rumore $\kappa$ necessario per soddisfare la $(\epsilon, \delta)$-DP, utilizzando coppie dominanti e la divergenza a "hockey-stick" per tenere conto della struttura di correlazione.

3. Contributi Chiave

Il lavoro apporta i seguenti contributi specifici:

• Primi Limiti del Rischio di Popolazione per le KAN in Regimi Pratici: Stabilisce i primi limiti del rischio di popolazione per KAN a due strati addestrate con SGD in mini-batch con clipping, coprendo sia contesti non privati che DP. Ciò sposta la teoria delle KAN oltre il contesto GD in full-batch di [60].
• Prima Analisi DP a Rumore Correlato Non Convessa: Per quanto noto agli autori, questa è la prima analisi del rischio di popolazione per un meccanismo a rumore correlato in un contesto non convesso. La applica alle KAN addestrate con DP-SGD in mini-batch con clipping.
• Specializzazioni Precise: I risultati recuperano e migliorano i limiti esistenti:
  • Per SGD in mini-batch non privato, i limiti producono un rischio di ottimizzazione e di popolazione dell'ordine $O(1/n)$ nel regime di larghezza polilogaritmica, sopprimendo i fattori logaritmici e la dipendenza dal margine NTK $\gamma$.
  • Per DP-SGD a rumore indipendente ($\lambda=0$), i limiti corrispondono al limite inferiore DP-SCO convesso di [7] fino a fattori logaritmici e migliorano i risultati DP-GD in full-batch di [60] riducendo la larghezza di rete richiesta e la dipendenza dal margine NTK.
  • Per DP-SGD a rumore correlato, l'analisi identifica come il parametro di correlazione $\lambda$ influenzi il rischio di ottimizzazione, sebbene il tasso finale del rischio di popolazione (sotto una calibrazione della privacy conservativa) corrisponda asintoticamente al tasso a rumore indipendente.

4. Risultati Principali

Sotto regimi di parametri rappresentativi (larghezza polilogaritmica $m \asymp \text{polylog}(n)$), il lavoro deriva i seguenti tassi di rischio di popolazione per le iterazioni mediate:

• SGD in Mini-batch Non Privato:
  $$\text{Rischio} \lesssim \frac{1}{n}$$
  Ciò migliora il tasso $O(1/(\gamma^4 n))$ per GD in full-batch in [60] raggiungendo $O(1/(\gamma^2 n))$ con una larghezza richiesta inferiore.

• Differentially Private (Rumore Indipendente e Correlato):
  Sotto $(\epsilon, \delta)$-DP, sia i meccanismi a rumore indipendente che quelli correlati raggiungono il tasso:
  $$\text{Rischio} \lesssim \frac{1}{\gamma \sqrt{n}} + \frac{\sqrt{d}}{\gamma^4 n \epsilon}$$
  (fino a fattori polilogaritmici).
  L'analisi mostra che, sebbene la correlazione temporale migliori il termine di errore di ottimizzazione (scalando con $1-\lambda$), la calibrazione della privacy in forma chiusa conservativa richiesta per la garanzia teorica compensa questo guadagno nel limite finale del rischio di popolazione. Gli autori notano che una contabilità della privacy più precisa potrebbe rivelare tassi dipendenti da $\lambda$ migliorati.

5. Significato e Affermazioni

Il lavoro afferma di fornire la prima analisi del rischio di ottimizzazione e di popolazione di un meccanismo a rumore correlato per l'addestramento DP oltre l'apprendimento convesso, specificamente per le reti neurali (KAN).

• Novità Teorica: Il nucleo tecnico — che combina dinamiche ausiliarie non proiettate, iterate spostate e bootstrap ad alta probabilità — offre una nuova via per analizzare l'addestramento DP a rumore correlato in regimi non convessi, il quale potrebbe essere di interesse indipendente oltre le KAN.
• Rilevanza Pratica: Coprendo l'SGD in mini-batch e il rumore correlato, i risultati colmano il divario tra garanzie teoriche e la "ricetta standard" utilizzata nei moderni sistemi di deep learning e federated learning.
• Limitazioni: Gli autori riconoscono modestamente che il tasso finale del rischio di popolazione per il rumore correlato corrisponde asintoticamente al tasso a rumore indipendente sotto la loro attuale calibrazione della privacy conservativa. Identificano una contabilità della privacy più precisa come una questione aperta che potrebbe potenzialmente sbloccare i benefici teorici della correlazione nei limiti finali del rischio. Inoltre, l'analisi è attualmente limitata a KAN a due strati con coefficienti del secondo strato fissi.