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

Technische Samenvatting: Graadbeperkte Intervaloptimalisatie voor Minimax-polynomiale Approximatie in Homomorfe Encryptie

Probleemstelling
In op Homomorfe Encryptie (HE) gebaseerde Privacy-Preserving Machine Learning (PPML) moet de inferentie van neurale netwerken worden uitgevoerd op versleutelde gegevens met behulp van uitsluitend rekenkundige operaties (optelling en vermenigvuldiging). Bijgevolg moeten niet-polynomiale activatiefuncties (bijv. ReLU, sigmoid, tanh, GELU) worden vervangen door polynomiale approximaties. De standaardaanpak is de minimax-approximatie (berekend via het Remez-algoritme), die de fout in het slechtste geval minimaliseert over een specifiek ontwerpinterval $[-t, t]$.

Er bestaat echter een cruciale afruil bij het selecteren van het ontwerpinterval $t$ onder een vastgesteld budget voor de polynoomgraad:

1. Brede intervallen: Verbeteren de dekking van inputs met grote magnitudes, maar verhogen de minimax-approximatiefout binnen het interval.
2. Smallere intervallen: Verminderen de minimax-fout binnen het interval, maar vergroten het risico op "ongecontroleerde extrapolatie" voor inputs die buiten het interval vallen. In HE kunnen dergelijke extrapolatiefouten, waarbij de plaintext-waarden onwaarneembaar zijn, duizenden keren worden versterkt, wat de nauwkeurigheid van de inferentie ernstig verslechtert.

Hoewel Domain Extension Functions (DEFs) en hun polynomiale tegenhangers, Domain Extension Polynomials (DEPs), zijn voorgesteld om inputs buiten het ontwerpinterval af te kappen en ongecontroleerde extrapolatie te voorkomen, blijft het optimale ontwerpinterval $t$ zelf een hyperparameter die moet worden afgestemd. Bestaande methoden vertrouwen vaak op conservatieve, vaste intervallen (bijv. $[-20\sigma, 20\sigma]$), die mogelijk niet de minimax-fout voor een specifieke inputverdeling minimaliseren.

Methodologie
Het artikel formuleert de selectie van het approximatie-interval $[-t, t]$ als een distributie-bewust optimalisatieprobleem. Het doel is om $t$ te kiezen om de gemiddelde kwadratische fout (MSE) te minimaliseren met betrekking tot de pre-activatie inputverdeling $X$.

1. Geïdealiseerd Doel (DEF-gebaseerd):
   De auteurs definiëren een ideaal doel $J_{DEF}(t)$ op basis van een niet-polynomiale hard-clipping kaart $D_t(x)$. Dit doel deelt de totale MSE op in:

   • Binnen-interval term: De fout van de minimax-polynoom $p_{n,t}$ op $[-t, t]$.
   • Buiten-interval term: De fout die optreedt wanneer inputs worden afgekapt naar de grenzen $\pm t$.

   Om dit analytisch hanteerbaar te maken, leiden de auteurs een proxy-doel $\hat{J}_{DEF}(t)$ af:

   • Binnen-interval approximatie: Ze modelleren de residuele verdeling van minimax-polynomen met behulp van de arcsinuswet, gerechtvaardigd door de equioscillatie-eigenschap van minimax-oplossingen. Dit maakt het mogelijk om het voorwaardelijke tweede moment van de fout te benaderen als $E_n(t)^2 / 2$, waarbij $E_n(t)$ de minimax-fout is.
   • Buiten-interval approximatie: Ze vervangen de eindwaarden van de polynoom door de eindwaarden van de doelunctie om een gesloten vorm surrogate te creëren voor de clipping-fout.

2. Afhandeling van Activatietypes:

   • Homogene Functies (ReLU, LeakyReLU): Voor deze functies schaalt de minimax-fout lineair met de intervalstraal ($E_n(t) = t E_n(1)$). Dit maakt een exacte analytische afleiding van de optimale genormaliseerde straal $\alpha^* = t^*/\sigma$ mogelijk via een eerste-orde conditie met de standaard normale PDF en CDF.
   • Niet-homogene Functies (Sigmoid, Tanh, GELU): Omdat er geen eenvoudige schaalwet bestaat, samplen de auteurs numeriek de minimax-foutcurve $E_n(t)$ over een rooster en passen ze een gladde polynomiale surrogate aan. Deze surrogate wordt vervolgens gebruikt binnen het proxy-doel om de optimale $t$ te vinden.

