확률적 서브그레이디언트 방법 (Stochastic subgradient method)의 마지막 반복(Last Iterate)에 대한 새로운 경계

우리는 1차원 볼록 Lipschitz 목적 함수 (one-dimensional convex Lipschitz objectives)에 대한 확률적 서브그레이디언트 방법 (stochastic subgradient method)의 마지막 반복 (last iterate)을 연구합니다. 고정된 지평 (horizon) $n$에 대해, 우리는 표준 고정 스텝사이즈 (fixed stepsizes) $\eta=\Theta(1/\sqrt{n})$를 고려합니다. 우리는 이러한 스텝사이즈 정책 하에서, 균등하게 유계된 분산 (uniformly bounded variance)을 가진 가법적 i.i.d. 서브그레이디언트 노이즈 (additive i.i.d. subgradient noise) 조건일 때, 마지막 반복이 $1/\sqrt{n}$ 차수의 최적화 오차 (optimization error)를 특징으로 함을 증명하며, 이를 통해 기존의 일반적인 경계 (generic bounds)에 존재하던 추가적인 $(\log n)$ 인자를 제거합니다. 반면, 우리는 i.i.d. 가정이 없을 경우 최적화 오차가 $(\log n)/\sqrt{n}$ 차수가 될 수 있음을 보여줍니다. 따라서, 균등하게 유계된 분산 가정만으로는 SsGM의 마지막 반복이 1차원에서도 차선책 (suboptimal)임을 나타내며, 이는 Koren과 Segal이 COLT 2020에서 제기한 미해결 문제 (open problem)를 부정적으로 해결합니다.