A primal-dual method for conic constrained distributed optimization problems
We consider cooperative multi-agent consensus optimization problems over an undirected network of agents, where only those agents connected by an edge can directly communicate. The objective is to minimize the sum of agentspecific composite convex functions over agent-specific private conic constraint sets; hence, the optimal consensus decision should lie in the intersection of these private sets. We provide convergence rates in sub-optimality, infeasibility and consensus violation; examine the effect of underlying network topology on the convergence rates of the proposed decentralized algorithms; and show how to extend these methods to handle time-varying communication networks.
The authors consider the problem of decentralized optimization when each local objective is a composition of a convex smooth non-smooth term. They consider the saddle point formulation of this constrained optimization problem, and by considering its Lagrangian relaxation, propose a primal dual scheme to solve it. This method is particularly useful for cases where projection onto the local constraint set is easily computable. By deriving a closed form expression for the Lagrange multiplier update of this problem, an efficient algorithm is developed. It is shown that this method converge a primal dual optimal pair at a rate of $1/K$ when the primal vector is recursively averaged. Then the authors consider the extension of this method to a time-varying graph by incorporating an inner-loop communications protocol between neighboring agents, which leads to a modified dual update with several consensus steps per objective gradient update. The convergence guarantees of the static network case are generalized to the switching network case. Then, numerical analysis on a support vector classification problem demonstrate's the proposed methods empirical convergence behavior.
Generally speaking, there is not enough explanation of key quantities of interest in between the presentation of main results or ideas, e.g., at the beginning of Algorithm DPDA-S the intialization variables should also be explained (initialize primal variables, dual variables, learning rate, etc); The derivation of the fact that the dual variable update may be written in terms of the sequence $s_i^k$ requires more explanation (perhaps a display equation relating $s$ and $lambda$); Theorem 2.2 has no discussion...all theorems and lemmas need discussion/interpretation.  The paper is not very readable as a result. The extension of the proposed method to time-varying topology could be omitted so that more explication and context for the algorithm derivation could fit. Nonetheless, the technical contributions of the paper are substantial in extending the primal-dual method to composite constrained convex programming in decentralized (time-varying network) settings. Numerical analysis for a decentralized support vector classification problem on a static network demonstrate the proposed method's practical utility, but are not very convincing for practitioners -- I find the multivariate Gaussian data example to be a mere toy problem. A switching network might arise in a cloud computing or computer network in which case a problem such as a playback buffer, resource allocation, or data packet routing would be more appropriate.     --The bounded linear operator $T$ in equation (4) is left undefined, and had to be looked up in reference [11]. This makes the initial presentation of the proposed algorithm confusing, and not self-contained. Must $T$ be as in Theorem 1.1, or could it be any linear operator?  --Also, why does a 2 appear in front of the inner-product term $\langle T( 2 x^{k+1} - x^k), y \rangle$ in equation (6)? This scaling does NOT appear in the update formula for (7) in reference [11]. This may be a mistake, but its carried through equations in the rest of the paper.   -- In equation (8) the Lagrange multipliers $\lambda_{ij}$ are included in the optimization problem as a domain constraint but don't actually effect the objective or the constraint functions. Thus, this is probably a typo and should be deleted until the Lagrangian relaxation presented in (9).