Complexity of Single Loop Algorithms for Nonlinear Programming with
  Stochastic Objective and Constraints
Ahmet Alacaoglu Stephen J. Wright
We analyze the complexity of single-loop quadratic penalty and augmented
Lagrangian algorithms for solving nonconvex optimization problems with
functional equality constraints. We consider three cases, in all of which the
objective is stochastic and smooth, that is, an expectation over an unknown
distribution that is accessed by sampling. The nature of the equality
constraints differs among the three cases: deterministic and linear in the
first case, deterministic, smooth and nonlinear in the second case, and
stochastic, smooth and nonlinear in the third case. Variance reduction
techniques are used to improve the complexity. To find a point that satisfies
$\varepsilon$-approximate first-order conditions, we require
$\widetilde{O}(\varepsilon^{-3})$ complexity in the first case,
$\widetilde{O}(\varepsilon^{-4})$ in the second case, and
$\widetilde{O}(\varepsilon^{-5})$ in the third case. For the first and third
cases, they are the first algorithms of "single loop" type (that also use
$O(1)$ samples at each iteration) that still achieve the best-known complexity
guarantees.