Pith. sign in

REVIEW 3 major objections 5 minor 46 references

Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Decentralized optimizer hits lower-bound speed on similar data

desk verdict Strong theory paper with a real contribution, but the 'lower-bound-optimal' claim compares average similarity upper bounds to a δmax-based lower bound, so that specific claim needs rework. read the letter →

arxiv 2506.05791 v1 pith:AHDIONID submitted 2025-06-06 cs.LG math.OC

Yuki Takezawa , Xiaowen Jiang , Anton Rodomanov , Sebastian U. Stich This is my paper
classification cs.LGmath.OC MSC 90C2590C30
keywords decentralizedoptimizationproximalpointmethodgradienttrackingfunctionalsimilaritycommunicationcomplexityacceleratedmethodsconvexgossipaveraging
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that decentralized optimization over a network can be made much cheaper when the local loss functions at different nodes are similar, and it supplies a method family that realizes this. It introduces Stabilized Proximal Decentralized Optimization (SPDO) and an accelerated variant, Accelerated-SPDO, and proves that these methods attain the best known communication and computational complexities among decentralized first-order methods under \u201caverage functional similarity\u201d measured by a constant $\delta$. In the strongly convex case the accelerated method reaches $\epsilon$-accuracy in $O(\sqrt{(\mu+\delta)/\mu} \log(1/\epsilon))$ communication rounds, giving communication cost $O(\sqrt{(\mu+\delta)/(\mu(1-\rho))} \log(L/\delta) \log(1/\epsilon))$ and per-node gradient cost $O(\sqrt{L/\mu} \log(1/\epsilon))$. When $\delta \ge \mu$ the communication rate matches the known lower bound up to logarithmic factors, and the computation rate matches the centralized first-order lower bound. A sympathetic reader would care because communication, not local computation, is usually the bottleneck in networked training, and the paper also relaxes the exact-subproblem requirement of earlier proximal decentralized methods and extends their analysis to the convex case.

What carries the argument

The load-bearing mechanism is the stabilized proximal update with three components. First, gradient tracking maintains an estimate $h_i^{(r)}$ of $\nabla(f-f_i)$ so that each node can build a local surrogate for the global function. Second, the stabilization step, written in closed form as $v_i^{(r+1/2)} = (\mu x_i^{(r+1)} + \lambda v_i^{(r)} - \nabla f_i(x_i^{(r+1)}) - h_i^{(r)})/(\mu+\lambda)$, forces the inexactness of the proximal subproblem to stay below a constant-accuracy threshold rather than one that tightens with $r$; this is the key relaxation that removes the computational overhead of existing PDO methods. Third, Accelerated-SPDO combines the Monteiro-Svaiter accelerated proximal-point schedule with accelerated gossip averaging, which changes the spectral-gap dependence from $1/(1-\rho)$ to $1/\sqrt{1-\rho}$ and produces the square-root round count. The proof machinery that replaces $\delta_{\max}$ by $\delta$ is the average similarity inequality $(3)$, $\frac{1}{n}\sum_i \lVert \nabla h_i(x) - \nabla h_i(y)\rVert^2 \le \delta^2 \lVert x-y\rVert^2$, used in place of the per-node Hessian closeness assumption.

What would settle it

Run Accelerated-SPDO on a synthetic strongly convex quadratic network where $\mu$, $L$, $\delta$, and $\rho$ are known exactly, set $\lambda = 96\delta$ and the prescribed number of accelerated gossip steps, and measure the rounds $R(\epsilon)$ needed for $f(\bar{x}^{(R)}) - f(x^\star) \le \epsilon$ over a range of $\delta/\mu$ values; the claimed rate is falsified if $R(\epsilon)$ grows faster than $O(\sqrt{(\mu+\delta)/\mu}\,\log(1/\epsilon))$. A cheaper check is to verify numerically whether condition $(10)$, $\sum_i \lVert \nabla F_{i,r}(x_i^{(r+1/2)})\rVert^2 \le (\lambda^2/352)\sum_i \lVert y_i^{(r)} - x_i^{(r+1/2)}\rVert^2$, is satisfied when each subproblem is solved with only $O(\sqrt{L/\delta})$ inner iterations; if it fails at any round, the stabilization mechanism is not doing the claimed work.

