Pith. sign in

REVIEW 2 major objections 5 minor 26 references

A leaving node can leave a gradient-anchored quadratic surrogate so the network still converges near the original full-sum optimum.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-14 14:26 UTC pith:XQS3DDAM

load-bearing objection Clean, near-optimal fix for permanent bias under node departures in gradient tracking; graceful-exit is the only real practical caveat. the 2 major comments →

arxiv 2607.09939 v1 pith:XQS3DDAM submitted 2026-07-10 math.OC

Robust Decentralized Optimization under Node Failures via Adaptive Regularization

Ilya Kuruzov , Anastasiia Murzina This is my paper
classification math.OC MSC 90C2568W1593A14
keywords decentralized optimizationgradient trackingnode failureslegacy surrogatesadaptive regularizationfault-tolerant controlstrong convexity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

In decentralized optimization, when nodes permanently leave a network the usual algorithms simply drop their functions. The survivors then converge to the wrong point, and the error stays proportional to data heterogeneity no matter how long they keep iterating. This paper shows that a single farewell message is enough to avoid that permanent bias. Before leaving, a node freezes a first-order snapshot of its function as a quadratic "legacy" (value, gradient and an optimally chosen curvature), hands the legacy to one neighbor, and applies a one-line correction that keeps the gradient-tracking invariant exact. The resulting method, Legacy-GT, converges linearly after the last departure to a residual that is only a small multiple of the optimization error already achieved when the node left (or of the heterogeneity radius for early exits). The classic drop-and-forget baseline never escapes its heterogeneity-sized floor. The construction works for both strongly convex and merely convex objectives and composes cleanly when several nodes leave in sequence.

Core claim

Under monotone departures, a gradient-anchored quadratic legacy whose curvature equals the midpoint of the local strong-convexity and smoothness constants, together with an exact tracker hand-off to a single heir, reduces the asymptotic distance to the original full-sum minimizer to a quantity that decays geometrically with departure time and is at most (κ−1)/n times the smaller of network error at departure and the heterogeneity radius.

What carries the argument

The legacy qi(x) = hi(yi) + ⟨∇hi(yi), x−yi⟩ + (ηi/2)∥x−yi∥² with frozen midpoint curvature ηi = (μi+Li)/2, plus the one-line tracker correction that preserves the exact gradient-tracking sum after the node departs.

Load-bearing premise

A departing node must be able to send one final message containing its chosen anchor, gradient, curvature and tracker state to a single surviving neighbor; without that farewell the geometric decay of bias is lost.

What would settle it

On a ring or small-world network of strongly convex quadratics with controlled condition number κ, let k nodes leave after known optimization accuracy ε; measure whether the final distance to the true full-sum minimizer scales as O((κ−1)k ε / n) for Legacy-GT while remaining Θ(k ζ /(n μ)) for ordinary gradient tracking that simply drops the leavers.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper studies decentralized minimization of a sum of local functions over a network under monotone node departures (nodes may only leave; remaining graph stays connected and freezes between departures). Classical gradient-tracking (GT) methods that simply drop departed nodes converge to the survivors' minimizer and incur a permanent bias of order kζ/(nμ). The authors propose Legacy-GT: a departing node freezes a gradient-anchored quadratic legacy q_i with midpoint curvature η_i=(μ_i+L_i)/2, bequeaths it to a single heir, and applies a one-line tracker correction that exactly preserves the GT invariant. They prove optimality of the midpoint curvature, lossless composition of chained legacies, and (under strong convexity and k(κ-1)≤n) a limit-point error that decays geometrically after the last departure to a residual of order ((κ-1)/n) times the min of network error at departure and heterogeneity radius; a matching lower bound shows near-optimality among first-order memories. An adaptive three-way anchor rule (consensus iterate / local track / drop) and a point-only fallback are analyzed; convex (non-strongly-convex) objectives are treated separately. Numerical experiments on heterogeneous quadratics and two non-IID logistic tasks support the claims.

