New stochastic algorithms for minimax-structured nonconvex nonsmooth optimization and applications in machine learning

Rensselaer Polytechnic Institute, Troy NY

Investigators

Abstract

This project focuses on problems arising in game theory, statistics, engineering, and machine learning. Research on minimax problems dates back almost a century, when von Neumann published his minimax theorem about zero-sum games. The past several years have witnessed tremendous research interest in solving minimax problems, motivated by training deep learning models, including generative artificial intelligence and robust machine learning. Though well-trained deep learning models can deliver high-quality performance in many tasks, they are often vulnerable to adversarial attacks. Using such models can cause serious safety and security risks; thus, improving their robustness is very important. Most existing methods for solving minimax problems require certain strong conditions that do not hold for modern applications, such as training robust deep learning models. This project will develop new optimization algorithms for solving minimax problems, which can deliver guaranteed stability and reliability under weaker and more practical conditions. Software packages will be developed and released for public use to benefit both academic and industry researchers. The results from the project will be integrated into regularly offered or topical courses at RPI for both undergraduate and graduate students. Different algorithms will be designed by leveraging the structures of the considered minimax problems, and analysis will be conducted as well to show the convergence of these algorithms and their complexity. For solving nonconvex nonsmooth minimax problems that satisfy a certain regularity condition for the dual part, a momentum-accelerated primal-dual stochastic subgradient method (PDSsG) will be investigated, and a Moreau-envelope based smoothed PDSsG, as an alternative, will also be explored. For solving nonconvex-nonconcave nonsmooth minimax problems that do not satisfy regularity conditions, new approaches will be developed by using the log-exponential smoothing function to approximate the maximization part. On solving problems that involve too-big data, new distributed methods will be designed under the setting of either a complete network or an incomplete connected network. Low-precision communication and error-compensation techniques will be used, for the first time, to solve nonconvex minimax problems, to save communication, and achieve fast convergence. These investigations are expected to invent new analysis techniques and lead to novel and efficient algorithms for solving large-scale minimax structured optimization. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.