Fast ADMM Algorithm for Distributed Optimization with Adaptive Penalty

Introduction

The need for algorithms and methods that can handle large data in a distributed setting has grown significantly in recent years. Specifically, such settings may arise in two prototypical scenarios: (a) induced distributed data: distribute and parallelize computationally demanding optimization tasks to connected computational nodes using a data distributed model and (b) intrinsically distributed data: data is collected across a connected network of sensors (e.g., mobile devices, camera networks), where some or all of the computation can be performed in individual sensor nodes without requiring centralized data pooling. Several distributed learning approaches have been proposed to meet these needs. In particular, the alternating direction method of multiplier (ADMM) [boyd2010] is an optimization technique that has been very often used in computer vision and machine learning to handle model estimation and learning in either of the two large data settings [risheng2012, liansheng2012, ehsan2013, zinan2013, chunyu2014, lai2014, boussaid2014, miksik2014].

In the distributed optimization setting, the distributed nodes process data locally by solving small optimization problems and aggregate the result by exchanging the (possibly compressed) local solutions (e.g., local model parameter estimates) to arrive at a consensus global result. However, the nature of distributed learning models, particularly in the fully distributed setting where no network topology is presumed, inherently requires repetitive communications between the device nodes. Therefore, it is desirable to reduce the amount of information exchanged and simultaneously improve computational efficiency through faster convergence of such distributed algorithms.

To this end, the contributions of this paper are three fold.

We propose two variants of ADMM for the consensus-based distributed learning faster than the standard ADMM. Our method extends an acceleration approach for ADMM [he2000] by an efficient variable penalty parameter update strategy. This strategy results in improved convergence properties of ADMM and also works in a fully distributed fashion.

We extend our proposed method to automatically determine the maximum number of iterations allocated to successive updates by employing a budget magement scheme. This strategy results in adaptive parameter tuning for ADMM, removing the need for arbitrary parameter settings, and effectively induces a varying network communication topology.

We apply the proposed method to a prototypical vision and learning problem, the distributed PPCA for structure-from-motion, and demonstrate its empirical utility over the traditional ADMM.

Problem Description and Related Works

The problem we consider in this paper can be formulated as a consensus-based optimization problem [bertsekas1989]. A general consensus-based optimization problem can be written as

where we want to find the set of optimal parameters $\theta_{i},i=1..J$ that minimizes the sum of convex objective functions $f_{i}(\theta_{i})$, where $J$ denotes the total number of the functions. This problem is typically a reformulation of a centralized optimization task $\arg\min f(\theta)$ with a decomposable objective $f(\theta)=\sum_{i=1}^{J}f_{i}(\theta)$. Given the consensus formulation, the original problem can be solved by decomposing the problem into $J$ subproblems so that $J$ processors can cooperate to solve the overall problem by changing the equality constraint to $\theta_{i}=\bar{\theta}$ where $\bar{\theta}$ denotes a globally shared parameter. The optimization can be approached efficiently by exploiting the alternating direction method of multiplier (ADMM) [boyd2010].

The above consensus formulation is particularly suitable for many optimization problems that appear in computer vision. For instance, since $f_{i}(\theta_{i})$ can be any convex function, we can also consider a probabilistic model with the joint negative log likelihood $f_{i}(\theta_{i})=-\log p(x_{i},z_{i}|\theta_{i})$ between the observation $x_{i}$ and the corresponding latent variable $z_{i}$. Assuming $(x_{i},z_{i})$ are independent and identically distributed, finding the maximum likelihood estimate of the shared paramter $\bar{\theta}$ can then be formulated as the optimization problem we described above for many exponential family parametric densities. Moreover, the function need not be a likelihood, but can also be a typical decomposable and regularized loss that occurs in many vision problems such as denoising or dictionary learning.

It is often very convenient to consider the above consensus optimization problem from the perspective of optimization on graphs. For instance, the centralized i.i.d. Maximum Likelihood learning can be viewed as the optimization on the graph in Fig. 1(a). Edges in this graph depict functional (in)dependencies among variables, commonly found in representations such as Markov Random Fields [miksik2014] or Factor Graphs [bishop2006]. In this context, to fully decompose $f(\cdot)$ and eliminate the need for a processing center completely, one can introduce auxiliary variables $\rho_{ij}$ on every edge to break the dependency between $\theta_{i}$ and $\theta_{j}$ [forero2011, yoon2012] as shown in Fig. 1(b). This generalizes to arbitrary graphs, where the connectivity structure may be implied by node placement or communication constraints (camera networks), imaging constraints (pixel neighborhoods in images or frames in a video sequence), or other contextual constraints (loss and regularization structure).

