Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
arXiv:2105.03793
Abstract
Many machine learning problems can be formulated as minimax problems such as Generative Adversarial Networks (GANs), AUC maximization and robust estimation, to mention but a few. A substantial amount of studies are devoted to studying the convergence behavior of their stochastic gradient-type algorithms. In contrast, there is relatively little work on their generalization, i.e., how the learning models built from training examples would behave on test examples. In this paper, we provide a comprehensive generalization analysis of stochastic gradient methods for minimax problems under both convex-concave and nonconvex-nonconcave cases through the lens of algorithmic stability. We establish a quantitative connection between stability and several generalization measures both in expectation and with high probability. For the convex-concave setting, our stability analysis shows that stochastic gradient descent ascent attains optimal generalization bounds for both smooth and nonsmooth minimax problems. We also establish generalization bounds for both weakly-convex-weakly-concave and gradient-dominated problems.
arXiv commentTo appear in ICML 2021 as Long Presentation
References in corpus (20)
- On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
- Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
- SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
- Data-Dependent Stability of Stochastic Gradient Descent
- Algorithmic stability and hypothesis complexity
- Generalization Properties and Implicit Regularization for Multiple Passes SGM
- A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent
- On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
- Efficient Algorithms for Smooth Minimax Optimization
- Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
- Variance-based regularization with convex objectives
- First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
- Learning with Non-Convex Truncated Losses by SGD
- Stochastic Hamiltonian Gradient Methods for Smooth Games
- Toward Better Generalization Bounds with Locally Elastic Stability
- Hypothesis Set Stability and Generalization
- Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent
- Generalization Bounds for Stochastic Saddle Point Problems
- Train simultaneously, generalize better: Stability of gradient-based minimax learners
- Learning with Gradient Descent and Weakly Convex Losses