{"id":"66891680-b161-451e-bdbb-5657afeb1939","arxiv_id":"1908.08098","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"BRIDGE combines coordinate-wise trimmed mean with decentralized gradient descent to achieve Byzantine-resilient consensus and sublinear convergence to the statistical risk minimizer under strong convexity.","lead":"This paper introduces BRIDGE, a decentralized gradient descent algorithm that uses coordinate-wise trimmed mean to filter out Byzantine (arbitrarily faulty) nodes, and proves consensus and convergence to the statistical risk minimizer for strongly convex problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Optimality proof in Appendix B fails to establish eventual small gradient; it only contradicts the 'always large' case, so Theorem 1's convergence to w* is unproved as written.","rationale":"The reader's weakest_assumption is the missing minimum-degree condition, but under the paper's Definition 2 this condition is actually forced by Assumption 4. For any nonfaulty node v, the reduced graph can be generated by choosing b neighbors of v as Byzantine and then removing b additional incoming edges from v; if |N_v|≤2b, v can be left with zero incoming edges. Since the source component must have directed paths to every other node in the reduced graph, no source component of size ≥ b+1 can exist in that reduced graph, contradicting Assumption 4. Thus every nonfaulty node satisfies |N_j|≥2b+1, and Algorithm 1 is well-defined on graphs satisfying Assumption 4. The genuine weakness is the optimality proof in Appendix B. The proof's contradiction setup only excludes the case where the gradient norm is always above the threshold. It does not exclude the case where the gradient norm is large infinitely often but sparsely, because the total descent from a sparse set of times can be finite. Consequently the proof does not establish that ||∇\\bar f(v(t))|| eventually becomes small, which is necessary for v(t)→w*. This is a substantive gap in the proof of the central theorem, but it does not by itself disprove the theorem; it makes the accepted version conditional on a repaired argument. Minor issues such as the index definition of v(t) and tie-breaking in the trimmed mean are secondary and fixable.","tokens_in":17903,"tokens_out":39722,"duration_ms":425873,"concrete_test":"Instantiate the Appendix B argument on a hypothetical trajectory in which ||∇\\bar f(v(t))|| exceeds ε∇+ε0 only at times t_k=2^k and is moderate otherwise. Verify that summing (60) over these times yields a finite total decrease, so the claimed contradiction fails. The proof is only repaired if a separate argument is supplied showing that large-gradient events cannot recur sparsely while the function remains decreasing and bounded below.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing gap is in Appendix B, which tries to prove that ||∇\\bar f(v(t))|| is eventually ≤ ε∇. The text argues by contradiction assuming ||∇\\bar f(v(t))|| − ε∇ > ε0 for all t. The negation of 'eventually below threshold' is not 'always above threshold'; it is the existence of an unbounded sequence t_k, possibly sparse, with gradient above threshold. The displayed inequality (60) is only valid at times where the gradient is above threshold, and for a sparse set the sum ∑ρ(t_k) may converge even though ∑ρ(t)=∞ (e.g., ρ(t)∼1/t with t_k=2^k). Lower boundedness of \\bar f then produces no contradiction, so the argument does not rule out infinitely many large-gradient epochs separated by long moderate periods. Since Theorem 1's optimality conclusion rests entirely on this step, the central claim is not proven as written. The reader's flagged degree condition, by contrast, appears to be implied by Assumption 4 when 'source component' is read as in Definition 2: otherwise a node with ≤2b neighbors can be left with zero incoming edges after removing b Byzantine neighbors and b additional edges, preventing any source component from reaching it.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes BRIDGE, a Byzantine-resilient decentralized gradient descent algorithm that combines a coordinate-wise trimmed mean with classical distributed gradient descent. The main theoretical claim, Theorem 1, states that under Assumptions 1-4 (bounded, strongly convex, smooth risks and a graph redundancy condition), all nonfaulty nodes achieve consensus and, as both the number of local samples and iterations grow, the common iterate converges in probability to the minimizer of the global statistical risk. The paper also reports experiments on MNIST with a linear classifier and a convolutional network, comparing BRIDGE with DGD, ByRDiE, and local training.","tokens_in":18159,"tokens_out":14923,"duration_ms":153984,"significance":"If Theorem 1 were fully established, BRIDGE would be a meaningful contribution to Byzantine-resilient decentralized learning: it is one of the few vector-valued decentralized algorithms with an explicit statistical convergence claim, and the coordinate-wise screening approach is computationally simple and communication-efficient. The experimental comparison with ByRDiE supports the communication-efficiency advantage. The paper also makes its assumptions and algorithm description clear enough to reimplement. However, the current proof has load-bearing gaps, so the theoretical contribution is not yet demonstrated with the rigor the central claim requires.","major_comments":[{"comment":"The identity E[g2(t)] = E[∇f(v(t))] is asserted without justification. In BRIDGE, both α(t) and v(t) are functions of the entire past trajectory and therefore of the same local datasets Zj that define the empirical gradients ∇fj(v(t)). For a generic nonlinear f, E[Σ_i α_i ∇f_i(v)] is not equal to E[∇f(v)]; a simple example with f(w,z) = wz and v taken as a data-dependent nonlinearity of a single node's sample shows the bias. Since the Hoeffding bound in Eq. (32) is applied around this asserted mean, Lemma 1 does not establish the stated high-probability bound on |g2(v(t)) − E[∇f(v(t))]|. This bound is then used in Eq. (29) to prove optimality, so the gap is load-bearing.","section":"Appendix A, Eqs. (30)-(32)"},{"comment":"The contradiction argument assumes that there exists ε0 > 0 such that ‖∇f̄(v(t))‖ − ε∇ > ε0 for all t. The negation of the desired conclusion '‖∇f̄(v(t))‖ ≤ ε∇ eventually' is only that the inequality ‖∇f̄(v(t))‖ > ε∇ holds for infinitely many t, possibly on a sparse sequence {t_k}. The decrease bound in Eq. (60) is valid only at those times, and Σ_k ρ(t_k) may be finite even though Σ_t ρ(t) = ∞ (for example, ρ(t) = 1/t with t_k = 2^k). A lower-bounded function can therefore decrease by a finite total amount on such a sparse set, so no contradiction follows. As written, the proof does not rule out infinitely many large-gradient epochs separated by long moderate periods, and the optimality half of Theorem 1 is unproved.","section":"Appendix B, paragraph beginning 'We prove this by contradiction'"},{"comment":"The consensus proof relies entirely on the matrix convergence bound from [42,43], but it does not verify that the random row-stochastic matrices Y(t) defined in Eq. (9) satisfy the hypotheses of that theorem for every Byzantine behavior. In particular, the support of Y(t) depends on the trimming sets N_j^k(t), which vary with t and with the Byzantine messages, so the required product structure over any block of ν matrices is not automatic. The authors should either state the precise theorem from [42,43] and prove that each Y(t) meets its conditions, or provide a self-contained argument. Without this verification, the consensus half of Theorem 1 is also not established as written.","section":"Section 4.1, Eq. (11)"}],"minor_comments":[{"comment":"Before presenting Algorithm 1, state explicitly that Assumption 4 together with Definition 2 implies every nonfaulty node has at least 2b+1 neighbors, so the denominator |N_j| − 2b + 1 in Eq. (7) is positive and the trimming sets are well-defined. This is a helpful clarification even though the condition is implicit in Assumption 4.","section":"Section 3, Algorithm 1"},{"comment":"The sentence 'as t → 0' after Eq. (17) should read 'as t → ∞'.","section":"Section 4.1, Eq. (17)"},{"comment":"Remark 3 states that the right-hand side of Eq. (29) 'converges to 1 as t→0 and N→0'; the intended statement is clearly about t → ∞ and N → ∞, and the wording should be corrected.","section":"Section 4.2, Remark 3"},{"comment":"The notation is inconsistent: the ambient dimension is denoted d in most of the paper, but the optimality analysis uses P (e.g., 'for 1 ≤ k ≤ P'). Please use one symbol throughout.","section":"Section 4.2"},{"comment":"Lemma 1 uses sup_t |g2(v(t)) − E[∇f(v(t))]| with an absolute value, while the quantity is vector-valued; this should be a norm ‖ · ‖, consistent with the proof in Appendix A.","section":"Appendix A, Lemma 1 statement"}],"recommendation":"major_revision","confidential_remarks":"The flaws in Appendix A and Appendix B are serious enough that the central theorem is not proven as written, but they do not appear to be irreparable. The sparse-subsequence issue can likely be fixed with a standard stochastic-approximation argument, and the statistical bias in Lemma 1 may be controlled by a data-splitting or two-sample argument or by proving convergence to the empirical-risk minimizer first. I therefore recommend major revision rather than rejection, provided the authors supply a rigorous replacement for these proof steps."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, the algorithm is a reasonable and well-motivated combination of coordinate-wise trimmed mean with decentralized gradient descent, and the experiments genuinely support that BRIDGE is Byzantine-resilient and more communication-efficient than the single-coordinate ByRDiE. Second, the proof of convergence to w* is not sound as written: Appendix B contains a load-bearing logical error, so the central optimality claim is unproved.\n\nWhat is actually new: BRIDGE updates the full vector per round, unlike ByRDiE, and the paper gives a consensus argument that traces the coordinated screening back to a time-varying stochastic matrix over nonfaulty nodes. The MNIST experiments (100 nodes, linear and CNN) show that BRIDGE stays close to faultless DGD, achieves consensus, and clearly outperforms local training. That is useful evidence.\n\nThe soft spots, in proportion. The most serious is in Appendix B. To prove that the gradient norms eventually become small, the authors assume, for contradiction, that ||grad fbar(v(t))|| - eps_grad > eps0 for all t. But the negation of 'eventually below threshold' is 'infinitely often above threshold', possibly on a sparse sequence. Inequality (60) only gives a per-step decrease at times when the gradient is large, and for a sparse sequence t_k (e.g., powers of two) the sum of rho(t_k) can be finite even though sum rho(t) diverges. Lower boundedness of fbar then yields no contradiction. So the proof does not rule out infinitely many large-gradient epochs separated by long moderate periods. This is not a missing detail; it is a genuine logical gap in the argument for convergence to w*.\n\nSecond, the consensus proof invokes the matrix convergence bound (11) from [42,43] without verifying that the time-varying matrices Y(t) satisfy the conditions of that bound. That may be repairable by citing the right theorem, but as written it is an unverified external invocation. Third, the paper never states the minimum-degree condition |N_j| >= 2b+1 needed for the denominator in (7) to be positive. The reader flagged this; I think Assumption 4 likely implies it when 'source component' is read as in Definition 2, but the paper should say so explicitly.\n\nNothing here convinces me the approach is wrong. The consensus part probably goes through with a proper citation, and the optimality claim may be fixable, for example by a more careful argument using the monotonicity of fbar(v(t)) to show the gradient norms must decay. But as submitted, Theorem 1 is not proven.\n\nWho is this for? Researchers working on Byzantine-resilient decentralized optimization who need a concrete, vector-valued algorithm and are willing to treat the guarantees as conditional. It deserves a serious referee: the method is nontrivial, the experiments are honest, and the flaws are identifiable rather than fatal. Send it to peer review, but tell the referees to focus on Appendix B.","headline":"A sensible algorithm with encouraging experiments, but the optimality proof in Appendix B argues against the wrong negation and leaves Theorem 1 unproved as written.","tokens_in":18625,"tokens_out":3428,"would_cite":false,"duration_ms":35887,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","68M15","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"BRIDGE claims that decentralized gradient descent with coordinate-wise trimmed mean reaches consensus and converges to the global risk minimizer even when up to b nodes behave Byzantine.","keywords":["Byzantine fault tolerance","decentralized learning","gradient descent","coordinate-wise trimmed mean","consensus","statistical risk","strong convexity","distributed optimization"],"falsifier":"Construct a directed graph satisfying Assumption 4 with $b=1$ in which some nonfaulty node has exactly two neighbors; at the first iteration the trimming step removes one smallest and one largest neighbor value in each coordinate, leaving an empty neighbor set, so the node's update reduces to its own value minus a gradient step, and nonfaulty nodes need not reach consensus—contradicting Theorem 1's claim that consensus holds for every graph covered by Assumptions 1–4.","tokens_in":17688,"feed_emoji":"🛡️","tokens_out":9035,"duration_ms":177838,"temperature":0.7,"pith_summary":"This paper introduces BRIDGE, a decentralized learning method that keeps a network of nodes training a shared model even when some nodes are Byzantine, meaning they can send arbitrary, adversarial values to their neighbors. The method changes standard distributed gradient descent in one way: before averaging neighbor updates, each node discards the b smallest and b largest values in every coordinate, then takes a gradient step on the remaining average. The paper proves that for strongly convex losses with Lipschitz gradients and on networks with enough redundancy, all nonfaulty nodes' models agree as time grows, and as the total sample size grows their common model converges sublinearly to the minimizer of the global statistical risk. This matters because a single Byzantine node can otherwise crash decentralized consensus-based learning, and existing robust methods either scale poorly to high-dimensional models or lack statistical convergence guarantees.","feed_headline":"Decentralized learning survives Byzantine nodes by trimming extremes","feed_subtitle":"Per-coordinate trimmed mean plus gradient steps yields consensus and sublinear convergence to the true risk minimizer.","key_machinery":"The load-bearing object is the coordinate-wise trimmed mean, called the screening step: for each coordinate $k$, node $j$ sorts the incoming neighbor values, removes the $b$ smallest and $b$ largest, and averages the survivors together with its own value, then subtracts a local gradient step. Because at most $b$ Byzantine nodes exist, this screening confines the influence of faulty messages in each coordinate. The consensus proof rewrites the update using only nonfaulty nodes as a time-varying stochastic matrix $Y(t)$ and appeals to convergence of products of such matrices to a rank-one limit, an argument that relies on Assumption 4 to guarantee enough redundancy in the network.","core_discovery":"The paper's central claim is Theorem 1: if the loss is bounded, $\\lambda$-strongly convex, and $L'$-Lipschitz gradient (Assumptions 1–3), and the graph is sufficiently redundant in the sense that every reduced graph has a source component of at least $b+1$ nodes (Assumption 4), then for at most $b$ Byzantine nodes BRIDGE drives all nonfaulty models $w_j(t)$ to consensus as $t\\to\\infty$, and as $N\\to\\infty$ the consensus value converges in probability to $w^*$, the minimizer of the global statistical risk. This is a convergence guarantee for a vector-valued, all-coordinates-at-once Byzantine-resilient decentralized algorithm; the main alternative updates one coordinate per round. The proof bounds $\\|w_j(t)-w^*\\|$ by four terms accounting for consensus error, gradient-estimation error, and the contraction of gradient descent, with the statistical error of order $O(\\sqrt{\\|\\bar\\alpha\\|_2 \\log(1/\\delta)/N})$.","pith_inferences":["The formal theorem silently assumes every nonfaulty node has at least $2b+1$ neighbors; without adding that condition, the algorithm is undefined or reduces to updating only from one's own value on some graphs satisfying Assumption 4, so a corrected statement would either assume minimum degree or adapt the number of trimmed values to each node's degree.","The trimming is per-coordinate, so a Byzantine node can still influence coordinates in which its value is not among the $b$ extremes; the guarantee is worst-case in number of nodes, not necessarily against adversaries that corrupt only selected coordinates.","A natural testable extension is to let each node trim $\\min(b, \\lfloor(|\\mathcal{N}_j|-1)/2\\rfloor)$ values adaptively; this would preserve the algorithm's spirit on sparse graphs and could be checked against the stated convergence rate.","Because the analysis relies on strong convexity, the nonconvex CNN experiment is suggestive rather than proof; a full extension would require bounding the effect of the screening bias under nonconvex landscape assumptions such as the Polyak–Łojasiewicz condition."],"forward_implications":["On any graph satisfying Assumption 4 with at most $b$ Byzantine nodes, a network can train a shared model without a central server and still converge to the statistically optimal model; exact consensus is reached asymptotically despite adversarial peers.","BRIDGE updates all $d$ coordinates in each message, so it needs fewer communication rounds than coordinate-descent Byzantine-resilient methods to reach a target accuracy; the MNIST linear-classifier experiments show accuracy close to fault-free distributed gradient descent.","With step size $\\rho(t)=O(1/t)$, the consensus error decays as $O(\\sqrt{d}/t)$, giving sublinear convergence in time; the statistical error after cooperation is no worse than local learning's $O(1/\\sqrt{N})$ and improves by a factor related to the consensus weights.","The same screening can be layered onto local optimizers such as Adam for nonconvex problems; experiments on a convolutional neural network show resilience against one Byzantine node, though the formal theorem covers only strongly convex objectives."],"supporting_citations":[{"why":"Supplies the distributed gradient descent update that BRIDGE robustifies.","marker":"[14]"},{"why":"Provides the resilient-consensus construction used to generate graphs satisfying Assumption 4.","marker":"[26]"},{"why":"Introduces the dimension-wise trimmed mean idea in the distributed setting that BRIDGE transfers to decentralized learning.","marker":"[27]"},{"why":"Provides Byzantine-robust distributed learning guarantees and statistical rates that motivate the trimmed-mean analysis.","marker":"[28]"},{"why":"The vector-valued decentralized Byzantine-resilient coordinate-descent baseline against which BRIDGE's communication efficiency is compared.","marker":"[38]"},{"why":"Supplies the impossibility of exact optimum and the transition-matrix convergence machinery used in the consensus proof.","marker":"[42]"},{"why":"Gives the matrix representation of approximate Byzantine consensus, including the deviation bound used to control products of the matrices $Y(t)$.","marker":"[43]"},{"why":"Provides the standard gradient-descent contraction inequality used in the optimality proof.","marker":"[44]"},{"why":"Hoeffding's inequality is the concentration tool behind Lemma 1's bound on gradient-estimation error.","marker":"[47]"}],"fun_headline_variants":["Byzantine-resilient decentralized learning via trimmed mean","Decentralized gradient descent survives Byzantine nodes","Trimmed mean makes decentralized learning Byzantine-safe","BRIDGE provably converges despite Byzantine failures","Robust decentralized learning with Byzantine failure guarantees"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Each nonfaulty node must have more than $2b$ neighbors—enough for the screening step to discard the $b$ worst and $b$ best values and still have someone left to average—and the paper's stated assumptions never require this, so the theorem's guarantee silently excludes networks with sparser neighborhoods.","fun_headline_variants_meta":{"raw":{"variants":["Byzantine-resilient decentralized learning via trimmed mean","Decentralized gradient descent survives Byzantine nodes","Trimmed mean makes decentralized learning Byzantine-safe","BRIDGE provably converges despite Byzantine failures","Robust decentralized learning with Byzantine failure guarantees"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000574,"raw_usage":{"total_tokens":2773,"prompt_tokens":1068,"completion_tokens":1705,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":684,"completion_tokens_details":{"reasoning_tokens":1635}},"tokens_in":684,"tokens_out":1705,"duration_ms":602997,"temperature":1.0,"reasoning_tokens":1635,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:51:43.033339+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a directed graph satisfying Assumption 4 with $b=1$ in which some nonfaulty node has exactly two neighbors; at the first iteration the trimming step removes one smallest and one largest neighbor value in each coordinate, leaving an empty neighbor set, so the node's update reduces to its own value minus a gradient step, and nonfaulty nodes need not reach consensus—contradicting Theorem 1's claim that consensus holds for every graph covered by Assumptions 1–4.","supporting_citations":[{"cited_title":"Nedi´ c and A","cited_arxiv_id":null,"evidence_quote":"Supplies the distributed gradient descent update that BRIDGE robustifies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the resilient-consensus construction used to generate graphs satisfying Assumption 4."},{"cited_title":"El Mhamdi, R","cited_arxiv_id":null,"evidence_quote":"Introduces the dimension-wise trimmed mean idea in the distributed setting that BRIDGE transfers to decentralized learning."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Byzantine-robust distributed learning guarantees and statistical rates that motivate the trimmed-mean analysis."},{"cited_title":"Yang and W","cited_arxiv_id":null,"evidence_quote":"The vector-valued decentralized Byzantine-resilient coordinate-descent baseline against which BRIDGE's communication efficiency is compared."},{"cited_title":"Byzantine Multi-Agent Optimization: Part I","cited_arxiv_id":"1506.04681","evidence_quote":"Supplies the impossibility of exact optimum and the transition-matrix convergence machinery used in the consensus proof."},{"cited_title":"Hoeffding","cited_arxiv_id":null,"evidence_quote":"Hoeffding's inequality is the concentration tool behind Lemma 1's bound on gradient-estimation error."}],"review_version":1}