Watch

Extended reading notes

Core claim

The central discovery is a proximal decentralized optimization framework in which each node approximately minimizes $F_{i,r}(x) = f_i(x) + \langle h_i^{(r)}, x\rangle + (\lambda/2)\lVert x - v_i^{(r)}\rVert^2$, with $h_i^{(r)}$ a gradient-tracking estimate of $\nabla(f - f_i)$ and $v_i^{(r)}$ a stabilized anchor point. The stabilized update rule (Algorithm 3) adds a closed-form step that makes the required subproblem accuracy independent of the round index: condition $(9)$, $\sum_i \lVert \nabla F_{i,r}(x_i^{(r+1)})\rVert^2 \le (\lambda^2/10)\sum_i \lVert v_i^{(r)} - x_i^{(r+1)}\rVert^2$, replaces the round-dependent condition $(8)$ of Inexact-PDO. Theorem 5 then gives $R = O(\sqrt{(\mu+\delta)/\mu}\log(1 + \sqrt{\min\{\mu,\delta\}}\,\lVert \bar{x}^{(0)} - x^\star\rVert/\sqrt{\epsilon}))$ rounds for the strongly convex case, and Theorem 6 shows that solving each subproblem with $O(\sqrt{L/\delta})$ inner accelerated-gradient iterations suffices, so total gradient complexity is $O(\sqrt{L/\mu}\log(1/\epsilon))$. The paper further claims that this is optimal up to logarithmic factors when $\delta \ge \mu$, and that refining the analysis of the older PDO methods reduces the dependence on the worst-case dissimilarity $\delta_{\max}$ to the average dissimilarity $\delta$, while extending guarantees to both convex and strongly convex cases.

Load-bearing premise

The theorems' hyperparameters are set from the unknown similarity constant $\delta$: the algorithms take $\lambda = 4\delta$, $20\delta$, $96\delta$, or $208\delta$ and require $M \ge (1/(1-\rho))\log(cL/\delta)$ gossip steps, yet the paper gives no way to estimate or adapt $\delta$. If the user's guessed $\delta$ is wrong, the Lyapunov inequalities that make the proofs go through can stop being nonnegative, so the promised rates are not guaranteed in practice.

Editorial extensions

If this is right

  • For networks of nodes with nearly identical loss functions ($\delta \ll \mu$), Accelerated-SPDO cuts communication rounds by roughly $\sqrt{\delta/\mu}$ compared with methods whose cost depends on the worst-case dissimilarity $\delta_{\max}$, while keeping per-node gradient work at the centralized accelerated rate $\sqrt{L/\mu}\log(1/\epsilon)$.
  • Because the subproblem accuracy condition for SPDO is independent of the round index, a fixed number of inner accelerated-gradient steps suffices at every outer round; earlier PDO analyses required subproblem solutions that become more accurate as the outer iteration grows.
  • The analysis covers the convex case $\mu=0$, giving Accelerated-SPDO communication cost $O(\sqrt{\delta d_0^2/((1-\rho)\epsilon)} \log(\max\{L/\delta, \delta d_0^2/\epsilon\}))$; previous accelerated PDO analyses covered only strongly convex problems.
  • When $\delta \ge \mu$, the strongly convex communication complexity matches the known lower bound for this problem class up to logarithmic factors, and the total gradient complexity matches the centralized first-order lower bound up to constants, so under high similarity the method is optimal within this class.
  • When the underlying graph is complete, SPDO and Accelerated-SPDO reduce to the federated methods S-DANE and Accelerated-S-DANE, showing the stabilization device directly contains those special cases.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural extension the authors leave implicit is an adaptive scheme that estimates $\delta$ from local gradient differences in early rounds and sets $\lambda$ and $M$ accordingly; because the stated theorems are not self-tuning, such a scheme would be needed to deploy the method on datasets where $\delta$ is unknown.
  • The constant-accuracy relaxation should transfer to other proximal-Newton or variance-reduced decentralized methods whose inner subproblems are solved iteratively, potentially removing the 'solve more accurately over time' requirement from those methods as well.
  • The convex-case acceleration suggests that matching lower bounds for decentralized convex optimization might need to involve $\delta$ alongside $\rho$ and $L$; constructing such bounds would clarify how far the new rates are from optimal.
  • A direct quantitative test would regress the measured communication rounds against the estimated $\delta$ on each dataset; the paper's experiments vary a Dirichlet parameter $\alpha$ as a proxy for $\delta$ and report an approximation of $\delta$ only in the appendix.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies decentralized proximal optimization under functional similarity among local loss functions. It introduces SPDO and an accelerated variant (Accelerated-SPDO), analyzes their communication and computation complexity in both convex and strongly convex settings, and refines the existing analysis of PDO/SONATA by replacing a worst-case dissimilarity constant δmax with an average dissimilarity constant δ. The central claims are that Accelerated-SPDO achieves state-of-the-art communication and computational complexities among decentralized first-order methods and, when δ ≥ µ, is optimal up to logarithmic factors.