In general, given a connected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with the nodes $i,j\in\mathcal{V}$ and the edges $e_{ij}=(i,j)\in\mathcal{E}$, the consensus optimization problem becomes

Solving that problem is equivalent to optimizing the augmented Lagrangian $\mathcal{L}(\bm{\Theta})=\sum_{i\in\mathcal{V}}\mathcal{L}_{i}(\bm{\Theta}_{i})$,

where $\bm{\Theta}=\{\bm{\Theta}_{i}:i\in\mathcal{V}\}$, $\bm{\Theta}_{i}=\{\theta_{i},\rho_{i},\lambda_{i}\}$ are parameters to find, $\lambda_{i}=\{\lambda_{ij1},\lambda_{ij2}:j\in\mathcal{B}_{i}\}$, $\lambda_{ij1}\text{, }\lambda_{ij2}$ are Lagrange multipliers, $\mathcal{B}_{i}=\{j|e_{ij}\in\mathcal{E}\}$ is the set of one hop neighbors of node $i$, $\eta>0$ is a fixed scalar penalty constraint, and $\|\cdot\|$ is induced norm. The ADMM approach suggests that the optimization can be done in coordinate descent fashion taking gradient of each variable while fixing all the others.

The currently known convergence rate of ADMM is $O(1/T)$ where $T$ is the number of iterations [he2012]. Even though $O(1/T)$ is the best known bound, it has been observed empirically that ADMM converges faster in many applications. Moreover, the computation time per each iteration may dominate the total algorithm running time. Thus many speed up techniques for ADMM have been proposed that are application specific. One way is to come up with a predictor-corrector step for the coordinate descent [goldstein2014] using some available acceleration method such as [nesterov1983]. It guarantees quadratic convergence for strongly convex $f_{i}(\cdot)$. Another way is to replace the gradient descent optimization with a stochastic one [ouyang2013, suzuki2013]. This approach has recently gained attention as it greatly reduces the computation per iteration. However, these methods usually require the coordinating center node thus may not readily applicable to the decentralized setting. Moreover, we want to preserve the application range of ADMM and avoid introducing additional assumptions on $f_{i}(\cdot)$.

One way to improve convergence speed of ADMM is through the use of different constraint penalty in each iteration. For example, [he2000] proposed ADMM with self-adaptive penalty, and it improved the convergence speed as well as made its performance less dependent on initial penalty values. The idea of [he2000] is to change the constraint penalty taking account of the relative magnitudes of primal and dual residuals of ADMM as follows

where $t$ is the iteration index, $\mu>1$, $\tau^{t}>0$ are parameters, $r^{t}$ and $s^{t}$ are the primal and dual residuals, respectivelyPlease refer [boyd2010], page 18 and 51 for their definitions.. The primal residual measures the violation of the consensus constraints and the dual residual measures the progress of the optimization in the dual space. This update converges when $\tau^{t}$ satisfies $\sum_{t=0}^{\infty}\tau^{t}<\infty$, i.e. we stop updating $\eta^{t}$ after a finite number of iterations. Typical choice for parameters are suggested as $\mu=10$ and $\tau^{t}=1$ at all $t$ iterations. The strength of this approach is that conservative changes in the penalty are guaranteed to converge [rockafellar1976, boyd2010]. However, like other ADMM speed up approaches mentioned above, this update scheme relies on the global computation of the primal and the dual residuals and requires the $\eta^{t}$ stored in nodes to be homogeneous over entire network thus it is not a fully decentralized scheme. Moreover, the choice of parameters as well as the maximum number of iterations require manually tuning.

Proposed Methods

We present our proposed ADMM penalty update schemes in three steps. First, we extend the aforementioned update scheme of (7) to be applicable on fully decentralized setting. Next, we propose the novel penalty parameter update strategy for ADMM speed up that does not require manual tuning of $\tau^{t}$. Finally, we extend the strategy so that we can automatically select the maximum number of penalty update iterations.

Note the difference from the standard residual definitions for consensus ADMM [boyd2010], used in (7), where the dual variable is considered as a single, globally accessible variable, $\bar{\theta}^{t}$ instead of local $\bar{\theta}_{i}^{t}$. This allows each node to change its $\eta_{i}^{t}$ based on its own local residuals. The penalty update scheme is similar to (7) but $\eta^{t}$, $\|r^{t}\|_{2}$ and $\|s^{t}\|_{2}$ are replaced with $\eta_{i}^{t}$, $\|r_{i}^{t}\|_{2}$ and $\|s_{i}^{t}\|_{2}$, respectively. Lastly, [he2000] stopped changing $\eta^{t}$ after $t>50$. However, in ADMM-VP, if we stop the same way, we end up with heterogeneously fixed penalty values which impacts the convergence of ADMM by yielding heavy oscillations near the saddle point. Therefore we reset all penalty values in all nodes to a pre-defined value (e.g. $\eta^{0}$, the initial penalty parameter) after a fixed number of iterations. As we fix the penalty values homogeneously after a finite number of iterations, it becomes the standard ADMM after that point thus the convergence of ADMM-VP update is guaranteed.

