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

Résumé Technique : Optimisation d'Intervalle sous Contrainte de Degré pour l'Approximation Polynomiale Minimax en Chiffrement Homomorphe

Énoncé du Problème
Dans l'apprentissage automatique préservant la confidentialité (PPML) basé sur le chiffrement homomorphe (HE), l'inférence de réseaux de neurones doit être effectuée sur des données chiffrées en utilisant uniquement des opérations arithmétiques (addition et multiplication). Par conséquent, les fonctions d'activation non polynomiales (ex. : ReLU, sigmoid, tanh, GELU) doivent être remplacées par des approximations polynomiales. L'approche standard, l'approximation minimax (calculée via l'algorithme de Remez), minimise l'erreur dans le pire des cas sur un intervalle de conception spécifique $[-t, t]$.

Cependant, un arbitrage critique existe dans la sélection de l'intervalle de conception $t$ sous un budget de degré polynomial fixe :

1. Intervalles plus larges : Améliorent la couverture des entrées de grande magnitude mais augmentent l'erreur d'approximation minimax à l'intérieur de l'intervalle.
2. Intervalles plus étroits : Réduisent l'erreur minimax à l'intérieur de l'intervalle mais augmentent le risque d'« extrapolation incontrôlée » pour les entrées tombant en dehors de l'intervalle. En HE, où les valeurs de texte clair intermédiaires sont inobservables, ces erreurs d'extrapolation peuvent être amplifiées des milliers de fois, dégradant gravement la précision de l'inférence.

Bien que des fonctions d'extension de domaine (DEF) et leurs équivalents polynomiaux, les polynômes d'extension de domaine (DEP), aient été proposés pour limiter les entrées en dehors de l'intervalle de conception et prévenir l'extrapolation incontrôlée, la sélection de l'intervalle de conception $t$ lui-même reste un hyperparamètre qui doit être ajusté. Les méthodes existantes reposent souvent sur des intervalles fixes conservateurs (ex. : $[-20\sigma, 20\sigma]$), qui peuvent ne pas minimiser l'erreur globale pour une distribution d'entrée spécifique.

Méthodologie
Le papier formule la sélection de l'intervalle d'approximation $[-t, t]$ comme un problème d'optimisation sensible à la distribution. L'objectif est de choisir $t$ pour minimiser l'erreur quadratique moyenne (MSE) par rapport à la distribution d'entrée pré-activation $X$.

1. Objectif Idéalisé (basé sur la DEF) :
   Les auteurs définissent un objectif idéal $J_{DEF}(t)$ basé sur une application de clipsage dur non polynomial $D_t(x)$. Cet objectif décompose la MSE totale en :

• Terme intra-intervalle : L'erreur du polynôme minimax $p_{n,t}$ sur $[-t, t]$.
• Terme extra-intervalle : L'erreur induite lorsque les entrées sont clipsées aux limites $\pm t$.

Pour rendre cela analytiquement traitable, les auteurs dérivent un objectif proxy $\hat{J}_{DEF}(t)$ :

• Approximation intra-intervalle : Ils modélisent la distribution résiduelle des polynômes minimax en utilisant la loi de l'arcsinus, justifiée par la propriété d'équioscillation des solutions minimax. Cela permet d'approximer le second moment conditionnel de l'erreur comme étant $E_n(t)^2 / 2$, où $E_n(t)$ est l'erreur minimax.
• Approximation extra-intervalle : Ils substituent les valeurs de l'extrémité du polynôme par les valeurs de l'extrémité de la fonction cible pour créer un substitut fermé pour l'erreur de clipsage.

2. Gestion des types d'activation :

• Fonctions homogènes (ReLU, LeakyReLU) : Pour celles-ci, l'erreur minimax évolue linéairement avec le rayon de l'intervalle ($E_n(t) = t E_n(1)$). Cela permet une dérivation analytique exacte du rayon normalisé optimal $\alpha^* = t^*/\sigma$ via une condition du premier ordre impliquant la densité de probabilité (PDF) et la fonction de répartition (CDF) de la loi normale standard.
• Fonctions non homogènes (Sigmoid, Tanh, GELU) : Comme aucune loi d'échelle simple n'existe, les auteurs échantillonnent numériquement la courbe d'erreur minimax $E_n(t)$ sur une grille et ajustent un substitut polynomial lisse. Ce substitut est ensuite utilisé dans l'objectif proxy pour trouver le $t$ optimal.

