{"id":"0add9afd-52bf-47cc-aa6e-b95d1d4514db","arxiv_id":"2411.16477","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A gossip-based FTRL algorithm for distributed online convex optimization with random agent availability achieves expected network regret O(κ/p min{√N, N^{1/4}/√p} √T).","lead":"This paper analyzes a distributed online learning algorithm for networks where agents randomly go offline, proving regret bounds that depend on the network structure and the probability of being active. It matters for federated learning deployments with unreliable clients, where theoretical guarantees under intermittent availability were missing.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 1's advertised κ/p bound is not implied by the proof; Theorem 1 with Lemma 4 gives κ/p², so the formal result overstates the p-dependence by a factor 1/p.","rationale":"The paper is read in good faith: the setting is novel, and the omniscient-agent decomposition in Theorem 1 is plausible. The reader's stated weakest assumption (independence of activations) is a real modeling limitation, but it is up-front and standard; it would not, by itself, make the central proof unsound. The more pressing issue is internal: the formal Corollary 1 is not a consequence of Theorem 1 plus Lemma 4. Optimizing Eq. (5) while respecting Lemma 4 gives the abstract's κ/p² dependence, not the κ/p stated in Corollary 1 and in the contributions bullet. Since p can be as small as 1/N, this is a factor-N discrepancy in the advertised bound. The lower bound Theorem 3 is not affected, and it appears correct in scaling, but it does not resolve the p-dependence inconsistency. A correction to Corollary 1 (and matching abstract and bullet) is therefore needed; the reader's CONDITIONAL verdict stands. We also note in passing that the lower-bound proof contains a small constant slip (λ1 of the cycle is 4, not 1, and the averaged lower-bound constant appears off by a small factor), but these do not affect the scaling and are not load-bearing.","tokens_in":30223,"tokens_out":19535,"duration_ms":182758,"concrete_test":"Re-derive Corollary 1 symbolically: combine the p-uniform bound (5) with Lemma 4's ρ/(1−ρ) ≤ 2κ/p², minimize over η, and compare the resulting p- and N-exponents with Eq. (14). As a numerical check, take G a cycle with N = 100 and p = 1/N; compute ρ exactly from Theorem 5, evaluate 1/(1−ρ), and compare the right-hand sides of (6) and (14). If the ratio of the (6)-based bound to the (14)-based bound grows as 1/p (≈ N), Corollary 1's κ/p claim is refuted and must be corrected to κ/p². Alternatively, exhibit from Theorem 1 a choice of η that attains the κ/p rate; if no such η exists (as the algebra indicates), the Corollary needs revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Load-bearing concern: Corollary 1 (Eq. 14) states E[Rnet_T] = O((κ(G)/p) min{√N, N^{1/4}/√p} √T), but this does not follow from the supporting results. Lemma 4 (with Theorem 5, b = 1/λ1(G)) gives ρ/(1−ρ) ≤ 2κ(G)/p²; because ρ ≤ sqrt(1 − p²/κ), the same bound holds for 1/(1−ρ). Substituting 1/(1−ρ) ≤ 2κ/p² into the optimized bound (6) yields O((κ/p²) min{√N, N^{1/4}/√p} √T), which is the abstract's version, not the κ/p version of Corollary 1. The claimed κ/p rate would require 1/(1−ρ) ≤ O(κ/p), which is false for small p: on a cycle or path, κ ≈ N² and 1−ρ ≈ p²/κ, so 1/(1−ρ) ≈ κ/p². Thus the formal Corollary understates regret by a factor 1/p and is inconsistent with the paper's own Theorem 1 and Lemma 4. This is not a typo in a constant: it changes the scaling in the regime p → 1/N, where the advertised bound is a factor N too optimistic. The main contribution should be stated as κ/p², or a genuinely new argument for κ/p must be supplied.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributed online convex optimization with stochastic agent availability: at each round each agent is active with probability p_v, inactive agents neither incur loss nor communicate. The authors propose Gossip-FTRL, a distributed FTRL variant with gossip-based gradient averaging, and analyze its expected and high-probability network regret, defined as the average over active agents of instantaneous regret. The main claims are an expected regret bound depending on the spectral gap of the expected gossip matrix (Theorem 1), a p-uniform rate stated as O(κ/p min{√N, N^{1/4}/√p}√T) (Corollary 1), a high-probability bound (Theorem 2), and a lower bound for p=1 showing the average-agent network regret is essentially as hard as worst-agent regret (Theorem 3). The paper also gives closed-form spectral-gap computations for cliques, strongly regular graphs, grids, and random edge-deletion, plus synthetic experiments comparing Gossip-FTRL with DOGD.","tokens_in":95,"tokens_out":41516,"duration_ms":480520,"significance":"If the quantitative claims are corrected, this is a solid contribution: it is, to my knowledge, the first DOO analysis with stochastic node availability, it recovers existing edge-availability bounds as a special case, and it provides a self-contained FTRL/gossip analysis with explicit learning-rate and gossip-weight formulas rather than fitted parameters. The appendix contains detailed proofs, the spectral computations in Section 6 are explicit, and the experiments are reproducible in principle. The lower bound at p=1 is valuable because it connects the average-agent network regret to the standard worst-agent regret. The main weakness is that several formal statements overstate what the proofs establish, most importantly the p-dependence in Corollaries 1 and 2; these issues are local and fixable, but they are load-bearing.","major_comments":[{"comment":"The advertised rate in Corollary 1, E[Rnet_T] = O((κ(G)/p) min{√N, N^{1/4}/√p}√T), does not follow from Theorem 1 and Lemma 4. Lemma 4 gives ρ/(1−ρ) ≤ 2κ(G)/p², hence 1/(1−ρ) ≤ 1+2κ/p² ≤ 3κ/p² for κ≥1; substituting into the optimized bound (6) yields O((κ(G)/p²) min{√N, N^{1/4}/√p}√T), which is the abstract's rate, not the κ/p rate of Eq. (14). This is not a loose-constant artifact: for a cycle or path, 1−ρ = Θ(p²/κ), so 1/(1−ρ) = Θ(κ/p²), and the claimed κ/p bound is a factor p too optimistic in the small-p regime. Corollary 2 has the same issue: with edge-activation probability q, the same derivation gives κ/(p²q²), not κ/(pq). Please correct these statements or provide a genuinely new argument for the stronger contraction.","section":"Corollary 1, Eq. (14); Corollary 2, Eq. (15)"},{"comment":"The displayed learning rate in Theorem 1, η = (D/L)√μ/2 · √(2p min(pN,√N)T), scales as √T, which is not the correct FTRL tuning for a finite-horizon bound. Substituting this η into Eq. (5) makes the two terms scale as T^{3/2} and 1/√T, so the stated regret bound (6) does not follow. The bound (6) appears to require the reciprocal scaling η = (D/L)√μ / (2√(2p min(pN,√N)T)). Please correct the displayed formula and re-derive the resulting constants.","section":"Theorem 1, Eq. (6)"},{"comment":"The lower-bound proof is internally inconsistent. The network loss is defined as ℓnet_t(V,x) = M(N−M+1)/N H_k(x), but the regret computation pulls out only (N−M+1)/N, dropping the factor M; carrying the M through changes the displayed bound by a factor M. In addition, the nonzero local losses are (N−M+1)H_k, whose Lipschitz constant is (N−M+1)L, not L, so the constructed losses do not satisfy the theorem's L-Lipschitz hypothesis. Finally, the transition from per-agent regret to network regret uses 1/N ∑_{v∈U} but does not multiply by |U|=M. The qualitative Θ(√N√T) lower bound may survive after rescaling the local losses and accounting for the averaging over agents, but the proof as written requires a substantial correction.","section":"Appendix E, proof of Theorem 3"},{"comment":"The proof of Theorem 4 asserts λ2(E[W1]) ≤ λ2(I − b P Lap(G)P). This inequality is false for non-uniform activation probabilities: for N=2, p1=0.1, p2=0.9, and b=1/λ1(G)=1/2, λ2(E[W1])=0.91 while λ2(I−b P Lap(G)P)=0.59. The claimed final bound ρ² ≤ 1−b p²_min λ_{N−1}(G) is nevertheless true and follows directly from x^T E[Lap(G1)]x = ∑_{(i,j)∈E} p_i p_j (x_i−x_j)^2 ≥ p²_min x^T Lap(G)x. Since Theorem 4 is used for the arbitrary-probability bound (7), please repair the proof rather than relying on the current chain of inequalities.","section":"Section 6, proof of Theorem 4"}],"minor_comments":[{"comment":"The introduction says activation probabilities are unknown, while the algorithm and tuning require p (or p_min) to be known; please clarify exactly which quantities must be known for each bound.","section":"Section 2 vs. Section 3"},{"comment":"The statement 'λ1(G)=1' for the cycle Laplacian is incorrect for the unnormalized Laplacian; the largest eigenvalue is 2−2cos(2π⌊N/2⌋/N), which is about 4 for large N. The subsequent bound still holds with the correct value, but the text should be corrected.","section":"Appendix E, proof of Theorem 3"},{"comment":"The phrase 'one can can set' contains a duplicated word and should read 'one can set'.","section":"Section 4, after Eq. (6)"},{"comment":"The high-probability bound as stated has a constant 3 inside the parentheses, while the final line of its proof, Eq. (28), has a 4; please align the constants.","section":"Theorem 2"},{"comment":"The caption says 'The quantity bρ2 is the second eigenvalue of W1²...' which appears to contain a typo; the intended quantity is likely the empirical estimate ρ̂². Please clarify.","section":"Figure 1 caption"}],"recommendation":"major_revision","confidential_remarks":"The core machinery is sound and the paper is likely fixable, but the public statements of the main rates (Corollaries 1 and 2) are stronger than the proofs, Theorem 1 contains a learning-rate typo that affects the derived bound, and the lower-bound proof has scaling inconsistencies. These are load-bearing but local; a careful revision with corrected statements and proofs should bring the paper to an acceptable state. The p-dependence discrepancy between the abstract (κ/p²) and Corollary 1 (κ/p) suggests the authors should decide on the correct rate and align all statements."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the first DOO analysis with random node availability, and the main proof machinery is sound. But the paper is internally inconsistent about the p-dependence: the abstract states κ/p², while Corollary 1 and the contributions list claim κ/p. The proof only supports κ/p². Fix that and the paper is a solid contribution.\n\nWhat is genuinely new: inactive agents neither incur loss nor communicate, and the network regret is defined as an average over active agents. The omniscient-agent decomposition and the gossip contraction analysis are carefully executed. Theorem 1 holds for arbitrary connected graphs and activation probabilities, with learning rates set by closed-form formulas. Theorem 4 and Theorem 5 give clean graph-theoretic bounds on the spectral gap. The high-probability bound in Theorem 2 is a useful extra. Theorem 3 gives a lower bound for p=1 that matches the upper bound up to constants and logs, so the 'essentially equivalent' claim for p=1 holds up. The experiments are modest but do show the predicted 1/p² scaling in Figure 4.\n\nThe main soft spot is exactly what the stress-test note says. Corollary 1 states E[R_net] = O((κ/p) min{√N, N^{1/4}/√p} √T). But Lemma 4 gives ρ/(1−ρ) ≤ 2κ/p², and since 1/(1−ρ) ≤ 1 + ρ/(1−ρ) ≤ O(κ/p²), substituting into Theorem 1's (6) yields κ/p², not κ/p. The abstract's κ/p² is the correct bound; Corollary 1 and the corresponding bullet in Section 1 are wrong by a factor p. This is not a constant typo: when p is small, it changes the scaling. The fix is to rewrite Corollary 1 with κ/p² or supply a genuinely new argument for the κ/p rate.\n\nLesser concerns: the lower bound only covers p=1, so the 'not significantly improvable' claim is strictly for p=1; the paper says that, but the abstract's phrasing could be read more broadly. The independence and known-p assumptions are restrictive, though the non-stationary extension in the appendix partly addresses this. These are acceptable for a first paper.\n\nRecommendation: send to peer review. The core analysis is original and careful, and the error in Corollary 1 is localized and fixable. A serious referee should verify the p-dependence in the final version, but the machinery is worth engaging with.","headline":"First clean analysis of stochastic node availability in distributed online optimization, but Corollary 1's κ/p bound is a factor 1/p too optimistic; the abstract's κ/p² is the correct statement.","tokens_in":31067,"tokens_out":4112,"would_cite":true,"duration_ms":36401,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Stochastic agent availability can be absorbed into the spectral gap of gossip averaging, leaving a √T network regret bound for distributed online optimization.","keywords":["distributed online optimization","network regret","stochastic client availability","gossip algorithms","follow-the-regularized-leader","convex online learning","spectral gap","intermittent participation"],"falsifier":"Run Gossip-FTRL on a graph where the same agents tend to be inactive in back-to-back rounds (for example, diurnal availability) with the learning rate tuned as if activations were independent, and measure the network regret over T steps; if the regret grows faster than √T, the independence assumption is doing the work. Alternatively, on a cycle, simulate the i.i.d. activation model and check empirically that E∥W_t ... W_{s+1} e_v - 1/N∥² decays at rate $ρ^{{2(t-s)}}$; a slower decay would break Lemma 2 and the upper bound.","tokens_in":30039,"feed_emoji":"🎲","tokens_out":8111,"duration_ms":70713,"temperature":0.7,"pith_summary":"This paper asks whether distributed online learning is still controllable when clients are not always available. It studies a protocol where each agent is active with probability p at every round, and communication is only possible between simultaneously active neighbors. The paper introduces Gossip-FTRL, in which each active agent runs FTRL on a gossip-averaged estimate of the cumulative gradient, and proves that the expected network regret—the average regret over active agents—is O((κ(G)/p) min{√N, $N^{{1/4}}$/√p} √T) in the uniform-activation case, where κ(G) is the condition number of the graph Laplacian. This shows that random availability costs roughly a 1/p factor, but the √T scaling of single-agent online learning survives. The paper also proves a lower bound at p=1 showing that the average-over-agents regret is essentially as hard as the standard worst-case regret, so the averaging notion is not a way to avoid the difficulty.","feed_headline":"Gossip-FTRL keeps regret near √T when agents vanish","feed_subtitle":"Random client availability multiplies network regret by roughly 1/p, and a lower bound shows the average-regret notion is no shortcut.","key_machinery":"The load-bearing object is the random gossip matrix W_t = I - b Lap(G_t), where G_t is the graph induced by the active agents and b ≤ 1/λ1(G) makes the matrix doubly stochastic and nonnegative. Its expected second eigenvalue ρ² = λ2(E[W_1 W_1^T]) is the contraction factor for the deviations between local cumulative-gradient estimates z_t(v) and the omniscient average; Lemma 2 bounds E∥W_t ... W_{s+1} e_v - 1/N∥² by $ρ^{{2(t-s)}}$. Around this, the proof uses an omniscient FTRL agent to decompose the regret, the duality between strong convexity of the regularizer and smoothness of the conjugate to convert gradient deviations into prediction deviations, and Theorems 4 and 5 to express ρ through the Fiedler value and condition number κ(G) of the Laplacian.","core_discovery":"The central discovery is that stochastic node availability can be absorbed into the spectral-gap analysis of gossip averaging. At each round the active agents induce a random graph, and the gossip matrix W_t = I - b Lap(G_t) is doubly stochastic; the quantity ρ = $\\sqrt$(λ2(E[W_1 W_1^T])) controls how fast information propagates through the network. The authors prove that, for any connected graph, an omniscient FTRL agent provides a benchmark such that each agent's deviation from the omniscient prediction contracts at rate $ρ^{{t-s}}$, yielding expected network regret of order (1/(1-ρ)) min{√N, $N^{{1/4}}$/√p} √T in the p-uniform case, and O(κ(G)/p min{√N, $N^{{1/4}}$/√p} √T) after expressing ρ through the Laplacian condition number. A complementary lower bound at p=1 shows that any distributed online algorithm must suffer network regret Ω((ρ/(1-ρ))^{α/4} $N^{{(1-α)/2}}$ √T) on some graph, meaning the average over agents does not make the problem fundamentally easier than worst-case regret.","pith_inferences":["If p is not known in advance, an adaptive learning-rate schedule could in principle preserve the √T guarantee; the current analysis requires p (or bounds pmin, pmax) for tuning.","Because the global loss is an average over active agents, the setting maps directly onto federated learning with client subsampling, so one testable extension is to compare Gossip-FTRL's communication protocol with standard partial-participation schedules on real non-i.i.d. data.","Time-correlated availability (for example diurnal client cycles) breaks the i.i.d. gossip-matrix assumption; a natural extension would replace the constant spectral gap ρ with a mixing-time-based contraction and would likely pay an extra factor depending on the correlation length.","The lower-bound construction uses a cycle, so topology bottlenecks appear to drive the price of intermittency; adding edges to a bottleneck should reduce regret, consistent with the paper's Figure 5."],"forward_implications":["In the p-uniform case, the expected network regret of Gossip-FTRL is O((κ(G)/p) min{√N, N^{1/4}/√p} √T), so random availability worsens regret only by roughly a 1/p factor while preserving the √T rate.","At p=1, the lower bound Ω((ρ/(1-ρ))^{α/4} N^{(1-α)/2} √T) shows that the average-over-active-agents regret is essentially as hard as the standard worst-case regret, so averaging over agents does not sidestep the difficulty.","The Erdős-Rényi random-edge setting is recovered as a special case, with expected regret O(κ(G)/(pq) min{√N, N^{1/4}/√p} √T) when each edge is active with probability q.","A high-probability version of the bound holds with probability 1-δ and only logarithmic dependence on 1/δ, at the cost of an extra polynomial-in-N factor that disappears when agents know |S_t|.","For dense graphs such as cliques the spectral gap makes ρ=0, giving an expected regret of order √T that does not grow with N."],"supporting_citations":[{"why":"Provides the DOGD baseline and the Erdős-Rényi random-edge analysis whose bounds the authors recover as a special case of their node-availability framework.","marker":"Lei et al., 2020"},{"why":"Supplies the online dual-averaging DOO algorithm and worst-case regret benchmark that Gossip-FTRL extends to arbitrary regularizers and random activations.","marker":"Hosseini et al., 2013"},{"why":"Gives the nearly optimal decentralized OCO bound and the RT = Θ̃(N(1-ρ)^{-1/4}√T) comparison that anchors the p=1 lower bound.","marker":"Wan et al., 2024"},{"why":"Provides the randomized-gossip contraction analysis (including the Markov inequality lemma) used for both the expectation and high-probability bounds.","marker":"Boyd et al., 2006"},{"why":"Supplies the single-agent FTRL regret bound and the strong-convexity/smoothness duality theorem used in the omniscient-agent decomposition.","marker":"Orabona, 2019"},{"why":"The lower-bound construction for arbitrary client participation is adapted in Theorem 3 to prove the network-regret lower bound at p=1.","marker":"Wang and Ji, 2022"},{"why":"Motivates the choice of gossip matrix W_t = I - b Lap(G_t) for fast distributed averaging.","marker":"Xiao and Boyd, 2004"},{"why":"Provides the spectral graph theory facts (Laplacian eigenvalues of cycles, paths, and grids) used in the closed-form ρ bounds.","marker":"Spielman, 2019"}],"fun_headline_variants":["Distributed FTRL: regret O(√T) even if clients vanish","Stochastic client dropout: gossip regret scales 1/p","Random availability: network regret O(√T) with penalty 1/p","Gossip-FTRL copes with absent clients, regret O(√T) times 1/p","Lower bound: average regret no easier with random clients"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument requires that agents' activation events are independent across agents and time with a known probability, so that the gossip matrices are i.i.d. and the spectral-gap contraction lemma applies; if availability is correlated over time or the probability is unknown, the stated bounds and learning-rate tuning no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["Distributed FTRL: regret O(√T) even if clients vanish","Stochastic client dropout: gossip regret scales 1/p","Random availability: network regret O(√T) with penalty 1/p","Gossip-FTRL copes with absent clients, regret O(√T) times 1/p","Lower bound: average regret no easier with random clients"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001541,"raw_usage":{"total_tokens":6196,"prompt_tokens":1005,"completion_tokens":5191,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":621,"completion_tokens_details":{"reasoning_tokens":5091}},"tokens_in":621,"tokens_out":5191,"duration_ms":30824,"temperature":1.0,"reasoning_tokens":5091,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:12:00.448630+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Gossip-FTRL on a graph where the same agents tend to be inactive in back-to-back rounds (for example, diurnal availability) with the learning rate tuned as if activations were independent, and measure the network regret over T steps; if the regret grows faster than √T, the independence assumption is doing the work. Alternatively, on a cycle, simulate the i.i.d. activation model and check empirically that E∥W_t ... W_{s+1} e_v - 1/N∥² decays at rate $ρ^{{2(t-s)}}$; a slower decay would break Lemma 2 and the upper bound.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the DOGD baseline and the Erdős-Rényi random-edge analysis whose bounds the authors recover as a special case of their node-availability framework."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the online dual-averaging DOO algorithm and worst-case regret benchmark that Gossip-FTRL extends to arbitrary regularizers and random activations."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the nearly optimal decentralized OCO bound and the RT = Θ̃(N(1-ρ)^{-1/4}√T) comparison that anchors the p=1 lower bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the randomized-gossip contraction analysis (including the Markov inequality lemma) used for both the expectation and high-probability bounds."},{"cited_title":"and Ji, M","cited_arxiv_id":null,"evidence_quote":"The lower-bound construction for arbitrary client participation is adapted in Theorem 3 to prove the network-regret lower bound at p=1."},{"cited_title":"and Boyd, S","cited_arxiv_id":null,"evidence_quote":"Motivates the choice of gossip matrix W_t = I - b Lap(G_t) for fast distributed averaging."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the spectral graph theory facts (Laplacian eigenvalues of cycles, paths, and grids) used in the closed-form ρ bounds."}],"review_version":1}