Constrained Nonconvex Stochastic Optimization with One Projection
Abstract
Constrained nonconvex optimization has seen increasing application in modern machine learning, such as safe LLM alignment/finetuning, transfer learning and rank-constrained continual learning. The commonly used approach is Projected SGD which requires projection at every iteration. However, projection onto a functional constraint can cost substantially more than a stochastic first-order update. We study whether this operation can be deferred until the end of nonconvex stochastic optimization, and only do it once. For weakly convex, possibly nonsmooth objectives with regular convex constraints, we give a penalized proximal method that uses Õ(ε−4) stochastic subgradients and one projection onto the constraint set. The returned point is exactly feasible and has a small Moreau-envelope stationarity measure; for smooth objectives, the same algorithm controls the projected-gradient mapping. For smooth nonconvex constraints, we assume a global lower bound on the infeasible constraint slope which permits arbitrary, possibly infeasible initialization. An exact-penalty variant attains the same stochastic-oracle order and returns an exactly feasible point within O(ε) of an ε-KKT point. All intermediate updates use only projections onto a simple Euclidean ball. These are oracle-complexity guarantees: the cost of the single terminal projection is separate, and no efficient projection algorithm for a general nonconvex set is assumed to follow from regularity.
Related
- Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization
- Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization
- A constraint dissolving method for generally constrained optimization over a nonconvex set
- Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption
- An Adaptive Augmented Lagrangian Method for Deterministic and Stochastic Nonconvex Optimization
BibTeX
@misc{deng2026constrained,
title = {{Constrained Nonconvex Stochastic Optimization with One Projection}},
author = {Yuyang Deng and Mohammadreza M. Kalan and Eitan J. Neugut and Mehrdad Mahdavi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34099},
eprint = {2609.34099},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34099},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Constrained Nonconvex Stochastic Optimization with One Projection
AU - Yuyang Deng
AU - Mohammadreza M. Kalan
AU - Eitan J. Neugut
AU - Mehrdad Mahdavi
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.34099
UR - https://arxiv.org/abs/2609.34099
AB - Constrained nonconvex optimization has seen increasing application in modern machine learning, such as safe LLM alignment/finetuning, transfer learning and rank-constrained continual learning. The commonly used approach is Projected SGD which requires projection at every iteration. However, projection onto a functional constraint can cost substantially more than a stochastic first-order update. We study whether this operation can be deferred until the end of nonconvex stochastic optimization, and only do it once. For weakly convex, possibly nonsmooth objectives with regular convex constraints, we give a penalized proximal method that uses Õ(ε^−4) stochastic subgradients and one projection onto the constraint set. The returned point is exactly feasible and has a small Moreau-envelope stationarity measure; for smooth objectives, the same algorithm controls the projected-gradient mapping. For smooth nonconvex constraints, we assume a global lower bound on the infeasible constraint slope which permits arbitrary, possibly infeasible initialization. An exact-penalty variant attains the same stochastic-oracle order and returns an exactly feasible point within O(ε) of an ε-KKT point. All intermediate updates use only projections onto a simple Euclidean ball. These are oracle-complexity guarantees: the cost of the single terminal projection is separate, and no efficient projection algorithm for a general nonconvex set is assumed to follow from regularity.
ER -