Adaptive ADMM with Spectral Penalty Parameter Selection

Introduction

The alternating direction method of multipliers (ADMM) is an invaluable element of the modern optimization toolbox. ADMM decomposes complex optimization problems into sequences of simpler subproblems, often solvable in closed form; its simplicity, flexibility, and broad applicability, make ADMM a state-of-the-art solver in machine learning, signal processing, and many other areas (Boyd et al., 2011).

It is well known that the efficiency of ADMM hinges on the careful selection of a penalty parameter, which needs to be manually tuned by users for their particular problem instances. In contrast, for gradient descent and proximal-gradient methods, adaptive (i.e. automated) stepsize selection rules have been proposed, which essentially dispense with user oversight and dramatically boost performance (Barzilai and Borwein, 1988; Fletcher, 2005; Goldstein et al., 2014b; Wright et al., 2009b; Zhou et al., 2006).

In this paper, we propose to automate and speed up ADMM by using stepsize selection rules adapted from the gradient descent literature, namely the Barzilai-Borwein “spectral” method for smooth unconstrained problems (Barzilai and Borwein, 1988; Fletcher, 2005). Since ADMM handles multi-term objectives and linear constraints, it is not immediately obvious how to adopt such rules. The keystone of our approach is to analyze the dual of the ADMM problem, which can be written without constraints. To ensure reliability of the method, we develop a correlation criterion that safeguards it against inaccurate stepsize choices. The resulting adaptive ADMM (AADMM) algorithm is fully automated and fairly insensitive to the initial stepsize, as testified for by a comprehensive set of experiments.

Background and Related Work

ADMM dates back to the 1970s Gabay and Mercier (1976); Glowinski and Marroco (1975). Its convergence was shown in the 1990s Eckstein and Bertsekas (1992), and convergence rates have been the topic of much recent work, e.g., by Goldstein et al. (2014a); He and Yuan (2015); Nishihara et al. (2015). In the last decade, ADMM became one of the tools of choice to handle a wide variety of optimization problems in machine learning, signal processing, and many other areas (Boyd et al., 2011).

where the sequence of penalties $\tau_{k}$ is the only free choice, and has a high impact on the algorithm’s speed. Our goal is to automate this choice, by adaptively tuning $\tau_{k}$ for optimal performance.

The convergence of the algorithm can be monitored using primal and dual “residuals,” both of which approach zero as the iterates become more accurate, and which are defined as

respectively (Boyd et al., 2011). The iteration is generally stopped when

where $\epsilon^{tol}>0$ is the stopping tolerance.

2 Parameter tuning and adaptation

Relatively little work has been done on automating ADMM, i.e., on adaptively choosing $\tau_{k}$. In the particular case of a strictly convex quadratic objective, criteria for choosing an optimal constant penalty have been recently proposed by Ghadimi et al. (2015); Raghunathan and Di Cairano (2014). Lin et al. (2011) proposed a non-increasing sequence for the linearization parameter in “linearized” ADMM; however, they do not address the question of how to choose the penalty parameter in ADMM or its variants.

Residual balancing (RB) He et al. (2000); Boyd et al. (2011) is the only available adaptive method for general form problems (1); it is based on the following observation: increasing $\tau_{k}$ strengthens the penalty term, yielding smaller primal residuals but larger dual ones; conversely, decreasing $\tau_{k}$ leads to larger primal and smaller dual residuals. As both residuals must be small at convergence, it makes sense to “balance” them, i.e., tune $\tau_{k}$ to keep both residuals of similar magnitude. A simple scheme for this goal is

with $\mu>1$ and $\eta>1$ Boyd et al. (2011). RB has recently been adapted to distributed optimization Song et al. (2015) and other primal-dual splitting methods Goldstein et al. (2015). ADMM with adaptive penalty is not guaranteed to converge, unless $\tau_{k}$ is fixed after a finite number of iterations He et al. (2000).

Despite some practical success of the RB idea, it suffers from several flaws. The relative size of the residuals depends on the scaling of the problem; e.g., with the change of variable $u\leftarrow 10u$, problem (1) can be re-scaled so that ADMM produces an equivalent sequence of iterates with residuals of very different magnitudes. Consequently, RB criteria are arbitrary in some cases, and their performance varies wildly with different problem scalings (see Section 4.4). Furthermore, the penalty parameter may adapt slowly if the initial value is far from optimal. Finally, without a careful choice of $\eta$ and $\mu$, the algorithm may fail to converge unless adaptivity is turned off He et al. (2000).

3 Dual interpretation of ADMM

