Accelerated Variance Reduction Stochastic ADMM for Large-Scale Machine Learning.

Area of Science:

• Optimization Algorithms
• Machine Learning Theory
• Convex Analysis

Background:

• Stochastic variance reduced alternating direction methods of multipliers (ADMMs) show linear convergence for strongly convex problems.
• Existing stochastic ADMMs have a suboptimal O(1/T) convergence rate for non-strongly convex problems.
• A gap exists between stochastic ADMM and accelerated deterministic algorithms' convergence rates for non-strongly convex problems.

Purpose of the Study:

• To bridge the convergence rate gap for non-strongly convex problems.
• To introduce a novel accelerated stochastic variance reduced ADMM (ASVRG-ADMM) method.
• To enhance the performance of ADMM for machine learning tasks.

Main Methods:

• Incorporation of a momentum acceleration trick into stochastic variance reduced ADMM.
• Design of linearized and simple proximal update rules for ADMM-style problems.
• Theoretical analysis of convergence rates for strongly and non-strongly convex problems.

Main Results:

• ASVRG-ADMM achieves linear convergence for strongly convex problems.
• ASVRG-ADMM improves convergence rate from O(1/T) to O(1/T^2) for non-strongly convex problems.
• Linearized proximal update rule avoids iterative sub-problem solving.

Conclusions:

• ASVRG-ADMM effectively accelerates convergence for a class of machine learning problems.
• The proposed method demonstrates superior performance compared to state-of-the-art techniques.
• ASVRG-ADMM offers a significant advancement in optimization for machine learning applications.