적응형 경사 하강법(Adaptive Gradient Methods)은 헤비테일 노이즈(Heavy-Tailed Noise) 하에서 수렴할 수

현대 머신러닝 (Machine Learning)의 많은 작업에서 최적화 (Optimization) 과정 중 헤비테일 경사 노이즈 (Heavy-tailed gradient noise)가 포함되는 것이 관찰됩니다. 이러한 현실적이고 까다로운 설정을 관리하기 위해, 1차 알고리즘 (First-order algorithms)의 수렴을 보장하고자 경사 클리핑 (Gradient clipping) 및 경사 정규화 (Gradient normalization)와 같은 새로운 메커니즘들이 도입되었습니다. 그러나 인기 있는 $\mathtt{Adam}$ 및 $\mathtt{AdamW}$를 포함하는 현대 옵티마이저 (Optimizer)의 유명한 부류인 적응형 경사 하강법 (Adaptive gradient methods)은 위에서 언급한 추가적인 연산 없이도 종종 잘 작동합니다. 따라서 알고리즘의 변경 없이 적응형 경사 하강법이 헤비테일 노이즈 하에서 수렴할 수 있는지 묻는 것은 자연스럽습니다. 본 연구에서는 적응형 경사 하강법의 기원인 $\mathtt{AdaGrad}$라는 특수한 사례를 조사함으로써 이 질문에 답하기 위한 첫 번째 발걸음을 내딛습니다. 우리는 테일 지수 (Tail index) $p$가 $4/3 < p \leq 2$를 만족할 때, 비볼록 최적화 (Non-convex optimization) 환경에서 $\mathtt{AdaGrad}$에 대한 최초의 증명 가능한 수렴 속도 (Convergence rate)를 제공합니다. 특히, 이 결과는 $p$에 대한 사전 지식을 요구하지 않고 달성되었으므로 테일 지수에 적응적 (Adaptive)입니다. 또한, 우리는 알고리즘 의존적 하한 (Algorithm-dependent lower bound)을 개발하여, 헤비테일 최적화 (Heavy-tailed optimization)에 대한 기존의 미니맥스 속도 (Minimax rate)가 $\mathtt{AdaGrad}$에 의해 달성될 수 없음을 시사합니다. 마지막으로, 이론적 연구에서 $\mathtt{AdaGrad}$의 대중적인 변형인 $\mathtt{AdaGrad} ext{-}\mathtt{Norm}$을 고려하며, 추가적인 완만한 가정 하에 모든 $1 < p \leq 2$에 대해 유효한 개선된 속도를 보여줍니다.