Equilibrate parametrization: optimal stepsizes and acceleration limits for ADMM-type algorithms

Abstract

This manuscript is devoted to solving a long-standing open problem, the optimal step-size choice for ADMM-type first-order algorithms. This issue is tightly connected to a well-known heuristic, preconditioning, which will be shown as equivalent. Our key contribution is proposing a new way of parametrization. Conventionally, the step-size parameter is always assigned to the range of a function or an operator. We show that this is not mathematically natural in the sense that an extra, step-size related scaling arises, posing a hidden obstacle to optimizing parameters. Also, it is the cause of certain inconsistencies and complications that appear to be overlooked in the current literature. Overall, we claim that the classical range-parametrization should be viewed as a shifted variant of our equilibrate parametrization, which associates the step-size parameter to the domain of a function, and both the domain and range of a monotone operator. Our demonstration is via a standard tool, the proximal operator. Our optimal step-size choice applies to all ADMM-type convex programs. Its optimality is in the worst-case convergence rate sense, and no tailored structure is exploited. Hence, in the applications, we will see that our step-size choice does not yield exactly the best fixed choice (which can be found by exhaustive grid search). Luckily, in all our preliminary simulations, our worst-case optimal step-size performs highly similarly to the underlying best fixed step-size, which seems sufficient for basic practical use. At last, we generalize the step-size from a scalar to an operator. Two examples are given regarding the l1-minimization and the semidefinite programming. Quite remarkably, we prove that — under zero initialization, choose the step-size to be a certain diagonal matrix, then the l1-minimization problem can be solved via a one-time proximal operator evaluation, i.e., the corresponding algorithm converges in one iteration, which attains the acceleration limit.