We now explain the close relationship between ADMM and Douglas-Rachdord splitting (DRS) Eckstein and Bertsekas (1992); Esser (2009); Goldstein et al. (2014a), which plays a central role in the proposed approach. The starting observation is that the dual of problem (1) has the form

where $F^{*}$ denotes the Fenchel conjugate of $F$, defined as $F^{*}(y)=\sup_{x}\langle x,y\rangle-F(x)$ Rockafellar (1970).

where we use the standard notation $\partial F(x)$ for the subdifferential of $F$ evaluated at $x$ Rockafellar (1970).

Referring back to ADMM in (2)–(4), and defining $\hat{\lambda}_{k+1}=\lambda_{k}+\tau_{k}(b-Au_{k+1}-Bv_{k}),$ the optimality condition for the minimization in (2) is

which is equivalent to $A^{T}\hat{\lambda}_{k+1}\in\partial H(u_{k+1}),$ thusAn important property relating $F$ and $F^{*}$ is that $y\in\partial H(x)$ if and only if $x\in\partial H^{*}(y)$ Rockafellar (1970). $u_{k+1}\in\partial H^{*}(A^{T}\hat{\lambda}_{k+1}).$ A similar argument using the optimality condition for (3) leads to $v_{k+1}\in\partial G^{*}(B^{T}\lambda_{k+1}).$ Recalling (8), we arrive at

4 Spectral stepsize selection

In a nutshell, the standard (there are variants) BB method sets $\tau_{k}=1/\alpha_{k}$, with $\alpha_{k}$ chosen such that $\alpha_{k}I$ mimics the Hessian of $F$ over the last step, seeking a quasi-Newton step. A least squares criterion yields

which is an estimate of the curvature of $F$ across the previous step of the algorithm. BB gradient methods often dramatically outperform those with constant stepsize Fletcher (2005); Zhou et al. (2006) and have been generalized to handle non-differentiable problems via proximal gradient methods Wright et al. (2009b); Goldstein et al. (2014b); Goldstein and Setzer (2010). Finally, notice that (14) is equivalent to approximating the gradient $\nabla F(x_{k})$ as a linear function of $x_{k}$,

where $a_{k}=\nabla F(x_{k-1})-\alpha_{k}\,x_{k-1}$. The observation that a local linear approximation of the gradient has an optimal parameter equal to the inverse of the BB stepsize will play an important role below.

Spectral penalty parameters

Inspired by the BB method, we propose a spectral penalty parameter selection method for ADMM. We first derive a spectral stepsize rule for DRS, and then adapt this rule to ADMM. Finally, we discuss safeguarding rules to prevent unexpected behavior when curvature estimates are inaccurate.

Consider the dual problem (8). Following the observation in (15) about the BB method, we approximate $\partial\hat{H}$ and $\partial\hat{G}$ at iteration $k$ as linear functions,

Then, the minimal residual of $\hat{H}(\zeta_{k+1})+\hat{G}(\zeta_{k+1})$ is obtained by setting $\tau_{k}=1/\sqrt{\alpha\,\beta}$.

Inserting (16) into the DRS step (9)–(10) yields

From (17)–(18), we can explicitly get the update for $\hat{\zeta}_{k+1}$ as

where $a\in\Psi$ and $b\in\Phi$, and for $\zeta_{k+1}$ as

where the second equality results from using the expression for $\hat{\zeta}_{k+1}$ in (19).

The residual $r_{\mbox{DR}}$ at $\zeta_{k+1}$ is simply the magnitude of the subgradient (corresponding to elements $a\in\Psi$ and $b\in\Phi$) of the objective that is given by

where $\zeta_{k+1}$ in (23) was substituted with (21). The optimal stepsize $\tau_{k}$ minimizes the residual

Proposition 1 shows how to adaptively choose $\tau_{k}$: begin by obtaining linear estimates of the subgradients of the two terms in the dual objective (8); the geometric mean of these optimal gradient descent stepsizes is then the optimal DRS stepsize, thus also the optimal ADMM penalty parameter, due to the equivalence shown in Subsection 2.3.

2 Spectral stepsize estimation

We now address the estimation of $\hat{\alpha}_{k}=1/\alpha_{k}$ and $\hat{\beta}_{k}=1/\beta_{k}$. These curvature parameters are estimated based on the results from iteration $k$ and an older iteration $k_{0}<k.$ Noting (11), we define

Assuming, as above, a linear model for $\partial\hat{H}$, we expect $\Delta\hat{H}_{k}\approx\alpha\,\Delta\hat{\lambda}_{k}+a.$ As is typical in BB-type methods Barzilai and Borwein (1988); Zhou et al. (2006), $\alpha$ is estimated via one of the two least squares problems

The closed form solutions for the corresponding spectral stepsizes $\hat{\alpha}_{k}=1/\alpha_{k}$ are, respectively,