Significance. The work cleanly fills a gap between classical fixed-node decentralized optimization and open multi-agent systems: it recovers the original full-sum minimizer rather than tracking the time-varying present sum, with a quantified, departure-time-dependent residual. The midpoint-curvature lemma, exact invariant hand-off, lossless composition, and first-order lower bound are technically solid contributions that sit well inside the GT literature. Strengths include fully explicit constants (β=(κ-1)/(2n), geometric rates), a clean lower-bound construction independent of the upper bound, and experiments that match closed-form theory on quadratics. The graceful-exit assumption is a practical limitation but is scoped honestly (buddy checkpoints, adaptive drop fallback). If the results hold, the paper is a useful, citable advance for fault-tolerant decentralized optimization and related federated settings with permanent dropouts.

major comments (2)
  1. Assumption 4 (graceful exit) and the abrupt-crash paragraph in Assumption 3 are load-bearing for the geometric-decay claim of Theorem 1 / Corollary 1. The paper correctly scopes the main guarantee to the farewell-message case and provides a drop fallback, but the residual under realistic crash models (large τ, failed buddy, simultaneous multi-node crashes) is only sketched. A short quantitative statement of the residual under the checkpoint protocol (or an explicit corollary that the method never exceeds the classic bias) would make the central claim fully self-contained for practitioners.
  2. Theorem 1 requires k(κ-1)≤n (i.e., kβ≤1/2) to keep compounding constants ≤2. Table 2 deliberately violates this (kβ up to 29.7) and shows the predicted degradation, yet the main text still presents the geometric residual as the headline guarantee. Either strengthen the compounding analysis for the large-kβ regime (the paper notes graceful e^{kβ} degradation) or state the small-kβ condition more prominently next to the abstract claim so readers do not over-extrapolate.
minor comments (5)
  1. Table 1 caption and the surrounding text use both ε_m and ε̂(t_m); a single consistent notation for certified network error would improve readability.
  2. Figure 2 caption claims Legacy-GT reaches 2.0·10^{-7}; the y-axis is log-scale and the final plateau is visible, but adding the numerical final errors for all four methods in a small inset table would make the seven-order claim easier to verify.
  3. In the convex case (Theorem 3), the common-minimizer Assumption 5 is natural for iterates of one run but is not automatic for arbitrary anchors; a one-sentence remark that the local-track branch is disabled without local QG (already in Prop. 4) would clarify the adaptive rule's scope.
  4. A few typographical issues: 'experiements' (Sec. 4), 'outpeforms' (Fig. 2 discussion), and occasional missing spaces around math in the abstract/introduction.
  5. The privacy remark (Assumption 3) is useful but could briefly note that the point-only variant (Prop. 2) already addresses the stricter 'no gradient' constraint.

Circularity Check

0 steps flagged

No circularity: optimal curvature, bias transfer, and geometric residual are derived from stated SC/smoothness assumptions and standard GT rates, not fitted or self-defined.

full rationale

The paper's load-bearing claims are self-contained first-principles arguments under Assumptions 1–4. Lemma 1 derives η⋆=(a+b)/2 by minimizing the co-coercivity residual max{b−η,η−a} via Baillon–Haddad; the same midpoint also minimizes the induced bias functional, so the choice is not an ansatz. Lemma 2 and Prop. 5 transfer residual error from first-order matching of the legacy, and Lemma 4 converts that residual into per-departure drift β=(L−μ)/(2nμ) by nμ-strong convexity of the surrogate. Theorem 1 then compounds these drifts with the standard GT Lyapunov contraction (Prop. 3, citing external works [18,21]) under the explicit smallness condition kβ≤1/2. Theorem 2 is an independent adversarial construction (two quadratics sharing one first-order snapshot) that lower-bounds any first-order memory; it does not reuse the upper-bound constants. No parameter is fitted to experimental data and then re-presented as a prediction; the numerical section only validates the already-proved rates. There are no self-citations by the present authors, no uniqueness theorem imported from prior work of the same authors, and no renaming of a known empirical pattern. The graceful-exit assumption scopes the geometric-decay claim but does not make the residual circular. Score 0 is therefore the correct outcome.

Axiom & Free-Parameter Ledger

2 free parameters · 4 axioms · 1 invented entities

