Variance-Reduced First-Order Methods for Deterministically Constrained Stochastic Nonconvex Optimization with Strong Convergence Guarantees

What the paper says

In this paper, we study a class of deterministically constrained stochastic nonconvex optimization problems. Existing methods typically aim to find an ϵ-expectedly feasible stochastic stationary point, where the expected violations of both constraints and first-order stationarity are within a prescribed tolerance ϵ. However, in many practical applications, it is crucial that the constraints be nearly satisfied with certainty, making such an ϵ-stochastic stationary point potentially undesirable due to the risk of substantial constraint violations. To address this issue, we propose single-loop variance-reduced stochastic first-order methods, where the stochastic gradient of the stochastic component is computed using either a truncated recursive momentum scheme or a truncated Polyak momentum scheme for variance reduction, while the gradient of the deterministic component is computed exactly. Under the error bound condition with a parameter θ ≥1 and other suitable assumptions, we establish that these methods respectively achieve sample complexity and first-order oracle complexity of (Formula presented) for finding an ϵ-surely feasible stochastic stationary point (formula presented) with logarithmic factors hidden), where the constraint violation is within ϵ with certainty, and the expected violation of first-order stationarity is within ϵ. For θ =1, these complexities reduce to (formula presented), respectively, which match, up to a logarithmic factor, the best-known complexities achieved by existing methods for finding an ϵ -stochastic stationary point of unconstrained smooth stochastic nonconvex optimization problems.