- Rating
- 2
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies decentralized convex composite optimization over connected undirected networks. It proposes CFI-spALM, an inexact semi-proximal augmented Lagrangian method whose block-diagonal majorizer separates the primal subproblem into independent local problems. Agents perform local proximal-gradient or accelerated proximal-gradient iterations until a locally computable absolute or relative residual criterion is satisfied, followed by one model-vector exchange per outer iteration. The analysis establishes finite termination of the local solver, convergence under both stopping rules, an best-iterate KKT residual bound, ergodic feasibility and objective-error bounds, and linear convergence under additional error-bound and inexactness conditions. Experiments on synthetic logistic regression and rank-deficient LASSO compare the methods in terms of communication cost.
Critical strengths
-
Building on the preconditioned proximal ALM framework, the method uses a structured semi-proximal term to decouple the primal subproblem across agents. This enables multiple local updates without inner communication, requiring only one model-vector exchange per outer iteration.
-
The absolute and relative stopping rules can be checked independently at each node, allowing adaptive local computation. A coherent analysis establishes convergence and sublinear rates for both rules, together with linear convergence under suitable error-bound and inexactness conditions
Critical weaknesses
-
The experiments are restricted to synthetic logistic regression and LASSO problems, using Erdős–Rényi graphs with a fixed edge probability. No real-data evaluation or controlled comparison across different network connectivity levels is reported. This limits the evidence that the observed communication gains extend to practical datasets and a broader range of network conditions.
-
Relationship to existing primal–dual methods. Prox-PDA (Hong et al., ICML 2017) employs a signless-Laplacian proximal term to obtain separable primal subproblems, which appears closely related to the proposed semi-proximal decoupling. Moreover, FlexPD-G (Mansoori and Wei, IEEE TSP 2021) allows multiple local gradient steps per communication round, while inexact consensus ADMM (Chang et al., IEEE TSP 2015) considers inexact local primal updates. Could the authors clarify the main algorithmic and theoretical differences from these methods, particularly the additional benefits of the proposed locally verifiable stopping criteria and convergence guarantees?
[1] Hong, Hajinezhad & Zhao (2017), ICML — Prox-PDA: The Proximal Primal-Dual Algorithm for Fast Distributed Nonconvex Optimization and Learning Over Networks.
[2] Mansoori & Wei (2021), IEEE TSP — FlexPD: A Flexible Framework of First-Order Primal-Dual Algorithms for Distributed Optimization
[3] Chang, Hong & Wang (2015), IEEE TSP — Multi-Agent Distributed Optimization via Inexact Consensus ADMM
Questions for authors
-
Could the authors explicitly characterize how the convergence rates and communication complexity depend on network connectivity? Furthermore, can the authors quantify the total local gradient/proximal evaluations required to reach a target accuracy, including their dependence on network conditions and stopping tolerances? How does the resulting communication–computation trade-off compare with existing methods?
-
For smooth nonconvex and convex , could an appropriate choice of preserve the communication-free local solves and locally verifiable stopping rules? What are the main obstacles to establishing convergence to stationary points?
5 comments
2/N. Connection to FlexPD-G (W2)
We thank the reviewer for suggesting FlexPD-G. We have added the appendix subsection Connection to FlexPD-G to explain its relationship to CFI-spALM. Specifically:
FlexPD-G performs a prescribed number of local gradient steps before each multiplier update. We compare its local objective, solution rule, and convergence assumptions with those of CFI-spALM.
-
Connection between the subproblems.
Consider the smooth case . For a direct comparison, choose the consensus matrix, network augmentation matrix, and dual stepsize in FlexPD-G as , , and , respectively. Writing , the resulting iteration is
U^{t,e+1} &=U^{t,e}-\alpha\left[\nabla F(U^{t,e})+\Omega^t+\rho\mathcal Z X^t\right], \qquad U^{t,0}=X^t,\\ \Omega^{t+1} =\Omega^t+\rho\mathcal Z X^{t+1}, \qquad X^{t+1}=U^{t,E}, \end{aligned}$$ where $\alpha>0$ is the primal stepsize, $E\ge1$ is a fixed number of local updates, and $e=0,\ldots,E-1$. Thus, the inner iterations perform $E$ gradient steps on $$Q_{\mathrm F}^t(X):=F(X)+\langle\Omega^t+\rho\mathcal Z X^t,X\rangle.$$ This objective is obtained algebraically from our separable subproblem by setting $G\equiv0$ and $M=0$, corresponding to $S=-\rho\mathcal Z$. Both methods use cached network information throughout the inner iterations and require one model-vector exchange per outer round. -
Regularization and local accuracy.
CFI-spALM retains the composite objective and includes the quadratic term , which makes each local subproblem strongly convex even when is only convex. This also allows the use of local solvers that exploit strong convexity, including accelerated proximal-gradient methods. The local solver terminates when the first-order residual satisfies the proposed absolute or relative stopping criterion, allowing the number of updates to vary across agents and rounds.
-
Convergence guarantees.
FlexPD-G establishes global linear convergence for smooth strongly convex local objectives under appropriate stepsize and matrix conditions. Our analysis additionally covers general convex composite objectives. Under the stated error conditions, we establish convergence to the KKT set, an best-iterate KKT residual bound, and ergodic objective and feasibility bounds. We further obtain local linear convergence under KKT error bounds and the corresponding accuracy conditions, without requiring strong convexity of the original objectives.
3/N. Connection to (I)C-ADMM (W2)
We thank the reviewer for this suggestion. We added the appendix subsection Connection to (I)C-ADMM to compare exact updates, parameter choices, and inexact local solves.
C-ADMM (Chang et al., 2015) uses edge splitting. Its local objective fits ours with , where is a local data matrix.
- Connection between the exact updates.
For the unweighted graph, let and be its adjacency and degree matrices, , and . C-ADMM updates:
x_i^{t+1}&\in\arg\min_x\left\\{f_i(x)+g_i(x)+\langle\omega_i^t,x\rangle+c\sum_{j\in\mathcal N_i}\left\\|x-\frac{x_i^t+x_j^t}{2}\right\\|^2\right\\},\\\\ \omega_i^{t+1}&=\omega_i^t+c\sum_{j\in\mathcal N_i}(x_i^{t+1}-x_j^{t+1}). \end{aligned} \tag{C1}$$ Here $c>0$ and $\omega_i^t$ is the $i$th block of $\Omega^t$. Expanding gives $$c\sum_{j\in\mathcal N_i}\left\\|x-\frac{x_i^t+x_j^t}{2}\right\\|^2 =cd_i\\|x-x_i^t\\|^2+c\langle(\mathcal L_GX^t)_i,x\rangle+\mathrm{const}, \tag{C2}$$ where the constant is independent of $x$. For admissible $\alpha>0$, set $W=I_n-\alpha L_G$ and $c=\alpha\rho$. Then $\rho\mathcal Z=c\mathcal L_G$, and (C1) becomes $$\begin{aligned} X^{t+1}&\in\arg\min_X\left\\{\Phi(X)+\langle\Omega^t+\rho\mathcal Z X^t,X\rangle+\frac12\\|X-X^t\\|_{M_{\mathrm C}}^2\right\\},\\\\ \Omega^{t+1}&=\Omega^t+\rho\mathcal Z X^{t+1}. \end{aligned} \tag{C3}$$ Here $D_Z:=\operatorname{diag}(Z_{11},\ldots,Z_{nn})=\alpha D_G$ and $$M_{\mathrm C}=2\rho(D_Z\otimes I_d),$$ $$S_{\mathrm C}=M_{\mathrm C}-\rho\mathcal Z =c\bigl((D_G+A_G)\otimes I_d\bigr)\succeq0.$$ With matching initialization, $M=M_{\mathrm C}$ recovers exact C-ADMM ($\gamma_M=0$ in our diagonal-majorization choice). - **Choice of $W$ and $M$.** C-ADMM corresponds to specific graph weights and $M$. CFI-spALM permits *nonuniform edge weights* and *general block-diagonal $M\succ0$* satisfying $M-\rho\mathcal Z\succeq0$. Consider the complete graph $K_n$, $n\ge3$, with $W=\mathbf{1}\mathbf{1}^\top/n$ and $f_i(x)=\frac12x^\top Qx-b_i^\top x$, $g_i=0$, where $0\prec Q\preceq\rho I_d$ and the vectors $b_i$ are arbitrary. Here $\alpha=1/n$, so C-ADMM uses $M_{\mathrm C}=m_{\mathrm C}I_{nd}$ with $m_{\mathrm C}:=2\rho(n-1)/n>\rho$. CFI-spALM also permits $M_{\mathrm{CFI}}=\rho I_{nd}$, for which $$M_{\mathrm{CFI}}-\rho\mathcal Z =\frac{\rho}{n}(\mathbf{1}\mathbf{1}^\top\otimes I_d)\succeq0.$$ For exact local solves and $\Omega^t\in\operatorname{range}(\mathcal Z)$, let $\chi_{\mathrm{CFI}}$ and $\chi_{\mathrm C}$ denote the spectral radii of the corresponding primal–dual error recursions. They satisfy $$\chi_{\mathrm{CFI}} =\frac{\rho}{\rho+\lambda_{\min}(Q)} < \frac{2\rho(n-1)/n}{2\rho(n-1)/n+\lambda_{\min}(Q)} =\chi_{\mathrm C}. \tag{C4}$$ Thus, with $W$ and $\rho$ fixed, $M_{\mathrm{CFI}}$ gives a strictly smaller asymptotic convergence factor in this example. - **Derivation of the spectral radii in (C4).** Let $e^t:=X^t-X^\star$ and $v^t:=\Omega^t-\Omega^\star$ for a solution $(X^\star,\Omega^\star)$ with $\Omega^\star\in\operatorname{range}(\mathcal Z)$. For $M=mI_{nd}$, the error recursion is $$\begin{aligned} (I_n\otimes Q+mI_{nd})e^{t+1} &=(mI_{nd}-\rho\mathcal Z)e^t-v^t,\\\\ v^{t+1}&=v^t+\rho\mathcal Z e^{t+1}. \end{aligned}$$ Since $\mathcal Z$ projects onto the disagreement subspace and $v^t$ has no consensus component, each eigenvalue $\lambda$ of $Q$ gives a consensus eigenvalue $m/(m+\lambda)$. The two disagreement eigenvalues are the roots of $$(m+\lambda)z^2-(2m+\lambda-2\rho)z+(m-\rho)=0.$$ For $m\ge\rho$ and $0 < \lambda\le\rho$, real roots are nonnegative and their maximum is at most $(m-\rho+\lambda)/(m+\lambda)\le m/(m+\lambda)$. A complex-conjugate pair has modulus $\sqrt{(m-\rho)/(m+\lambda)}\le m/(m+\lambda)$, since $$m^2-(m-\rho)(m+\lambda)=m(\rho-\lambda)+\rho\lambda>0.$$ Consequently, the spectral radius for this scalar family is $$\chi_m=\frac{m}{m+\lambda_{\min}(Q)},\qquad m\ge\rho.$$ Applying this identity with $m=\rho$ and $m=m_{\mathrm C}$ proves (C4). - **Inexact local solves.** Exact local solves are generally impractical. IC-ADMM (Chang et al., 2015) takes *one proximal-gradient update* per outer round, which may require more communication rounds than a suitably accurate local solve. CFI-spALM uses *adaptive stopping criteria*: agents take local steps until the first-order residual satisfies our absolute or relative criterion. Local work can vary across agents and rounds; all inner updates and stopping tests use only local information and cached neighbor variables.
1/N. Additional experiments (W1)