View PDF HTML (experimental)

Abstract:We tackle the challenging problem of stochastic weakly convex optimization subject to mixed (equality and inequality) expected-value constraints. While optimal $\mathcal{O}(\epsilon^{-3})$ sample complexity algorithms exist for unconstrained weakly convex problems, dealing with complex functional constraints typically requires cumbersome multi-loop penalty or augmented Lagrangian methods, which suffer from high inner-loop complexity and sensitive parameter tuning. To bridge this fundamental gap, we propose the primal-dual Halpern-PAGE (PD-HP) algorithm. As a purely single-loop method, PD-HP completely bypasses the computational burden of nested iterations. At each step, it merely requires solving a simple strongly convex surrogate subproblem alongside a straightforward dual projection, making it exceptionally efficient and convenient to implement. Crucially, we prove that this computationally lightweight algorithm achieves the optimal $\mathcal{O}(\epsilon^{-3})$ sample complexity for mixed-constrained stochastic weakly convex problems, successfully matching the theoretical lower bounds.
Furthermore, when the primal domain is a compact polyhedral convex set, we establish the deterministic stability of the dual multipliers by exploiting the generalized Mangasarian-Fromovitz constraint qualification (MFCQ) alongside Hoffman's error bound. This ensures that our optimal complexity bound holds strictly under the standard, unbounded KKT residual metric without any theoretical gaps or artificial residual truncations.

Submission history

From: Liwei Zhang [view email]
[v1] Wed, 24 Jun 2026 03:43:39 UTC (393 KB)