A SPIDER-Type Stochastic Subgradient Method for Expectation-Constrained Nonconvex Nonsmooth Optimization
SIAM Journal on Optimization · 30.06.2026 · 36 (2) · 1125-1153
DOI: 10.1137/25m1730703 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 24.06.2026. Verfasst von Wei Liu und 1 weiteren Autor:innen. Die Arbeit nennt 66 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
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 that have no constraint, or have constraints that admit an easy projection, or only have deterministic constraints. In this paper, we consider weakly convex stochastic optimization problems with expectation constraints, for which we build an 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 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 the Slater-type constraint qualification (CQ), we establish an iteration complexity result of [Formula: see text] to reach a near-[Formula: see text] stationary point of the penalized problem in expectation, matching the lower bound for such tasks. Building on the exact penalization, an [Formula: see text]-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 [Formula: see text]. Moreover, on solving two fairness-constrained problems and a multi-class Neyman–Pearson classification problem, our method is significantly (up to 466 times in terms of data pass) faster than the state-of-the-art algorithms, including the switching subgradient method - and the inexact proximal point methods.
Förderung
- National Science Foundation
Zitieren
APA
Liu, W., & Xu, Y. (2026). A SPIDER-Type Stochastic Subgradient Method for Expectation-Constrained Nonconvex Nonsmooth Optimization. SIAM Journal on Optimization, 36(2), 1125-1153. https://doi.org/10.1137/25m1730703
Vancouver
Liu W, Xu Y. A SPIDER-Type Stochastic Subgradient Method for Expectation-Constrained Nonconvex Nonsmooth Optimization. SIAM Journal on Optimization. 2026;36(2):1125-1153. doi:10.1137/25m1730703
BibTeX
@article{Liu2026,
author = {Liu, Wei and Xu, Yangyang},
title = {A SPIDER-Type Stochastic Subgradient Method for Expectation-Constrained Nonconvex Nonsmooth Optimization},
journal = {SIAM Journal on Optimization},
year = {2026},
volume = {36},
number = {2},
pages = {1125--1153},
doi = {10.1137/25m1730703}
}
EUVIMED