3. HE-Realiseerbare Implementatie (DEP-gebaseerd):
   Omdat de ideale hard-clipping kaart niet-polynomiaal is, verbindt het framework het ideale onderzoek met HE-realiseerbare constructies met behulp van Domain Extension Polynomials (DEPs).

   • Een compositie van geschaalde DEP-stadia brengt een conservatief inputbereik $[-R_0, R_0]$ in het ontwerpinterval $[-t, t]$.
   • De auteurs leiden een implementatie-foutdecompositie af en een bovengrens ($U_{impl}$) die de kloof kwantificeert tussen het ideale DEF-doel en de praktische DEP-realisatie. Deze bovengrens houdt rekening met de bijna-identiteit-fout binnen de preservatie-regio en de begrensde fout voor inputs in de uitgebreide regio.

Belangrijkste Bijdragen

• Geprincipeerde Formulering: Het artikel biedt de eerste geprincipeerde formulering van intervaloptimalisatie voor graadbeperkte minimax-polynomiale approximatie, waarbij expliciet de MSE wordt geminimaliseerd over de pre-activatieverdeling in plaats van het gebruik van vaste, conservatieve intervallen.
• Analytisch Hanteerbare Proxy: De auteurs leiden een DEF-gebaseerde proxy-doel af die de afruil tussen de binnen-interval minimax-fout en de buiten-interval clipping-fout vangt. Deze proxy maakt gebruik van de arcsinus-verdeling voor residuen en eindwaarde-substitutie voor clipping-fouten.
• Foutdecompositie en Grenzen: Het werk vestigt een rigoureuze verbinding tussen de ideale DEF-analyse en HE-realiseerbare DEP-constructies, waarbij een bovengrens wordt geboden op de MSE-kloof veroorzaakt door het vervangen van de ideale clipping-functie door polynomiale composities.
• Numerieke Validatie: Het artikel valideert het framework op representatieve activatiefuncties (ReLU, LeakyReLU, Sigmoid, Tanh, GELU) onder Gaussische en Laplace inputverdelingen.

Resultaten
Numerieke experimenten tonen aan dat de voorgestelde intervaloptimalisatie aanzienlijk beter presteert dan conventionele fixed-interval minimax-baselines (bijv. het gebruik van $[-20\sigma, 20\sigma]$):

• MSE-Reductie: De geoptimaliseerde aanpak bereikt een substantieel lagere MSE. De winst is bijzonder uitgesproken voor sigmoid, tanh en GELU, waarbij de MSE met meerdere grootheden wordt verminderd vergeleken met de fixed-interval baseline.
• Proxy-Nauwkeurigheid: De minimizer van de analytische proxy $\hat{J}_{DEF}(t)$ komt nauw overeen met de minimizer van het numeriek geëvalueerde ideale doel $J_{DEF}(t)$ voor alle geteste functies, wat het nut van de surrogate voor intervalselectie valideert.
• DEP-Prestaties: Praktische DEP-gebaseerde evaluatoren bereiken een lagere MSE dan de fixed-interval baseline. De experimenten onthullen ook een afruil in DEP-ontwerp: een grotere extensiefactor ($L=2.5$) vermindert het aantal vereiste stadia en de geaccumuleerde compositiefout, wat een betere praktische MSE oplevert dan een kleinere factor ($L=1.6$), ondanks het feit dat deze laatste dichter bij de ideale clipping per stadium ligt.

Betekenis en Claims
Het artikel beweert dat het behandelen van het approximatie-interval als een optimalisatievariabele, in plaats van een vaste hyperparameter, essentieel is voor het maximaliseren van de nauwkeurigheid van HE-gebaseerde inferentie onder graadbeperkingen. Door de minimax-fout binnen het interval af te wegen tegen de clipping-fout buiten het interval, stelt het voorgestelde framework in staat tot nauwkeurigere inferentie zonder de polynomiale graad of de multiplicatieve diepte te verhogen.

De auteurs positioneren dit werk als een fundamentele stap voor end-to-end HE-gebaseerde neurale netwerkinferentie. Ze merken op dat toekomstig werk de integratie van dit framework in volledige netwerkpipelines moet onderzoeken, waarbij rekening wordt gehouden met de interactie tussen laag-specifieke verdelingen en cumulatieve fouten, evenals specifieke kosten voor implementatie in cryptografische bibliotheken. Het artikel claimt niet het gehele PPML-probleem op te lossen, maar biedt een specifieke, analytisch onderbouwde methode om een kritiek onderdeel (polynomiale approximatie-intervallen) te optimaliseren dat de inferentie-nauwkeurigheid direct beïnvloedt.