기술 요약: 경량 제로차 최적화를 위한 일관된 좌표 하강법

문제 정의

제로차 (Zeroth-Order, ZO) 최적화는 역전파가 불가능하거나 계산 비용이 과도하게 높은 시나리오, 예를 들어 메모리 제약이 있는 온디바이스 학습, 블랙박스 적대적 공격, 시뮬레이션 기반 강화학습 등에 필수적입니다. 그러나 기존 ZO 방법들은 샘플 효율성과 분산 사이의 근본적인 트레이드오프에 직면해 있습니다.

• 표준 유한차분 (Finite Differences, FD): 낮은 분산을 가진 기울기 추정을 제공하지만, $d$개의 매개변수당 $O(d)$개의 함수 평가가 필요하여 샘플 효율성이 낮습니다.
• 무작위화 방법 (예: 진화 전략, SPSA, 무작위 부분공간): 단계당 쿼리 비용을 줄이지만 높은 분산을 도입하여, 종종 벽시계 (wall-clock) 수렴을 저해하는 작은 학습률이나 큰 배치 크기를 필요로 합니다.

현재의 접근법들은 종종 "오래된 (stale)" 기울기 (이전 반복에서 계산된 것) 를 유해한 지연으로 간주하여 폐기하고, 유한차분 단계 크기 ($\epsilon$) 를 실제 기울기를 정확하게 근사하기 위해 최소화해야 한다고 가정합니다. 본 논문은 이러한 가정들에 도전합니다.

방법론: 일관된 좌표 하강법 (Coherent Coordinate Descent, CoCD)

저자들은 결정론적이고, 샘플 효율적이며, 예산을 인지하는 ZO 옵티마이저인 **일관된 좌표 하강법 (CoCD)**을 제안합니다. CoCD 는 두 가지 핵심 통찰에 기반합니다.

1. 시간적 일관성 (Temporal Coherence): 최적화 궤적은 연속성을 띠며, 기울기는 함수의 리프시츠 (Lipschitz) 매끄러움에 의해 제한된 시간 동안 부드럽게 진화합니다. 따라서 오래된 기울기는 단순히 노이즈가 아니라 현재 기하학의 비용 없는 근사치 ("웜 스타트") 로 활용될 수 있습니다.
2. 암시적 지형 매끄러움 (Implicit Landscape Smoothing): 역설적으로, 더 큰 유한차분 단계 크기 ($\epsilon$) 는 최적화 지형을 암시적으로 매끄럽게 만들어 유효 매끄러움 상수 ($L_\epsilon$) 를 감소시킴으로써 수렴 안정성을 향상시킬 수 있습니다.

알고리즘 프레임워크

CoCD 는 전역 기울기 추정치 $\hat{g} \in \mathbb{R}^n$을 유지하기 위해 선입선출 (FIFO) 버퍼를 활용합니다.

• 순환 업데이트: 알고리즘은 좌표를 순환적으로 탐색합니다. 각 단계에서 $B$개의 함수 쿼리 (계산 예산) 를 수행하여 신선한 유한차분 추정을 사용하여 특정 좌표를 업데이트합니다.
• 모멘텀 및 감쇠: 전체 버퍼에 업데이트 전에 전역 모멘텀 감쇠 인자 $\gamma \in [0, 1]$가 적용됩니다.
  • $\gamma = 1.0$: 순환적으로 새로 고침될 때까지 모든 역사적 기울기를 보존합니다 (완벽한 기억).
  • $\gamma = 0.0$: 각 단계에서 버퍼를 비워 표준 블록 순환 좌표 하강법 (BCCD) 을 복원합니다.
  • $0 < \gamma < 1$: "소멸하는 기억"을 제공하여 매우 오래된 기울기는 지수적으로 억제하면서 최근의 기록은 유지합니다.
• 업데이트 규칙: 업데이트 방향은 학습률 $\alpha$로 스케일링된 하이브리드 기울기 추정치 $\hat{g}_t$로 형성됩니다: $x_{t+1} = x_t - \alpha \cdot \hat{g}_t$.
• 효율적인 구현: 구조화된 텐서 (예: CNN 커널) 를 처리할 때 과도한 메모리 복사 오버헤드 없이, CoCD 는 연속적인 1D 텐서 버퍼와 인플레이스 (in-place) 연산을 사용하여 가상화된 평탄화 메커니즘을 도입하며, 엄격한 메모리 발자국을 모델 복사본 하나로 유지합니다.

이론적 기여

본 논문은 CoCD 에 대한 엄밀한 이론적 근거를 제공합니다:

