Nonconvex Stochastic Nested Optimization via Stochastic ADMM

We consider the stochastic nested composition optimization problem where the objective is a composition of two expected-value functions. We proposed the stochastic ADMM to solve this complicated objective. In order to find an $ϵ$ stationary point where the expected norm of the subgradient of corresponding augmented Lagrangian is smaller than $ϵ$, the total sample complexity of our method is $\mathcal{O}({ϵ}^{-3})$ for the online case and $\mathcal{O}((2N_1+N_2)+(2N_1+N_2{)}^{1\mathrm{/}2}{ϵ}^{-2})$ for the finite sum case. The computational complexity is consistent with proximal version proposed in \cite{zhang2019multi}, but our algorithm can solve more general problem when the proximal mapping of the penalty is not easy to compute.