When and Why SignSGD Outperforms SGD: A Theoretical Study Based on

SignSGD 와 Muon 과 같은 시그널 기반 최적화 알고리즘은 대규모 foundation model 훈련에서의 놀라운 성능으로 인해 큰 주목을 받고 있습니다. 이러한 경험적 성공에도 불구하고, 우리는 여전히 왜 그리고 언제 이러한 시그널 기반 방법들이 vanilla SGD 를 능가하는지에 대한 이론적 이해가 부족합니다. 핵심적인 장애물은 표준적인 smoothness 와 finite variance 조건 하에서 SGD 는 $\ell_2$-norm 으로 측정된 stationary point 탐색에 대해 minimax optimal 이며, 이는 표준 설정에서 시그널 기반 방법의 복잡성 향상을 근본적으로 막아놓는다는 점입니다. 이를 극복하기 위해 우리는 $\ell_1$-norm stationarity, $\ell_
fty$-smoothness, 그리고 separable noise 모델을 활용하는 시그널 기반 옵티마이저를 분석했습니다. 이는 signed updates 의 좌표별 특성을 더 잘 포착할 수 있습니다. 이러한 고유한 문제 기하학 하에서 우리는 SignSGD 에 대해 일치된 상한과 하한을 유도하고, SignSGD 가 확실히 SGD 를 능가하는 문제 클래스를 명시적으로 특징화했습니다. 구체적으로, 우리는 \emph{SignSGD 의 상한} 과 \emph{SGD 의 하한} 을 비교하여, SignSGD 가 \emph{sparse noise} 하에서 $d$ (문제 차원) 로 복잡성을 효과적으로 줄인다는 것을 보여줍니다. 또한, 우리는 이 프레임워크를 행렬 도메인으로 확장하고 Muon 옵티마이저에 대한 등가적 최적 하한을 제공하여, 시그널 연산자를 행렬로 확장해도 차원성과 함께 이 최적 스케일을 유지함을 증명했습니다. 마지막으로, 우리는 이론적 상한과 실제를 연결하여, SignSGD 의 이론적 우위가 124M 파라미터 GPT-2 모델의 pretraining 과정에서 더 빠른 수렴을 정확히 예측한다는 것을 입증했습니다.