# Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization

arXiv: https://arxiv.org/abs/1908.02734 · HTML: https://mlsanity.com/paper/1908.02734/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2019.

## Built on by (most cited first, 30 of 38)

- [Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process](https://mlsanity.com/paper/2110.10351/) (2021)
- [Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization](https://mlsanity.com/paper/2212.09513/) (2022)
- [Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023)
- [A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minima](https://mlsanity.com/paper/2203.01123/) (2022)
- [A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/2207.05650/) (2022)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [A safe exploration approach to constrained Markov decision processes](https://mlsanity.com/paper/2312.00561/) (2023)
- [Independent Learning in Constrained Markov Potential Games](https://mlsanity.com/paper/2402.17885/) (2024)
- [Stochastic Methods for AUC Optimization subject to AUC-based Fairness Constraints](https://mlsanity.com/paper/2212.12603/) (2022)
- [A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization](https://mlsanity.com/paper/2501.19214/) (2025)
- [Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints](https://mlsanity.com/paper/2504.15243/) (2025)
- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [Data-Driven Minimax Optimization with Expectation Constraints](https://mlsanity.com/paper/2202.07868/) (2022)
- [Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints](https://mlsanity.com/paper/2504.07607/) (2025)
- [Stochastic Compositional Optimization with Compositional Constraints](https://mlsanity.com/paper/2209.04086/) (2022)
- [Fairness Uncertainty Quantification: How certain are you that the model is fair?](https://mlsanity.com/paper/2304.13950/) (2023)
- [A Retention-Centric Framework for Continual Learning with Guaranteed Model Developmental Safety](https://mlsanity.com/paper/2410.03955/) (2024)
- [Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems](https://mlsanity.com/paper/2209.04604/) (2022)
- [Primal Methods for Variational Inequality Problems with Functional Constraints](https://mlsanity.com/paper/2403.12859/) (2024)
- [Projection-Free Functional Constrained Optimization for Risk Aversion and Sparsity Control](https://mlsanity.com/paper/2210.05108/) (2022)
- [Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2404.09438/) (2024)
- [Enforcing Fair Predicted Scores on Intervals of Percentiles by Difference-of-Convex Constraints](https://mlsanity.com/paper/2505.12530/) (2025)
- [On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization](https://mlsanity.com/paper/2507.23155/) (2025)
- [GBM-based Bregman Proximal Algorithms for Constrained Learning](https://mlsanity.com/paper/2308.10767/) (2023)
- [Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions](https://mlsanity.com/paper/2502.19764/) (2025)
- [First-order methods for stochastic and finite-sum convex optimization with deterministic constraints](https://mlsanity.com/paper/2506.20630/) (2025)
- [Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity](https://mlsanity.com/paper/2607.08954/) (2026)
- [Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints](https://mlsanity.com/paper/2212.11143/) (2022)
- [First-order methods for Stochastic Variational Inequality problems with Function Constraints](https://mlsanity.com/paper/2304.04778/) (2023)
- [Accelerated Neural Network Training with Rooted Logistic Objectives](https://mlsanity.com/paper/2310.03890/) (2023)

## Abstract (arXiv)

Functional constrained optimization is becoming more and more important in machine learning and operations research. Such problems have potential applications in risk-averse machine learning, semisupervised learning, and robust optimization among others. In this paper, we first present a novel Constraint Extrapolation (ConEx) method for solving convex functional constrained problems, which utilizes linear approximations of the constraint functions to define the extrapolation (or acceleration) step. We show that this method is a unified algorithm that achieves the best-known rate of convergence for solving different functional constrained convex composite problems, including convex or strongly convex, and smooth or nonsmooth problems with a stochastic objective and/or stochastic constraints. Many of these rates of convergence were in fact obtained for the first time in the literature. In addition, ConEx is a single-loop algorithm that does not involve any penalty subproblems. Contrary to existing primal-dual methods, it does not require the projection of Lagrangian multipliers into a (possibly unknown) bounded set. Second, for nonconvex functional constrained problems, we introduce a new proximal point method that transforms the initial nonconvex problem into a sequence of convex problems by adding quadratic terms to both the objective and constraints. Under a certain MFCQ-type assumption, we establish the convergence and rate of convergence of this method to KKT points when the convex subproblems are solved exactly or inexactly. For large-scale and stochastic problems, we present a more practical proximal point method in which the approximate solutions of the subproblems are computed by the aforementioned ConEx method. To the best of our knowledge, most of these convergence and complexity results of the proximal point method for nonconvex problems also seem to be new in the literature.