mlsanityData to 14 Oct 2026

Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization

arXiv 2301.13314 ↗First posted 30 Jan 2023math.OC cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

We consider a non-convex constrained optimization problem, where the objective function is weakly convex and the constraint function is either convex or weakly convex. To solve this problem, we consider the classical switching subgradient method, which is an intuitive and easily implementable first-order method whose oracle complexity was only known for convex problems. This paper provides the first analysis on the oracle complexity of the switching subgradient method for finding a nearly stationary point of non-convex problems. Our results are derived separately for convex and weakly convex constraints. Compared to existing approaches, especially the double-loop methods, the switching gradient method can be applied to non-smooth problems and achieves the same complexity using only a single loop, which saves the effort on tuning the number of inner iterations.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 59 of its 92 references that are in the map. First posted on arXiv 30 Jan 2023.

Builds on

59 of 92 references.

References · 59

  1. 2018A Reductions Approach to Fair Classificationcited by 587
  2. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  3. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  4. 2015Global Convergence of ADMM in Nonconvex Nonsmooth Optimizationcited by 98
  5. 2014Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problemscited by 64
  6. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 63
  7. 2016Efficiency of minimizing compositions of convex functions and smooth mapscited by 59
  8. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
  9. 2019Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimizationcited by 38
  10. 2019The Complexity of Finding Stationary Points with Stochastic Gradient Descentcited by 35
  11. 2018Subgradient methods for sharp weakly convex functionscited by 33
  12. 2018Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functionscited by 32
38 more
  1. 2021On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functionscited by 31
  2. 2017Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problemscited by 30
  3. 2020Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimizationcited by 30
  4. 2019An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraintscited by 29
  5. 2019Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraintscited by 25
  6. 2021An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangianscited by 25
  7. 2021A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobianscited by 22
  8. 2020Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimizationcited by 21
  9. 2021Worst-Case Complexity of an SQP Method for Nonlinear Equality Constrained Stochastic Optimizationcited by 19
  10. 2018On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimizationcited by 18
  11. 2022First-Order Methods for Nonsmooth Nonconvex Functional Constrained Optimization with or without Slater Pointscited by 17
  12. 2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 17
  13. 2015RSG: Beating Subgradient Method without Smoothness and Strong Convexitycited by 15
  14. 2018Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programscited by 15
  15. 2018A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimizationcited by 14
  16. 2016Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysiscited by 13
  17. 2020Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functionscited by 13
  18. 2020A global dual error bound and its application to the analysis of linearly constrained nonconvex optimizationcited by 13
  19. 2022A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimizationcited by 12
  20. 2021Inexact Sequential Quadratic Optimization for Minimizing a Stochastic Objective Function Subject to Deterministic Nonlinear Equality Constraintscited by 11
  21. 2014Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programscited by 10
  22. 2017Mirror Descent and Convex Optimization Problems With Non-Smooth Inequality Constraintscited by 10
  23. 2021Moreau Envelope Augmented Lagrangian Method for Nonconvex Optimization with Linear Constraintscited by 10
  24. 2021Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimizationcited by 10
  25. 2022Level Constrained First Order Methods for Function Constrained Optimizationcited by 8
  26. 2022On the Complexity of Finding Small Subgradients in Nonsmooth Optimizationcited by 8
  27. 2023A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimizationcited by 8
  28. 2017Ghost Penalties in Nonconvex Constrained Optimization: Diminishing Stepsizes and Iteration Complexitycited by 6
  29. 2018ADMM for Multiaffine Constrained Optimizationcited by 6
  30. 2020Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problemscited by 6
  31. 2020Iteration-complexity of a proximal augmented Lagrangian method for solving nonconvex composite optimization problems with nonlinear convex constraintscited by 6
  32. 2022On the Iteration Complexity of Smoothed Proximal ALM for Nonconvex Optimization Problem with Convex Constraintscited by 6
  33. 2017Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimizationcited by 5
  34. 2020Iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian method based on the classical Lagrangian functioncited by 5
  35. 2018Complexity of finding near-stationary points of convex functions stochasticallycited by 4
  36. 2019On Modification of an Adaptive Stochastic Mirror Descent Algorithm for Convex Optimization Problems with Functional Constraintscited by 4
  37. 2020Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?cited by 4
  38. 2020A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimizationcited by 4

50 most cited of 59 All 59 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 7; 2026: 3.

11 papers.

  1. 2025A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimizationcited by 9
  2. 2025Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraintscited by 6
  3. 2026Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variancecited by 5
  4. 2024Primal Methods for Variational Inequality Problems with Functional Constraintscited by 3
  5. 2025Enforcing Fair Predicted Scores on Intervals of Percentiles by Difference-of-Convex Constraintscited by 2
  6. 2025Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functionscited by 1
  7. 2025humancompatible.train: Implementing Optimization Algorithms for Stochastically-Constrained Stochastic Optimization Problemscited by 1
  8. 2026First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraintscited by 1
  9. 2025Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimizationcited by 0
  10. 2025Benchmarking Stochastic Approximation Algorithms for Fairness-Constrained Training of Deep Neural Networkscited by 0
  11. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0