변질된 기울기를 안정적인 기울기로 전환: 경량 제로차원 최적화를 위한 암묵적 경관 평활화와 조화로운 좌표 하강법

Turning Stale Gradients into Stable Gradients: Coherent Coordinate Descent with Implicit Landscape Smoothing for Lightweight Zeroth-Order Optimization

제로차원 최적화는 역전파가 불가능한 경우, 예를 들어 메모리 제약이 있는 온디바이스 학습 및 블랙박스 최적화와 같은 시나리오에서 매우 중요합니다. 그러나 기존 방법들은 샘플 효율성이 낮거나(예: 표준 유한 차분법) 랜덤 추정으로 인해 높은 분산을 나타내는(예: 랜덤 서브스페이스 방법)이라는 명확한 상충 관계에 직면합니다. 본 연구에서는 결정론적이고 샘플 효율적이며 예산에 민감한 제로차원 최적화 알고리즘인 조화로운 좌표 하강법(Coherent Coordinate Descent, CoCD)을 제안합니다. 이론적으로, 기울기 일관성이라는 개념을 정의하고 CoCD가 "웜 스타트(warm starts)"를 갖는 블록 순환 좌표 하강법(Block Cyclic Coordinate Descent, BCCD)과 동등하다는 것을 보여줍니다. 이 메커니즘은 과거(변질된) 기울기를 단순한 부담이 아닌 계산 자원으로 전환시켜, 단계별로 O(1)의 쿼리 복잡도를 유지하면서 전역적인 하강 방향을 확보합니다. 또한, 도출된 오차 경계는 직관에 반하는 통찰력을 제공합니다. 즉, 더 큰 유한 차분 단계 크기는 효과적인 평활 상수(smoothness constant)를 줄여 최적화 경관에 암묵적인 평활 효과를 유도하여 수렴 안정성을 향상시킬 수 있습니다. MLP, CNN 및 ResNet 아키텍처(최대 27만 개의 파라미터)에 대한 실험 결과, CoCD는 샘플 효율성과 수렴 손실/정확도 측면에서 BCCD보다 훨씬 뛰어난 성능을 보이며, 랜덤 제로차원 방법보다 우수한 안정성을 나타냅니다. 우리의 결과는 결정론적이고 구조에 민감한 업데이트가 경량 제로차원 최적화를 위한 랜덤화보다 우수한 대안을 제공한다는 것을 시사합니다.

Zeroth-Order (ZO) optimization is pivotal for scenarios where backpropagation is unavailable, such as memory-constrained on-device learning and black-box optimization. However, existing methods face a stark trade-off: they are either sample-inefficient (e.g., standard finite differences) or suffer from high variance due to randomized estimation (e.g., random subspace methods). In this work, we propose Coherent Coordinate Descent (CoCD), a deterministic, sample-efficient, and budget-aware ZO optimizer. Theoretically, we formalize the notion of gradient coherence and demonstrate that CoCD is equivalent to Block Cyclic Coordinate Descent (BCCD) with ``warm starts,'' effectively converting historical (stale) gradients from a liability into a computational asset. This mechanism enables $O(1)$ query complexity per step while maintaining global descent directions. Furthermore, we derive error bounds revealing a counter-intuitive insight: larger finite-difference step sizes can induce an implicit smoothing effect on the optimization landscape by reducing the effective smoothness constant, thereby improving convergence stability. Experiments on MLP, CNN, and ResNet architectures (up to 270k parameters) demonstrate that CoCD significantly outperforms BCCD in terms of sample efficiency and convergence loss/accuracy, and exhibits superior stability over randomized ZO methods. Our results suggest that deterministic, structure-aware updates offer a superior alternative to randomization for lightweight ZO optimization.