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

arXiv: https://arxiv.org/abs/2104.08406 · HTML: https://mlsanity.com/paper/2104.08406/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2021.

## Built on by (most cited first, 3 of 3)

- [A Meta-learning Formulation of the Autoencoder Problem for Non-linear Dimensionality Reduction](https://mlsanity.com/paper/2207.06676/) (2022)
- [A Randomized Zeroth-Order Hierarchical Framework for Heterogeneous Federated Learning](https://mlsanity.com/paper/2504.01839/) (2025)
- [Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking](https://mlsanity.com/paper/2610.13871/) (2026)

## Abstract (arXiv)

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.