Nonconvex Stochastic Nested Optimization via Stochastic ADMM
This addresses optimization challenges for researchers in machine learning and operations research, offering a more general solution when proximal mappings are difficult to compute, though it is incremental relative to existing methods.
The paper tackled the stochastic nested composition optimization problem by proposing a stochastic ADMM method, achieving a total sample complexity of O(ε^{-3}) for the online case and O((2N_1 + N_2) + (2N_1 + N_2)^{1/2}ε^{-2}) for the finite sum case to find an ε stationary point.
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} \Bigl((2N_1 + N_2) + (2N_1 + N_2)^{1/2}ε^{-2}\Bigr)$ 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.