Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning

2021/12/22 by Chen, Ziyi, Ma, Shaocong, Zhou, Yi · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2112.11663

Abstract

Alternating gradient-descent-ascent (AltGDA) is an optimization algorithm that has been widely used for model training in various machine learning applications, which aims to solve a nonconvex minimax optimization problem. However, the existing studies show that it suffers from a high computation complexity in nonconvex minimax optimization. In this paper, we develop a single-loop and fast AltGDA-type algorithm that leverages proximal gradient updates and momentum acceleration to solve regularized nonconvex minimax optimization problems. By leveraging the momentum acceleration technique, we prove that the algorithm converges to a critical point in nonconvex minimax optimization and achieves a computation complexity in the order of O(κ^(11)/(6)ε^-2), where ε is the desired level of accuracy and κ is the problem's condition number. Such a computation complexity improves the state-of-the-art complexities of single-loop GDA and AltGDA algorithms (see the summary of comparison in \Creftable1). We demonstrate the effectiveness of our algorithm via an experiment on adversarial deep learning.

Cited by

• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization

Related

• GDA-AM: On the effectiveness of solving minimax optimization via Anderson Acceleration
• Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization
• Fundamental Benefit of Alternating Updates in Minimax Optimization