Significance. If the claims are established, this is a meaningful contribution: it shows that the average functional similarity constant δ, rather than the maximum δmax, controls the communication cost, and it relaxes the exact subproblem-solution requirement of earlier proximal decentralized methods. The appendix contains substantial Lyapunov-style proofs for all theorems, with explicit constants, and the numerical section includes sensitivity experiments as well as a comparison of communication and computation costs. These strengths make the upper-bound results credible and valuable. The main unresolved issue is the optimality claim with respect to the lower bound, which compares two different similarity parameters.

major comments (3)
  1. [Appendix B / Remark 1] The optimality comparison in Appendix B attributes to Tian et al. (2022) a lower bound Ω(√(δ/(µ(1−ρ))) log(...)), but Section 3 and Table 1 place Tian et al.'s results under Assumption 3, whose parameter is δmax, not the average δ of Definition 1. Since Remark 1 states that δ ≤ δmax and that δ can be √n smaller than δmax, a lower bound over the δmax-class does not automatically transfer to the average-similarity class with parameter δ: the hard instance for the δmax lower bound may have an average dissimilarity much smaller than δmax. The claim that Accelerated-SPDO is optimal up to logarithmic factors when δ ≥ µ is therefore not established unless a lower bound is proved for Definition 1 or it is shown that the Tian et al. construction already has average dissimilarity equal to δmax. Please either supply that argument or rephrase the optimality claim.
  2. [Theorems 1, 3, and 5] All convergence guarantees require hyperparameters set from the similarity constant δ: λ is set to a multiple of δ (λ = 4δ, 20δ, 96δ, 208δ) and M to Ω((1/(1−ρ)) log(L/δ)) or Ω((1/√(1−ρ)) log(...)), yet Definition 1 only asserts the existence of δ and the paper provides no estimation or adaptive tuning procedure. If δ is misestimated, the nonnegativity conditions in the Lyapunov proofs (e.g., Eq. (8), Eq. (9), Eq. (10)) and the stated M thresholds are not guaranteed to hold, so the complexity bounds do not apply to the implemented method. The statements should either be explicitly conditional on exact knowledge of δ, or an adaptive/estimation procedure should be provided.
  3. [Theorem 5 and Lemma 30] The strong-convexity statement of Theorem 5 reads "M ≥ 4√(1−ρ) log(18L²(192δ+µ)/(µδ²))" (and Lemma 30 contains the same expression). With this scaling, M goes to 0 as ρ goes to 1, which is inconsistent with the stated communication complexity O(√((µ+δ)/(µ(1−ρ))) · polylog) and with the proof of Lemma 30, which requires M = Ω((1/√(1−ρ)) log(...)). This should be corrected to M ≥ 4/√(1−ρ) log(18L²(192δ+µ)/(µδ²)). Please also check the formula for γ: the denominator shown as 1+√(1+ρ²) should presumably be 1+√(1−ρ²), matching the cited Proposition 1 of Yuan et al. (2022).
