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

기술 요약: 동형 암호 내 미니맥스 다항식 근사를 위한 차수 제한 구간 최적화

문제 정의
동형 암호(HE) 기반의 개인정보 보호 머신러닝(PPML)에서, 신경망 추론은 덧셈과 곱셈만을 사용하는 산술 연산을 통해 암호화된 데이터 상에서 수행되어야 합니다. 결과적으로, 비다항식 활성화 함수(예: ReLU, sigmoid, tanh, GELL)는 다항식 근사로 대체되어야 합니다. 표준적인 접근 방식인 미니맥스 근사(Remez 알고리즘을 통해 계산됨)는 특정 설계 구간 $[-t, t]$에 대해 최악의 오차를 최소화합니다.

그러나 고정된 다항식 차수 예산 하에서 설계 구간 $t$를 선택할 때는 다음과 같은 결정적인 트레이드오프가 존재합니다:

1. 넓은 구간: 큰 크기의 입력을 더 잘 커버하지만, 구간 내 미니맥스 근사 오차를 증가시킵니다.
2. 좁은 구간: 구간 내 미니맥스 오차를 줄이지만, 구간 밖으로 벗어나는 입력에 대한 "제어되지 않은 외삽(uncontrolled extrapolation)"의 위험을 높입니다. HE 환경에서는 중간 평문 값을 관찰할 수 없으므로, 이러한 외삽 오차는 수천 배 증폭될 수 있으며 이는 추론 정확도를 심각하게 저하시킬 수 있습니다.

입력을 설계 구간 외부로 클리핑하여 제어되지 않은 외삽을 방지하는 도메인 확장 함수(DEF) 및 그 다항식 형태인 도메인 확장 다항식(DEP)이 제안되었으나, 최적의 설계 구간 $t$ 자체는 여전히 튜닝이 필요한 하이퍼파라미터로 남아 있습니다. 기존 방법들은 종종 보수적이고 고정된 구간(예: $[-20\sigma, 20\sigma]$)에 의존하며, 이는 특정 입력 분포에 대해 전체 오차를 최소화하지 못할 수 있습니다.

방법론
본 논문은 근사 구간 $[-t, t]$의 선택을 분포 인식 최적화 문제로 정식화합니다. 목표는 pre-activation 입력 분포 $X$에 대한 평균 제곱 오차(MSE)를 최소화하는 $t$를 선택하는 것입니다.

1. 이상적인 목적 함수 (DEF 기반):
   저자들은 비다항식 하드 클리핑 맵 $D_t(x)$에 기반한 이상적인 목적 함수 $J_{DEF}(t)$를 정의합니다. 이 목적 함수는 전체 MSE를 다음 두 가지로 분해합니다:
   • 구간 내 항: $[-t, t]$에서의 미니맥스 다항식 $p_{n,t}$의 오차.
   • 구간 외 항: 입력을 경계값 $\pm t$로 클리핑할 때 발생하는 오차.

이를 분석적으로 다룰 수 있도록 하기 위해, 저자들은 대리 목적 함수 $\hat{J}_{DEF}(t)$를 유도합니다:

• 구간 내 근사: 미니맥스 다항식의 잔차 분포를 모델링하기 위해 **아크사인 법칙(arcsine law)**을 사용하며, 이는 미니맥스 해의 등치 진동(equioscillation) 특성에 의해 정당화됩니다. 이를 통해 오차의 조건부 이차 모멘트를 $E_n(t)^2 / 2$로 근사할 수 있습니다 (여기서 $E_n(t)$는 미니맥스 오차).
• 구간 외 근사: 클리핑 오차에 대한 폐쇄형 대리 함수를 만들기 위해, 다항식의 끝점 값을 타겟 함수의 끝점 값으로 대체합니다.

2. 활성화 함수 유형 처리:

   • 동차 함수 (ReLU, LeakyReLU): 이러한 함수의 경우 미니맥스 오차는 구간 반지름에 따라 선형적으로 스케일링됩니다 ($E_n(t) = t E_n(1)$). 이를 통해 표준 정규 분포의 PDF 및 CDF를 포함하는 1차 조건을 사용하여 최적의 정규화된 반지름 $\alpha^* = t^*/\sigma$를 정확하게 분석적으로 유도할 수 있습니다.
   • 비동차 함수 (Sigmoid, Tanh, GELU): 단순한 스케일링 법칙이 존재하지 않으므로, 저자들은 반지름 그리드 상에서 미니맥스 오차 곡선 $E_n(t)$를 수치적으로 샘플링하고 매끄러운 다항식 대리 함수를 피팅합니다. 이 대리 함수는 대리 목적 함수 내에서 최적의 $t$를 찾는 데 사용됩니다.