The central claim rests on standard first-order convexity assumptions, the monotone-departure network model, and the ability of a node to emit one farewell message. The only invented object is the legacy quadratic itself, whose form and weight are derived rather than postulated. No free parameters are fitted to data; all constants are either absolute or taken from the classical GT literature.

free parameters (2)
  • stepsize α
    Chosen as Θ((1−λ)² / L̂_loc) following the classical GT analysis; not fitted to the paper’s experiments.
  • certificate constants C, θ, C_Ψ
    Absolute constants inherited from the Lyapunov analysis of gradient tracking; calibrated once from a pilot run only for the point-only weight schedule in the quadratic plots.
axioms (4)
  • domain assumption Each local f_i is a_i-strongly convex / b_i-smooth (Assumption 1 SC or C).
    Standard curvature class used throughout decentralized optimization; invoked for all residual and rate statements.
  • domain assumption Nodes may only leave, remaining graph stays connected, topology freezes between departures (N1–N2, Assumption 3).
    Defines the monotone-departure regime; without connectivity the heir may be unreachable.
  • domain assumption A departing node can send one final message to one neighbor (Assumption 4).
    Load-bearing for the exact tracker correction; abrupt crashes fall back to a weaker checkpointed branch.
  • standard math Doubly-stochastic mixing matrices with uniform spectral gap 1−λ>0 exist on every epoch graph.
    Classical Metropolis-weight construction; used for the linear rate θ of Proposition 3.
invented entities (1)
  • Legacy quadratic q_i(x) = h_i(y_i) + ⟨∇h_i(y_i), x−y_i⟩ + (η_i/2)∥x−y_i∥² with η_i = (a_i+b_i)/2 + ledger independent evidence
    purpose: Compress a departing node’s function into a constant-size surrogate that preserves first-order information and composes losslessly.
    The functional form is classical (proximal / Tikhonov), but the gradient anchor, midpoint curvature and single-heir hand-off are specific to this paper; independent evidence is the matching lower bound of Theorem 2.

pith-pipeline@v1.1.0-grok45 · 25555 in / 2748 out tokens · 29626 ms · 2026-07-14T14:26:47.362214+00:00 · methodology

0 comments
read the original abstract

We study decentralized minimization of a sum of functions over a network where nodes may only leave, the remaining nodes stay connected, and the topology freezes between departures. Standard methods forget departed functions, causing a permanent bias proportional to the heterogeneity of the data. We propose Legacy Gradient Tracking (Legacy-GT): before leaving, a node compresses its function into a gradient-anchored quadratic legacy, bequeaths it to a neighbor, and provides a correction that exactly preserves the gradient-tracking invariant. We prove that the optimal legacy curvature is the average of the strong-convexity and smoothness constants, that legacies compose losslessly across chained departures, and that an adaptive anchor rule yields error bounds that decay geometrically after the last departure to a small residual--the minimum of the network's optimization error at departure and its heterogeneity radius. In contrast, the classic drop-and-forget baseline suffers a bias that never decays. Numerical experiments confirm the theory.

Figures

Figures reproduced from arXiv: 2607.09939 by Anastasiia Murzina, Ilya Kuruzov.

