Research map / Optimization / Nonconvex and smooth optimization
Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes single-loop stochastic smoothed linearized augmented Lagrangian methods (with a Moreau-envelope analysis, dual updates, and a STORM variant) for nonconvex stochastic optimization with polyhedral constraints and linear (in)equality constraints, achieving O(ε^-4) and O(ε^-3) sample complexity.
Problem
Stochastic smooth nonconvex minimization subject to linear equality/inequality constraints (polyhedral feasible set), where prior optimal-complexity results needed large penalty parameters, subproblems, or did not handle polyhedral X.
Approach
Interprets a single-step stochastic primal-dual augmented Lagrangian update as an inexact gradient descent on the Moreau envelope of the constrained objective, with a smoothed proximal center update, a Moreau-envelope potential for single-sample projected SGD, constant penalty, and non-negligible dual steps.
Key results
- Single-loop stochastic smoothed ALM achieves O(ε^-4) sample complexity for ε-stationary points with one sample per iteration, with no subproblems or large batches (except one post-processing batch).
- With STORM variance reduction and expected smoothness, complexity improves to O(ε^-3).
- Extends to stochastic linear constraints with O(ε^-4) complexity under CQ and compact domain assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the stochastic smoothed linearized ALM for linear constraints with polyhedral X | Nonconvex optimization with stochastic objective gradients · Linear constraints, polyhedral X | sample complexity: O(\varepsilon^{-4}) | Helped |
| Use dual safeguarding for sampled linear constraints | Stochastic smoothed linearized ALM · Random linear constraints, polyhedral X | stochastic oracle complexity: O(\varepsilon^{-4}) | Helped |
| Add STORM variance reduction under expected smoothness | Stochastic smoothed linearized ALM · Linear constraints, polyhedral X | oracle complexity: O(\varepsilon^{-4}) to O(\varepsilon^{-3}) | Helped |
Limitations
- Stochastic linear constraints require constraint qualification, compact domains, and a dual safeguarding step.
- O(ε^-3) result requires the stronger expected smoothness assumption.
- Analysis is theoretical with no experiments reported in the provided text.
Experimental setup
Metrics: sample complexity iteration complexity
Baselines: stochastic penalty methods double-loop stochastic augmented Lagrangian methods
Builds on: linearized proximal augmented Lagrangian method STORM variance reduction global error bounds for linearly constrained optimization
Closest papers by meaning
- Proximal Stochastic Methods for Nonsmooth Nonconvex Finite-Sum Optimization (NeurIPS 2016 · similarity 0.90)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.90)
- RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates (ICLR 2023 · similarity 0.90)
- Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions (NeurIPS 2024 · similarity 0.89)
- Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion (ICML 2024 · similarity 0.88)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.