math.OCJan 31, 2025

A SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization

Authors: Wei Liu, Yangyang Xu

Organizations: Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY

Abstract

Many real-world problems, such as those with fairness constraints, involve complex expectation constraints and large datasets, necessitating the design of efficient stochastic methods to solve them. Most existing research focuses on cases with no {constraint} or easy-to-project constraints or deterministic constraints. In this paper, we consider nonconvex nonsmooth stochastic optimization problems with expectation constraints, for which we build a novel exact penalty model. We first show the relationship between the penalty model and the original problem. Then on solving the penalty problem, we present a single-loop SPIDER-type stochastic subgradient method, which utilizes the subgradients of both the objective and constraint functions, as well as the constraint function value at each iteration. Under certain regularity conditions (weaker than Slater-type constraint qualification or strong feasibility assumed in existing works), we establish an iteration complexity result of O(ε−4)O(ε^{-4}) to reach a near-εε stationary point of the penalized problem in expectation, matching the lower bound for such tasks. Building on the exact penalization, an (ε,ε)(ε,ε)-KKT point of the original problem is obtained. For a few scenarios, our complexity of either the {objective} sample subgradient or the constraint sample function values can be lower than the state-of-the-art results by a factor of ε−2ε^{-2}. Moreover, on solving two fairness-constrained problems and a multi-class Neyman-Pearson classification problem, our method is significantly (up to 466 times) faster than the state-of-the-art algorithms, including switching subgradient method and inexact proximal point methods.

Figures & tables

Explore similar work

Oct 9, 2026

Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints

We present new algorithms for stochastic optimization problems in which the objective is neither smooth nor convex, subject to a convex constraint set. Our algorithms return a (δ,ε)(δ,\varepsilon)-Goldstein stationary point, as recently defined for constrained problems by Liu et al. (2024), with improved complexities, and are the first to achieve optimal convergence rates for this task in several settings. In particular, we design projection-based and projection-free algorithms that achieve a O~(δ−1ε−3)\widetilde O(δ^{-1}\varepsilon^{-3}) rate using stochastic gradients, which we show to be optimal, and a O~(dδ−1ε−3)\widetilde O(dδ^{-1}\varepsilon^{-3}) rate using zeroth-order queries, which is also optimal in its dependence on the dimension dd and improves over prior work. Notably, our lower bound is given in terms of the Frank-Wolfe gap and holds even for smooth problems, which is of independent interest. These results show that in nonconvex stochastic optimization, the convergence rate is degraded neither by the presence of constraints nor by nonsmoothness. Our analysis is based on a reduction to online linear optimization, extending a related technique from unconstrained optimization.
May 18, 2026

Stochastic Penalty-Barrier Method for Constrained Machine Learning

Constrained Machine Learning (CML) enables fairness-aware training, physics-informed neural networks, and integration of symbolic domain knowledge into statistical models. In this work, we introduce the Stochastic Penalty-Barrier Method (SPBM) for CML problems. SPBM extends classical penalty and barrier methods by incorporating an exponential averaging of the dual variables, a stabilized penalty schedule, and the Moreau envelope to handle non-smoothness. We analyze the bias that mini-batching introduces in the barrier function and show that the feasible set of the resulting transformed problem is contained within the original one. We compare SPBM with CML baselines across multiple fairness and physics informed neural networks experiments. We find that SPBM is competitive with state-of-the-art methods. We also observe, on our fairness-based computational benchmark, that the per-epoch runtime of CML methods is largely independent of the number of constraints, and within 1.3×1.3\times of the per-epoch runtime of regularized Adam, for a number of constraints ranging from 9090 to 99009900.
Apr 15, 2026

Stochastic Trust-Region Methods for Over-parameterized Models

Under interpolation-type assumptions such as the strong growth condition, stochastic optimization methods can attain convergence rates comparable to full-batch methods, but their performance, particularly for SGD, remains highly sensitive to step-size selection. To address this issue, we propose a unified stochastic trust-region framework that eliminates manual step-size tuning and extends naturally to equality-constrained problems. For unconstrained optimization, we develop a first-order stochastic trust-region algorithm and show that, under the strong growth condition, it achieves an iteration and stochastic first-order oracle complexity of O(ε−2log⁡(1/ε))O(\varepsilon^{-2} \log(1/\varepsilon)) for finding an ε\varepsilon-stationary point. For equality-constrained problems, we introduce a quadratic-penalty-based stochastic trust-region method with penalty parameter μμ, and establish an iteration and oracle complexity of O(ε−4log⁡(1/ε))O(\varepsilon^{-4} \log(1/\varepsilon)) to reach an ε\varepsilon-stationary point of the penalized problem, corresponding to an O(ε)O(\varepsilon)-approximate KKT point of the original constrained problem. Numerical experiments on deep neural network training and orthogonally constrained subspace fitting demonstrate that the proposed methods achieve performance comparable to well-tuned stochastic baselines, while exhibiting stable optimization behavior and effectively handling hard constraints without manual learning-rate scheduling.