3. HE 구현 가능 구현 (DEP 기반):
   이상적인 클리핑 맵은 비다항식이므로, 본 프레임워크는 이상적인 DEF 분석을 DEP를 사용한 HE 구현 가능한 구조와 연결합니다.

   • 스케일링된 DEP 단계들의 합성은 보수적인 입력 범위 $[-R_0, R_0]$를 설계 구간 $[-t, t]$로 매핑합니다.
   • 저자들은 이상적인 DEF 목적 함수와 실제적인 DEP 구현 사이의 격차를 정량화하는 구현 오차 분해와 상한($U_{impl}$)을 유도합니다. 이 상한은 보존 영역 내의 근사 항등(near-identity) 오차와 확장 영역에서의 유계 오차를 모두 고려합니다.

주요 기여

• 원칙적인 정식화: 본 논문은 고정된 보수적 구간을 사용하는 대신, 특정 입력 분포에 대해 MSE를 명시적으로 최소화함으로써 차수 제한 미니맥스 다식 근사를 위한 구간 선택에 대한 최초의 원칙적인 정식화를 제공합니다.
• 분석적으로 다룰 수 있는 대리 함수: 저자들은 구간 내 미니맥스 오차와 구간 외 클리핑 오차 사이의 트레이드오프를 포착하는 DEF 기반의 대리 목적 함수를 유도했습니다. 이 대리 함수는 잔차를 위해 아크사인 분포 모델을 사용하고, 클리핑 오차를 위해 끝점 값 치환을 활용합니다.
• 오차 분해 및 경계값: 본 연구는 이상적인 DEF 분석과 HE 구현 가능한 DEP 구조 사이의 엄격한 연결을 확립하며, 이상적인 클리핑 함수를 다항식 합성으로 대체할 때 발생하는 MSE 격차에 대한 상한을 제공합니다.
• 수치적 검증: 본 프레임워크를 가우시안 및 라플라스 입력 분포 하의 대표적인 활성화 함수(ReLU, LeakyReLU, Sigmoid, Tanh, GELU)에 대해 검증하였습니다.

결과
수치 실험 결과, 제안된 구간 최적화가 기존의 고정 구간 미니맥스 베이스라인(예: $[-20\sigma, 20\sigma]$ 사용)보다 성능이 월등히 높음을 입증했습니다:

• MSE 감소: 최적화된 접근 방식은 실질적으로 낮은 MSE를 달ek합니다. 특히 sigmoid, tanh, GELU의 경우, 고정 구간 베이스라인에 비해 MSE가 수 차례의 오더(order)만큼 감소하는 현상이 두드러졌습니다.
• 대리 함수의 정확도: 분석적 대리 함수 $\hat{J}_{DEF}(t)$의 최솟값은 모든 테스트된 함수에 대해 수치적으로 평가된 이상적인 목적 함수 $J_{DEF}(t)$의 최솟값과 밀접하게 일치하며, 이를 통해 대리 함수의 유용성을 검증했습니다.
• DEP 성능: 실제 DEP 기반 평가기는 고정 구간 베이스라인보다 낮은 MSE를 달성했습니다. 또한 실험을 통해 DEP 설계의 트레이드오프를 밝혀냈습니다. 더 큰 확장 계수($L=2.5$)를 사용하는 것이 필요한 단계를 줄이고 누적되는 합성 오차를 줄여, 단계당 이상적인 클리핑에 더 가까운 $L=1.6$을 사용할 때보다 테스트된 설정에서 더 나은 실제 MSE를 제공했습니다.

의의 및 주장
본 논문은 근사 구간을 고정된 하이퍼파라미터가 아닌 최적화 변수로 취급하는 것이 차수 제한 하에서 HE 기반 추론의 정확도를 극대화하는 데 필수적이라고 주장합니다. 구간 내 미니맥스 오차와 구간 외 클리핑 오차 사이의 균형을 맞춤으로써, 제안된 프레임워크는 다항식 차수나 곱셈 깊이를 늘리지 않고도 더 정확한 추론을 가능하게 합니다.

저자들은 본 연구를 엔드 투 엔드 HE 기반 신경망 추론을 위한 기초적인 단계로 위치시킵니다. 향후 연구에서는 층별 분포 및 누적 오차의 상호작용, 그리고 특정 암호 라이브러리의 구현 비용을 고려하여 이 프레임워크를 전체 네트워크 파이프라인에 통합하는 것을 조사해야 한다고 언급합니다. 본 논문은 전체 PPML 문제를 해결한다고 주장하는 것이 아니라, 추론 정확도에 직접적인 영향을 미치는 핵심 구성 요소(다항식 근사 구간)를 최적화하는 구체적이고 분석적으로 근거가 있는 방법을 제시합니다.