Degree-Constrained Interval Optimization for Minimax Polynomial Approximation in Homomorphic Encryption

Sintesi Tecnica: Ottimizzazione dell'Intervallo con Vincolo di Grado per l'Approssimazione Polinomiale Minimax in Crittografia Omomorfica

Definizione del Problema
Nell'apprendimento automatico preservante la privacy (PPML) basato sulla crittografia omomorfica (HE), l'inferenza delle reti neurali deve essere eseguita su dati cifrati utilizzando esclusivamente operazioni aritmetiche (addizione e moltiplicazione). Di conseguenza, le funzioni di attivazione non polinomiali (es. ReLU, sigmoid, tanh, GELU) devono essere sostituite da approssimazioni polinomiali. L'approccio standard, l'approssimazione minimax (calcolata tramite l'algoritmo di Remez), minimizza l'errore nel caso peggiore su un intervallo di progettazione specifico $[-t, t]$.

Tuttavia, esiste un compromesso critico nella selezione dell'intervallo di progettazione $t$ sotto un budget di grado polinomiale fisso:

1. Intervalli più ampi: Migliorano la copertura per input di grande magnitudo, ma aumentano l'errore di approssimazione minimax all'interno dell'intervallo stesso.
2. Intervalli più stretti: Riducono l'errore minimax all'interno dell'intervallo, ma aumentano il rischio di "estrapolazione incontrollata" per input che cadono al di fuori dell'intervallo. Nell'HE, dove i valori di plaintext intermedi sono inosservabili, tali errori di estrapolazione possono essere amplificati migliaia di volte, degradando gravemente l'accuratezza dell'inferenza.

Sebbene siano state proposte Funzioni di Estensione del Dominio (DEF) e i loro corrispettivi polinomiali, i Polinomi di Estensione del Dominio (DEP), per limitare gli input al di fuori dell'intervallo di progettazione e prevenire l'estrapolazione incontrollata, la scelta dell'intervallo di progettazione $t$ rimane un iperparametro che deve essere sintonizzato. I metodi esistenti spesso si affidano a intervalli fissi conservativi (ad esempio, $[-20\sigma, 20\sigma]$), che possono non minimizzare l'errore complessivo per una specifica distribuzione di input.

Metodologia
Il documento formula la selezione dell'intervallo di approssimazione $[-t, t]$ come un problema di ottimizzazione consapevole della distribuzione. L'obiettivo è scegliere $t$ per minimizzare l'Errore Quadratico Medio (MSE) rispetto alla distribuzione dell'input pre-attivazione $X$.

1. Obiettivo Idealizzato (basato su DEF):
   Gli autori definiscono un obiettivo ideale $J_{DEF}(t)$ basato su una mappa di hard-clipping non polinomiale $D_t(x)$. Questo obiettivo decompone l'MSE totale in:

• Termine entro l'intervallo: L'errore del polinomio minimax su $[-t, t]$.
• Termine fuori dall'intervallo: L'errore derivante dagli input che vengono tagliati (clipped) ai confini $\pm t$.

Per rendere l'analisi analiticamente trattabile, gli autori derivano un obiettivo proxy $\hat{J}_{DEF}(t)$:

• Approssimazione entro l'intervallo: Modellano la distribuzione residua dei polinomi minimax utilizzando la legge dell'arcsine, giustificata dalla proprietà di equioscillazione delle soluzioni minimax. Ciò consente di approssimare il secondo momento condizionato dell'errore come $E_n(t)^2 / 2$, dove $E_n(t)$ è l'errore minimax.
• Approssimazione fuori dall'intervallo: Sostituiscono i valori terminali del polinomio con i valori terminali della funzione target per creare un surrogato a forma chiusa per l'errore di clipping.

2. Gestione dei Tipi di Attivazione:

• Funzioni Omogenee (ReLU, LeakyReLU): Per queste, l'errore minimax scala linearmente con il raggio dell'intervallo ($E_n(t) = t E_n(1)$). Ciò consente una derivazione analitica esatta del raggio normalizzato ottimale $\alpha^* = t^*/\sigma$ tramite una condizione del primo ordine che coinvolge la PDF e la CDF della normale standard.
• Funzioni Non Omogenee (Sigmoid, Tanh, GELU): Poiché non esiste una semplice legge di scala, gli autori campionano numericamente la curva dell'errore minimax $E_n(t)$ su una griglia di raggi e adattano un smooth polynomial surrogate. Tale surrogato viene poi utilizzato all'interno dell'obiettivo proxy per trovare l'ottimale $t$.

3. Implementazione Realizzabile in HE (basata su DEP):
   Poiché la mappa di hard-clipping ideale è non polinomiale, il framework collega l'analisi ideale alle costruzioni realizzabili in HE tramite i Polinomi di Estensione del Dominio (DEP).

• Una composizione di stadi DEP scalati mappa un intervallo di input conservativo $[-R_0, R_0]$ nell'intervallo di progettazione $[-t, t]$.
• Gli autori derivano una decomposizione dell'errore di implementazione e un limite superiore ($U_{impl}$) che quantifica il divario tra l'obiettivo DEF ideale e la realizzazione pratica DEP. Questo limite tiene conto dell'errore quasi-identico nella regione di preservazione e dell'errore limitato per gli input nella regione estesa.

Contributi Chiave

• Formulazione Principata: Il documento fornisce la prima formulazione fondata per l'ottimizzazione dell'intervallo per l'approssimazione polinomiale minimax con grado vincolato, minimizzando esplicitamente l'MSE rispetto alla distribuzione dell'input piuttosto che utilizzare intervalli fissi e conservativi.
• Proxy Analiticamente Trattabile: Gli autori derivano un obiettivo proxy basato su DEF che cattura il compromesso tra l'errore minimax entro l'intervallo e l'errore di clipping fuori dall'intervallo. Questo proxy utilizza il modello della distribuzione dell'arcsine per i residui e la sostituzione dei valori terminali per gli errori di clipping.
• Decomposizione dell'Errore e Limiti: Il lavoro stabilisce una connessione rigorosa tra l'analisi ideale DEF e le costruzioni DEP realizzabili in HE, fornendo un limite superiore sull'MSE indotto dalla sostituzione della funzione di clipping ideale con composizioni polinomiali.
• Validazione Numerica: Il documento valida il framework su funzioni di attivazione rappresentative (ReLU, LeakyReLU, Sigmoid, Tanh, GELU) sotto distribuzioni di input Gaussiana e di Laplace.

Risultati
Gli esperimenti numerici dimostrano che l'ottimizzazione dell'intervallo proposta supera significativamente le convenzionali baseline a intervallo fisso (ad esempio, utilizzando $[-20\sigma, 20\sigma]$):

• Riduzione dell'MSE: L'approccio ottimizzato raggiunge un MSE sostanzialmente inferiore. I guadagni sono particolarmente pronunciati per sigmoid, tanh e GELU, dove l'MSE è ridotto di diversi ordini di grandezza rispetto alla baseline a intervallo fisso.
• Accuratezza del Proxy: Il minimizzatore dell'obiettivo proxy analitico $\hat{J}_{DEF}(t)$ corrisponde strettamente al minimizzatore dell'obiettivo ideale numerico $J_{DEF}(t)$ in tutte le funzioni testate, validando l'utilità del surrogato per la selezione dell'intervallo.
• Prestazioni dei DEP: Gli evaluator pratici basati su DEP ottengono un MSE inferiore rispetto alla baseline a intervallo fisso. Gli esperimenti rivelano anche un compromesso nella progettazione dei DEP: un fattore di estensione maggiore ($L=2.5$) riduce il numero di stadi richiesti e l'errore di composizione accumulato, fornendo un MSE pratico migliore rispetto a un fattore più piccolo ($L=1.6$), nonostante quest'ultimo sia più vicino al clipping ideale per singolo stadio.

Significatività e Rivendicazioni
Il documento sostiene che trattare l'intervallo di approssimazione come una variabile di ottimizzazione, piuttosto che come un iperparametro fisso, è essenziale per massimizzare l'accuratezza dell'inferenza basata su HE sotto vincoli di grado. Bilanciando l'errore minimax entro l'intervallo con l'errore di clipping fuori da esso, il framework proposto consente un'inferenza più accurata senza aumentare il grado del polinomio o la profondità moltiplicativa.

Gli autori pongono questo lavoro come un passo fondamentale per l'inferenza di reti neurali end-to-end basata su HE. Notano che il lavoro futuro dovrà investigare l'integrazione di questo framework in pipeline complete di rete, considerando l'interazione tra le distribuzioni per livello e gli errori cumulativi, nonché i costi di implementazione specifici delle librerie crittografiche. Il documento non pretende di risolvere l'intero problema della PPML, ma offre un metodo specifico e analiticamente fondato per ottimizzare una componente critica (gli intervalli di approssimazione polinomiale) che impatta direttamente l'accuratezza dell'inferenza.