Solving Non-Concave Min-Max Problems with Fast Polynomial Gap and Duality

Bookmarks

Keep Up With Latest Trending Papers. Computer Science, AI and Machine Learning and more.Subscribe

Fast Objective & Duality Gap Convergence for Nonconvex-Strongly-Concave Min-Max Problems

We propose and analyze a generic framework of proximal epoch-based method with many well-known stochastic updates embeddable.

Fast convergence is established in terms of both {\bf the primal objective gap and the duality gap}.

Our analysis is based on a novel lyapunov function consisting of the primal objective gap and the duality gap of a regularized function.

Our results are more comprehensive with improved rates that have better dependenceon the condition number under different assumptions.

We also conduct deep and non-deep learning experiments to verify the effectiveness of our methods.

Authors

Zhishuai Guo, Yan Yan, Zhuoning Yuan, Tianbao Yang

◐ Recommended Follows