Stochastic gradient descent-ascent (SGDA) is one of the main workhorses for solving finite-sum minimax optimization problems. Most practical implementations of SGDA randomly reshuffle components and sequentially use them (i.e., without-replacement sampling); however, there are few theoretical results on this approach for minimax algorithms, especially outside the easier-to-analyze (strongly-)monotone setups. To narrow this gap, we study the convergence bounds of SGDA with random reshuffling (SGDA-RR) for smooth nonconvex-nonconcave objectives with Polyak-Łojasiewicz (PŁ) geometry. We analyze both simultaneous and alternating SGDA-RR for nonconvex-PŁ and primal-PŁ-PŁ objectives, and obtain convergence upper bounds faster than with-replacement SGDA. Our rates also extend to mini-batch SGDA-RR, recovering known rates for full-batch gradient descent-ascent (GDA). Lastly, we present a comprehensive lower bound for two-time-scale GDA, which matches the full-batch rate for primal-PŁ-PŁ case.
확률적 경사 하강 상승법(stochastic gradient descent-ascent, SGDA)은 성분 함수들의 유한합으로 표현되는 목적함수에 대한 최대최소화 문제를 풀기 위한 대표적인 알고리즘이다. 일반적으로 SGDA를 구현할 때 성분 함수들의 순서를 무작위로 비복원 추출하여 재배열(random reshuffling, RR)하곤 한다. 그러나 비복원 추출 방식을 고려한 최대최소화 알고리즘의 수렴성 연구는 복원 추출 기반 결과에 비해 알려진 바가 거의 없다. 본 연구에서는 무작위 셔플링 기반 SGDA(이하 SGDA-RR)의 수렴 속도를 분석하였다. 립시츠 매끄러움과 폴랴크-워야시에비치(Polyak-Łojasiewicz, PŁ) 조건 등의 약한 가정하에서, 비볼록-비오목 목적함수를 대상으로 하여, 동시 갱신 및 교차 갱신 방식을 포괄하는 수렴 속도를 얻었다. 그 결과, SGDA-RR의 수렴 속도가 복원 추출 기반 SGDA보다 빠름을 보였다. 또한, 해당 결과를 임의의 미니-배치 크기에 대해 확장하였다. 이 확장된 결과로부터 모든 성분 함수를 동시에 이용하는 비확률적 경사 하강 상승법의 수렴 속도를 특수한 경우로서 얻을 수 있었으며, 이 수렴 속도의 상계는 특정한 가정하에 그 하계와 상응함을 확인하였다.
