Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization

Abstract

In the paper, we study the stochastic alternating direction method of multipliers (ADMM) for the nonconvex optimizations, and propose three classes of the nonconvex stochastic ADMM with variance reduction, based on different reduced variance stochastic gradients. Specifically, the first class called the nonconvex stochastic variance reduced gradient ADMM (SVRG-ADMM), uses a multi-stage scheme to progressively reduce the variance of stochastic gradients. The second is the nonconvex stochastic average gradient ADMM (SAG-ADMM), which additionally uses the old gradients estimated in the previous iteration. The third called SAGA-ADMM is an extension of the SAG-ADMM method. Moreover, under some mild conditions, we establish the iteration complexity bound of $O(1/\epsilon )$ of the proposed methods to obtain an $\epsilon$-stationary solution of the nonconvex optimizations. In particular, we provide a general framework to analyze the iteration complexity of these nonconvex stochastic ADMM methods with variance reduction. Finally, some numerical experiments demonstrate the effectiveness of our methods.

34 pages, 4 figures and 2 tables

References in corpus (11)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Variance Reduction for Nonconvex Optimization
• Online Alternating Direction Method
• NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• Fast Incremental Method for Nonconvex Optimization
• Convergence of multi-block Bregman ADMM for nonconvex composite problems
• Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis
• A SMART Stochastic Algorithm for Nonconvex Optimization with Applications to Robust Machine Learning
• Variance-Reduced Proximal Stochastic Gradient Descent for Non-convex Composite optimization

Cited by in corpus (5)

• Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity
• Distributed Inexact Successive Convex Approximation ADMM: Analysis-Part I
• Linear Convergence of Accelerated Stochastic Gradient Descent for Nonconvex Nonsmooth Optimization
• Zeroth-Order Stochastic Alternating Direction Method of Multipliers for Nonconvex Nonsmooth Optimization