Accelerated Variance Reduced Stochastic ADMM

Abstract

Recently, many variance reduced stochastic alternating direction method of multipliers (ADMM) methods (e.g.\ SAG-ADMM, SDCA-ADMM and SVRG-ADMM) have made exciting progress such as linear convergence rates for strongly convex problems. However, the best known convergence rate for general convex problems is O(1/T) as opposed to O(1/T^2) of accelerated batch algorithms, where $T$ is the number of iterations. Thus, there still remains a gap in convergence rates between existing stochastic ADMM and batch algorithms. To bridge this gap, we introduce the momentum acceleration trick for batch optimization into the stochastic variance reduced gradient based ADMM (SVRG-ADMM), which leads to an accelerated (ASVRG-ADMM) method. Then we design two different momentum term update rules for strongly convex and general convex cases. We prove that ASVRG-ADMM converges linearly for strongly convex problems. Besides having a low per-iteration complexity as existing stochastic ADMM methods, ASVRG-ADMM improves the convergence rate on general convex problems from O(1/T) to O(1/T^2). Our experimental results show the effectiveness of ASVRG-ADMM.

16 pages, 5 figures, Appears in Proceedings of the 31th AAAI Conference on Artificial Intelligence (AAAI), San Francisco, California, USA, pp. 2287--2293, 2017

References in corpus (8)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Piecewise linear regularized solution paths
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• A General Analysis of the Convergence of ADMM
• Online Alternating Direction Method
• Scalable Stochastic Alternating Direction Method of Multipliers
• Fast Proximal Linearized Alternating Direction Method of Multiplier with Parallel Splitting

Cited by in corpus (11)

• A Stochastic Alternating Direction Method of Multipliers for Non-smooth and Non-convex Optimization
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
• Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity
• SI-ADMM: A Stochastic Inexact ADMM Framework for Stochastic Convex Programs
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
• Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT
• Scalable Peaceman-Rachford Splitting Method with Proximal Terms
• IS-ASGD: Accelerating Asynchronous SGD using Importance Sampling