acceptodds
Under review as a conference paper at ICLR 2027

An Inexact Semi-Proximal ALM with Adaptive Communication-Free Local Solves for Decentralized Composite Optimization

Abstract

Decentralized optimization enables agents to collaboratively solve learning and decision-making problems using only local computation and neighbor communication. In many practical networks, communication is substantially more expensive than local computation, motivating algorithms that perform multiple local updates between successive exchanges. Augmented Lagrangian methods provide an effective framework for composite optimization, but their decentralized subproblems are typically coupled through the network and may require repeated communication during the inner iterations. To alleviate this issue, we propose CFI-spALM, a Communication-Free Inexact Semi-Proximal Augmented Lagrangian Method that uses a structured semi-proximal term to decompose the coupled subproblem into independent nodewise problems. Each agent adaptively performs local proximal-gradient updates under an absolute or relative stopping rule, requiring only one model-vector exchange per outer iteration. For convex composite objectives, we establish global convergence, sublinear communication complexity, and linear convergence under metric subregularity. Experiments on logistic regression and rank-deficient LASSO demonstrate that CFI-spALM can achieve the prescribed optimization target with fewer model-vector exchanges than the comparison methods.

Primary area:
optimization
Keywords:
Decentralized optimization, Composite optimization, Inexact augmented Lagrangian methods, Communication-efficient algorithms.

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_cvF4OpenReview ↗
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 O(K−1/2)O(K^{-1/2}) best-iterate KKT residual bound, O(K−1)O(K^{-1}) 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
  1. 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.

  2. 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
  1. 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.

  2. 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
  1. 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?

  2. For smooth nonconvex fif_i and convex gig_i, could an appropriate choice of MiM_i preserve the communication-free local solves and locally verifiable stopping rules? What are the main obstacles to establishing convergence to stationary points?

5 comments
AuthorsOpenReview ↗

1/N. Additional experiments (W1)

We thank the reviewer for suggesting a broader experimental evaluation. We have added four groups of experiments on decentralized LASSO with λc=0.1\lambda_c=0.1 in the appendix subsection Effects of Network Conditions and Problem Scale. These experiments cover:

  • Network conditions: Erdős–Rényi graphs with p∈{0.1,0.2,0.5,0.8}p\in\{0.1,0.2,0.5,0.8\} and a sparse ring topology.
  • Numbers of agents: n∈{10,20,50,100}n\in\{10,20,50,100\}.
  • Problem dimensions: d∈{1000,3000,4000,5000}d\in\{1000,3000,4000,5000\}.
  • Local sample sizes: mi∈{10,30,50,60}m_i\in\{10,30,50,60\}.

The results provide further evidence of CFI-spALM's communication efficiency across the tested network conditions and problem scales.

Broader evaluation on real-world datasets and in more complex applications, particularly those involving nonconvex objectives, is an important direction for our future work.

AuthorsOpenReview ↗

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 G≡0G\equiv0. For a direct comparison, choose the consensus matrix, network augmentation matrix, and dual stepsize in FlexPD-G as A\mathcal A, ρZ\rho\mathcal Z, and ρ\rho, respectively. Writing Ωt=A⊤yt\Omega^t=\mathcal A^\top y^t, 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 fi+gif_i+g_i and includes the quadratic term 12∥x−xit∥Mi2\frac12\|x-x_i^t\|_{M_i}^2, which makes each local subproblem strongly convex even when fif_i 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 O(K−1/2)O(K^{-1/2}) best-iterate KKT residual bound, and O(K−1)O(K^{-1}) 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.

AuthorsOpenReview ↗

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 f^i(Cix)+gi(x)\widehat f_i(C_i x)+g_i(x) fits ours with fi(x):=f^i(Cix)f_i(x):=\widehat f_i(C_i x), where CiC_i is a local data matrix.

  • Connection between the exact updates.

For the unweighted graph, let AGA_G and DG=diag⁡(d1,…,dn)D_G=\operatorname{diag}(d_1,\ldots,d_n) be its adjacency and degree matrices, LG:=DG−AGL_G:=D_G-A_G, and LG:=LG⊗Id\mathcal L_G:=L_G\otimes I_d. 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.
Reviewer_63KuOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies Augmented Lagrangian-based decentralized optimization. The existing method, IDEAL, suffers from the issue that communication is required during the inner iterations. This paper proposes CFI-spALM, which can alleviate this issue. This paper also analyzes the convergence behavior of CFI-spALM, showing that CFI-spALM converges to the optimal solution linearly.

Critical strengths
  • The proposed method, CFI-spALM, uses a structured proximal term to decouple the augmented Lagrangian subproblems, allowing multiple local updates without additional communication. It alleviates the drawback of the existing method, IDEAL.
  • This paper analyzes the convergence rate of CFI-spALM, showing that it can converge to the optimal solution linearly.
Critical weaknesses
  • This paper is largely devoted to improving the existing IDEAL method. The main limitation addressed in the paper, namely the additional communication overhead incurred when IDEAL solves subproblems, is specific to IDEAL and does not affect many alternative approaches, e.g., [1,2,3]. Given that IDEAL is neither a SOTA nor a standard baseline in the decentralized literature, the significance of the paper's contribution appears rather limited.
  • Several important related works are missing. For instance, [1,2,3] have already proposed proximal-based methods, which have a similar double-loop structure. This paper criticizes that solving the subproblem in IDEAL involves additional communication, while SONATA and (Accelerated) SPDO do not involve such additional communication when solving the subproblem. I believe it is necessary to explain why CFI-spALM is superior to these methods. In particular, [1] also studied the inexact solution of the subproblem and has claimed that Accelerated SPDO is optimal up to logarithmic factors in terms of both communication complexity and computational complexity.
  • The numerical evaluation is not sufficient. It is important to compare CFI-spALM with existing communication-efficient methods, particularly SONATA and (Accelerated) SPDO. Furthermore, the experiments only evaluate communication costs, without reporting the number of local gradient evaluations. Since the proposed method may require many local updates to solve each subproblem, evaluating computational costs is also essential to understand the trade-off between communication and computation.
  • The experimental comparisons are inconsistent across problem settings. While NIDS, PG-EXTRA, and D-iPGM are included in the LASSO experiments, they are excluded from the logistic regression experiments without explanation.

Reference

[1] Takezawa et. al., Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization, ICML 2025
[2] Sun et. al., Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation. SIAM Journal on Optimization, 2022
[3] Tian et. al., Acceleration in distributed optimization under similarity. AISTATS 2022.

Questions for authors

See the weakness section.

Reviewer_cK3EOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies decentralized convex composite optimization over a fixed connected undirected network. CFI-spALM selects a block-diagonal matrix MM satisfying S=M−ρZ⪰0S=M-\rho\mathcal Z\succeq0, making its augmented-Lagrangian primal subproblem separable across agents. Agents use proximal-gradient or accelerated proximal-gradient iterations with locally computable absolute or relative residual tests, followed by one model-vector exchange per outer iteration. The analysis establishes full primal–dual sequence convergence for summable absolute errors, KKT-set convergence under the relative rule, an O(K−1/2)O(K^{-1/2}) best-iterate KKT residual bound, and O(K−1)O(K^{-1}) ergodic feasibility and objective error bounds. Additional error-bound and accuracy conditions yield linear convergence. Four synthetic configurations, covering regularized logistic regression and rank-deficient LASSO, report communication advantages over the selected baselines.

Critical strengths
  1. An implementable local accuracy certificate without inner residual aggregation. The local subproblem preserves the smooth-plus-proximable structure, and its residual can be constructed from the proximal optimality condition even with nonsmooth regularizers. Each node checks its own stopping condition using cached network information. Together with the stated finite-termination result for proximal gradient, this provides a concrete way to implement inexact local solves and may be useful when communication is expensive.

  2. Careful convergence analysis. The paper addresses both absolute and relative errors and distinguishes best-iterate residual bounds, ergodic primal bounds, and conditional linear rates. The absolute-error proof also treats possibly singular SS: feasibility and M=S+ρAc⊤Ac≻0M=S+\rho A_c^\top A_c\succ0 supply control missing from the semidefinite energy alone.

Critical weaknesses
  1. The incremental contribution over existing separable multiplier frameworks is insufficiently established. A particularly close reference is Wu and Lu, A Unifying Approximate Method of Multipliers for Distributed Composite Optimization, IEEE TAC, 2023. In its DAMM Algorithm 1 and Eq. (17), choose h_i^{\mathrm D}=f_i+g_i,\qquad \psi_i^k(x)=\frac12\|x-x_i^k\|_{M_i}^2,\qquad P=\widetilde P=Z.$$ Identify DAMM's transformed multiplier with $\Omega^k$. The resulting updates are $$x_i^{k+1} =\arg\min_x\left\{ f_i(x)+g_i(x)+\frac12\|x-x_i^k\|_{M_i}^2 +\langle\omega_i^k+\rho(\mathcal ZX^k)_i,x\rangle \right\},\qquad \Omega^{k+1}=\Omega^k+\rho\mathcal ZX^{k+1}.$$ These recover exact CFI-spALM under matching parameters and initialization. The quadratic surrogate satisfies DAMM's regularity and convexity requirements when $M\succ0$ and $S=M-\rho\mathcal Z\succeq0$.
  2. The numerical evaluation is limited in scope and does not yet adequately establish the algorithm's performance. The experiments cover only four synthetic configurations of logistic regression and rank-deficient LASSO, using networks of 10 or 20 agents. The baseline coverage and evaluation metrics are also limited: closely related local-solve methods are not compared, and performance is assessed primarily through model-vector exchanges, without complementary measures of local computation or runtime. These results support a communication advantage in the reported settings, but provide insufficient evidence of its robustness across problem scales and network conditions.
Questions for authors
  1. Novelty and theoretical inheritance. Do the authors agree with the DAMM specialization above? Please identify which implementation properties, error conditions, or convergence guarantees are new, and which are inherited from existing exact or inexact multiplier frameworks. A result-by-result comparison, including the singular SS absolute-error case and the nodewise relative rule, would materially affect the assessment.

  2. Experimental coverage, baselines, and performance metrics. The current evaluation covers a limited range of settings and scales. Could the authors extend the existing tasks with representative experiments addressing the following aspects?

    • Baselines: Beyond the current comparisons, prioritize a matched DAMM or decentralized proximal ADMM instance; FlexPD-G is an additional relevant comparator for the smooth strongly convex logistic-regression task.
    • Problem scale and network conditions: Beyond the current networks of 10 or 20 agents, include representative larger configurations, for example n=50n=50 or 100100, and vary the dimension dd or local sample size mim_i where appropriate. Consider Erdős–Rényi graphs with different connectivity levels and one sparse topology, such as a ring, reporting λ2(Z)\lambda_2(Z) or λmax⁡(Z)/λ2(Z)\lambda_{\max}(Z)/\lambda_2(Z).
  3. Scope of theoretical validation — clarification. Theorem 4 requires θ<(1+κP,r+1+κP,r2)−1<1/2,\theta<\bigl(1+\kappa_{P,r}+\sqrt{1+\kappa_{P,r}^2}\bigr)^{-1}<1/2, whereas the relative-rule experiments use θ=0.9\theta=0.9 or 0.990.99. These satisfy Theorem 2's threshold restriction but not Theorem 4's linear-rate condition.

4 comments
AuthorsOpenReview ↗

1/N. Compared with DAMM (W1 & Q1)

