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

요약

본 연구는 헤비테일 경사 노이즈가 존재하는 비볼록 최적화 환경에서 적응형 경사 하강법의 수렴 가능성을 분석합니다. 특히 AdaGrad가 테일 지수 $p$에 대한 사전 지식 없이도 $4/3 < p ext{ } ext{leq} ext{ } 2$ 범위에서 수렴함을 최초로 증명하였으며, AdaGrad-Norm의 개선된 수렴 속도 또한 제시합니다.

핵심 포인트

• 헤비테일 경사 노이즈 환경에서 AdaGrad의 비볼록 최적화 수렴 속도를 최초로 증명함
• 제시된 수렴 결과는 테일 지수 $p$에 대한 사전 정보가 필요 없는 적응적(Adaptive) 특성을 가짐
• AdaGrad가 기존의 미니맥스 속도(Minimax rate)를 달성할 수 없음을 시사하는 알고리즘 의존적 하한을 개발함
• AdaGrad-Norm 변형 모델이 $1 < p ext{ } ext{leq} ext{ } 2$ 범위에서 더 개선된 수렴 속도를 보임을 확인함