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

Resumen Técnico: Optimización de Intervalos con Restricción de Grado para la Aproximación Polinómica Minimax en Cifrado Homomórfico

Planteamiento del Problema
En el Aprendizaje Automático Preservador de la Privacidad (PPML) basado en Cifrado Homomórfico (HE), la inferencia de redes neuronales debe realizarse sobre datos cifrados utilizando únicamente operaciones aritméticas (suma y multiplicación). En consecuencia, las funciones de activación no polinómicas (p. ej., ReLU, sigmoid, tanh, GELU) deben ser reemplazadas por aproximaciones polinómicas. El enfoque estándar, la aproximación minimax (calculada mediante el algoritmo de Remez), minimiza el error en el peor de los casos sobre un intervalo de diseño específico $[-t, t]$.

Sin embargo, existe un compromiso crítico en la selección del intervalo de diseño $t$ bajo un presupuesto fijo de grado polinómico:

1. Intervalos más amplios: Mejoran la cobertura de entradas de gran magnitud, pero aumentan el error de aproximación minimax dentro del intervalo.
2. Intervalos más estrechos: Reducen el error minimax dentro del intervalo, pero aumentan el riesgo de "extrapolación no controlada" para entradas que caen fuera del intervalo. En HE, donde los valores de texto plano intermedios son inobservables, tales errores de extrapolación pueden amplificarse miles de veces, degradando severamente la precisión de la inferencia.

Aunque se han propuesto Funciones de Extensión de Dominio (DEF) y sus contrapartes polinómicas, los Polinomios de Extensión de Dominio (DEP), para recortar (clip) las entradas fuera del intervalo de diseño y prevenir la extrapolación no controlada, la selección del intervalo de diseño $t$ sigue siendo un hiperparámetro que debe ajustarse. Los métodos existentes suelen depender de intervalos fijos conservadores (p. ej., $[-20\sigma, 20\sigma]$), que pueden no minimizar el error total para una distribución de entrada específica.

Metodología
El artículo formula la selección del intervalo de aproximación $[-t, t]$ como un problema de optimización consciente de la distribución. El objetivo es elegir $t$ para minimizar el Error Cuadrático Medio (MSE) con respecto a la distribución de la entrada pre-activación $X$.

1. Objetivo Idealizado (basado en DEF):
   Los autores definen un objetivo ideal $J_{DEF}(t)$ basado en un mapa de recorte duro (hard-clipping) no polinómico $D_t(x)$. Este objetivo descompone el MSE total en:

   • Término dentro del intervalo: El error del polinomio minimax $p_{n,t}$ en $[-t, t]$.
   • Término fuera del intervalo: El error incurrido cuando las entradas se recortan a los límites $\pm t$.

   Para que sea analíticamente tratable, los autores derivan un objetivo proxy $\hat{J}_{DEF}(t)$:

   • Aproximación dentro del intervalo: Modelan la distribución residual de los polinomios minimax utilizando la ley del arco seno, justificada por la propiedad de equioscilación de las soluciones minimax. Esto permite que el segundo momento condicional del error se aproxime como $E_n(t)^2 / 2$, donde $E_n(t)$ es el error minimax.
   • Aproximación fuera del intervalo: Sustituyen los valores de los puntos finales del polinomio por los valores de los puntos finales de la función objetivo para crear un sustituto de forma cerrada para el error de recorte.

2. Manejo de Tipos de Activación:

   • Funciones Homogéneas (ReLU, LeakyReLU): Para estas, el error minimax escala linealmente con el radio del intervalo ($E_n(t) = t E_n(1)$). Esto permite una derivación analítica exacta del radio normalizado óptimo $\alpha^* = t^*/\sigma$ mediante una condición de primer orden que involucra la PDF y CDF de la distribución normal estándar.
   • Funciones No Homogéneas (Sigmoid, Tanh, GELU): Dado que no existe una ley de escala simple, los autores muestrean numéricamente la curva de error minimax $E_n(t)$ sobre una rejilla de radios y ajustan un sustituto polinómico suave. Este sustituto se utiliza dentro del objetivo proxy para encontrar el $t$ óptimo.

