# A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization arXiv: https://arxiv.org/abs/2207.05650 ยท HTML: https://mlsanity.com/paper/2207.05650/ ## Key facts - Cited by 12 papers in the map (data through 14 Oct 2026). - Builds on 21 of its 38 references that are in the map. - First posted on arXiv 12 Jul 2022. ## Builds on (most cited first, 21 of 21) - [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021) - [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019) - [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019) - [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019) - [Conservative Safety Critics for Exploration](https://mlsanity.com/paper/2010.14497/) (2020) - [Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems](https://mlsanity.com/paper/1410.1390/) (2014) - [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020) - [Convergent Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/1910.12156/) (2019) - [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019) - [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019) - [An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints](https://mlsanity.com/paper/1906.11357/) (2019) - [Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints](https://mlsanity.com/paper/1908.01871/) (2019) - [Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming](https://mlsanity.com/paper/1711.05812/) (2017) - [Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization](https://mlsanity.com/paper/2007.01284/) (2020) - [Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints](https://mlsanity.com/paper/1908.00131/) (2019) - [Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs](https://mlsanity.com/paper/1802.03504/) (2018) - [ECC: Platform-Independent Energy-Constrained Deep Neural Network Compression via a Bilinear Regression Model](https://mlsanity.com/paper/1812.01803/) (2018) - [A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization](https://mlsanity.com/paper/1812.10229/) (2018) - [A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization](https://mlsanity.com/paper/2006.16440/) (2020) - [Moreau Envelope Augmented Lagrangian Method for Nonconvex Optimization with Linear Constraints](https://mlsanity.com/paper/2101.08519/) (2021) - [Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems](https://mlsanity.com/paper/2006.08048/) (2020) ## Built on by (most cited first, 12 of 12) - [Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023) - [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023) - [A first-order augmented Lagrangian method for constrained minimax optimization](https://mlsanity.com/paper/2301.02060/) (2023) - [Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes](https://mlsanity.com/paper/2306.07001/) (2023) - [A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees](https://mlsanity.com/paper/2301.03139/) (2023) - [Federated Learning with Convex Global and Local Constraints](https://mlsanity.com/paper/2310.10117/) (2023) - [The inexact power augmented Lagrangian method for constrained nonconvex optimization](https://mlsanity.com/paper/2410.20153/) (2024) - [Primal-Dual Methods for Nonsmooth Nonconvex Optimization with Orthogonality Constraints](https://mlsanity.com/paper/2604.04130/) (2026) - [Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications](https://mlsanity.com/paper/2306.05655/) (2023) - [A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints](https://mlsanity.com/paper/2405.01984/) (2024) - [A first-order method for nonconvex-strongly-concave constrained minimax optimization](https://mlsanity.com/paper/2512.22909/) (2025) - [Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making](https://mlsanity.com/paper/2606.07088/) (2026) ## Abstract (arXiv) Nonconvex constrained optimization problems can be used to model a number of machine learning problems, such as multi-class Neyman-Pearson classification and constrained Markov decision processes. However, such kinds of problems are challenging because both the objective and constraints are possibly nonconvex, so it is difficult to balance the reduction of the loss value and reduction of constraint violation. Although there are a few methods that solve this class of problems, all of them are double-loop or triple-loop algorithms, and they require oracles to solve some subproblems up to certain accuracy by tuning multiple hyperparameters at each iteration. In this paper, we propose a novel gradient descent and perturbed ascent (GDPA) algorithm to solve a class of smooth nonconvex inequality constrained problems. The GDPA is a primal-dual algorithm, which only exploits the first-order information of both the objective and constraint functions to update the primal and dual variables in an alternating way. The key feature of the proposed algorithm is that it is a single-loop algorithm, where only two step-sizes need to be tuned. We show that under a mild regularity condition GDPA is able to find Karush-Kuhn-Tucker (KKT) points of nonconvex functional constrained problems with convergence rate guarantees. To the best of our knowledge, it is the first single-loop algorithm that can solve the general nonconvex smooth problems with nonconvex inequality constraints. Numerical results also showcase the superiority of GDPA compared with the best-known algorithms (in terms of both stationarity measure and feasibility of the obtained solutions).