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

Resumo Técnico: Otimização de Intervalo com Restrição de Grau para Aproximação Polinomial Minimax em Criptografia Homomórfica

Enunciado do Problema
Na Aprendizagem de Máquina Preservadora de Privacidade (PPML) baseada em Criptografia Homomórfica (HE), a inferência de redes neurais deve ser realizada sobre dados criptografados utilizando apenas operações aritméticas (adição e multiplicação). Consequentemente, funções de ativação não polinomiais (ex: ReLU, sigmoid, tanh, GELU) devem ser substituadas por aproximações polinomiais. A abordagem padrão, a aproximação minimax (calculada via algoritmo de Remez), minimiza o erro de pior caso sobre um intervalo de design específico $[-t, t]$.

No entanto, existe um compromisso crítico na seleção do intervalo de design $t$ sob um orçamento fixo de grau polinomial:

1. Intervalos Mais Largos: Melhoram a cobertura de entradas de grande magnitude, mas aumentam o erro de aproximação minimax dentro do intervalo.
2. Intervalos Mais Estreitos: Reduzem o erro minimax dentro do intervalo, mas aumentam o risco de "extrapolação descontrolada" para entradas que caem fora do intervalo. Em HE, onde os valores de texto simples intermediários são inobserváveis, tais erros de extrapolação podem ser amplificados milhares de vezes, degradando severamente a precisão da inferência.

Embora Funções de Extensão de Domínio (DEFs) e seus equivalentes polinomiais, Polinômios de Extensão de Domínio (DEPs), tenham sido propostos para limitar as entradas fora do intervalo de design e prevenir a extrapolação descontrolada, o próprio $t$ do intervalo de design permanece um hiperparâmetro que deve ser ajustado. Métodos existentes frequentemente dependem de intervalos fixos conservadores (ex: $[-20\sigma, 20\sigma]$), que podem não minimizar o erro total para uma distribuição de entrada específica.

Metodologia
O artigo formula a seleção do intervalo de aproximação $[-t, t]$ como um problema de otimização consciente da distribuição. O objetivo é escolher $t$ para minimizar o Erro Quadrático Médio (MSE) em relação à distribuição de entrada pré-ativação $X$.

1. Objetivo Idealizado (baseado em DEF):
   Os autores definem um objetivo ideal $J_{DEF}(t)$ baseado em um mapa de corte rígido (hard-clipping) não polinomial $D_t(x)$. Este objetivo decompõe o MSE total em:
   • Termo dentro do intervalo: O erro do polinômio minimax $p_{n,t}$ em $[-t, t]$.
   • Termo fora do intervalo: O erro incorrido quando as entradas são limitadas aos limites $\pm t$.

Para tornar isso analiticamente tratável, os autores derivam um objetivo substituto (proxy) $\hat{J}_{DEF}(t)$:

• Aproximação dentro do intervalo: Eles modelam a distribuição residual dos polinômios minimax usando a lei do arco seno, justificada pela propriedade de equioscilação das soluções minimax. Isso permite que o segundo momento condicional do erro seja aproximado como $E_n(t)^2 / 2$, onde $E_n(t)$ é o erro minimax.
• Aproximação fora do intervalo: Eles substituem os valores de extremidade do polinômio pelos valores de extremidade da função alvo para criar um substituto de forma fechada para o erro de corte.

2. Tratamento de Tipos de Ativação:

   • Funções Homogêneas (ReLU, LeakyReLU): Para estas, o erro minimax escala linearmente com o raio do intervalo ($E_n(t) = t E_n(1)$). Isso permite uma derivação analítica exata do raio normalizado ótimo $\alpha^* = t^*/\sigma$ via uma condição de primeira ordem envolvendo a PDF e a CDF da normal padrão.
   • Funções Não Homogêneas (Sigmoid, Tanh, GELU): Como não existe uma lei de escala simples, os autores amostram numericamente a curva de erro minimax $E_n(t)$ sobre uma grade de raios e ajustam um substituto polinomial suave. Esse substituto é então usado dentro do objetivo proxy para encontrar o $t$ ótimo.

