Nonconvex Stochastic Nested Optimization via Stochastic ADMM

2019/11/12 by Zhongruo Wang, Wang, Zhongruo
Computer Science · Decision Sciences · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1911.05167

openalex publication_date 2019/11/12 · openalex created_date 2019/11/22 · openalex updated_date 2026/07/28

Abstract

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 O(ε^-3) for the online case and O ((2N₁ + N₂) + (2N₁ + N₂)^1/2ε^-2) for the finite sum case. The computational complexity is consistent with proximal version proposed in \citezhang2019multi, but our algorithm can solve more general problem when the proximal mapping of the penalty is not easy to compute.

Related

• Multi-Level Composite Stochastic Optimization via Nested Variance Reduction
• Fast Stochastic Variance Reduced ADMM for Stochastic Composition Optimization
• A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization
• Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems
• Stochastic ADMM for Nonsmooth Optimization