2 ADMM with Adaptive Penalty (ADMM-AP)

We further extend $\eta_{i}$ by introducing a bi-directional graph with a penalty constraint parameter $\eta_{ij}$ specific to directed edge $e_{ij}$ from node $i$ to $j$. The modified augmented Lagrangian $\mathcal{L}_{i}$ is similar to (3) except that we replace $\eta$ with $\eta_{ij}$. The penalty constraint controls the amount each constraint contributes to the local minimization problem. The penalty constraint parameter $\eta_{ij}$ is determined by evaluating the parameter $\theta_{j}$ from node $j$ with the objective function $f_{i}(\cdot)$ of node $i$ as

where $t^{max}$ is the maximum number of iterations for the update as proposed in [he2000] and

The interpretation of this update strategy is straightforward. In each iteration $t$, each $i$-th node will evaluate its objective using its own estimate of $\theta_{i}^{t}$ and the estimates from other nodes $\theta_{j}^{t}$ (we use $\rho_{ij}^{t}$ instead of actual $\theta_{j}^{t}$ to retain locality of each node from the neighbors). Then, we assign more weight to the neighbor with better parameter estimate for the local $f_{i}(\cdot)$ (i.e. larger penalty $\eta_{ij}^{t}$ if $f_{i}(\theta_{j})<f_{i}(\theta_{i})$) with the above update scheme. The intuition behind the ADMM-AP update is to emphasize the local optimization during early stages and then deal with the consensus update at later, subsequence stages. If all local parameters yield similarly valued local objectives $f_{i}(\cdot)$, the onus is placed on consensus. This makes ADMM-AP different from pre-initialization that does the local optimization using the local observations and ignores the consensus constraints.

Note that unlike the update strategy of (7), we do not need to specify $\tau^{t}$ and the update weight is automatically chosen according to the normalized difference in the local objective evaluation among neighboring parameters. The proposed algorithm also emphasizes the objective minimization over the minimization that solely depends on the norms of primal and dual residuals of constraints. The hope is that we not only achieve the consensus of the parameters of the model but also a good estimate with respect to the objective.

On the other hand, the convergence property of [he2000] still holds for the proposed algorithm. Following Remark 4.2 of [he2000], the requirement for the convergence is to satisfy the update ratio to be fixed after some $t^{\max}<\infty$ iteartions. Moreover, the proposed update ensures bounding by $\eta_{ij}^{t+1}/\eta_{ij}^{t}\in[0.5,2]$, which matches with the increase and decrease amount suggested in [he2000, boyd2010]. One may use $t^{\max}=50$ as in [he2000].

3 ADMM with Network Adaptive Penalty (ADMM-NAP)

To extend the proposed method for automatically deciding the maximum number of penalty updates, the penalty update for the ADMM becomes

Fig. 1(c) depicts how the proposed model have different structures from centralized and traditional distributed models, and how nodes share their parameters via network.

In addition to the adaptive penalty update, the inequality condition on the summation of $\tau_{ij}^{u},u=1..t$ encodes the spent budget that the edge $e_{ij}$ can change $\eta_{ij}$. All nodes have its upper bound $\mathcal{T}_{ij}^{t}$ and everytime it makes a change to $\eta_{ij}$, it has to pay exactly the amount they changed. If the edge has changed too much, too often, the update strategy will block the edge from changing $\eta_{ij}$ any more.

The update scheme is guaranteed to convergence if $\mathcal{T}_{ij}^{t}$ is simply set to constant $\mathcal{T}$ for all $i,j,t$ or if $\tau_{ij}^{t}=0$ for $t>t^{max}$. However, with a different objective function and different network connectivity, a different upper bound should be imposed. This is because a given upper bound $\mathcal{T}$ or maximum iteration $t^{max}$ could be too small for a certain node to fully take an advantage of our adaptation strategy or they could be too big so that it converges much slowly because of the continuously changing $\eta_{ij}^{t}$. To this end, we propose updating strategy for $\mathcal{T}_{ij}^{t}$ as following:

where $\mathcal{T}_{ij}^{0}$ is set by an initial parameter $\mathcal{T}$ and $\alpha,\beta\in(0,1)$ are parameters. Whenever $\mathcal{T}_{ij}^{t+1}>\mathcal{T}_{ij}^{t}$, we increase $n$ by 1. Once $\sum_{u=1}^{t}|\tau_{ij}^{u}|\geq\mathcal{T}_{ij}^{t}$ but its objective value is still significantly changing, i.e. $|f_{i}(\theta_{i}^{t})-f_{i}(\theta_{i}^{t-1})|>\beta$, $\mathcal{T}_{ij}^{t+1}$ is increased by $\alpha^{n}\mathcal{T}$. Note that the independent upper bound $\mathcal{T}_{ij}^{t}$ for each $\eta_{ij}^{t}$ update on the edge $e_{ij}$ makes it sensitive to the various network topology, but it still satisfies the convergence condition because

4 Combined Update Strategies (ADMM-VP + AP, ADMM-VP + NAP)

Observing (7) and the proposed update schemes (11) and (16), one can easily come up with a combined update strategy by replacing $\tau^{t}$ in (7) with $\tau_{ij}^{t}$. Based on preliminary experiments, we found that this replacement yields little utility. Instead, we suggest another penalty update strategy combining ADMM-VP and ADMM-AP as

which we denote as ADMM-VP + AP. We reset $\eta_{ij}^{t}=\eta^{0}$ when $t>t^{\max}$. In order to combine ADMM-VP and ADMM-NAP, we consider the summation condition of $\tau_{ij}^{t}$ as in (16). We denote this strategy as ADMM-VP + NAP.

Distributed Maximum Likelihood Learning

In this section, we show how our method can be applied to an existing distributed learning framework in the context of distributed probabilistic principal component analysis (D-PPCA). D-PPCA can be viewed as fundamental approach to a general matrix factorization task in the presence of potentially missing data, with many applications in machine learning.

where $\mathbf{M}=\mathbf{W}^{\top}\mathbf{W}+a^{-1}\mathbf{I}$. The parameters $\mathbf{W}$, $\bm{\mu}$, and $a$ can be estimated using a number of methods, including SVD and Expectation Maximization (EM) algorithm.

2 Distributed PPCA

The distributed extension of PPCA (D-PPCA) [yoon2012] can be derived by applying ADMM to the centralized PPCA model above. Each node learns its local copy of PPCA parameters with its set of local observations $\mathbf{X}_{i}=\{\mathbf{x}_{in}|n=1..N_{i}\}$ where $\mathbf{x}_{in}$ denotes the $n$-th observation in $i$-th node and $N_{i}$ is the number of observations available in the node. Then, they exchange the parameters using the Lagrange multipliers and impose consensus constraints on the parameters. The global constrained optimization is

where $i\in\mathcal{V},j\in\mathcal{B}_{i}$, $\bm{\Theta}_{i}=\{\mathbf{W}_{i},\bm{\mu}_{i},a_{i}\}$ is the set of local parameters and $\rho_{ij}^{\bm{\Theta}}=\{\rho_{ij}^{\mathbf{W}},\rho_{ij}^{\bm{\mu}},\rho_{ij}^{a}\}$ is the set of auxiliary variables for the parameters. For the details regarding how the decentralized model is optimized, see [yoon2012].

3 D-PPCA with Network Adpative Penalty

The augmented Lagrangian applying the proposed ADMM with Network Adpative Penalty is similar to [yoon2012] except that $\eta$ becomes $\eta_{ij}$. with $\lambda_{i}$, $\gamma_{i}$, $\beta_{i}$ are Lagrange multipliers for the PPCA parameters for node $i$. The adaptive penalty constraint $\eta_{ij}^{t}$ controls the speed of parameter propagation dynamically so that the overall optimization empirically converges faster than [yoon2012]. One can solve this optimization using the distributed EM approach [forero2011]. The E-step of the D-PPCA is the same as centralized counterpart [tipping1999]. The M-step is similar to [yoon2012] except we use separate $\eta_{ij}$ for each edge. Since the update formulas for the three parameters are similar, we present the $\bm{\mu}_{i}$ update as an example. First, $\bm{\mu}_{i}$ can be updated as

Experiments

We first analyze and compare the proposed methods (ADMM-VP, ADMM-AP, ADMM-NAP, ADMM-VP + AP, ADMM-VP + NAP) with the baseline method using synthetic data. Next, we apply our method to a distributed structure from motion problem using two benchmark real world datasets. For the baseline, we compare with the standard ADMM-based D-PPCA [yoon2012] denoted as ADMM. Unless noted otherwise, we used $\eta^{0}=10$. To assess convergence, we compare the relative change of (26) to a fixed threshold ($10^{-3}$ in this case) for the D-PPCA experiments as in [yoon2012].