Linearized Alternating Direction Method with Parallel Splitting and Adaptive Penalty for Separable Convex Programs in Machine Learning

Risheng Liu, Zhouchen Lin, Zhixun Su

Abstract

Scaling the Alternating Direction Method (ADM) to complex, multi-block convex programs remains a significant challenge in machine learning optimization. Traditional ADM variants often struggle with convergence when applied to more than two variable blocks and require extensive manual tuning of penalty parameters. This paper introduces the Linearized Alternating Direction Method with Parallel Splitting and Adaptive Penalty (LADMPSAP), a robust framework designed for high-dimensional problems such as low-rank recovery and sparse representation. By integrating linearization, parallel updates, and an automated adaptive penalty scheme, the proposed algorithm ensures global convergence with an $O(1/K)$ rate, significantly outperforming state-of-the-art solvers in both speed and numerical precision.

Introduction

Many fundamental tasks in machine learning—including matrix completion, subspace clustering, and sparse regression—are formulated as separable convex programs. These problems involve minimizing a sum of functions subject to linear constraints. While the Alternating Direction Method (ADM) has become a standard tool for these tasks due to its ability to decompose large problems into manageable subproblems, it faces two primary bottlenecks: the "Multi-Block Trap" and the "Hyperparameter Headache."

Standard ADM is theoretically guaranteed to converge for two-block problems. However, when extended to three or more blocks, the algorithm can diverge. Furthermore, the performance of ADM is highly sensitive to the penalty parameter ($\beta$). A poorly chosen $\beta$ can lead to agonizingly slow convergence or numerical instability, necessitating tedious manual tuning. LADMPSAP addresses these issues by providing a parallelizable, multi-block framework with automated parameter adjustment.

The LADMPSAP Framework

The architecture of LADMPSAP rests on three innovative pillars that enhance the flexibility and efficiency of the ADM approach.

1. Linearization

Rather than solving complex quadratic subproblems at each iteration, LADMPSAP linearizes the penalty term. This approach allows for the use of proximal operators, which provide simple, closed-form solutions for common regularizers. For instance, sparsity-inducing norms can be handled via soft-thresholding, while low-rank constraints are addressed through singular value shrinkage. This significantly reduces the computational cost per iteration.

2. Parallel Splitting (Jacobi-style Updates)

Unlike standard ADM, which typically employs sequential (Gauss-Seidel) updates, LADMPSAP updates all variable blocks simultaneously. This "parallel splitting" makes the algorithm embarrassingly parallel and ideally suited for distributed computing environments. To ensure convergence in the multi-block case—a result that previously eluded researchers for parallel ADM—the authors decoupled variable updates from the multiplier update by using a predicted Lagrange multiplier ($\hat{\lambda}$) based on values from the previous iteration.

3. Adaptive Penalty Scheme

To eliminate the need for manual hyperparameter tuning, LADMPSAP incorporates an automated adaptive penalty scheme. The algorithm dynamically adjusts the penalty parameter $\beta$ during execution based on the balance between feasibility error (constraint satisfaction) and optimality error. The authors established that if the objective functions have bounded subgradients—a condition met by most norm-based machine learning problems—the penalty parameter can grow indefinitely without compromising the algorithm's stability.

Theoretical Contributions

The authors provide a rigorous proof of global convergence for LADMPSAP, establishing an ergodic convergence rate of $O(1/K)$. This theoretical foundation is particularly significant because it guarantees that the parallel, multi-block updates will reach an optimal solution, even when handling complex linear constraints exactly rather than through approximations.

Experimental Results

The efficacy of LADMPSAP was evaluated across several challenging benchmarks, ranging from synthetic data to real-world biological and image datasets.

  • Latent Low-Rank Representation (LRR): In tests involving synthetic data, LADMPSAP was approximately twice as fast as its closest competitor, LADMPS, and significantly outperformed the Accelerated Proximal Gradient (APG) method. It also achieved lower relative errors, whereas naive ADM variants often converged to incorrect solutions in multi-block settings.
  • Gene Expression Analysis: Using breast cancer gene expression data (8,141 genes across 295 tumors), the proximal version of LADMPSAP was over 10 times faster than specialized active-set methods for group sparse logistic regression, despite the high dimensionality of the training set.
  • Motion Segmentation: On the Hopkins155 database, the algorithm demonstrated superior efficiency in real-world low-rank recovery tasks.
  • Image Inpainting: Experiments on the SIPI image database showed that LADMPSAP produced higher Peak Signal-to-Noise Ratio (PSNR) values compared to other state-of-the-art solvers like FPCA, indicating higher reconstruction quality.

Conclusion and Future Work

LADMPSAP represents a significant advancement in the scalability of ADM for machine learning. By solving the convergence issues of multi-block parallel updates and automating penalty parameter selection, it provides a robust, "off-the-shelf" solver for complex convex programs.

While the algorithm is theoretically parallelizable, future work remains to fully integrate it with high-performance distributed computing frameworks. Specifically, optimizing individual computational primitives—such as Singular Value Decomposition (SVD) for massive matrices—and implementing advanced caching techniques will be essential for scaling LADMPSAP to "Big Data" applications. Additionally, while the proximal version is highly efficient, it requires the calculation of Lipschitz constants, which may be challenging for certain non-standard loss functions.

Summary updated

Abstract

Many problems in statistics and machine learning (e.g., probabilistic graphical model, feature extraction, clustering and classification, etc) can be (re)formulated as linearly constrained separabl...
BibTeX
@article{liu2015linearized,
  author = {Risheng Liu and Zhouchen Lin and Zhixun Su},
  title = {{Linearized Alternating Direction Method with Parallel Splitting and Adaptive Penalty for Separable Convex Programs in Machine Learning}},
  journal = {Machine Learning},
  year = {2015},
  doi = {10.1007/s10994-014-5469-5},
}
Figure