We study convergence lower bounds of without-replacement stochastic gradient descent (SGD) for solving smooth (strongly-)convex finite-sum minimization problems. Unlike most existing results focusing on lower bounds for SGD with Random Reshuffling where the random permutation is chosen independently on each epoch to sample the component function in each iterate, we seek bounds applicable to arbitrary permutation-based SGD. This method includes all variants that carefully select the best permutation beyond Random Reshuffling. Notably, our bounds significantly improve upon existing lower bounds and tightly match the upper bounds shown for a recently proposed algorithm called GraB, across all factors including the number of component functions $n$, the number of epochs $K$, and the condition number $\kappa$. We also extend our bounds to arbitrary weighted average iterates, providing a generalized result that covers the final iterate.
본 학위 논문에서는 유한합 최소화 문제를 해결하기 위한 비복원 추출 기반(without-replacement) 확률적 경사 하강법(Stochastic Gradient Descent, 이하 SGD)의 수렴 속도 하한에 대하여 다룬다. 기존 연구들에서 주로 매 epoch마다 무작위 구성 함수 순열을 뽑고 이 순열에 따라 SGD 알고리즘을 수행하는 무작위 셔플링 기반 SGD의 수렴 속도 하한을 분석했던 것에 비해, 본 연구에서는 임의 순열 기반 SGD에 대한 수렴 속도 하한을 제시한다. 이는 무작위 셔플링 기반 SGD를 넘어, 임의로 순열을 고르는 방법까지 포괄하는 SGD 알고리즘이다. 분석 결과, 본 연구에서 제시하는 무작위 셔플링 기반 SGD의 수렴 속도 하한이 기존에 알려진 수렴 속도 하한을 크게 개선하는 것으로 나타났다. 이에 더해, 최근 제안된 비복원 추출 기반 SGD의 일종인 GraB 알고리즘이 제시하는 수렴 속도 상한과 비교하였을 때, 구성 함수 개수 $n$, epoch 횟수 $K$, 조건수(condition number) $\kappa$를 포함한 모든 인자에 대해 일치하는 것을 증명하였다. 마지막으로, 이 결과가 최종 iterate을 포함하는 임의 가중 평균 iterate에 대한 하한으로 확장될 수 있음을 확인하였다.