where, following Zhou et al. (2006), SD stands for steepest descent and MG for minimum gradient. The Cauchy-Schwarz inequality implies that $\hat{\alpha}_{k}^{\mbox{SD}}\geq\hat{\alpha}_{k}^{\mbox{MG}}.$ Rather than choosing one or the other, we suggest the hybrid stepsize rule proposed by Zhou et al. (2006),

The spectral stepsize $\hat{\beta}_{k}=1/\beta_{k}$ is similarly set to

where ${\hat{\beta}_{k}^{\mbox{SD}}}=\langle\Delta\lambda_{k},\Delta\lambda_{k}\rangle/\langle\Delta\hat{G}_{k},\Delta\lambda_{k}\rangle$, $\hat{\beta}_{k}^{\mbox{MG}}=\langle\Delta\hat{G}_{k},\Delta\lambda_{k}\rangle/\langle\Delta\hat{G}_{k},\Delta\hat{G}_{k}\rangle$, $\Delta\hat{G}_{k}=B(v_{k}-v_{k_{0}})$, and $\Delta\lambda_{k}=\lambda_{k}-\lambda_{k_{0}}$. It is important to note that $\hat{\alpha}_{k}$ and $\hat{\beta}_{k}$ are obtained from the iterates of ADMM, i.e., the user is not required to supply the dual problem.

3 Safeguarding

On some iterations, the linear models (for one or both subgradients) underlying the spectral stepsize choice may be very inaccurate. When this occurs, the least squares procedure may produce ineffective stepsizes. The classical BB method for unconstrained problems uses a line search to safeguard against unstable stepsizes resulting from unreliable curvature estimates. In ADMM, however, there is no notion of “stable” stepsize (any constant stepsizes is stable), thus line search methods are not applicable. Rather, we propose to safeguard the method by assessing the quality of the curvature estimates, and only updating the stepsize if the curvature estimates satisfy a reliability criterion.

The linear model (16) assumes the change in dual (sub)gradient is linearly proportional to the change in the dual variables. To test the validity of this assumption, we measure the correlation between these quantities (equivalently, the cosine of their angle):

The spectral stepsizes are updated only if the correlations indicate the estimation is credible enough. The safeguarded spectral adaptive penalty rule is

where $\epsilon^{\mbox{cor}}$ is a quality threshold for the curvature estimates, while $\hat{\alpha}_{k}$ and $\hat{\beta}_{k}$ are the stepsizes given by (27)–(28). Notice that (30) falls back to constant $\tau_{k}$ when both curvature estimates are deemed inaccurate.

4 Adaptive ADMM

Algorithm 1 shows the complete adaptive ADMM (AADMM). We suggest only updating the stepsize every $T_{f}$ iterations. Safeguarding threshold $\epsilon^{\mbox{cor}}=0.2$ and $T_{f}=2$ generally perform well. The overhead of AADMM over ADMM is modest: only a few inner products plus the storage to keep one previous iterate.

5 Convergence

He et al. (2000) proved that convergence is guaranteed for ADMM with adaptive penalty when either of the two following conditions are satisfied:

Condition 1 (Condition 2) suggests that increasing (decreasing) of adaptive penalty is bounded. In practice, these conditions can be satisfied by turning off adaptivity after a finite number of steps, which we have found unnecessary in our experiments with AADMM.

Experiments

For comparison, we implemented vanilla ADMM (fixed stepsize), fast ADMM with a restart strategy Goldstein et al. (2014a), and ADMM with residual balancing Boyd et al. (2011); He et al. (2000), using (7) with $\mu=10$ and $\eta=2$, and adaptivity was turned off after 1000 iterations to guarantee convergence. The proposed AADMM is implemented as shown in Algorithm 1, with fixed parameters $\epsilon^{\mbox{cor}}=0.2$ and $T_{f}=2$.

We set the stopping tolerance to $\epsilon^{tol}=10^{-5},10^{-3},$ and $0.05$ for small, medium, and large scale problems, respectively. The initial penalty $\tau_{0}=0.1$ is used for all problems, except the canonical QP, where $\tau_{0}$ is set to the value proposed for quadratic problems by Raghunathan and Di Cairano (2014). For each problem, the same randomly generated initial variables $v_{0},\lambda_{0}$ are used for ADMM and all the variants thereof.

2 Applications

The synthetic dataset introduced by Zou and Hastie (2005) and realistic dataset introduced by Efron et al. (2004); Zou and Hastie (2005) are investigated. Typical parameters $\rho_{1}=\rho_{2}=1$ are used in all experiments.