1. 웜 스타트가 적용된 BCCD 와의 동등성: 저자들은 CoCD 가 오래된 기울기 웜 스타트가 적용된 블록 순환 좌표 하강법 (BCCD) 과 수학적으로 동등함을 증명합니다. 이를 통해 공식적인 수렴 분석이 가능해집니다.
2. 근사 오차 상한: 본 논문은 근사 오차가 유효 매끄러움 상수 ($L_\epsilon$) 와 단계 크기 ($\delta$) 의 곱에 의존함을 보여주는 오차 상한을 유도합니다. 핵심적으로, 더 큰 $\epsilon$이 $L_\epsilon$을 감소시켜 지형을 효과적으로 매끄럽게 만들고, 안정성을 희생하지 않으면서 더 큰 단계 크기와 더 긴 기울기 역사를 허용함을 입증합니다.
3. 수렴 보장: Polyak-Łojasiewicz (PŁ) 조건과 약한 가정 하에서, CoCD 는 오래된 기울기 추정치로 작동하더라도 1 차 방법과 비교 가능한 선형 수렴을 달성합니다. 분석에 따르면, 전체 예산 경우 ($B=n$) 에 CoCD 는 표준 경사 하강법의 수렴 속도를 복원합니다.
4. 안정성 분석: 이론적 분석은 모멘텀 ($\gamma$) 이 오래된 기울기의 가중치를 지수적으로 억제하여 비볼록 지형에서의 하강을 안정화함을 보여줍니다.

실증 결과

실험은 회귀 (SARCOS) 및 분류 (MNIST, CIFAR-10) 작업 전반에 걸쳐 MLP, CNN, ResNet 아키텍처 (최대 27 만 개 매개변수) 에서 수행되었습니다.

• BCCD 대비 성능: CoCD 는 샘플 효율성과 최종 정확도 모두에서 표준 BCCD ($\gamma=0$) 를 크게 능가합니다.
  • CIFAR-10에서 BCCD 는 무작위 추측 영역 (10.13% 정확도) 에서 탈출하지 못했으나, CoCD 는 45.08% 의 정확도를 달성했습니다.
  • SARCOS에서 CoCD 는 최종 손실을 BCCD 의 188.73 에서 31.18 로 감소시켰습니다.
• 무작위화 방법 대비 안정성: SPSA 및 ZO-SGD 와 같은 무작위화 ZO 베이스라인과 비교하여 CoCD 는 우수한 안정성을 보였습니다. 무작위화 방법들은 SARCOS 회귀 작업에서 발산하는 반면, CoCD 는 안정화되었습니다.
• 효율성: CoCD 는 밀집 가우시안 샘플링의 오버헤드를 피함으로써 ZO-SGD 보다 약 2 배 빠른 벽시계 속도를 보여주었습니다 (에피소드당 8.1 초 vs 15.7 초).
• 하이퍼파라미터 민감도:
  • 매끄러움 반지름 ($\epsilon$): 더 큰 $\epsilon$ 값 (예: $\epsilon=1.0$) 은 안정성과 성능을 향상시켜 암시적 매끄러움 가설을 검증했습니다.
  • 모멘텀 ($\gamma$): 더 높은 $\gamma$ 값은 일관되게 수렴을 가속화했으며, 고차원 설정에서 일관성을 유지하는 데 필수적이었습니다.

중요성과 주장

본 논문은 결정론적이고 구조를 인지하는 업데이트가 경량 ZO 최적화를 위한 무작위화보다 우월한 대안이라고 주장합니다. 오래된 기울기를 계산적 자산이 아닌 부채로 재해석함으로써, CoCD 는 휴리스틱 효율성과 이론적 엄밀함 사이의 간극을 메웁니다.

주요 주장에는 다음이 포함됩니다:

• 자원 효율성: CoCD 는 무작위화 추정기에 내재된 높은 분산 없이 낮은 쿼리 복잡도 ($O(1)$ per step) 를 달성하여 메모리 제약이 있는 엣지 장치에 적합합니다.
• 이론적 통찰: 이 연구는 비볼록 지형에서 수렴을 개선하기 위해 더 큰 유한차분 단계 크기를 사용하여 암시적 매끄러움을 유도하는 것에 대한 역설적인 이론적 정당성을 제공합니다.
• 실용적 영향: 이 방법은 기울기에 접근할 수 없는 온디바이스 또는 블랙박스 시나리오에서 모델을 학습할 수 있는 실현 가능한 경로를 제공하며, 안정성과 수렴 속도 측면에서 기존 최첨단 ZO 방법들을 능가합니다.

저자들은 CoCD 가 현재 소형에서 중형 규모 모델에서 가장 효과적이며, 향후 연구는 더 큰 시스템을 위한 확장 전략 (예: 블록 단위 병렬화) 에 초점을 맞출 것이라고 언급했습니다.