Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization

Abstract

With the large rising of complex data, the nonconvex models such as nonconvex loss function and nonconvex regularizer are widely used in machine learning and pattern recognition. In this paper, we propose a class of mini-batch stochastic ADMMs (alternating direction method of multipliers) for solving large-scale nonconvex nonsmooth problems. We prove that, given an appropriate mini-batch size, the mini-batch stochastic ADMM without variance reduction (VR) technique is convergent and reaches a convergence rate of $O(1/T)$ to obtain a stationary point of the nonconvex optimization, where $T$ denotes the number of iterations. Moreover, we extend the mini-batch stochastic gradient method to both the nonconvex SVRG-ADMM and SAGA-ADMM proposed in our initial manuscript \cite{huang2016stochastic}, and prove these mini-batch stochastic ADMMs also reaches the convergence rate of $O(1/T)$ without condition on the mini-batch size. In particular, we provide a specific parameter selection for step size $\eta$ of stochastic gradients and penalty parameter $\rho$ of augmented Lagrangian function. Finally, extensive experimental results on both simulated and real-world data demonstrate the effectiveness of the proposed algorithms.

arXiv commentWe have fixed some errors in the proofs. arXiv admin note: text overlap with arXiv:1610.02758

References in corpus (13)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• A Universal Catalyst for First-Order Optimization
• NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• Fast Incremental Method for Nonconvex Optimization
• Accelerated Variance Reduced Stochastic ADMM
• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• Scalable Stochastic Alternating Direction Method of Multipliers
• A SMART Stochastic Algorithm for Nonconvex Optimization with Applications to Robust Machine Learning
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Faster and Non-ergodic O(1/K) Stochastic Alternating Direction Method of Multipliers
• Stochastic Variance-Reduced ADMM

Cited by in corpus (3)

• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
• A Stochastic Alternating Direction Method of Multipliers for Non-smooth and Non-convex Optimization
• Fully Decentralized Federated Learning Based Beamforming Design for UAV Communications