Timezone: »

Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimization
Feihu Huang · Songcan Chen · Heng Huang

Tue Jun 11 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #93

In this paper, we propose a faster stochastic alternating direction method of multipliers (ADMM) for nonconvex optimization by using a new stochastic path-integrated differential estimator (SPIDER), called as SPIDER-ADMM. Moreover, we prove that the SPIDER-ADMM achieves a record-breaking incremental first-order oracle (IFO) complexity for finding an ϵ-approximate solution. As one of major contribution of this paper, we provide a new theoretical analysis framework for nonconvex stochastic ADMM methods with providing the optimal IFO complexity. Based on this new analysis framework, we study the unsolved optimal IFO complexity of the existing non-convex SVRG-ADMM and SAGA-ADMM methods, and prove their the optimal IFO complexity. Thus, the SPIDER-ADMM improves the existing stochastic ADMM methods. Moreover, we extend SPIDER-ADMM to the online setting, and propose a faster online SPIDER-ADMM. Our theoretical analysis also derives the IFO complexity of the online SPIDER-ADMM. Finally, the experimental results on benchmark datasets validate that the proposed algorithms have faster convergence rate than the existing ADMM algorithms for nonconvex optimization.

Author Information

Feihu Huang (University of Pittsburgh)
Songcan Chen (Nanjing University of Aeronautics and Astronautics)

2018 IAPR Fellow

Heng Huang (University of Pittsburgh)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors