Stochastic ADMM with Balanced Augmented Lagrangian Method for Nonconvex and Nonsmooth Finite-Sum Optimization

Abstract

In this paper, we propose a balanced augmented Lagrangian method based on accelerated stochastic ADMM (b-ASADMM) to efficiently solve structured separable nonconvex optimization problems subject to linear constraints. The objective function in this problem comprises potentially nonsmooth and smooth functions, where the smooth function is an average of multiple nonconvex smooth functions. The involved smooth subproblem is tackled by an accelerated stochastic gradient method based on weighting of stochastic item and pre-variable. The involved nonsmooth subproblem is solved under incorporation of Bregman distance to avoid the case that subproblem does not have a closed-form solution due to the complicated quadratic term or other hindering. The involved balanced augmented Lagrangian method advances the original ALM by balancing its subproblems and improving its implementation. In contrast to most deterministic and stochastic ADMMs, our dual variable allows a more flexible and larger step-size region. By standard smoothness assumption, we establish the global convergence and iteration complexity of the generated sequence. Furthermore, we provide a linear convergence rate of b-ASADMM under a local error bound condition and the weakly convex property of the nonsmooth component. Numerical experiments on the graph-guided fused Lasso problem and the smooth clipped absolute deviation penalty problem are conducted to verify the effectiveness of b-ASADMM.