Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning

기술 요약: LMO 기반 방법론을 위한 제로 차수 파라미터 프리 최적화 (Zero-order Parameter-free Optimization)

문제 정의
대규모 언어 모델(LLM)의 미세 조정(Fine-tuning)은 현대 최적화의 핵심적인 응용 분야이지만, 역전파(backpropagation)로 인한 메모리 오버헤드라는 결정적인 병목 현상에 직면해 있습니다. OPT-1.3B와 같은 모델을 위해 중간 활성화 함수(activations), 그래디언트, 옵티마이저 상태를 저장하는 데는 상당한 메모리(예: 약 25 GB)가 필요하며, 이는 확장성을 제한합니다. 제로 차수(Zeroth-order, ZO) 최적화는 그래디언트 계산을 함수 값 쿼리로부터 유도된 유한 차분 추정치로 대체함으로써 메모리 효율적인 대안을 제공합니다. 그러나 기존의 ZO 방법들은 두 가지 주요한 한계를 가집니다:

1. 하이퍼파라미터 민감도: 성능이 스텝사이즈(stepsize)와 평활화 파라미터($\tau$)에 크게 의존합니다. 최적의 설정은 일반적으로 문제 의존적인 상수(예: 리프시츠 상수, 최적점까지의 거리)에 대한 지식을 필요로 하지만, 실제 상황에서는 이를 알 수 없으므로 비용이 많이 드는 태스크별 그리드 탐색(grid search)이 필수적입니다.
2. 기하학적 불일치: 표준 유클리드 업데이트는 파라미터 블록(예: LLM의 행렬 형태 가중치)의 이질적인 구조를 포착하지 못할 수 있습니다. 선형 최소화 오라클(Linear Minimization Oracles, LMO)을 활용하는 방법은 비유클리드 기하학(예: 행렬의 스펙트럼 노름)에 적응할 수 있지만, 이를 ZO 환경에서 파라미터 프리(parameter-free, PF) 적응과 결합하는 연구는 아직 미개척 분야로 남아 있습니다.

방법론
저자들은 제로 차수 최적화, 파라미터 프리 적응, 그리고 LMO를 통한 기하학 인지 업데이트를 통합하는 새로운 알고리즘인 AdaNAGED(ADAptive Norm-Agnostic Gradient-frEe Descent)를 제안합니다.

• 파라미터 프리 추정:

  • 매끄러움 (Smoothness, $L$): 사전 리프시츠 상수를 요구하는 대신, 이 방법은 최적화 궤적을 따라 국소 매끄러움을 반복적으로 추정합니다. 연속된 반복(iterates) 사이의 거리와 ZO 그래디언트 근사치의 차이 비율을 계산합니다: $L_t = \|g_t(x_{t+1}, e_t) - g_t(x_t, e_t)\|_* / \|x_{t+1} - x_t\|$. 메모리 효율성을 유지하기 위해 동일한 섭동 방향 $e_t$(랜덤 시드로 저장됨)가 두 지점에서 모두 사용됩니다.
  • 초기 격차 (Initial Gap, $\Delta$): 방법론은 목적 함수의 알려진 하한값($f_{min}$)을 사용하여 초기 격차 $\Delta \leq f(x_0) - f_{min}$를 추정함으로써, 최적점까지의 거리를 알 필요가 없도록 합니다.
  • 적응형 스텝사이즈 (Adaptive Stepsize): 스텝사이즈 $\gamma_t$는 국소 매끄러움 추정치의 AdaGrad-Norm 스타일 누적($S_t = S_{t-1} + L_t$)을 사용하여 업데이트되며, 이에 따라 $\gamma_t \propto 1/\sqrt{S_t}$가 됩니다.
  • 평활화 파라미터 ($\tau$): 안정성을 보장하기 위해, $\tau_t$는 수렴 증명의 이론적 요구 사항으로부터 도출된 바와 같이 스텝사이즈에 따라 선형적으로 스케일링됩니다 ($\tau_t = \rho C_2 \gamma_t$).

• LMO 기반 업데이트:
  알고리즘은 노름 볼(norm ball)에 대한 선형 최소화 오라클을 통해 업데이트를 정의합니다: $v_t = \text{lmo}(g_t)$. 이를 통해 방법론은 다양한 기하학에 적응할 수 있습니다:

  • 벡터 기하학: $\ell_\infty$ 노름을 사용하여 Sign-SGD와 유사한 업데이트를 생성합니다.
  • 행렬 기하학: 스펙트럼 노름을 사용하여 Muon과 유사한 업데이트를 생성합니다. 정확한 극 분해(Polar Decomposition, SVD)는 계산 비용이 많이 들기 때문에, 저자들은 행렬 역행렬을 피하면서 뉴턴-슐츠(Newton–Schulz, N-SS) 반복을 몇 단계 적용하여 폴라 연산자(polar operator)를 근사하는 AdaMuGED를 도입합니다.

주요 기여

1. 새로운 파라미터 프리 ZO 구성: 본 논문은 문제 상수에 대한 사전 지식 없이 제로 차수 환경에서 국소 매끄러움을 추정하고 스텝사이즈를 설정하는 방법을 제시합니다. 이는 섭동 방향의 생성 시드만을 저장함으로써 ZO의 메모리 효율성을 보존합니다.
2. 패러다임의 통합: 제안된 AdaNAGED 알고리즘은 메모리 효율적인 ZO, 감소된 하이퍼파라미터 의존성, 그리고 기하학 인지 LMO 업데이트를 결합합니다.
3. 수렴 보장: 저자들은 리프시츠 연속, 매끄럽고 볼록한(smooth and convex) 목적 함수에 대한 수렴 속도를 확립했습니다. 결과적인 속도는 파라미터 프리 추정과 확률성을 고려한 추가 요인을 포함하여 점근적으로 최적($O(1/\epsilon^2)$)입니다.
4. 실용적 변형: AdaMuGED의 도입은 뉴턴-슐츠 반복을 사용하여 행렬 값 파라미터로 프레임워크를 확장하며, 이를 통해 파라미터가 행렬로 구조화된 LLM 미세 조정에 적용 가능하게 만듭니다.

실험 결과
방법론은 메모리 제약이 있는 LLM 적응의 벤치마크인 SST-2 감성 분류 태스크에 대해 OPT-1.3B 모델을 미세 조정하여 평가되었습니다.

• 베이스라인: 저자들은 튜닝된 제로 차수 옵티마이저인 ZO-AdaMM, ZO-SignSGD, ZO-Muon과 비교했습니다.
• 성능:
  • AdaNAGED (SignSGD 유사 방식)는 0.903의 정확도를 달성하여, 튜닝된 ZO-SignSGD(0.910)와 0.7 퍼센트 포인트 차이 내에 있었습니다.
  • AdaMuGED (Muon 유사 방식)는 0.908의 정확도를 달성하여, 튜닝된 ZO-SignSGD와의 격차를 0.2 퍼센트 포인트로 줄였으며, AdaNAGED보다 0.5 퍼센트 포인트 더 높은 성능을 보였습니다.
  • 튜닝된 ZO-Muon이 0.921로 가장 강력한 베이스라인으로 남았으며, 이는 행렬 인지 기하학의 이점을 확인시켜 줍니다.
• 결론: 파라미터 프리 방법들은 튜닝된 ZO 베이스라인들과 경쟁력 있는 성능을 보여주었으며, 이는 적응형 규칙이 값비싼 하이퍼파라미터 탐색 없이도 튜닝된 ZO 방법의 성능 상당 부분을 회복할 수 있음을 입증합니다.

의의
본 논문은 제로 차수(Zeroth-Order), 파라미터 프리(Parameter-Free), 그리고 선형 최소화 오라클(Linear Minimization Oracle) 최적화의 교차점에서 작동하는 첫 번째 방법론이라고 주장합니다. 그 의의는 다음과 같습니다:

1. 메모리 효율성: 역전파를 피함으로써 ZO 최적화를 LLM에 실용적으로 적용할 수 있음을 보여줍니다.
2. 자동화: 비용이 많이 드는 태스크별 하이퍼파라미터 튜닝에 대한 의존성을 적응형 파라미터 프리 매끄러움 및 스텝사이즈 추정을 통해 제거할 수 있습니다.
3. 기하학적 유연성: 제안된 프레임워크는 모델 파라미터의 구조적 특성(예: 행렬)에 부합하는 비유클리드 업데이트(LMO를 통해)를 지원하여 컨디셔닝과 안정성을 개선합니다.

저자들은 파라미터 프리 접근법이 경쟁력이 있지만, 튜닝된 베이스라인(특히 ZO-Muon)이 여전히 약간의 우위를 점하고 있다는 점을 언급하며 겸손한 입장을 유지합니다. 이는 수동 튜닝이 여전히 최적일 수 있지만, 제안된 방법이 강력하고 자동화된 대안이 될 수 있음을 시사합니다.