Low rank least squares (LRLS) uses the nuclear matrix norm (sum of singular values) as the convex surrogate of matrix rank,

Support vector machine (SVM) and QP: the dual of the SVM learning problem is a QP

where $z$ is the SVM dual variable, $Q$ is the kernel matrix, $c$ is a vector of labels, $e$ is a vector of ones, and $C>0$ Chang and Lin (2011). We also consider the canonical QP

here, $\iota_{S}$ is the indicator function of set $S$: $\iota_{S}(v)=0$, if $v\in S$, and $\iota_{S}(v)=\infty$, otherwise.

Basis pursuit (BP) seeks a sparse representation of a vector $c$ by solving the constrained problem

A synthetic problem is constructed with Gaussian random data and sparse ground truth solutions. Binary classification problems from Lee et al. (2006); Liu et al. (2009), and Schmidt et al. (2007) are also used to test the effectiveness of the proposed method. We use $\rho=1$, for small and medium datasets, and $\rho=5$ for the large datasets to encourage sparsity. We split the data equally into two blocks and use a loop to simulate the distributed computing of consensus subproblems.

Semidefinite programming (SDP) solves the problem

where $\mathcal{D}^{*}(y)=\sum_{i=1}^{m}y_{i}D_{i}$, and $S$ is a symmetric positive semidefinite matrix.

As test data, we use 6 graphs from the Seventh DIMACS Implementation Challenge on Semidefinite and Related Optimization Problems (following Burer and Monteiro (2003)).

3 Convergence results

Table 1 reports the convergence speed of ADMM and its variants for the applications described in Subsection 4.2. Vanilla ADMM with fixed stepsize does poorly in practice: in 13 out of 23 realistic datasets, it fails to converge in the maximum number of iterations. Fast ADMM Goldstein et al. (2014a) often outperforms vanilla ADMM, but does not compete with the proposed AADMM, which also outperforms residual balancing in all test cases except in the Rcv1 problem for consensus logistic regression.

Fig. 1 presents the relative residual (top) and penalty parameter (bottom) for the synthetic BP problem. The relative residual is defined as

which is based on stopping criterion (6). Fast ADMM often restarts and is slow to converge. The penalty parameter chosen by RB oscillates. AADMM quickly adapts the penalty parameter and converges fastest.

4 Sensitivity

We study the sensitivity of the different ADMM variants to problem scaling and initial penalty parameter ($\tau_{0}$). Scaling sensitivity experiments were done by multiplying the measurement vector $c$ by a scalar $s$. Fig. 2 presents iteration counts for a wide range of values of initial penalty $\tau_{0}$ (top) and problems scale $s$ (bottom) for EN regression, canonical QP, and LRLS with synthetic datasets. Fast ADMM and vanilla ADMM use the fixed initial penalty parameter $\tau_{0}$, and are highly sensitive to this choice, as shown in Fig. 2; in contrast, AADMM is very stable with respect to $\tau_{0}$ and the scale $s$.

Finally, Fig. 3 presents iteration counts when applying AADMM with various safeguarding correlation thresholds $\epsilon^{{\text{cor}}}.$ When $\epsilon^{{\text{cor}}}=0$ the new penalty value is always accepted, and when $\epsilon^{{\text{cor}}}\!=\!1$ the penalty parameter is never changed. The proposed AADMM method is insensitive to $\epsilon^{{\text{cor}}}$ and performs well for a wide range of $\epsilon^{{\text{cor}}}\in[0.1,\,0.4]$ for various applications.

Conclusion

We have proposed adaptive ADMM (AADMM), a new variant of the popular ADMM algorithm that tackles one of its fundamental drawbacks: critical dependence on a penalty parameter that needs careful tuning. This drawback has made ADMM difficult to use by non-experts, thus AADMM has the potential to contribute to wider and easier applicability of this highly flexible and efficient optimization tool. Our approach imports and adapts the Barzilai-Borwein “spectral” stepsize method from the smooth optimization literature, tailoring it to the more general class of problems handled by ADMM. The cornerstone of our approach is the fact that ADMM is equivalent to Douglas-Rachford splitting (DRS) applied to the dual problem, for which we develop a spectral stepsize selection rule; this rule is then translated into a criterion to select the penalty parameter of ADMM. A safeguarding function that avoids unreliable stepsize choices finally yields AADMM. Experiments on a comprehensive range of problems and datasets have shown that AADMM outperforms other variants of ADMM and is robust with respect to initial parameter choice and problem scaling.

TG and ZX were supported by the US Office of Naval Research (N00014-17-1-2078), and by the US National Science Foundation (CCF-1535902). MF was partially supported by the Fundação para a Ciência e Tecnologia, grant UID/EEA/5008/2013.

References