3. Implementação Realizável em HE (baseada em DEP):
   Como o mapa de corte rígido ideal é não polinomial, o framework conecta a análise ideal a construções realizáveis em HE usando Polinômios de Extensão de Domínio (DEPs).

   • Uma composição de estágios de DEP escalonados mapeia um intervalo de entrada conservador $[-R_0, R_0]$ para o intervalo de design $[-t, t]$.
   • Os autores derivam uma decomposição de erro de implementação e um limite superior ($U_{impl}$) que quantifica a lacuna entre o objetivo DEF ideal e a construção prática de DEP. Este limite contabiliza o erro de quase-identidade dentro da região de preservação e o erro limitado para entradas na região estendida.

Contribuições Principais

• Formulação Principiada: O artigo fornece a primeira formulação principiada para a otimização de intervalo para aproximação polinomial minimax com grau restrito, minimizando explicitamente o MSE sobre a distribuição de pré-ativação em vez de usar intervalos fixos e conservadores.
• Proxy Analiticamente Tratável: Os autores derivam um objetivo proxy baseado em DEF que captura o compromisso entre o erro minimax dentro do intervalo e o erro de corte fora do intervalo. Este proxy utiliza o modelo de distribuição do arco seno para os resíduos e a substituição de valores de extremidade para os erros de corte.
• Decomposição de Erro e Limites: O trabalho estabelece uma conexão rigorosa entre a análise ideal de DEF e as construções de DEP realizáveis em HE, fornecendo um limite superior na lacuna de MSE induzida pela substituição da função de corte ideal pelo polinômio composto.
• Validação Numérica: O artigo valida o framework em funções de ativação representativas (ReLU, LeakyReLU, Sigmoid, Tanh, GELU) sob distribuições de entrada Gaussiana e de Laplace.

Resultados
Experimentos numéricos demonstram que a otimização de intervalo proposta supera significativamente as linhas de base convencionais de intervalo fixo (ex: usar $[-20\sigma, 20\sigma]$):

• Redução de MSE: A abordagem otimizada alcança um MSE substancialmente menor. Os ganhos são particularmente pronunciados para sigmoid, tanh e GELU, onde o MSE é reduzido em várias ordens de magnitude em comparação com a linha de base de intervalo fixo.
• Precisão do Proxy: O minimizador do proxy analítico $\hat{J}_{DEF}(t)$ coincide de perto com o minimizador do objetivo ideal numericamente avaliado $J_{DEF}(t)$ em todas as funções testadas, validando a utilidade do substituto para a seleção de intervalo.
• Desempenho do DEP: Avaliadores práticos baseados em DEP alcançam um MSE menor do que a linha de base de intervalo fixo. Os experimentos também revelam um compromisso no design do DEP: um fator de extensão maior ($L=2.5$) reduz o número de estágios necessários e o erro de composição acumulado, resultando em um MSE prático melhor do que um fator menor ($L=1.6$), apesar deste último estar mais próximo do corte ideal por estágio.

Significância e Alegações
O artigo afirma que tratar o intervalo de aproximação como uma variável de otimização, em vez de um hiperparâmetro fixo, é essencial para maximizar a precisão da inferência baseada em HE sob restrição de grau. Ao equilibrar o erro minimax dentro do intervalo com o erro de corte fora dele, o framework proposto permite uma inferência mais precisa sem aumentar o grau do polinômio ou a profundidade multiplicativa.

Os autores posicionam este trabalho como um passo fundamental para a inferência de redes neurais de ponta a ponta baseada em HE. Eles observam que trabalhos futuros devem investigar a integração deste framework em pipelines completos de redes, considerando a interação de distribuições camada a camada e erros cumulativos, bem como os custos de implementação em bibliotecas criptográficas específicas. O artigo não pretende resolver todo o problema de PPML, mas oferece um método específico e analiticamente fundamentado para otimizar um componente crítico (intervalos de aproximação polinomial) que impacta diretamente a precisão da inferência.