최고차 이분법 최소 극대 최적화의 안정성과 일반화 성능에 대한 연구

On the Stability and Generalization of First-order Bilevel Minimax Optimization

최근, 최고차 이분법 최적화 및 최고차 이분법 최소 극대 최적화는 하이퍼파라미터 최적화 및 강화 학습을 포함한 다양한 머신러닝 작업에 대한 통합 프레임워크로 부상했습니다. 기존 연구는 주로 경험적 효율성과 수렴 보장에 초점을 맞추고 있으며, 이러한 알고리즘이 얼마나 잘 일반화되는지에 대한 중요한 이론적 공백이 존재합니다. 이러한 격차를 해소하기 위해, 본 연구는 하위 레벨에서 최소 극대 문제를 갖는, 최적화 기반의 최고차 이분법 최소 극대 솔버에 대한 최초의 체계적인 일반화 성능 분석을 제공합니다. 구체적으로, 알고리즘 안정성 논리를 활용하여, 싱글 타임스케일 확률적 경사하강-상승법 및 두 가지 타임스케일 확률적 경사하강-상승법의 두 가지 변형을 포함한 세 가지 대표적인 알고리즘에 대한 정밀한 일반화 성능 경계를 도출했습니다. 우리의 결과는 알고리즘 안정성, 일반화 성능 격차 및 실제 환경 간의 정확한 상호 관계를 보여줍니다. 또한, 광범위한 실험적 평가를 통해, 최고차 이분법 최소 극대 구조를 갖는 실제 최적화 작업에서 우리의 이론적 통찰력을 뒷받침합니다.

Bilevel optimization and bilevel minimax optimization have recently emerged as unifying frameworks for a range of machine-learning tasks, including hyperparameter optimization and reinforcement learning. The existing literature focuses on empirical efficiency and convergence guarantees, leaving a critical theoretical gap in understanding how well these algorithms generalize. To bridge this gap, we provide the first systematic generalization analysis for first-order gradient-based bilevel minimax solvers with lower-level minimax problems. Specifically, by leveraging algorithmic stability arguments, we derive fine-grained generalization bounds for three representative algorithms, including single-timescale stochastic gradient descent-ascent, and two variants of two-timescale stochastic gradient descent-ascent. Our results reveal a precise trade-off among algorithmic stability, generalization gaps, and practical settings. Furthermore, extensive empirical evaluations corroborate our theoretical insights on realistic optimization tasks with bilevel minimax structures.