SPRING: A fast stochastic proximal alternating method for non-smooth non-convex optimization

Derek Driggs, Junqi Tang, Jingwei Liang, Mike E. Davies, Carola‐Bibiane SchönliebarXiv 2020 · DOI · arXiv

Abstract

We introduce SPRING, a novel stochastic proximal alternating linearized minimization algorithm for solving a class of non-smooth and non-convex optimization problems. Large-scale imaging problems are becoming increasingly prevalent due to advances in data acquisition and computational capabilities. Motivated by the success of stochastic optimization methods, we propose a stochastic variant of the proximal alternating linearized minimization (PALM) algorithm. We provide global convergence guarantees, demonstrating that our proposed method with variance-reduced stochastic gradient estimators, such as SAGA and SARAH, achieves state-of-the-art oracle complexities. We also demonstrate the efficacy of our algorithm via several numerical examples including sparse non-negative matrix factorization, sparse principal component analysis, and blind image deconvolution.

Introduction

In modern machine learning and computational imaging, researchers frequently encounter optimization problems characterized by two significant hurdles: non-convexity/non-smoothness and massive scale. The objective functions often involve "finite-sum" structures where the total error is aggregated over millions of data samples.

Traditional deterministic methods, such as the Proximal Alternating Linearized Minimization (PALM) algorithm, are theoretically robust but computationally expensive because they require a full gradient pass over the entire dataset at every iteration. Conversely, standard stochastic methods like Stochastic Gradient Descent (SGD) offer per-iteration speed but suffer from high variance (noise), leading to slow convergence or instability when handling the complex coupling between variables—such as the relationship between an image and its blur kernel in deconvolution tasks. To address these limitations, we present SPRING (Stochastic Proximal alternating linearized minimization).

The SPRING Algorithm

SPRING is designed to bridge the gap between the stability of deterministic block-alternating methods and the efficiency of stochastic optimization. The algorithm operates by partitioning variables into blocks (e.g., $x$ and $y$) and updating them alternatingly.

The core innovation of SPRING lies in its integration of variance-reduced gradient estimators:

  • SAGA: Utilizes a memory of previous gradients to stabilize the current estimate.
  • SARAH: Employs a recursive step to update gradients, which proves particularly effective for complex, non-convex landscapes.

By incorporating these estimators, SPRING can maintain the per-iteration speed of stochastic methods while utilizing a constant step size in many scenarios. This allows the algorithm to converge to a critical point without the aggressive step-size decay typically required by standard SGD, which often hampers convergence speed.

Theoretical Contributions and Convergence

A key theoretical contribution of this work is the proof that SPRING inherits the convergence properties of PALM under the Kurdyka–Łojasiewicz (KL) property. The KL property is a broad condition satisfied by most functions encountered in real-world applications, ensuring that the algorithm reliably converges to a stable solution even in non-convex settings.

Furthermore, the paper establishes state-of-the-art oracle complexities. Notably, when using the SARAH estimator, SPRING achieves a complexity of $O(\sqrt{n}/\epsilon^2)$. This represents a significant improvement in dependence on the number of samples ($n$), making it exceptionally well-suited for massive-scale datasets.

Experimental Results

The efficacy of SPRING was evaluated across several high-dimensional optimization tasks:

  1. Sparse Non-negative Matrix Factorization (Sparse-NMF): Tested on the Extended Yale-B and ORL facial recognition datasets, SPRING demonstrated significantly faster convergence than both the original PALM and its inertial (momentum-based) variants.
  2. Sparse Principal Component Analysis (Sparse-PCA): The algorithm efficiently handled the coupling between principal components and sparse loadings, showing superior stability compared to standard stochastic approaches.
  3. Blind Image Deconvolution: Using the Kodim08 and Kodim15 benchmarks, SPRING-SARAH outperformed existing methods in both speed and visual fidelity. While deterministic methods often required excessive computation to reach a clear image, SPRING produced sharp, natural-looking results in fewer epochs.

Discussion and Future Work

While SPRING offers a powerful framework for non-smooth non-convex optimization, its performance can be sensitive to initialization. In cases where the initial guess is poor, the gradient "memory" in variance-reduced methods may initially be misleading. The authors suggest a "warm-start" strategy—using a few iterations of standard SGD—to move the variables into a favorable region before deploying SPRING.

Future research directions include the integration of inertial schemes (momentum) to further accelerate the stochastic alternating process and the development of automated methods for hyperparameter tuning, such as adaptive mini-batch sizing and step-size estimation via power-method-based approaches.

Summary updated

Abstract

We introduce SPRING, a novel stochastic proximal alternating linearized minimization algorithm for solving a class of non-smooth and non-convex optimization problems. Large-scale imaging problems are becoming increasingly prevalent due to advances in data acquisition and computational capabilities. Motivated by the success of stochastic optimization methods, we propose a stochastic variant of proximal alternating linearized minimization (PALM) algorithm \cite{bolte2014proximal}. We provide global convergence guarantees, demonstrating that our proposed method with variance-reduced stochastic gradient estimators, such as SAGA \cite{SAGA} and SARAH \cite{sarah}, achieves state-of-the-art oracle complexities. We also demonstrate the efficacy of our algorithm via several numerical examples including sparse non-negative matrix factorization, sparse principal component analysis, and blind image deconvolution.
BibTeX
@misc{driggs2020spring,
  author = {Derek Driggs and Junqi Tang and Jingwei Liang and Mike E. Davies and Carola‐Bibiane Schönlieb},
  title = {{SPRING: A fast stochastic proximal alternating method for non-smooth non-convex optimization}},
  year = {2020},
  eprint = {2002.12266},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.12266},
}
Figure