minor comments (5)
  1. [Appendix C.2, Lemma 1] The proof of Lemma 1 concludes with "≤ L ∥x−y∥²"; since the left-hand side is a squared norm, the correct inequality is L²∥x−y∥². As printed, the claim δ ≤ L is not established.
  2. [Lemma 13 and Lemma 21] There are typographical corruptions in these statements: Lemma 13 has "bounded by blow" instead of "below", and Lemma 21 has a malformed exponent "x_i^{(r+1/2}" and an incomplete summation. These should be corrected so the displayed conditions are unambiguous.
  3. [Table 1] The header repeats "communication communication" and the table is dense enough that the footnote markers are easy to confuse; please clean up the header and clarify which rows assume µ ≤ δ vs. µ ≤ δmax.
  4. [Section 7 / Appendix H.1] The experimental comparison replaces the theoretical subproblem condition of Inexact Accelerated SONATA with a modified, computable stopping condition. Since this is not the condition used in the cited analysis of Tian et al., the figure caption or text should state this limitation when interpreting the comparison.
  5. [Section 7, last paragraph] There is a typo: "when nods have similar functions" should be "when nodes have similar functions".

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: SPDO and Accelerated-SPDO convergence proofs are self-contained; δ is a problem parameter, not a fitted output.

full rationale

The paper's central derivation is a standard Lyapunov proof: Definition 1 fixes δ as a problem parameter, and Theorems 1, 3, and 5 state convergence under hyperparameters λ=Θ(δ) and M=Θ(log(L/δ)). The rates follow from the displayed subproblem-accuracy conditions (8)-(10), and the proof appendices bound explicit Lyapunov functions in terms of the problem constants without assuming the convergence rates being claimed. The dependence on δ is not a fitted input renamed as a prediction, because δ is not estimated from iterates or from a subset of the target error; it is a property of the function class. The self-citations to Jiang et al. (2024a,b) supply auxiliary algebraic lemmas from prior peer-reviewed work, for example Lemma 17 for the accelerated coefficient sequence; these are external support rather than assumptions equivalent to the paper's optimality conclusion, so under the stated evidence rules they do not raise the circularity score. A correctness caveat does exist and is distinct from circularity: the Appendix B optimality comparison quotes a lower bound stated under Assumption 3 with δmax, while the upper bound uses the average constant δ of Definition 1, and Remark 1 notes δ can be much smaller than δmax. This is a benchmarking and parameter-identification concern, not a derivation that reduces to its own input. Similarly, the practical requirement that λ and M be set using the unknown δ is a tuning and robustness issue, not a circular step. Overall, the central claims do not reduce to their inputs by construction.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The paper adds no new physical or mathematical entities. The state variables h_i and v_i are algorithmic artifacts with direct interpretation as gradient tracking and stabilized anchors.

free parameters (4)
  • λ (subproblem regularization) = 4δ / 20δ / 96δ / 208δ depending on variant
    The analysis requires λ to be a specific multiple of the similarity constant δ; since δ is generally unknown a priori, λ acts as a hand-tuned parameter in practice (grid-searched in experiments, Sec. H.2).
  • M (number of gossip averaging steps) = ≥ (1/(1-ρ)) log(cL/δ) for different constants c
    Needed to bring the consensus error below the threshold that makes the Lyapunov terms nonnegative; in practice M is tuned by grid search.
  • γ (acceleration parameter for fast gossip) = γ=(1-sqrt(1-ρ²))/(1+sqrt(1+ρ²))
    Set as a function of spectral gap ρ; if ρ is unknown or estimated incorrectly, convergence can degrade. This is standard for accelerated gossip.
  • η (inner gradient descent step size in experiments) = grid-searched {0.05, 0.01, 0.005, 0.001}
    Chosen by tuning to minimize final gradient norm; not part of the theory.
assumptions (6)
  • domain assumption Assumption 1: each f_i is µ-strongly convex (µ≥0)
    Used pervasively in Lemmas 9, 13, 21 to derive lower bounds on quadratic terms.
  • domain assumption Assumption 2: each f_i is L-smooth
    Used for Lipschitz gradient bounds in Lemmas 8, 22 and for subproblem condition-number estimates.
  • domain assumption Assumption 4: doubly stochastic gossip matrix W with spectral gap ρ
    Gives consensus error decay and sum preservation used in every length estimate of the paper.
  • domain assumption Definition 1: global average dissimilarity δ exists and is finite
    Central parameter; all rates are stated in terms of δ. Existence is shown in Lemma 1, but the lemma's proof has a typo.
  • ad hoc to paper Initial values: h_i(0)=∇f(x̄(0))-∇f_i(x̄(0)), x_i(0)=x̄(0) (or v_i(0)=v̄(0)), ensuring E(0)=0 and Ξ(0)=0
    These initialization assumptions are stated in Secs. 4.1/5.1/6.1 and are needed for the telescoping sums (e.g., Lemma 15, Lemma 29). They require extra communication at start.
  • standard math External lemmas from Jiang et al. 2024a/b (e.g., Lemma 12 in both papers, Lemma 14 in Jiang et al. 2024a)
    The paper cites these published lemmas for weighted-average recursions; they are not proved in this paper but are peer-reviewed background.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization." pith.science (2026). https://pith.science/paper/AHDIONID