We thank the reviewer for pointing out this close connection. We agree that exact CFI-spALM is a specialization of DAMM under matching parameters and initialization. We have added the appendix subsection Connection to DAMM to clarify this relationship and our extensions.

  • Connection between the exact updates.

    In DAMM, choose

    \psi_i^t(x)=\frac12\\|x\\|_{M_i}^2,\qquad H=\widetilde H=\mathcal Z.$$ Its iteration then becomes $$\begin{aligned} X^{t+1}&=\arg\min_X\left\\{\Phi(X)+\langle\Omega^t+\rho\mathcal Z X^t,X\rangle+\frac12\\|X-X^t\\|_M^2\right\\},\\\\ \Omega^{t+1}&=\Omega^t+\rho\mathcal Z X^{t+1}, \end{aligned}$$ where $\Phi(X)=\sum_i[f_i(x_i)+g_i(x_i)]$ and $M=\operatorname{diag}(M_1,\ldots,M_n)$. These are exactly the CFI-spALM updates with exact local solves. Separability and communication-free local solves are shared properties.
  • Conditions on MM.

    For the specialization above, our absolute-rule analysis permits M≻0M\succ0 and S=M−ρZ⪰0S=M-\rho\mathcal Z\succeq0, allowing singular SS. The surrogate UtU^t in DAMM has Hessian ∇2Ut=M−ρH=S\nabla^2U^t=M-\rho H=S. For convex problems, DAMM's Theorem 1 requires ∇2Ut≻Λ^/2\nabla^2U^t\succ\widehat\Lambda/2, where Λ^:=diag⁡(L^1,…,L^n)⊗Id\widehat\Lambda:=\operatorname{diag}(\widehat L_1,\ldots,\widehat L_n)\otimes I_d and L^i\widehat L_i is a gradient Lipschitz bound for f^i\widehat f_i. This strict inequality is used in its unified proof to control errors from linearizing the smooth term. The condition still excludes singular SS when F^≡0\widehat F\equiv0. Our analysis instead combines M=S+ρA⊤A≻0M=S+\rho\mathcal A^\top\mathcal A\succ0 with asymptotic feasibility to control the primal sequence without requiring S≻0S\succ0.

    To illustrate the benefit of allowing singular SS, consider the quadratic example on the complete graph presented in our comparison with C-ADMM, where W=11⊤/nW=\mathbf1\mathbf1^\top/n and the local objectives have a common Hessian 0≺Q⪯ρId0\prec Q\preceq\rho I_d. CFI-spALM can use MCFI=ρIndM_{\mathrm{CFI}}=\rho I_{nd}, which gives the singular matrix SS. For MD=mIndM_{\mathrm D}=mI_{nd}, the matrix condition in DAMM's Theorem 1 requires m>ρm>\rho, which gives S≻0S\succ0. The spectral radii derived in the appendix satisfy

    =\frac{\rho}{\rho+\lambda_{\min}(Q)} < \frac{m}{m+\lambda_{\min}(Q)} =\chi_{\mathrm D}.$$ Thus, our analysis allows a choice of $M$ with a strictly smaller asymptotic convergence factor in this example.
  • Locally checkable inexact solves.

    Limited computational resources can make the exact local solves required by DAMM impractical, and such accuracy may be unnecessary for the outer iterations to converge. We therefore develop a practical and communication-efficient inexact method by introducing nodewise absolute and relative stopping criteria. These criteria use only local objective information and cached neighbor variables, allowing the number of local updates to vary adaptively across agents and rounds without communication during the solve. Using only locally available information for both inner updates and stopping decisions is a key distinction between our method and the inexact ALM framework D-ripALM.

  • Convergence guarantees for inexact updates.

    For the proposed inexact updates, we retain DAMM's O(K−1)O(K^{-1}) ergodic objective and feasibility rates and further establish an O(K−1/2)O(K^{-1/2}) best-iterate KKT residual bound. Summable absolute residuals also ensure convergence of the full primal–dual sequence when SS is singular, while the relative rule ensures convergence to the KKT set under S⪰B≻0S\succeq B\succ0. Under the respective KKT error-bound and accuracy conditions, we also prove local linear convergence for composite problems without requiring restricted strong convexity. By comparison, DAMM's Theorem 2 establishes linear convergence for smooth problems under local restricted strong convexity and additional matrix conditions.

AuthorsOpenReview ↗

2/N. Compared with FlexPD-G (Q2)

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 G≡0G\equiv0. For a direct comparison, choose the consensus matrix, network augmentation matrix, and dual stepsize in FlexPD-G as A\mathcal A, ρZ\rho\mathcal Z, and ρ\rho, respectively. Writing Ωt=A⊤yt\Omega^t=\mathcal A^\top y^t, 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 fi+gif_i+g_i and includes the quadratic term 12∥x−xit∥Mi2\frac12\|x-x_i^t\|_{M_i}^2, which makes each local subproblem strongly convex even when fif_i 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 O(K−1/2)O(K^{-1/2}) best-iterate KKT residual bound, and O(K−1)O(K^{-1}) 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.

AuthorsOpenReview ↗

3/N. Additional experiments (W2 & Q2)

We thank the reviewer for suggesting a broader evaluation of problem scale and network conditions. We have added four groups of experiments on decentralized LASSO with λc=0.1\lambda_c=0.1 to the appendix subsection titled ``Effects of Network Conditions and Problem Scale''. Specifically:

  • The three scale studies use Erdős–Rényi graphs with p=0.2p=0.2. The CFI-spALM variants retain a communication advantage across the tested network conditions and agent counts.
  • CFI-spALM-Rel also consistently reaches comparable KKT residual levels with lower communication costs across the tested dimensions and local sample sizes.

These results provide further evidence that the observed communication advantage persists across different network and problem configurations.

AuthorsOpenReview ↗

4/N. Scope of theoretical validation (Q3)

We thank the reviewer for highlighting this distinction. Our experiments focus on the practical convergence behavior and communication efficiency of CFI-spALM. As clarified in the appendix subsection Hyperparameter Settings, we use the theoretical parameter conditions as a reference and search over broader ranges, selecting the final hyperparameters based on experimental performance. For example, some selected PG-EXTRA stepsizes exceed the sufficient bounds in its original convergence analysis while still yielding good empirical performance.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.