3. Implementación Realizable en HE (basada en DEP):
   Dado que el mapa de recorte duro ideal no es polinómico, el marco conecta el análisis ideal con construcciones de Polinomios de Extensión de Dominio (DEP) realizables en HE.

   • Una composición de etapas de DEP escaladas mapea un rango de entrada conservador $[-R_0, R_0]$ al intervalo de diseño $[-t, t]$.
   • Los autores derivan una descomposición del error de implementación y un límite superior ($U_{impl}$) que cuantifica la brecha entre el objetivo DEF ideal y la realización práctica de DEP. Este límite contabiliza el error de casi-identidad dentro de la región de preservación y el error acotado para entradas en la región extendida.

Contribuciones Clave

• Formulación Basada en Principios: El artículo proporciona la primera formulación basada en principios para la optimación de intervalos de aproximación polinómica con restricción de grado, minimizando explícitamente el MSE sobre la distribución de la pre-activación en lugar de utilizar intervalos fijos y conservadores.
• Proxy Analíticamente Tratable: Los autores derivan un objetivo proxy basado en DEF que captura el compromiso entre el error minimax dentro del intervalo y el error de recorte fuera del intervalo. Este proxy utiliza el modelo de distribución de arco seno para los residuos y la sustitución de valores de puntos finales para los errores de recorte.
• Descomposición de Errores y Límites: El trabajo establece una conexión rigurosa entre el análisis DEF ideal y las construcciones DEP realizables en HE, proporcionando un límite superior sobre la brecha de MSE inducida por el reemplazo de la función de recorte ideal con composiciones polinómicas.
• Validación Numérica: El artículo valida el marco en funciones de activación representativas (ReLU, LeakyReLU, Sigmoid, Tanh, GELU) bajo distribuciones de entrada Gaussiana y de Laplace.

Resultados
Los experimentos numéricos demuestran que la optimización de intervalos propuesta supera significativamente a las líneas base de minimax de intervalo fijo convencional (p. ej., usar $[-20\sigma, 20\sigma]$):

• Reducción de MSE: El enfoque optimizado logra un MSE sustancialmente menor. Las ganancias son particularmente pronunciadas para sigmoid, tanh y GELU, donde el MSE se reduce en varios órdenes de magnitud en comparación con la línea base de intervalo fijo.
• Precisión del Proxy: El minimizador del proxy analítico $\hat{J}_{DEF}(t)$ coincide estrechamente con el minimizador del objetivo ideal $J_{DEF}(t)$ evaluado numéricamente en todas las funciones probadas, validando la utilidad del sustituto para la selección del intervalo.
• Desempeño de DEP: Los evaluadores prácticos basados en DEP logran un MSE menor que la línea base de intervalo fijo. Los experimentos también revelan un compromiso en el diseño de DEP: un factor de extensión mayor ($L=2.5$) reduce el número de etapas requeridas y el error de composición acumulado, produciendo un MSE práctico mejor que un factor menor ($L=1.6$), a pesar de que este último está más cerca del recorte ideal por etapa.

Significado y Reivindicaciones
El artículo sostiene que tratar el intervalo de aproximación como una variable de optimización, en lugar de un hiperparámetro fijo, es esencial para maximizar la precisión de la inferencia basada en HE bajo restricciones de grado. Al equilibrar el error minimax dentro del intervalo frente al error de recorte fuera de este, el marco propuesto permite una inferencia más precisa sin aumentar el grado del polinomio o la profundidad multiplicativa.

Los autores posicionan este trabajo como un paso fundacional para la inferencia de redes neuronales de extremo a extremo basada en HE. Señalan que el trabajo futuro debería investigar la integración de este marco en tuberías (pipelines) de red completas, considerando la interacción de las distribuciones capa por capa y los errores acumulados, así como los costos de implementación en bibliotecas criptográficas específicas. El artículo no pretende resolver todo el problema de PPML, sino que ofrece un método específico y analíticamente fundamentado para optimizar un componente crítico (los intervalos de aproximación polinómica) que impacta directamente en la precisión de la inferencia.