A Constant Step Stochastic Douglas-Rachford Algorithm with Application to non Separable Regularizations

Adil Salim, Pascal Bianchi, Walid HachemICASSP 2018 · OpenReview

TL;DR

This paper introduces a novel stochastic version of the Douglas-Rachford algorithm that can handle non-separable regularizations, a common challenge in machine learning and signal processing. By using a constant step size and randomizing both objective functions, the algorithm achieves theoretical convergence guarantees and demonstrates practical advantages in speed and efficiency for structured regularization problems.

What Problem Does This Paper Address?

Many real-world problems in machine learning and signal processing require minimizing a sum of two convex functions, often representing a cost and a regularization term. The Douglas-Rachford algorithm is a popular method for this, but it typically requires computing "proximity operators" for each function separately. When the regularization term is "structured" (e.g., enforcing group sparsity), its proximity operator can be computationally expensive or even intractable. This paper tackles the challenge of developing an efficient algorithm for such scenarios, particularly when the objective functions themselves are defined as expectations over random variables, making them inherently stochastic.

Methods

The core contribution is a stochastic Douglas-Rachford algorithm with a constant step size. Unlike the standard algorithm, this version replaces the deterministic functions with random realizations at each iteration. This allows for online processing and avoids the need to compute the full proximity operator of the complex regularization term. The authors leverage techniques from stochastic approximation and analyze the algorithm's convergence by studying its behavior in continuous time via differential inclusions. They establish theoretical guarantees that the algorithm's iterates stay close to the optimal solution with high probability, especially for small step sizes.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and provides a simulated application.

Key Insights and Ideas

  • Stochasticity as a Solution: By making both objective functions random, the algorithm bypasses the need for expensive exact proximity operator computations for complex regularizers. This is a key insight for handling structured regularization.
  • Constant Step Size Advantage: The use of a constant step size makes the algorithm suitable for online learning and adaptive signal processing, where step sizes might not be easily adjusted.
  • Theoretical Guarantees for Stochasticity: The paper provides rigorous mathematical proofs showing that this stochastic approach, despite its inherent randomness, converges to the correct solution with high probability.
  • Structured Regularization Benefits: The application to overlapping group lasso demonstrates that the stochastic approach can be significantly faster than methods that rely on exact (but slow) computations for structured regularizers.

Key Results

The paper establishes a main convergence theorem stating that for any probability measure with a finite second moment, the iterates of the stochastic Douglas-Rachford algorithm converge to the set of solutions with high probability as the number of iterations increases. This convergence is shown to be faster than a partially stochastic counterpart in their experimental setup. Specifically, the application to overlapping group lasso regularization showed that the stochastic algorithm was faster than a method that used a specialized subroutine for the regularization term.

Limitations and Future Work

The authors acknowledge that their theoretical analysis relies on several assumptions, including conditions on the integrability of gradients and the behavior of proximity operators. While they demonstrate a specific application to overlapping group lasso, future work could explore the algorithm's performance on a wider range of structured regularization problems and different types of stochastic objective functions. The paper also suggests that further investigation into the interplay between the step size and convergence rate could be beneficial.

Summary updated

Abstract

The Douglas Rachford algorithm is an algorithm that converges to a minimizer of a sum of two convex functions. The algorithm consists in fixed point iterations involving computations of the proximity operators of the two functions separately. The paper investigates a stochastic version of the algorithm where both functions are random and the step size is constant. We establish that the iterates of the algorithm stay close to the set of solution with high probability when the step size is small enough. Application to structured regularization is considered.
BibTeX
@inproceedings{salim2018constant,
  author = {Adil Salim and Pascal Bianchi and Walid Hachem},
  title = {{A Constant Step Stochastic Douglas-Rachford Algorithm with Application to non Separable Regularizations}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2018},
  url = {https://openreview.net/forum?id=l6bVczVaGFV},
}
Figure