Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs

Stochastic MPECs have found increasing relevance for modeling a broad range of settings in engineering and statistics. Yet, there seem to be no efficient first/zeroth-order schemes equipped with non-asymptotic rate guarantees for resolving even deterministic variants of such problems. We consider SMPECs where the parametrized lower-level equilibrium problem is given by a deterministic/stochastic VI problem whose mapping is strongly monotone. We develop a zeroth-order implicit algorithmic framework by leveraging a locally randomized spherical smoothing scheme. We present schemes for single-stage and two-stage stochastic MPECs when the upper-level problem is either convex or nonconvex. (I). Single-stage SMPECs: In convex regimes, our proposed inexact schemes are characterized by a complexity in upper-level projections, upper-level samples, and lower-level projections of O(tfrac1ε2), O(tfrac1ε2), and O(tfrac1ε2ln(tfrac1ε)) , respectively. Analogous bounds for the nonconvex regime are O(tfrac1ε), O(tfrac1ε2), and O(tfrac1ε3), respectively . (II). Two-stage SMPECs: In convex regimes, our proposed inexact schemes have a complexity in upper-level projections, upper-level samples, and lower-level projections of O(tfrac1ε2),O(tfrac1ε2), and O(tfrac1ε2ln(tfrac1ε)) while the corresponding bounds in the nonconvex regime are O(tfrac1ε), O(tfrac1ε2), and O(tfrac1ε2ln(tfrac1ε)) , respectively . In addition, we derive statements for exact as well as accelerated counterparts. We also provide a comprehensive set of numerical results for validating the theoretical findings.