@misc{pith2026250605791,
  author       = {Pith},
  title        = {Pith review of: Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AHDIONID}},
  note         = {Machine review of arXiv:2506.05791}
}
read the original abstract

Reducing communication complexity is critical for efficient decentralized optimization. The proximal decentralized optimization (PDO) framework is particularly appealing, as methods within this framework can exploit functional similarity among nodes to reduce communication rounds. Specifically, when local functions at different nodes are similar, these methods achieve faster convergence with fewer communication steps. However, existing PDO methods often require highly accurate solutions to subproblems associated with the proximal operator, resulting in significant computational overhead. In this work, we propose the Stabilized Proximal Decentralized Optimization (SPDO) method, which achieves state-of-the-art communication and computational complexities within the PDO framework. Additionally, we refine the analysis of existing PDO methods by relaxing subproblem accuracy requirements and leveraging average functional similarity. Experimental results demonstrate that SPDO significantly outperforms existing methods.

Figures

Figures reproduced from arXiv: 2506.05791 by the authors.

Figure 1
Figure 1. Convergence of the gradient norm with α = 0.1. In (a), we ran gradient descent until the condition for an approximate subproblem solution was satisfied for all methods except for Gradient Tracking. For Gradient Tracking, we ran gradient descent for 10 times. In (b), we ran gradient descent for 10 times to approximately solve the subproblem. See Sec. H for a more detailed setting. SONATA (Tian et al., 2022). Tian et … view at source ↗
Figure 2
Figure 2. Convergence of the gradient norm with different α. We set the coefficient of L2 regularization to 0.01. For SPDO, we approximately solve the subproblem as in [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. (a) indicates that setting M to 3 is optimal. Comparing the results with M = 1, increasing the number of gossip averaging decreased the gradient norm. This implies that performing gossip averaging multiple times is important. Furthermore, increasing the number of gossip averaging too much increases the gradient norm since the total number of communications is fixed. These observations are consistent with Theorem 3. … view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: shows the results when using a different seed value for the experiments shown in [PITH_FULL_IMAGE:figures/full_fig_p047_4.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

46 extracted references · 45 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Convex optimization: Algorithms and complexity

    Bubeck, S. Convex optimization: Algorithms and complexity. In Foundations and Trends in Machine Learning, 2015

    work page 2015

  3. [3]

    Dcatalyst: A unified accelerated framework for decentralized optimization

    Cao, T., Chen, X., and Scutari, G. Dcatalyst: A unified accelerated framework for decentralized optimization. In arXiv, 2025

    work page 2025

  4. [4]

    New proximal point algorithms for convex minimization

    G\" u ler, O. New proximal point algorithms for convex minimization. In SIAM Journal on Optimization, 1992

    work page 1992

  5. [5]

    H., Qi, H., and Brown, M

    Hsu, T.-M. H., Qi, H., and Brown, M. Measuring the effects of non-identical data distribution for federated visual classification. In arXiv, 2019

    work page 2019

  6. [6]

    Jiang, X., Rodomanov, A., and Stich, S. U. Federated optimization with doubly regularized drift correction. In International Conference on Machine Learning, 2024 a

    work page 2024

  7. [7]

    Jiang, X., Rodomanov, A., and Stich, S. U. Stabilized proximal-point methods for federated optimization. In Advances in Neural Information Processing Systems, 2024 b

    work page 2024

  8. [8]

    P., Jaggi, M., Kale, S., Mohri, M., Reddi, S

    Karimireddy, S. P., Jaggi, M., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., and Suresh, A. T. Mime: Mimicking centralized stochastic algorithms in federated learning. In arXiv, 2021

    work page 2021

Show all 46 references
  1. [9]

    and Jin, C

    Khaled, A. and Jin, C. Faster federated optimization under second-order similarity. In arXiv, 2022

    2022

  2. [10]

    and Jin, C

    Khaled, A. and Jin, C. Faster federated optimization under second-order similarity. In International Conference on Learning Representations, 2023

    2023

  3. [11]

    A unified theory of decentralized SGD with changing topology and local updates

    Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. A unified theory of decentralized SGD with changing topology and local updates. In International Conference on Machine Learning, 2020

    2020

  4. [12]

    Koloskova, A., Lin, T., and Stich, S. U. An improved analysis of gradient tracking for decentralized machine learning. In Advances in Neural Information Processing Systems, 2021

    2021

  5. [13]

    A linearly convergent algorithm for decentralized optimization: Sending less bits for free! In International Conference on Artificial Intelligence and Statistics, 2021

    Kovalev, D., Koloskova, A., Jaggi, M., Richtarik, P., and Stich, S. A linearly convergent algorithm for decentralized optimization: Sending less bits for free! In International Conference on Artificial Intelligence and Statistics, 2021

    2021

  6. [14]

    D., Gasnikov, A., and Scutari, G

    Kovalev, D., Beznosikov, A., Borodich, E. D., Gasnikov, A., and Scutari, G. Optimal gradient sliding and its application to optimal distributed optimization under similarity. In Advances in Neural Information Processing Systems, 2022

    2022

  7. [15]

    Gradient-based learning applied to document recognition

    Lecun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient-based learning applied to document recognition. In IEEE, 1998

    1998

  8. [16]

    Communication-efficient distributed optimization in networks with gradient tracking and variance reduction

    Li, B., Cen, S., Chen, Y., and Chi, Y. Communication-efficient distributed optimization in networks with gradient tracking and variance reduction. In Journal of Machine Learning Research, 2020

    2020

  9. [17]

    A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates

    Li, Z., Shi, W., and Yan, M. A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates. In IEEE Transactions on Signal Processing, 2019

    2019

  10. [18]

    Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent

    Lian, X., Zhang, C., Zhang, H., Hsieh, C.-J., Zhang, W., and Liu, J. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, 2017

    2017

  11. [19]

    Stochastic distributed optimization under average second-order similarity: Algorithms and analysis

    Lin, D., Han, Y., Ye, H., and Zhang, Z. Stochastic distributed optimization under average second-order similarity: Algorithms and analysis. In Advances in Neural Information Processing Systems, 2023

    2023

  12. [20]

    and Morse, A

    Liu, J. and Morse, A. Accelerated linear iterations for distributed averaging. In Annual Reviews in Control, 2011

    2011

  13. [21]

    Liu, Y., Lin, T., Koloskova, A., and Stich, S. U. Decentralized gradient tracking with local steps. In Optimization Methods and Software, 2024 a

    2024

  14. [22]

    Liu, Y., Lin, T., Koloskova, A., and Stich, S. U. Decentralized gradient tracking with local steps. In Optimization Methods and Software, 2024 b

    2024

  15. [23]

    Lorenzo, P. D. and Scutari, G. Next: In-network nonconvex optimization. In IEEE Transactions on Signal and Information Processing over Networks, 2016

    2016

  16. [24]

    Monteiro, R. D. C. and Svaiter, B. F. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. In SIAM Journal on Optimization, 2013

    2013

  17. [25]

    and Suzuki, T

    Murata, T. and Suzuki, T. Bias-variance reduced local SGD for less heterogeneous federated learning. In International Conference on Machine Learning, 2021

    2021

  18. [26]

    and Ozdaglar, A

    Nedic, A. and Ozdaglar, A. Distributed subgradient methods for multi-agent optimization. In IEEE Transactions on Automatic Control, 2009

    2009

  19. [27]

    Lectures on convex optimization

    Nesterov, Y. Lectures on convex optimization. In Springer, 2018

    2018

  20. [28]

    V., Guminov, S., and Dvurechensky, P

    Nesterov, Y., Gasnikov, A. V., Guminov, S., and Dvurechensky, P. E. Primal–dual accelerated gradient methods with small-dimensional relaxation oracle. In Optimization Methods and Software, 2018

    2018

  21. [29]

    K., Glasgow, M., Zindari, A., Wang, L., Stich, S

    Patel, K. K., Glasgow, M., Zindari, A., Wang, L., Stich, S. U., Cheng, Z., Joshi, N., and Srebro, N. The limits and potentials of local SGD for distributed heterogeneous learning with intermittent communication. In Conference on Learning Theory, 2024

    2024

  22. [30]

    and Nedic, A

    Pu, S. and Nedic, A. Distributed stochastic gradient tracking methods. In Mathematical Programming, 2021

    2021

  23. [31]

    Rockafellar, R. T. Monotone operators and the proximal point algorithm. In SIAM Journal on Control and Optimization, 1976

    1976

  24. [32]

    T., and Massouli \'e , L

    Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massouli \'e , L. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In International Conference on Machine Learning, 2017

    2017

  25. [33]

    and Sun, Y

    Scutari, G. and Sun, Y. Distributed nonconvex constrained optimization over time-varying digraphs. In Mathematical Programming, 2019

    2019

  26. [34]

    and Srebro, N

    Shamir, O. and Srebro, N. Distributed stochastic optimization and learning. In Annual Allerton Conference on Communication, Control, and Computing, 2014

    2014

  27. [35]

    Communication-efficient distributed optimization using an approximate newton-type method

    Shamir, O., Srebro, N., and Zhang, T. Communication-efficient distributed optimization using an approximate newton-type method. In International Conference on Machine Learning, 2014

    2014

  28. [36]

    Extra: An exact first-order algorithm for decentralized consensus optimization

    Shi, W., Ling, Q., Wu, G., and Yin, W. Extra: An exact first-order algorithm for decentralized consensus optimization. In SIAM Journal on Optimization, 2015

    2015

  29. [37]

    and Svaiter, B

    Solodov, M. and Svaiter, B. A hybrid projection-proximal point algorithm. In Journal of Convex Analysis, 1999

    1999

  30. [38]

    Solodov, M. V. and Svaiter, B. F. A unified framework for some inexact proximal point algorithms. In Numerical Functional Analysis and Optimization, 2001

    2001

  31. [39]

    Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation

    Sun, Y., Scutari, G., and Daneshmand, A. Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation. In SIAM Journal on Optimization, 2022

    2022

  32. [40]

    Momentum tracking: Momentum acceleration for decentralized deep learning on heterogeneous data

    Takezawa, Y., Bao, H., Niwa, K., Sato, R., and Yamada, M. Momentum tracking: Momentum acceleration for decentralized deep learning on heterogeneous data. In Transactions on Machine Learning Research, 2023

    2023

  33. [41]

    Acceleration in distributed optimization under similarity

    Tian, Y., Scutari, G., Cao, T., and Gasnikov, A. Acceleration in distributed optimization under similarity. In International Conference on Artificial Intelligence and Statistics, 2022

    2022

  34. [42]

    K., Yang, Z., Joshi, G., and Kar, S

    Wang, J., Sahu, A. K., Yang, Z., Joshi, G., and Kar, S. Matcha: Speeding up decentralized SGD via matching decomposition sampling. In Indian Control Conference, 2019

    2019

  35. [43]

    A scheme for robust distributed sensor fusion based on average consensus

    Xiao, L., Boyd, S., and Lall, S. A scheme for robust distributed sensor fusion based on average consensus. In International Symposium on Information Processing in Sensor Networks, 2005

    2005

  36. [44]

    Yuan, K., Ying, B., Zhao, X., and Sayed, A. H. Exact diffusion for distributed optimization and learning—part i: Algorithm development. In IEEE Transactions on Signal Processing, 2019

    2019

  37. [45]

    Revisiting optimal convergence rate for smooth and non-convex stochastic decentralized optimization

    Yuan, K., Huang, X., Chen, Y., Zhang, X., Zhang, Y., and Pan, P. Revisiting optimal convergence rate for smooth and non-convex stochastic decentralized optimization. In Advances in Neural Information Processing Systems, 2022

    2022

  38. [46]

    Zindari, A., Luo, R., and Stich, S. U. On the convergence of local SGD under third-order smoothness and hessian similarity. In Optimization for Machine Learning, 2023

    2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.