Stochastic Strictly Contractive Peaceman-Rachford Splitting Method

Sen Na, Mingyuan Ma, Shuming Ma, Guangju PengarXiv 2017 · arXiv

Introduction

In large-scale machine learning, optimization problems often involve separable objective functions subject to linear constraints, such as Lasso and Sparse Logistic Regression. Two primary frameworks for solving these are the Alternating Direction Method of Multipliers (ADMM) and the Peaceman-Rachford Splitting Method (PRSM). While PRSM typically converges faster than ADMM in batch settings, it has historically struggled in stochastic environments, often suffering from instability or slow $O(1/\sqrt{K})$ convergence rates.

This paper introduces Stochastic Scalable PRSM (SS-PRSM), a novel algorithm that achieves a state-of-the-art $O(1/K)$ ergodic convergence rate, bridging the performance gap between batch and stochastic optimization.

The SS-PRSM Framework

The proposed SS-PRSM algorithm incorporates three critical modifications to the standard splitting framework to ensure stability and speed in stochastic settings:

  1. Variance Reduction: Drawing inspiration from SVRG (Stochastic Variance Reduced Gradient), SS-PRSM uses periodic full batch gradient computations to anchor stochastic updates. This significantly reduces noise and is the key to reaching the $O(1/K)$ convergence rate.
  2. Proximal Terms: By adding quadratic proximal terms to subproblems, the algorithm allows for approximate solutions. This is particularly beneficial for complex loss functions where exact solutions are computationally prohibitive.
  3. Dual Relaxation: The method utilizes two relaxation factors ($\alpha$ and $\gamma$) to update Lagrange multipliers, maintaining the "strictly contractive" property required for guaranteed convergence.

Crucially, the authors demonstrate that applying these accelerated updates to only one variable ($x_1$) is sufficient to achieve the improved global convergence rate. The specific parameter configurations used for the experimental models are detailed in the table below.

Table 1: Parameter settings for Lasso, group Lasso, and sparse logistic regression models.

Experimental Evaluation

The performance of SS-PRSM was evaluated against several state-of-the-art algorithms, including S-ADMM and SSPB-SCPRSM, across various datasets such as Communities and Crime, EE2006-tfidf, Sido, and NSL-KDD.

Key Results

Empirical tests on Lasso, Group Lasso, and Sparse Logistic Regression demonstrate that SS-PRSM consistently outperforms its competitors. As shown in the comparative plots, SS-PRSM reaches lower loss values with significantly fewer passes over the data (epochs).

Figure 1: Comparison of loss values versus iteration epochs for (a, b) Lasso, (c) group Lasso, and (d) sparse logistic regression across different optimization methods.

The results highlight that SS-PRSM not only matches the theoretical best-known rates for stochastic ADMM but also maintains the practical speed advantages inherent to the PRSM framework. Furthermore, the algorithm proved robust to the choice of proximal parameters ($S$ and $T$), simplifying the tuning process for practitioners compared to previous PRSM variants.

Insights and Future Directions

The primary contribution of this work is demonstrating that PRSM—long considered the faster but riskier alternative to ADMM—can be made theoretically robust in stochastic environments without losing its empirical edge. By utilizing proximal terms and variance reduction, the algorithm becomes highly scalable for a wide variety of machine learning models.

However, some challenges remain. While ergodic convergence (the average of iterates) is proven, the non-ergodic convergence of the last iterate for stochastic PRSM remains an open theoretical challenge. Additionally, extending SS-PRSM to non-convex settings, such as deep learning, represents a promising avenue for future research.

Summary updated

Abstract

Along with developing of Peaceman-Rachford Splittling Method (PRSM), many batch algorithms based on it have been studied very deeply. But almost no algorithm focused on the performance of stochastic version of PRSM. In this paper, we propose a new stochastic algorithm based on PRSM, prove its convergence rate in ergodic sense, and test its performance on both artificial and real data. We show that our proposed algorithm, Stochastic Scalable PRSM (SS-PRSM), enjoys the $O(1/K)$ convergence rate, which is the same as those newest stochastic algorithms that based on ADMM but faster than general Stochastic ADMM (which is $O(1/\sqrt{K})$). Our algorithm also owns wide flexibility, outperforms many state-of-the-art stochastic algorithms coming from ADMM, and has low memory cost in large-scale splitting optimization problems.
BibTeX
@misc{na2017stochastic,
  author = {Sen Na and Mingyuan Ma and Shuming Ma and Guangju Peng},
  title = {{Stochastic Strictly Contractive Peaceman-Rachford Splitting Method}},
  year = {2017},
  eprint = {1711.04955},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1711.04955},
}
Figure