3. Implémentation réalisable en HE (basée sur la DEP) :
   Puisque l'application de clipsage dur idéale est non polynomiale, le cadre relie l'analyse idéale aux constructions réalisables en HE utilisant des polynômes d'extension de domaine (DEP).

• Une composition de stades de DEP mis à l'échelle mappe une plage d'entrée conservatrice $[-R_0, R_0]$ dans l'intervalle de conception $[-t, t]$.
• Les auteurs dérivent une décomposition de l'erreur d'implémentation et une borne supérieure ($U_{impl}$) qui quantifie l'écart entre l'objectif DEF idéal et la réalisation pratique par DEP. Cette borne prend en compte l'erreur quasi-identité dans la région de préservation et l'erreur bornée pour les entrées dans la région étendue.

Contributions Clés

• Formulation Principiée : Le papier fournit la première formulation principiée de l'optimisation d'intervalle pour l'approximation polynomiale minimax sous contrainte de degré, minimisant explicitement la MSE par rapport à la distribution de pré-activation plutôt que d'utiliser des intervalles fixes et conservateurs.
• Proxy Analytiquement Traitable : Les auteurs dérivent un objectif proxy basé sur la DEF qui capture l'arbitrage entre l'erreur minimax intra-intervalle et l'erreur de clipsage extra-intervalle. Ce proxy utilise le modèle de distribution de l'arcsinus pour les résidus et la substitution des valeurs d'extrémité pour les erreurs de clipsage.
• Décomposition d'Erreur et Bornes : Le travail établit un lien rigoureux entre l'analyse idéale de la DEF et les constructions DEP réalisables en HE, fournissant une borne supérieure sur l'écart de MSE induit par le remplacement de la fonction de clipsage idéale par des compositions polynomiales.
• Validation Numérique : Le papier valide le cadre sur des fonctions d'activation représentatives (ReLU, LeakyReLU, Sigmoid, Tanh, GELU) sous des distributions d'entrée Gaussienne et de Laplace.

Résultats
Les expériences numériques démontrent que l'optimisation d'intervalle proposée surpasse significativement les bases de référence minimax à intervalle fixe conventionnelles (ex. : utiliser $[-20\sigma, 20\sigma]$) :

• Réduction de la MSE : L'approche optimisée atteint une MSE substantiellement plus faible. Les gains sont particulièrement prononcés pour sigmoid, tanh et GELU, où la MSE est réduite de plusieurs ordres de grandeur par rapport à la base de référence à intervalle fixe.
• Précision du Proxy : Le minimiseur de l'objectif proxy analytique $\hat{J}_{DEF}(t)$ correspond étroitement au minimiseur de l'objectif idéal numériquement évalué $J_{DEF}(t)$ pour toutes les fonctions testées, validant l'utilité du substitut pour la sélection d'intervalle.
• Performance de la DEP : Les évaluateurs basés sur la DEP pratique atteignent une MSE plus faible que la base de référence à intervalle fixe. Les expériences révèlent également un arbitrage dans la conception de la DEP : un facteur d'extension plus grand ($L=2.5$) réduit le nombre de stades requis et l'erreur de composition accumulée, offrant une MSE pratique meilleure que le facteur plus petit ($L=1.6$), malgré ce dernier étant plus proche du clipsage idéal par stade.

Signification et Revendications
Le papier affirme que traiter l'intervalle d'approximation comme une variable d'optimisation, plutôt que comme un hyperparamètre fixe, est essentiel pour maximiser la précision de l'inférence basée sur le HE sous des contraintes de degré. En équilibrant l'erreur minimax à l'intérieur de l'intervalle et l'erreur de clipsage à l'extérieur, le cadre proposé permet une inférence plus précise sans augmenter le degré polynomial ou la profondeur multiplicative.

Les auteurs positionnent ce travail comme une étape fondamentale pour l'inférence de réseaux de neurones de bout en bout basée sur le HE. Ils notent que les travaux futurs devront étudier l'intégration de ce cadre dans des pipelines de réseaux complets, en considérant l'interaction entre les distributions par couche et les erreurs cumulées, ainsi que les coûts d'implémentation spécifiques aux bibliothèques cryptographiques. Le papier ne prétend pas résoudre l'ensemble du problème du PPML, mais propose une méthode spécifique et analytiquement fondée pour optimiser un composant critique (les intervalles d'approximation polynomiale) qui impacte directement la précision de l'inférence.