기술 요약: 제로 차수 헤시안 근사 재고: 단일 단계 정책 최적화 관점

1. 문제 정의

제로 차수(Zeroth-order, ZO) 최적화는 목적 함수 $F(\theta) = \mathbb{E}_\xi[f(\theta; \xi)]$가 노이즈가 있는 함수 평가를 통해서만 접근 가능한 블랙박스인 시나리오를 다룹니다. ZO 그래디언트 추정은 잘 확립되어 있으나, 정확한 **ZO 헤시안 근사(Hessian approximation)**는 특히 고차원 및 노이즈가 심한 환경에서 여전히 중요한 과제로 남아 있습니다.

정확한 곡률 정보는 다음과 같은 작업에 필수적입니다:

• 미분 불가능한(derivative-free) 바이레벨 최적화(bilevel optimization).
• 불확실성 정량화(uncertainty quantification).
• 대규모 언어 모델(LLM)의 곡률 인지 미세 조정(curvature-aware fine-tuning).

기존 방법론들은 두 가지 주요 한계점에 직면해 있습니다:

1. 높은 분산: 고차원 설정에서 클래식한 무작위 추정기(예: Stein 유형 추정기)는 종종 높은 분산으로 인해 불안정한 최적화를 초도합니다.
2. 제한된 범위: 이전 연구들은 헤시안 행렬 $\nabla^2 F(\theta)$ 자체를 추정하는 데 주로 집중했습니다. 이계(second-order) ZO 업데이트에 필수적인 정규화된 역 헤시안(regularized inverse Hessian) $(\nabla^2 F(\theta) + \lambda I_d)^{-1}$ 및 역 헤시안-그래디언트 곱(inverse Hessian-gradient product) $(\nabla^2 F(\theta) + \lambda I_d)^{-1}\nabla F(\theta)$에 대한 연구는 부족합니다.
3. 쿼리 효율성: 나이브한 유한 차분(finite-difference) 방식은 $O(d^2)$의 쿼리를 요구하는 반면, 기존의 무작위 방식들은 분산 감소와 쿼리 재사용 사이의 균형을 효과적으로 맞추지 못합니다.

2. 방법론

2.1. 이론적 프레임워크: 정책 최적화 관점

저자들은 ZO 헤시안 근사를 **단일 단계 정책 최적화(Single-Step Policy Optimization, PO)**의 관점으로 재해석하는 통합 프레임워크를 제안합니다.

• 평활화된 목적 함수(Smoothed Objective): ZO 목적 함수를 평활화된 목적 함수 $F_\mu(\theta) = \mathbb{E}_{x \sim \pi_\theta(x)}[\mathbb{E}_\xi[f(x; \xi)]]$로 재구성합니다. 여기서 $\pi_\theta$는 매개변수화된 샘플링 정책(예: 가우시안 $N(\theta, \mu^2 I_d)$)입니다.
• 헤시안 항등식(Hessian Identity): 정책 그래디언트를 미분함으로써, 저자들은 평활화된 목적 함수에 대한 일반적인 헤시안 항등식을 도출합니다:
  $$\nabla^2 F_\mu(\theta) = \mathbb{E}_{x \sim \pi_\theta(x)} \left[ H_{\pi_\theta} \cdot \mathbb{E}_\xi[f(x; \xi)] \right]$$
  여기서 $H_{\pi_\theta}$는 정책 로그 밀도의 헤시안입니다.
• 추정기의 통합: 이 관점은 클래식한 Stein 유형 추정기(One-point, Two-point, Three-point)가 베이스라인(예: 제로 베이스라인, 앵커 베이스라인 $f(\theta)$, 또는 대칭 샘플링)의 선택에 따라 구분될 뿐, 이 프레임워크의 특수한 사례임을 보여줍니다.

2.2. ZoVH: 분산 감소 헤시안 추정기

PO 프레임워크를 기반으로, 저자들은 ZoVH(Zeroth-Order Variance-reduced Hessian)를 도입하며, 이는 두 가지 핵심 기술을 사용합니다:

1. 최적 평균 베이스라인(Optimal Averaged Baseline):

   • 그래디언트 추정기에서 베이스라인이 흔히 휴리스틱하게 결정되는 것과 달리, 저자들은 랭크-1 항등식에서 유도된 헤시안 추정기에 대해 평균 베이스라인 $\hat{b} = \frac{1}{K}\sum f(x_k)$가 불편성(unbiasedness)을 유지하는 유일한 선택임을 증명합니다.
   • 이론적으로, 이 베이스라인은 모든 상수 베이스라인 중에서 추정기의 분산을 최소화하는 것으로 증명되었습니다.

2. 쿼리 재사용 전략(Query Reuse Strategy):

   • 쿼리 비용을 늘리지 않으면서 분산을 더욱 줄이기 위해, ZoVH는 과거의 함수 쿼리 이력 버퍼를 활용합니다.
   • 이는 PO 프레임워크 내에서의 **오프-폴리시 학습(off-policy learning)**으로 해석되며, 과거 데이터(이전 반복에서 생성된)를 중요도 샘플링(importance sampling)을 통해 가중치를 부여하여 현재의 헤시안을 추정합니다.
   • 이는 추가적인 함수 평가 없이 샘플 크기를 $K$에서 $NK$($N$은 이력 길이)로 효과적으로 증가시킵니다.

2.3. 효율적인 역 행렬 근사

실질적인 이계 업데이트를 가능하게 하기 위해, 본 논문은 ZoVH를 역 헤시안 및 역 헤시안-그래디언트 곱 근사로 확장합니다:

• 역 헤시안: **우드베리 행렬 항등식(Woodbury matrix identity)**을 사용하여, 밀집된(dense) $d \times d$ 행렬을 역행렬 계산하는 대신 정규화된 랭크-$K$ 헤시안 추정기의 역행렬을 효율적으로 계산합니다 ($O(K^2 d)$ 또는 대각 근사를 통한 $O(Kd)$).
• 편향 수정된 곱(Bias-Corrected Product): 쿼리를 절약하기 위해 동일한 무작위 방향을 그래디언트와 헤시안 추정에 모두 사용하는 경우 상관 편향(correlation bias)이 발생합니다. 저자들은 이 편향을 수정하기 위해 리브-원-아웃(leave-one-out) 전략을 제안하며, 이를 통해 최소한의 오버헤드로 $(\nabla^2 F + \lambda I)^{-1}\nabla F$를 효율적으로 계산할 수 있습니다.

3. 주요 기여

1. 통합된 PO 관점: 일반적인 ZO 헤시안 추정기와 평활화된 PO 목적 함수의 헤시안 사이의 이론적 동등성을 확립하여, 클래식한 무작위 추정기들을 베이스라인 선택의 구체적인 사례로 통합하였습니다.
2. ZoVH 알고리즘: 전체 헤시안, 정규화된 역 헤시안, 그리고 편향이 수정된 역 헤시안-그래디언트 곱을 위한 포괄적인 분산 감소 추정기 세트를 개발하였습니다.
3. 이론적 보장:
   • 평균 베이스라인을 사용한 헤시안 추정기의 **불편성(unbiasedness)**을 증명하였습니다.
   • 평균 베이스라인의 **분산 최적성(variance optimality)**을 입증하였습니다.
   • 전체 ZoVH 세트에 대한 오차 범위(편향-분산 분해)를 제공하였습니다.
   • 결과적인 곡률 인지 ZO 알고리즘이 $\epsilon$-정지점(stationary point)으로 수렴함을 보장하였습니다.
4. 실용적 효율성: 샘플 효율성을 높이면서 쿼리 예산을 팽창시키지 않는 쿼리 재사용 메커니즘을 도입하였으며, 고차원 문제(LLM 파인튜닝 등)에 적합한 안정적인 역 행렬 근사를 도출하였습니다.

4. 실험 결과

저자들은 합성 벤치마크, 신경망 훈련, 블랙박스 적대적 공격을 통해 ZoVH를 검증하였습니다.

• 헤시안 추정 정확도:

  • 합성 함수(Quadratic, Rosenbrock, Styblinski-Tang) 및 CNN 레이어에서, ZoVH(쿼리 재사용, $N=4$ 적용 시)는 클래식한 Stein 및 Central-Difference 추정기에 비해 일관되게 가장 낮은 프로베니우스 노름(Frobenius norm) 오차를 달성했습니다.
  • ZoVH ($N=1$)는 Quadratic 및 Rosenbrock 함수에서 Central-Difference 추정기 대비 8배의 정확도 향상을 보였습니다.
  • CNN 레이어에서 ZoVH ($N=4$)는 Central-Difference 추정기 대비 9배의 오차 감소를 달성했습니다.

• 최적화 수렴 성능:

  • 합성 최적화 작업에서 ZoVH ($N=4$)는 수렴 속도와 최종 정확도 모두에서 Vanilla ZOO, HiZOO, ZoAR를 크게 앞질렀으며, Vanilla ZOO 대비 평균 22배의 속도 향상을 달ach했습니다.
  • 블랙박스 적대적 공격에서 ZoVH ($N=4$)는 Vanilla ZOO에 비해 성공적인 공격을 달성하는 데 4배 적은 반복 횟수가 필요했습니다.

• LLM 미세 조정:

  • GLUE/SuperGLUE 태스크에 대해 OPT-1.3B 및 OPT-13B 모델을 미세 조정하는 데 적용되었습니다.
  • ZoVH는 MeZO 및 HiZOO에 비해 더 빠른 수렴과 더 높은 테스트 정확도를 보여주었습니다.
  • 런타임 및 메모리 오버헤드는 미미했으며, ZoVH는 MeZO보다 약간 느릴 뿐이며 스칼라 값과 시드(seed)만을 저장하므로 추가 메모리 사용량이 매우 적었습니다.

5. 의의 및 주장

본 논문은 ZoVH가 곡률 인지 미분 불가능 최적화(curvature-aware derivative-free optimization)를 위한 견고한 토대를 제공한다고 주장합니다. ZO 근사와 정책 최적화 사이의 간극을 메움으로써, 이 연구는 다음을 제공합니다:

• 이론적 명확성: 특정 추정기가 왜 작동하는지, 그리고 베이스라인 선택을 통해 어떻게 최적화할 수 있는지를 설명하는 엄격한 유도 과정을 제공합니다.
• 실용적 유용성: 전면적인 유한 차분 방식의 막대한 쿼리 비용 없이도, 실세계 응용 분야(LLM 포함)에서 우수한 추정 정확도와 수렴 성능을 달성하는 방법을 제시합니다.
• 확장성: 효율적인 역 행렬 근사와 쿼리 재사용을 통해, 이전에는 불가능했던 블랙박스 환경에서의 이계(second-order) 최적화를 수백만 개의 파라미터를 가진 고차원 문제(예: LLM)에서도 가능하게 합니다.

저자들은 이 방법이 평활화 편향(ZO 방식의 고유한 특성)을 도입하지만, 분산 감소 및 쿼리 효율성 이득이 이 트레이드오프를 상쇄하여 노이즈가 심한 고차원 환경에서 더 빠르고 안정적인 수렴을 이끌어낸다고 강조합니다.