{"id":"04b65465-3455-4b65-8c3b-e4e831f17415","arxiv_id":"2602.14830","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Network-GIANT converges linearly with rate equal to the spectral radius of an explicit 3×3 matrix, and, under a Hessian-approximation assumption, achieves an approximate local rate of 1−η.","lead":"This paper proves explicit convergence rates for Network-GIANT, a distributed approximate-Newton optimization algorithm, showing it converges linearly at a rate given by a simple 3x3 matrix and explaining why it can be much faster than gradient-tracking methods. The headline local rate of about 1−η, however, rests on an unverified Hessian-approximation assumption and a partly informal asymptotic argument.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised fast local rate rests entirely on Assumption 3 (uniform γ<μ), which is never verified numerically or analytically; without it the linear coefficient in (14) is ≥1 and the claimed 1−η rate is unsupported.","rationale":"The reader's weakest assumption identified the same core concern I find: the local fast-rate claim is gated by Assumption 3, which is unverified and admitted to have no useful analytic bound. My own reading of the proof confirms that (14) is a valid inequality but that its advertised consequence—an asymptotic rate of 1−η(1−γ/μ)—requires both γ<μ and a formal argument that the consensus/tracking-error terms decay faster than the optimality gap. The paper gives only a qualitative justification for the latter; although it is plausible for small η, it is not proven. The global linear convergence result (Theorems 1 and 2) appears sound: the characteristic-polynomial derivation in Appendix B checks out algebraically, and the proof of Theorem 1 is consistent with the claims. Thus the paper's core contribution—an explicitly computable, matrix-based global rate—stands, but the headline local-rate explanation remains conditional. This supports leaving the verdict at CONDITIONAL rather than upgrading to ACCEPT, and does not warrant REJECT because the main theorem is not invalidated.","tokens_in":17801,"tokens_out":18437,"duration_ms":175492,"concrete_test":"Re-run the Section V logistic-regression experiment (d=14 expander, η=0.07) and, at each iteration k, compute γ_k = ||H_tr(x^k)−H_app(x^k)||_2 and compare max_k γ_k with the empirical μ (≈0.002 for the full dataset; measure for the reduced set). If max_k γ_k ≥ μ, then Assumption 3 is violated in the very experiment used to claim the 1−η rate. Additionally, plot the empirical ratio r_k from (15) against both 1−η(1−γ_k/μ) and the spectral radius of G(η); if r_k stays near 1−η while γ_k≥μ, the fast rate cannot be attributed to Theorem 3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central new result is the local asymptotic rate 1−η(1−γ/μ) for Network-GIANT. That rate is the linear coefficient in inequality (14) of Theorem 3, but the inequality is derived under Assumption 3: a uniform bound ||H_tr(x)−H_app(x)||≤γ for all x. The authors themselves state in Remark 7 that no useful explicit analytical bound on γ is available, and the numerical section (Section V) never measures γ. Thus nothing in the paper establishes that the regime γ<μ actually holds for the tested problems. If γ≥μ, the coefficient 1−η(1−γ/μ) is ≥1, so inequality (14) provides no linear contraction, and the claimed '≈1−η' empirical rate is not explained by Theorem 3. Moreover, the transition from (14) to the clean asymptotic rate rests on the qualitative assertion that consensus and gradient-tracking errors decay faster than the optimality gap. While this can likely be formalized in the small-η regime, the paper does not supply the required comparison argument; in the worst case, those error terms propagate the slower global rate from Theorem 1. Therefore the 'rigorous proof' of the local rate is conditional in a way that the abstract and conclusion do not fully convey.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes Network-GIANT, a fully distributed approximate-Newton method that combines consensus updates with gradient tracking and local Hessian inverses. It provides two main theoretical contributions: (i) a global linear convergence rate for the optimality gap, given explicitly as the spectral radius of a 3x3 matrix G(η) depending on L, μ, σ, and η, together with an explicit sufficient step-size bound η̄ ensuring ρ(G(η))<1 (Theorems 1–2); and (ii) a mixed linear-quadratic inequality for the optimality gap under a uniform Hessian-approximation error bound γ (Theorem 3, Eq. (14)), from which the paper claims an asymptotic local rate of 1−η(1−γ/μ) ≈ 1−η. Numerical experiments on logistic regression over expander and Erdős–Rényi graphs illustrate the convergence behavior and compare with gradient-tracking baselines.","tokens_in":18067,"tokens_out":18125,"duration_ms":160095,"significance":"If the local-rate claim were fully established, the paper would provide a formal explanation for the empirically observed speedup of Network-GIANT over first-order distributed methods and would give the first explicit rate formulas for this algorithm. The global linear convergence result in Theorems 1–2 is explicit and parameter-free, and its proof appears structurally sound; this is a useful contribution. Theorem 3's mixed linear-quadratic inequality is also a valuable conditional bound. However, the advertised asymptotic local rate is not rigorously derived from (14): the paper does not prove that the consensus and gradient-tracking error terms are asymptotically negligible relative to the optimality gap, and the key assumption γ<μ is never verified numerically or analytically. Thus the central explanatory claim remains conditional in a way the abstract and conclusions do not fully convey.","major_comments":[{"comment":"The claimed local asymptotic rate 1−η(1−γ/μ) does not follow from inequality (14) alone. The right-hand side contains additive consensus/tracking terms and a bilinear term in ||x^k−1\\bar x^k||·||\\bar x^k−x*||. To conclude that the optimality gap contracts at the stated rate, one must prove these terms are o(||\\bar x^k−x*||). The paper's justification—that for small η the matrix in (12) is diagonally dominant and hence consensus/tracking errors decay faster—is not sufficient: for η>0, G(η) is a positive matrix, so the coupled upper-bound recursion gives the same Perron-root asymptotic rate to all components; diagonal dominance does not imply permanent rate separation. A rigorous small-gain or comparison argument for the actual trajectories is needed, or the 'rigorous proof' wording must be downgraded.","section":"Section IV-B, Eq. (14) and following paragraph"},{"comment":"The advertised local rate is conditional on γ<μ, but no analytical bound on γ is provided and the experiments never measure γ. Consequently the numerical observation r_k≈1−η cannot be positively linked to Theorem 3; it is only consistent with the theorem under an unverified hypothesis. Please either estimate γ for the logistic-regression problems or explicitly state that the numerical section does not verify the key assumption of the local-rate result.","section":"Assumption 3, Remark 7, and Section V (Eq. (15))"}],"minor_comments":[{"comment":"The sums in the algorithm definition should be over j=1,...,N and should involve x^k_j and s^k_j, not x^k_i and s^k_i. The compact matrix form (5) is correct, but (4) as written does not match the analyzed consensus update.","section":"Eq. (4)"},{"comment":"The identity matrix in µI ≤ ∇²f_i(x) ≤ LI should be n×n, not N×N.","section":"Assumption 1"},{"comment":"The displayed formula \\barη = (1−σ)µ/L / [2(2−σ)(1+(L/µ)^2)] is inconsistent with Theorem 2's \\barη = (1−σ)^2/(2(2−σ)(κ+κ^3)). The derivation in the appendix supports the main-text formula; the appendix appears to have dropped a square on (1−σ).","section":"Appendix II"},{"comment":"The rate r_k is defined with x^{k+1} and x^k, but from context it should be the ratio for the average iterate \\bar x^k. Please use \\bar x^k throughout to avoid ambiguity.","section":"Eq. (15)"},{"comment":"The acronym for the accelerated algorithm is ACC-NGD-SC in the text but Acc-DNGD-SC in the figure captions; please harmonize. Also, L and μ are not reported for the experiments, so the reader cannot check whether the chosen step sizes satisfy the sufficient conditions of Theorem 2.","section":"Section V"}],"recommendation":"major_revision","confidential_remarks":"The paper contains two solid results—Theorems 1 and 2—that are likely correct and publishable. The third result (Theorem 3) is a valid conditional inequality, but the paper overclaims when it calls the local asymptotic rate 'rigorous.' The missing rate-separation argument is the main technical gap; it is fixable either by adding a formal proof or by reframing the contribution as a conditional inequality. I would not reject, but the current abstract and conclusions should not be accepted as they stand."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Net take: the global convergence analysis is solid and worth having; the local-rate story is oversold. The paper gives the first explicit global linear convergence rate for Network-GIANT as the spectral radius of a 3x3 matrix, plus a conservative step-size bound. That is the core contribution, and the proofs in Appendices A-B are standard but appear correct. The step-size bound depends only on σ, κ, L, μ — no fitted constants.\n\nThe mixed linear-quadratic inequality (14) is also new and is proven cleanly in Appendix C under Assumptions 2 and 3. The trouble is what the authors claim on top of it. The clean asymptotic rate 1−η(1−γ/μ) requires both (i) a uniform bound γ<μ that the paper admits cannot be bounded analytically (Remark 7) and never measures in the experiments, and (ii) an informal claim that consensus and gradient-tracking errors decay faster than the optimality gap. Point (ii) may well be true for small η, but it is not proven; the paper just asserts it. That makes the abstract's \"rigorous proof of a local asymptotic convergence rate\" too strong. What is rigorously proven is the inequality; the clean rate is a plausible corollary under extra conditions.\n\nThe experiments illustrate the 1−η behavior on two graph families, but they are single runs without error bars, code is not included, and γ is not reported. That is acceptable for a theory paper, but it does not close the gap on Assumption 3.\n\nOn the citation pattern: the algorithm comes from the authors' own prior work, but the proofs here do not lean on [21]'s theorems; they use standard lemmas from [6] and [24]. No circularity problem. Self-citation is appropriate.\n\nWho is this for? People working on distributed second-order methods. The spectral-radius rate and step-size bound give practitioners something computable, and the inequality (14) is a useful stepping stone even if the final rate needs more work.\n\nMy recommendation: send it to peer review. A serious referee should ask the authors to either (a) verify or bound γ for the logistic regression setting, or (b) soften the abstract and turn the asymptotic rate into a clearly labeled conjecture/partial result. The global part is solid enough to publish; the local part needs a more honest framing.","headline":"The global linear rate for Network-GIANT is a real, usable result; the advertised fast local rate is conditional on an unverified Hessian-approximation bound and an informal asymptotic step.","tokens_in":18619,"tokens_out":1892,"would_cite":true,"duration_ms":20163,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C53"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves Network-GIANT, a distributed approximate-Newton algorithm, converges linearly with a computable rate, and locally at rate ≈1−η when the Hessian approximation error is small.","keywords":["Network-GIANT","distributed optimization","approximate Newton method","linear convergence","Hessian approximation","gradient tracking","consensus algorithm","strongly convex"],"falsifier":"Run Network-GIANT on a logistic regression problem engineered with strongly heterogeneous local datasets so that the harmonic-mean Hessian differs from the global Hessian by more than μ, and check whether the ratio r_k=||x_{k+1}−x*||/||x_k−x*|| still approaches 1−η or degrades; equivalently, directly compute γ for the real problem and test whether γ<μ holds on every iterate.","tokens_in":17612,"feed_emoji":"📈","tokens_out":8175,"duration_ms":68820,"temperature":0.7,"pith_summary":"Network-GIANT is a fully distributed optimization algorithm in which each node takes a damped Newton step using its own local Hessian and a gradient-tracking vector, with consensus averaging for both parameters and gradients. The paper's goal is to explain analytically why this approximate-Newton method converges faster than first-order gradient tracking. The authors prove a global linear convergence bound: the vector of consensus error, gradient-tracking error, and optimality gap is driven by a 3×3 matrix whose spectral radius gives an explicit rate. They also derive a mixed linear-quadratic inequality for the optimality gap, which yields an asymptotic local rate of 1−η(1−γ/μ), nearly 1−η when the Hessian approximation error γ is well below the strong-convexity constant μ. This local rate is network-independent and much faster than the 1−ημ typical of gradient-tracking methods.","feed_headline":"Network-GIANT's local rate is 1−η under small Hessian error","feed_subtitle":"A proof of explicit linear and network-independent asymptotic rates explains the approximate-Newton method's speed.","key_machinery":"The main object is the 3×3 nonnegative matrix G(η) that couples the consensus error, gradient-tracking error, and optimality gap; its spectral radius provides the global linear rate, and Perron-Frobenius theory guarantees the largest eigenvalue is real. The second central object is the harmonic-mean Hessian H_app, the matrix inverse of the average of local Hessian inverses, which Network-GIANT implicitly uses in place of the true global Hessian H_tr. The approximation error γ=||H_tr−H_app|| enters the local rate through the coefficient 1−η(1−γ/μ).","core_discovery":"The paper's central discovery is that the convergence of Network-GIANT decomposes into three coupled error recursions that can be bounded by a single linear matrix inequality. Theorems 1 and 2 show the optimality gap decays at a rate given by the spectral radius of a 3×3 matrix G(η) built from L, μ, and the consensus spectral norm σ, provided the step size is below an explicit threshold. The sharper Theorem 3 shows that when the local Hessians are Lipschitz and the harmonic-mean Hessian approximates the global arithmetic-mean Hessian with uniform error γ<μ, the optimality gap satisfies a mixed linear-quadratic bound with linear coefficient 1−η(1−γ/μ). For small step sizes, the consensus and","pith_inferences":["If the 1−η local rate holds whenever γ<μ, then the practical bottleneck for highly connected graphs is the consensus and gradient-tracking dynamics, not the Newton direction; acceleration should therefore target those error channels.","Since the paper offers no computable bound for γ or a way to measure it, a natural next step is to estimate γ empirically on the actual data and verify that γ<μ, turning the asymptotic rate into a testable prediction.","The result suggests a design principle: cheap harmonic-mean Hessian consensus can capture most of Newton's benefit even without exact Hessian averaging, as long as data heterogeneity keeps γ small.","The observation that sparse graphs (σ close to 1) do not exhibit the 1−η asymptote within the iteration budget suggests that the number of iterations needed to reach the local regime scales with 1/(1−σ), so the local rate is only relevant after consensus has nearly settled."],"forward_implications":["Network-GIANT converges linearly on any connected undirected graph for step sizes below the explicit bound in Theorem 2, with a rate computable from L, μ, and σ.","When the Hessian approximation error γ is smaller than μ and the step size is small, the optimality gap eventually decays at rate about 1−η, independent of the graph spectrum.","The mixed linear-quadratic bound predicts a fast transient phase (quadratic in the gap) followed by a linear tail, matching the observed convergence plots.","The same proof technique applies to any distributed approximate-Newton algorithm whose Hessian approximation error is uniformly small, not just to Network-GIANT.","The explicit global rate allows quantifying the trade-off between network connectivity (σ) and step size, and shows that a larger η can yield a faster rate if it stays below the bound."],"fun_headline_variants":["Network-GIANT's rate proven: mixed linear-quadratic bound","Distributed Newton converges at 1−η with small Hessian error","Analytic rate for Network-GIANT: spectral radius bound","Faster distributed optimization: explicit convergence proof","Network-GIANT's speed justified by explicit linear rate"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The fast local rate rests on the assumption that the difference between the true global Hessian and its harmonic-mean approximation is uniformly smaller than the strong-convexity constant μ; the paper gives no way to compute or verify this difference, and it is never measured in the experiments.","fun_headline_variants_meta":{"raw":{"variants":["Network-GIANT's rate proven: mixed linear-quadratic bound","Distributed Newton converges at 1−η with small Hessian error","Analytic rate for Network-GIANT: spectral radius bound","Faster distributed optimization: explicit convergence proof","Network-GIANT's speed justified by explicit linear rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000222,"raw_usage":{"total_tokens":1339,"prompt_tokens":838,"completion_tokens":501,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":426}},"tokens_in":582,"tokens_out":501,"duration_ms":4833,"temperature":1.0,"reasoning_tokens":426,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T23:02:11.185252+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Network-GIANT on a logistic regression problem engineered with strongly heterogeneous local datasets so that the harmonic-mean Hessian differs from the global Hessian by more than μ, and check whether the ratio r_k=||x_{k+1}−x*||/||x_k−x*|| still approaches 1−η or degrades; equivalently, directly compute γ for the real problem and test whether γ<μ holds on every iterate.","supporting_citations":[],"review_version":1}