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.
Introduction
In the fields of machine learning and control, Douglas-Rachford Splitting (DRS) and its dual counterpart, the Alternating Direction Method of Multipliers (ADMM), are considered "workhorse" algorithms for solving complex composite optimization problems. However, their efficiency is highly sensitive to two key parameters: the proximal step size ($\alpha$) and the relaxation parameter ($\lambda$).
Traditionally, these parameters have been selected using heuristics or exhaustive trial-and-error grid searches. While theoretical bounds exist for specific cases, a unified, automated method for analyzing DRS and selecting optimal parameters across a broad range of function classes has remained elusive. This paper bridges that gap by reframing optimization through the lens of control theory.
A Control-Theoretic Framework
The core innovation of this work is the representation of the DRS update equations as a discrete-time linear dynamical system. In this model, the algorithm's iterate is treated as the "state," and the nonlinear proximal operator is treated as "feedback." To analyze this system, the authors utilize three primary control-theoretic tools:
- Incremental Quadratic Constraints (IQCs): These mathematical inequalities bound the behavior of the nonlinear proximal operators based on objective properties like convexity and smoothness.
- Lyapunov Analysis: By proposing a family of energy functions (Lyapunov functions) and proving they decrease at each iteration, the authors can guarantee convergence.
- Matrix Inequalities: The convergence conditions are transformed into dimensionally independent matrix inequalities.
As shown in Figure 1, this framework allows for the visualization and calculation of the convergence rate $\rho$ across different parameter spaces and problem condition numbers ($\kappa_f$).
Automated Parameter Selection via SDP
Unlike previous research that used Semidefinite Programming (SDP) merely to verify if a specific parameter choice would work, this framework is the first to directly solve for optimal parameters. By utilizing the Schur Complement to linearize the dependence on the relaxation parameter $\lambda$, the authors can use an SDP solver to output the mathematically optimal $\lambda$ and convergence rate $\rho$ simultaneously.
A key insight from this analysis is that for strongly convex problems, the SDP consistently identifies $\lambda = 2$ as the optimal relaxation parameter across various condition numbers and step sizes.
Key Results and Empirical Validation
The control-theoretic approach yields several significant theoretical and empirical results:
- Simplified $O(1/k)$ Proof: The framework provides a new, simpler proof for the convergence rate in the most general, non-strongly convex cases.
- Dimension Independence: The derived inequalities do not depend on the dimension of the decision variables, ensuring the analysis scales to massive datasets.
- Empirical Accuracy: Numerical experiments on standard benchmarks like Basis Pursuit and LASSO regression confirm that the "optimal" step size $\alpha^*$ predicted by the theory matches the peak performance observed in practice.
As illustrated in Figure 2, the predicted optimal parameters lead to significantly faster objective value reduction and lower error residuals compared to heuristic settings.
Conclusion
By treating optimization as a dynamical system with feedback, this research provides a robust and automated methodology for tuning Douglas-Rachford Splitting. While currently focused on two-block problems ($f + g$), the authors suggest that this approach can be extended to accelerated versions of DRS and multi-block ADMM formulations, potentially standardizing parameter selection for a wide array of optimization challenges.
Summary updated