SVRG의 학습 이론: 일반화 및 수렴 분석

Learning Theory of the SVRG: Generalization and Convergence Analysis

분산 감소(Variance Reduction, VR) 방법은 점진적으로 분산을 줄이는 확률적 경사를 사용하여 효율성이 뛰어나기 때문에 머신러닝 분야에서 대규모 최적화 문제를 해결하는 데 널리 사용됩니다. 기존의 VR 방법에 대한 이론적 연구는 주로 수렴 분석에 초점을 맞추고 있으며, 일반화 성능에 대한 탐색은 부족한 실정입니다. 본 논문에서는 알고리즘 안정성(algorithmic stability)의 관점에서 대표적인 VR 방법인 확률적 분산 감소 경사법(Stochastic Variance Reduced Gradient, SVRG)에 대한 최초의 의미 있는 일반화 분석을 제시합니다. 특히, SVRG의 알고리즘 구조를 활용하여 볼록 및 강하게 볼록 환경에서 SVRG의 엄격한 안정성 바운드를 도출했습니다. 얻어진 바운드는 데이터 의존적이며, 학습 오류가 전체 과정에 걸쳐 반영됩니다. 본 연구는 최적화와 일반화 간의 상호작용을 명확히 밝혀냄으로써, 볼록 및 강하게 볼록 환경 모두에서 최적의 과잉 모집단 위험(excess population risk) 바운드를 제공합니다. 저희의 접근 방식은 기존의 확률적 알고리즘 분석과 크게 다르며, SVRG 업데이트를 SGD와 유사한 단계에 더하여 평균이 0인 보정 항을 추가하고, 기준점(reference points)에서 발생하는 추가적인 경사 항을 흡수하기 위해 새로운 리아푸노프 함수(Lyapunov functions)를 도입합니다. 저희의 분석 프레임워크는 다른 VR 방법에도 일반화될 수 있으며, 잘 알려진 확률적 평균 경사 가속법(Stochastic Average Gradient Accelerated, SAGA) 방법을 통해 이를 입증했습니다.

Variance reduction (VR) methods employ stochastic gradients with decreasing variance, and they have been widely applied to solve large-scale optimization problems in machine learning because of their efficiency. Existing theoretical studies of VR methods are mainly focused on the convergence analysis, leaving the generalization behavior largely unexplored. In this paper, we bridge this gap by developing the first non-vacuous generalization analysis of the representative VR method: Stochastic Variance Reduced Gradient (SVRG), through the lens of algorithmic stability. In particular, we establish sharp stability bounds of the SVRG in both convex and strongly convex settings by exploiting its algorithmic structure. The obtained bounds are data-dependent, because the training errors are incorporated along the trajectory. Our analysis clarifies the interplay between optimization and generalization, leading to optimal excess population risk bounds in both settings. Our approach differs substantially from existing analyses of stochastic algorithms in the sense that we decompose the SVRG update as an SGD-like step plus a zero-mean correction term and then introduce novel Lyapunov functions to absorb the additional gradient terms induced by the reference points. Our analytical framework can be generalized to other VR methods, and we demonstrate the generalization by the well-known Stochastic Average Gradient Accelerated (SAGA) method.