Stochastic Gradient Descent ($\textsf{SGD}$)는 유리한 이론적 보장을 가진 가장 고전적인 최적화 알고리즘 중 하나이지만, $\textsf{SGD}$의 실제 구현은 잘 알려진 형태와 미묘하게 다르며 종종 Shuffling Stochastic Gradient Descent ($\textsf{Shuffling SGD}$)라고 불립니다. $\textsf{Shuffling SGD}$에서 특히 인기 있는 전략은 Random Reshuffling ($\textsf{RR}$)로, 이는 수많은 실험을 통해 큰 경험적 성공을 거두었습니다. 강력한 성능에도 불구하고, $\textsf{RR}$은 이론적 뒷받침의 부족으로 인해 오랫동안 휴리스틱 (heuristic)으로 간주되어 왔습니다. 지난 10년 동안 사람들은 마침내 $\textsf{RR}$에 대해 증명 가능한 수렴 속도 (convergence rates)를 확립하였고, 이로써 관찰된 우수성을 정당화했습니다. 그러나 매끄러운 볼록 최적화 (smooth convex optimization)에 있어서, $\textsf{RR}$의 수렴 이론에는 오늘날까지 두 가지 의구심이 남아 있습니다. 더 정확하게는, 현재의 이론에 따르면 $\textsf{RR}$ 하에서의 $\textsf{Shuffling SGD}$는 단계 크기 (stepsize)가 목적 함수의 항의 개수(또는 데이터 포인트의 개수)인 $n$에 비례하는 $1/n$ 임계값보다 작을 때만 수렴합니다. 결과적으로, $\textsf{RR}$ 하에서의 $\textsf{Shuffling SGD}$의 최적으로 조정된 이론적 속도는 에포크 (epoch)의 수가 $n$에 비례하는 또 다른 임계값보다 작을 때 $\textsf{SGD}$보다 엄격하게 더 나쁩니다. 이 두 가지 제한 사항은 기존 이론의 적용 가능성을 심하게 제한하며 실제 사례와의 중대한 불일치를 남깁니다. 본 연구에서는 처음으로, 임의의 합리적인 단계 크기 하에서 임의의 유한한 에포크 이후 매끄러운 볼록 최적화에서 $\textsf{RR}$이 $\textsf{SGD}$를 압도한다는 것을 증명함으로써, 오랫동안 해결되지 않은 문제를 해결합니다.