Figure 1
Figure 1. Figure 1: Legacy-GT (code for node j; round t) Require: stepsize α = Θ (1−λ) 2 Lˆ loc  ; hj = fj ; z 0 j = ∇hj (x 0 j ); local track u 0 j = x 0 j ; curva￾ture ledger η led j = 0. 1: // — standard gradient-tracking round on current graph G t — 2: x t+1 j = P l∈Nj∪{j} w t jl (x t l − αzt l ) {mix a local descent step; w t : Metropolis weights of G t } 3: z t+1 j = P l w t jlz t l + ∇hj (x t+1 j ) − ∇hj (x t j ) {tra… view at source ↗
Figure 2
Figure 2. Figure 2: that Legacy-GT significantly outpeforms all other algorithms in the sense of approached quality. At the same time, other algorithms gives convergence better too. 0 500 1000 1500 2000 2500 round t 10 7 10 6 10 5 10 4 10 3 10 2 10 1 10 0 x t x classic (drop-and-forget) GT-P (point-only legacy) GT-M (minimizer anchor) Legacy-GT (adaptive) [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Logistic regression (ℓ2-regularized) on two real datasets "breast cancer" and "digits", split non-IID across n = 10 nodes (sorted by label and leading principal component, then chunked). The three most heterogeneous nodes depart permanently. Left: breast cancer (569×30, estimated κˆi up to 322). Right: digits, odd-vs-even (1797× 64, κˆi up to 157). 4.2 Real datasets Further, let us make three observations.… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 1 linked inside Pith

  1. [1]

    In: 2021 IEEE symposium on security and privacy (SP)

    Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C.A., Jia, H., Travers, A., Zhang, B., Lie, D., Papernot, N.: Machine unlearning. In: 2021 IEEE symposium on security and privacy (SP). pp. 141–159. IEEE (2021)

    2021

  2. [2]

    In: 2015 IEEE symposium on security and privacy

    Cao, Y., Yang, J.: Towards making systems forget with machine unlearning. In: 2015 IEEE symposium on security and privacy. pp. 463–480. IEEE (2015)

    2015

  3. [3]

    Advances in neural information processing systems27(2014)

    Defazio, A., Bach, F., Lacoste-Julien, S.: Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems27(2014)

    2014

  4. [4]

    IEEE Trans- actions on Signal and Information Processing over Networks2(2), 120–136 (2016)

    Di Lorenzo, P., Scutari, G.: Next: In-network nonconvex optimization. IEEE Trans- actions on Signal and Information Processing over Networks2(2), 120–136 (2016)

    2016

  5. [5]

    IEEE Transactions on Automatic Control66(5), 2326–2331 (2020)

    Franceschelli, M., Frasca, P.: Stability of open multiagent systems and applications to dynamic consensus. IEEE Transactions on Automatic Control66(5), 2326–2331 (2020)

    2020

  6. [6]

    IEEE Transactions on Automatic Control68(2), 646–659 (2022)

    de Galland, C.M., Hendrickx, J.M.: Fundamental performance limitations for av- erage consensus in open multi-agent systems. IEEE Transactions on Automatic Control68(2), 646–659 (2022)

    2022

  7. [7]

    arXiv preprint arXiv:2002.05516 (2020)

    Hanzely, F., Richtárik, P.: Federated learning of a mixture of global and local models. arXiv preprint arXiv:2002.05516 (2020)

    Pith/arXiv arXiv 2002

  8. [8]

    In: 2017 IEEE 56th Annual Conference on Decision and Control (CDC)

    Hendrickx, J.M., Martin, S.: Open multi-agent systems: Gossiping with random arrivals and departures. In: 2017 IEEE 56th Annual Conference on Decision and Control (CDC). pp. 763–768. IEEE (2017) Title Suppressed Due to Excessive Length 15

    2017

  9. [9]

    In: 2020 59th IEEE Conference on Decision and Control (CDC)

    Hendrickx, J.M., Rabbat, M.G.: Stability of decentralized gradient descent in open multi-agent systems. In: 2020 59th IEEE Conference on Decision and Control (CDC). pp. 4885–4890. IEEE (2020)

    2020

  10. [10]

    In: 2021 60th IEEE Conference on Decision and Control (CDC)

    Hsieh, Y.G., Iutzeler, F., Malick, J., Mertikopoulos, P.: Optimization in open net- works via dual averaging. In: 2021 60th IEEE Conference on Decision and Control (CDC). pp. 514–520. IEEE (2021)

    2021

  11. [11]

    In: International conference on machine learning

    Karimireddy, S.P., Kale, S., Mohri, M., Reddi, S., Stich, S., Suresh, A.T.: Scaffold: Stochastic controlled averaging for federated learning. In: International conference on machine learning. pp. 5132–5143. PMLR (2020)

    2020

  12. [12]

    Proceedings of the national academy of sciences114(13), 3521–3526 (2017)

    Kirkpatrick, J., Pascanu, R., Rabinowitz, N., Veness, J., Desjardins, G., Rusu, A.A., Milan, K., Quan, J., Ramalho, T., Grabska-Barwinska, A., et al.: Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences114(13), 3521–3526 (2017)

    2017

  13. [13]

    In: International con- ference on machine learning

    Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., Stich, S.: A unified theory of decentralized sgd with changing topology and local updates. In: International con- ference on machine learning. pp. 5381–5393. PMLR (2020)

    2020

  14. [14]

    In: International conference on machine learning

    Li, T., Hu, S., Beirami, A., Smith, V.: Ditto: Fair and robust federated learn- ing through personalization. In: International conference on machine learning. pp. 6357–6368. PMLR (2021)

    2021

  15. [15]

    Proceedings of Machine learning and sys- tems2, 429–450 (2020)

    Li, T., Sahu, A.K., Zaheer, M., Sanjabi, M., Talwalkar, A., Smith, V.: Federated optimization in heterogeneous networks. Proceedings of Machine learning and sys- tems2, 429–450 (2020)

    2020

  16. [16]

    In: Artificial intelligence and statistics

    McMahan, B., Moore, E., Ramage, D., Hampson, S., y Arcas, B.A.: Communication-efficient learning of deep networks from decentralized data. In: Artificial intelligence and statistics. pp. 1273–1282. Pmlr (2017)

    2017

  17. [17]

    IEEE Transactions on Automatic Control61(12), 3936–3947 (2016)

    Nedić, A., Olshevsky, A.: Stochastic gradient-push for strongly convex functions on time-varying directed graphs. IEEE Transactions on Automatic Control61(12), 3936–3947 (2016)

    2016

  18. [18]

    SIAM Journal on Optimization27(4), 2597–2633 (2017)

    Nedic, A., Olshevsky, A., Shi, W.: Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization27(4), 2597–2633 (2017)

    2017

  19. [19]

    IEEE Transactions on automatic control54(1), 48–61 (2009)

    Nedic, A., Ozdaglar, A.: Distributed subgradient methods for multi-agent opti- mization. IEEE Transactions on automatic control54(1), 48–61 (2009)

    2009

  20. [20]

    Mathematical Programming187(1), 409–457 (2021)

    Pu, S., Nedić, A.: Distributed stochastic gradient tracking methods. Mathematical Programming187(1), 409–457 (2021)

    2021

  21. [21]

    IEEE Transactions on Control of Network Systems5(3), 1245–1260 (2017)

    Qu, G., Li, N.: Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems5(3), 1245–1260 (2017)

    2017

  22. [22]

    Mathematical Programming162(1), 83–112 (2017)

    Schmidt, M., Le Roux, N., Bach, F.: Minimizing finite sums with the stochastic average gradient. Mathematical Programming162(1), 83–112 (2017)

    2017

  23. [23]

    SIAM Journal on Optimization25(2), 944– 966 (2015)

    Shi, W., Ling, Q., Wu, G., Yin, W.: Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization25(2), 944– 966 (2015)

    2015

  24. [24]

    Advances in neural information processing systems33, 21394–21405 (2020)

    T Dinh, C., Tran, N., Nguyen, J.: Personalized federated learning with moreau envelopes. Advances in neural information processing systems33, 21394–21405 (2020)

    2020

  25. [25]

    In: Inter- national Conference on Machine Learning

    Yang, H., Zhang, X., Khanduri, P., Liu, J.: Anarchic federated learning. In: Inter- national Conference on Machine Learning. pp. 25331–25363. PMLR (2022) 16 I. Kuruzov et al. A Missing Proofs for Section 3 (General Analysis and Main Theoretical Results) A.1 Optimal Curvature We start from some auxilliary Lemmas to prove our result. Lemma 1 (Curvature cent...

    2022

  26. [26]

    If departuremchooses an anchored legacy, its contribution toB k is2βρ m withρ m bounded by the corresponding branch of (15), as in A.A.4

    Also note for later use,ρm ≤a m +B m−1 ≤a m +β P m′<m ρm′, which is inequality (8) of the main text onceam is bounded by the anchor rule. If departuremchooses an anchored legacy, its contribution toB k is2βρ m withρ m bounded by the corresponding branch of (15), as in A.A.4. If it chooses no legacy, then bFm = bFm−1 −h im, and ∇bFm(x⋆ m−1) = ∇him(x⋆ m−1) ...