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

技术摘要：同态加密中极小极大多项式逼近的度数约束区间优化

问题陈述
在基于同态加密（HE）的隐私保护机器学习（PPML）中，神经网络推理必须仅使用算术运算（加法和乘法）在加密数据上执行。因此，非多项式激活函数（如 ReLU、sigmoid、tanh、GELU）必须被多项式逼近所取代。标准方法是极小极大逼近（通过 Remez 算法计算），它在特定的设计区间 $[-t, t]$ 内最小化最坏情况误差。

然而，在固定多项式次数预算下，选择设计区间 $t$ 存在一个关键的权衡：

1. 较宽的区间： 改善了对大数值输入的覆盖能力，但也增加了区间内的极小极大逼近误差。
2. 较窄的区间： 减少了区间内的极小极大误差，但增加了输入落在区间之外时发生“失控外推”的风险。在 HE 中，由于中间明文值是不可观测的，这种外推误差可能会被放大数千倍，从而严重降低推理精度。

虽然领域扩展函数（DEF）及其多项式对应物——领域扩展多项式（DEP）已被提议用于将输入限制在设计区间之外以防止失控外推，但设计区间 $t$ 本身仍是一个必须进行调优的超参数。现有方法通常依赖于保守的固定区间（例如 $[-20\sigma, 20\sigma]$），这可能无法针对特定的输入分布最小化整体误差。

方法论
本文将选择逼近区间 $[-t, t]$ 建模为一个分布感知的优化问题。目标是选择 $t$ 以最小化相对于预激活输入分布 $X$ 的均方误差（MSE）。

1. 理想化目标（基于 DEF）：
   作者定义了一个基于非多项式硬截断映射 $D_t(x)$ 的理想目标 $J_{DEF}(t)$。该目标将总 MSE 分解为：

   • 区间内项： 极小极大多项式 $p_{n,t}$ 在 $[-t, t]$ 上的误差。
   • 区间外项： 输入被截断至边界 $\pm t$ 时产生的误差。

   为了使该目标在分析上可处理，作者推导了一个代理目标 $\hat{J}_{DEF}(t)$：

   • 区间内逼近： 他们利用**弧度律（arcsine law）**对极小极大多项式的残差分布进行建模，这由极小极大解的等波纹特性所证明。这使得误差的条件二阶矩可以近似为 $E_n(t)^2 / 2$，其中 $E_n(t)$ 是极小极大误差。
   • 区间外逼近： 他们用目标函数的端点值替换多项式的端点值，从而为截断误差创建了一个闭合形式的代理。

2. 处理不同类型的激活函数：

   • 齐次函数（ReLU、LeakyReLU）： 对于这些函数，极小极大误差随区间半径线性缩放（$E_n(t) = t E_n(1)$）。这使得可以通过涉及标准正态分布 PDF 和 CDF 的一阶条件，精确地推导出最优归一化半径 $\alpha^* = t^*/\sigma$。
   • 非齐次函数（Sigmoid、Tanh、GELU）： 由于不存在简单的缩放律，作者在半径网格上对极小极大误差曲线 $E_n(t)$ 进行数值采样，并拟合一个平滑的多项式代理。该代理随后被用于在代理目标中寻找最优的 $t$。

3. HE 可实现的实现（基于 DEP）：
   由于理想的硬截断映射是非多项式的，该框架将理想分析与使用领域扩展多项式（DEP）构建的 HE 可实现构造联系起来。

   • 一组缩放的 DEP 阶段将保守的输入范围 $[-R_0, R_0]$ 映射到设计区间 $[-t, t]$。
   • 作者推导了一个实现误差分解和一个上界（$U_{impl}$），用于量化理想 DEF 目标与实际 DEP 实现之间的差距。该上界考虑了在保持区域内的近恒等误差以及在扩展区域内的有界误差。

核心贡献

• 原则性的公式化： 本文提供了针对度数受限的极小极大多项式逼近进行区间优化的首次原则性公式化，明确地通过最小化关于预激活分布的 MSE，而非使用固定的保守区间。
• 解析可处理的代理： 作者推导了一个基于 DEF 的代理目标，捕捉了区间内极小极大误差与区间外截断误差之间的权衡。该代理利用弧度分布模型处理残差，并使用端点值替换法处理截断误差。
• 误差分解与界限： 该工作建立了理想 DEF 分析与 HE 可实现的 DEP 构造之间的严谨联系，为使用多项式组合替代理想截断函数所导致的 MSE 差距提供了上界。
• 数值验证： 本文在代表性激活函数（ReLU、LeakyReLU、Sigmoid、Tanh、GELU）以及高斯和拉普拉斯输入分布下验证了该框架。

结果
数值实验表明，所提出的区间优化显著优于传统的固定区间极小极大基准（例如使用 $[-20\sigma, 20\sigma]$）：

• MSE 降低： 优化后的方法实现了显著更低的 MSE。对于 Sigmoid、Tanh 和 GELU，这种提升尤为明显，其 MSE 与固定区间基准相比降低了数个数量级。
• 代理准确性： 解析代理 $\hat{J}_{DEF}(t)$ 的极小值点在所有测试函数中都与数值评估的理想目标 $J_{DEF}(t)$ 的极小值点高度吻合，验证了该代理在区间选择中的实用性。
• DEP 性能： 实际的基于 DEP 的评估器实现了比固定区间基准更低的 MSE。实验还揭示了 DEP 设计中的权衡：较大的扩展因子（$L=2.5$）减少了所需的阶段数和累积组合误差，尽管其单阶段更接近理想截断，但在测试设置中，较大的扩展因子比较小的因子（$L=1.6$）能产生更好的实际 MSE。

意义与主张
本文主张，将近似区间视为优化变量而非固定超参数，对于在度数约束下最大化基于 HE 的推理精度至关重要。通过平衡区间内的极小极大误差与区间外的截断误差，该框架能够在不增加多项式次数或乘法深度的情况下实现更精确的推理。

作者将这项工作定位为端到端 HE 神经网络推理的基础性步骤。他们指出，未来的工作应研究如何将此框架集成到完整的网络流水线中，考虑层间分布与累积误差之间的相互作用，以及特定密码学库的实现成本。本文并不声称解决了整个 PPML 问题，而是提供了一种特定的、具有解析基础的方法来优化一个关键组件（多项式逼近区间），该组件直接影响推理精度。