High Probability Generalization Bounds for Minimax Problems with Fast Rates
Minimax problems are receiving an increasing amount of attention in a wide range of applications in machine learning (ML), for instance, reinforcement learning, robust optimization, adversarial learning, and distributed computing, to mention but a few. Current studies focus on the fundamental understanding of general minimax problems with an emphasis on convergence behavior. As a comparison, there is far less work to study the generalization performance. Additionally, existing generalization bounds are almost all derived in expectation, and the high probability bounds are all presented in the slow order $\mathcal{O}\left( 1/\sqrt{n}\right)$, where $n$ is the sample size. In this paper, we provide improved generalization analyses for almost all existing generalization measures of minimax problems, which enables the minimax problems to establish sharper bounds of order $\mathcal{O}\left( 1/n \right)$, significantly, with high probability. We then use the improved learning bounds to establish $\mathcal{O}\left(1/n \right)$ high probability generalization bounds for classical empirical saddle point (ESP) solution and several popular gradient-based optimization algorithms, including gradient descent ascent (GDA), stochastic gradient descent ascent (SGDA), proximal point method (PPM), extra-gradient (EG), and optimistic gradient descent ascent (OGDA). Overall, we provide a comprehensive understanding of sharper generalization bounds of minimax problems.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed ComputingGeneralization BoundsVocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
Towards Sharper Risk Bounds for Minimax Problems
Minimax problems have achieved success in machine learning such as adversarial training, robust optimization, reinforcement learning. For theoretical analysis, current optimal excess risk bounds, which are composed by ge…
Generalization BoundsStability and Generalization of Stochastic Gradient Methods for Minimax Problems
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 devot…
Generalization BoundsStability and Generalization for Markov Chain Stochastic Gradient Methods
Recently there is a large amount of work devoted to the study of Markov chain stochastic gradient methods (MC-SGMs) which mainly focus on their convergence analysis for solving minimization problems. In this paper, we pr…
Generalization BoundsLearning TheoryHigh-probability minimax lower bounds
The minimax risk is often considered as a gold standard against which we can compare specific statistical procedures. Nevertheless, as has been observed recently in robust and heavy-tailed estimation problems, the inhere…
Density EstimationregressionLexicographically Fair Learning: Algorithms and Generalization
We extend the notion of minimax fairness in supervised learning problems to its natural conclusion: lexicographic minimax fairness (or lexifairness for short). Informally, given a collection of demographic groups of inte…
FairnessGeneralization Bounds