A Control-Theoretic Approach to Analysis and Parameter Selection of Douglas-Rachford Splitting

Jacob H. Seidman, Mahyar Fazlyab, Victor M. Preciado, George J. Pappas

TL;DR

This paper reframes the popular Douglas-Rachford Splitting (DRS) optimization algorithm as a control system consisting of a linear dynamical system with nonlinear feedback. By applying control-theoretic tools like Lyapunov functions and Integral Quadratic Constraints (IQCs), the authors derive a unified framework to prove convergence rates and—for the first time—directly solve for optimal algorithm parameters using Semidefinite Programming (SDP).

What Problem Does This Paper Address?

In the worlds of machine learning and control, Douglas-Rachford Splitting (DRS) and its dual form, ADMM, are "workhorse" algorithms used to solve complex optimization problems. However, their performance is highly sensitive to two parameters: the proximal step size ($\alpha$) and the relaxation parameter ($\lambda$).

Traditionally, these parameters are either set using heuristics or found through an expensive trial-and-error "grid search." While some theoretical bounds exist, they often rely on complex operator theory and are specific to certain types of functions (e.g., only smooth or only strongly convex). There has been a lack of a unified, automated way to analyze DRS and select the best parameters for a wide range of problem classes.

Methods

The authors bridge the gap between optimization and control theory using three key techniques:

  1. Algorithm as a Dynamical System: They rewrite the DRS update equations as a discrete-time linear system where the "state" is the algorithm's iterate and the "feedback" is the nonlinear proximal operator.
  2. Incremental Quadratic Constraints (IQCs): To handle the "black box" nature of the nonlinear proximal operators, they use IQCs. These are mathematical inequalities that bound how much the output of a nonlinear function can change relative to its input, based on properties like convexity and smoothness.
  3. Lyapunov Analysis: They propose a family of Lyapunov functions (energy functions). If they can prove this "energy" decreases at every step, the algorithm is guaranteed to converge.
  4. Automated Parameter Selection via SDP: The convergence conditions are transformed into a dimensionally independent Matrix Inequality. In the strongly convex case, the authors use a mathematical trick (the Schur Complement) to linearize the dependence on the relaxation parameter $\lambda$. This allows them to use Semidefinite Programming (SDP) to find the mathematically optimal $\lambda$ and convergence rate $\rho$ simultaneously.

Datasets

The paper evaluates its theoretical findings using standard optimization benchmarks rather than traditional ML datasets:

  • Basis Pursuit: A non-smooth, non-strongly convex problem using a synthetic matrix $A \in \mathbb{R}^{300 \times 10000}$.
  • LASSO Regression: Used to test both non-strongly convex (rank-deficient $A$) and strongly convex (full-rank $A$) scenarios with $A \in \mathbb{R}^{300 \times 200}$.

Key Insights and Ideas

  • The Residual as Feedback: A major "aha" moment is the realization that the feedback nonlinearity in their control model is exactly the "optimality residual" of the optimization problem. Driving this dynamical system to a stable fixed point is mathematically equivalent to finding the optimal solution to the objective function.
  • Unified Proofs: By changing just a single term in the Lyapunov function, the authors can provide convergence proofs for three distinct scenarios: non-smooth/non-strongly convex, smooth/non-strongly convex, and smooth/strongly convex.
  • Direct Optimization vs. Verification: Previous research used SDPs to verify if a specific parameter choice would work. This paper’s framework is the first that can output the optimal relaxation parameter directly from the solver without needing to search over a range of values.

Key Results

  • Simplified $O(1/k)$ Proof: The authors provide a new, simpler proof for the $O(1/k)$ convergence rate in the most general (non-strongly convex) case.
  • Optimal Relaxation: For strongly convex problems, the SDP consistently identifies $\lambda = 2$ as the optimal relaxation parameter across various condition numbers and step sizes.
  • Empirical Validation: Numerical experiments show that the "optimal" step size $\alpha^*$ predicted by their theorems perfectly matches the peak performance observed in empirical tests (see Figure 2 in the paper).
  • Dimension Independence: The derived matrix inequalities do not depend on the dimension of the decision variables, meaning the analysis scales to very large problems.

Limitations and Future Work

  • Two-Block Limitation: The current framework is designed for problems split into two parts ($f + g$). Many real-world problems involve three or more blocks.
  • Worst-Case Bounds: The parameters selected are optimized for the worst-case function within a specific class (e.g., all $L$-smooth functions). If a specific problem has unique structural properties beyond smoothness, these settings might be conservative.
  • Future Directions: The authors suggest extending this control-theoretic approach to "accelerated" versions of DRS and multi-block ADMM formulations.

Summary updated

Abstract

Douglas-Rachford splitting and its equivalent dual formulation ADMM are widely used iterative methods in composite optimization problems arising in control and machine learning applications. The performance of these algorithms depends on the choice of step size parameters, for which the optimal values are known in some specific cases, and otherwise are set heuristically. We provide a new unified method of convergence analysis and parameter selection by interpreting the algorithm as a linear dynamical system with nonlinear feedback. This approach allows us to derive a dimensionally independent matrix inequality whose feasibility is sufficient for the algorithm to converge at a specified rate. By analyzing this inequality, we are able to give performance guarantees and parameter settings of the algorithm under a variety of assumptions regarding the convexity and smoothness of the objective function. In particular, our framework enables us to obtain a new and simple proof of the O(1/k) convergence rate of the algorithm when the objective function is not strongly convex.
BibTeX
@inproceedings{seidman2020control,
  author = {Jacob H. Seidman and Mahyar Fazlyab and Victor M. Preciado and George J. Pappas},
  title = {{A Control-Theoretic Approach to Analysis and Parameter Selection of Douglas-Rachford Splitting}},
  booktitle = {IEEE Control. Syst. Lett},
  year = {2020},
  url = {https://openreview.net/forum?id=JOiwL87ejdV},
}

Loading related content...

Figure