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

技術要約：準同型暗号における極小最大（Minimax）多項式近似のための次数制約付き区間最適化

問題提起
準同型暗号（HE）に基づくプライバシー保護機械学習（PPML）において、ニューラルネットワークの推論は、加算と乗算のみを用いた算術演算を用いて暗号化されたデータに対して実行されなければならない。その結果、非多項式活性化関数（ReLU、sigmoid、tanh、GELUなど）は、多項式近似に置き換えられる必要がある。標準的な手法は、レメッツ（Remez）アルゴリズムを用いて計算される極小最大近似であり、これは特定の設計区間 $[-t, t]$ における最悪誤差を最小化するものである。

しかし、固定された多項式次数予算の下では、設計区間 $t$ の選択において重要なトレードオフが存在する：

1. 広い区間： 大きな値の入力に対するカバー範囲を改善するが、区間内における極小最大近似誤差が増大する。
2. 狭い区間： 区間内の極小最大誤差を減少させるが、区間外に落ちた入力による「制御不能な外挿（uncontrolled extrapolation）」のリスクを高める。HEにおいては、中間的なプレーンテキストの値は観測不可能であるため、このような外挿誤差は数千倍に増幅され、推論精度を著しく低下させる可能性がある。

ドメイン拡張関数（DEF）およびその多項式版であるドメイン拡張多項式（DEP）は、入力を設計区間の外側にクリップして制御不能な外挿を防ぐために提案されているが、最適な設計区間 $t$ 自体も調整が必要なハイパーパラメータとして残っている。既存の手法は、多くの場合、保守的で固定された区間（例：$[-20\sigma, 20\sigma]$）に依存しているが、これらは特定の入力分布に対して誤差を最小化するものではない。

手法
本論文は、近似区間 $[-t, t]$ の選択を、分布を考慮した最適化問題として定式化している。目標は、事前活性化入力分布 $X$ に関する平均二乗誤差（MSE）を最小化するように $t$ を選択することである。

1. 理想的な目的関数（DEFベース）：
   著者らは、非多項式のハードクリッピング写像 $D_t(x)$ に基づく理想的な目的関数 $J_{DEF}(t)$ を定義している。この目的関数は、全MSEを以下の2つに分解する：
   • 区間内項： 区間 $[-t, t]$ における極小最大多項式 $p_{n,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）を用いた構成へと接続する。

   • スケールされたDEPステージの合成により、保守的な入力範囲 $[-R_0, R_0]$ を設計区間 $[-t, t]$ へと写像する。
   • 著者らは、実装誤差分解と、理想的なDEF目的関数と実用的なDEP実現との間のギャップを定量化する上界（$U_{impl}$）を導出している。この上界は、保存領域内における恒等写像に近い誤差と、拡張領域における有界な誤差を考慮している。

主な貢献

• 原理的な定式化： 本論文は、特定の入力分布に対して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問題全体を解決すると主張するものではなく、推論精度に直接影響を与える重要なコンポーネント（多項式近似の区間）を最適化するための、解析に基づいた特定の手法を提供するものである。