{"id":"c8a5bc9a-e385-4d47-b4ca-bb73f59de8e9","arxiv_id":"2507.10325","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Agnostic FedAvg converges at O(1/sqrt T) to the availability-weighted objective under unknown non-uniform client participation, for convex losses.","lead":"This paper proves that a simple federated averaging algorithm, which averages whatever clients happen to be online, converges for convex problems even when the chance of being online varies across clients and is unknown. The result matters because real federated systems cannot control or even observe client availability, so convergence guarantees that require knowing participation probabilities have limited practical reach.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4 rests on every client performing local SGD and receiving the broadcast each round; if intermittent participation means offline clients skip updates, Eq. (7) fails and the advertised guarantee is not established.","rationale":"I agree with the reader's weakest assumption. The proof of Theorem 4 depends structurally on all clients being reset to the server model and performing local SGD every round, not just on the sampled subset uploading. If the intended real-world setting is standard intermittent participation, in which offline clients do not compute, then the core advertised contribution is not covered. I also checked the other flagged issue, the appearance of the global variance σ² in Lemma 2: it is notationally odd but not a correctness failure, because Assumption 3 gives a G² term large enough to make the displayed bound valid despite using a weighted-average variance. Thus the all-clients-update requirement is the single most load-bearing concern. The paper does honestly specify Algorithm 1 with this requirement, so the issue is scope rather than internal inconsistency; nonetheless, the abstract and introduction generalize to intermittent participation without stating this limitation, which is why the conditional verdict is appropriate and no change to the reader's verdict is needed.","tokens_in":8788,"tokens_out":16236,"duration_ms":193905,"concrete_test":"Run the §4 synthetic convex linear-regression task under two variants: (A) all N clients perform H local SGD steps every round and only the sampled subset uploads (Algorithm 1 as analyzed); (B) only sampled clients perform local SGD and upload, while unsampled clients keep their stale local iterate. For both, compute E[f((1/T)Σ_{t=1}^T \\hat θ_{tH})] - f(θ*) over many seeds. If variant B does not decrease at the predicted O(1/√T) rate or does not approach zero under the same p-weighted objective, the all-clients-update condition in Eq. (7) is necessary for Theorem 4, and the advertised intermittent-participation claim must be narrowed. An analytical companion check is to verify whether θ_i^{(T-1)H} = \\hat θ_{(T-1)H} holds for every i in variant B; it fails immediately for any client not selected in round T-1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Eq. (7), which assumes θ_i^{(T-1)H} = \\hat θ_{(T-1)H} for every client i, and Eq. (6), which weights every client's local subproblem by p_i. These are guaranteed only by Algorithm 1 lines 6–9, where every one of the N clients receives the server broadcast and performs H local SGD steps each global round. If an unavailable client is truly offline, it cannot receive the broadcast or update locally; its local iterate becomes stale, the equality behind Eq. (7) fails, and the descent inequality (8) does not follow. The paper's phrasing ('if available at time t transmit') suggests availability affects only uploading, but the abstract and title promise convergence under intermittent participation, which in federated learning standardly means unselected clients do no computation. The paper never flags the all-clients-update requirement as a limitation. This is a scope concern rather than an internal contradiction: the stated Algorithm 1 is internally consistent, but the central claim is not established for the common interpretation of partial participation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies agnostic Federated Averaging (Algorithm 1) under random, non-uniform, and unknown client availability. It defines marginal inclusion weights p_i via Eq. (2), shows in Lemma 4 that the server's unweighted averaging step satisfies a Jensen-type inequality against the p-weighted squared distance, and claims in Theorem 4 that agnostic FedAvg converges at O(1/sqrt(T)) for convex, possibly nonsmooth losses to the minimum of the p-weighted global objective (Eq. (3)). The paper also reports experiments on MNIST and a synthetic linear regression task comparing agnostic FedAvg with a weighted FedAvg variant. Full proofs of the central lemmas are deferred to a forthcoming submission, as stated in the note after the abstract.","tokens_in":8979,"tokens_out":5354,"duration_ms":57195,"significance":"If correct, this would be the first convergence guarantee for FedAvg under entirely unknown, non-uniform client participation, and the induced-objective perspective (the p_i weights arising from availability rather than from data importance) is a useful conceptual contribution. The proof of Lemma 4 is clear and self-contained, and the empirical comparison with weighted FedAvg is a meaningful sanity check. However, the central convergence proof is not included in the manuscript, and the stated assumptions do not match the advertised setting of intermittent participation as commonly understood, so the significance can only be assessed after a substantial revision that addresses the points below.","major_comments":[{"comment":"The convergence proof assumes that every client, including clients not in the availability set S_t, performs H local SGD steps and receives the server broadcast each round (Algorithm 1, lines 6 and 8–9). The equality θ_i^{(T−1)H} = \\hat θ_{(T−1)H} used in Eq. (7) and the p_i-weighting in Eq. (6) depend on this. If “intermittent participation” is interpreted in the standard federated-learning sense—unavailable clients are offline and do not compute or receive the model—the theorem does not apply. The paper should either state explicitly that the result covers only the all-clients-update model and adjust the abstract and introduction accordingly, or extend the analysis to the case where only available clients update.","section":"Algorithm 1 and §3.3, Eqs. (7)–(8)"},{"comment":"The lemma states a per-client inequality using the global variance bound σ² = Σ_k p_k σ_k², but Assumption 2 provides only the per-client bound σ_i². Since σ² is a weighted average, it need not dominate each σ_i², so the inequality is not justified as written. The proof is deferred, so the reader cannot verify whether the intended statement uses σ_i² and later passes to σ² after weighting, or whether σ² is meant to be a uniform upper bound. This needs correction or clarification because this σ² term appears in the final rate expression (Eq. (9)).","section":"Lemma 2, Eq. (l1-(1))"},{"comment":"The main theorem relies on Lemma 2, Lemma 3, and the derivation of Eq. (7), none of which are proven in the manuscript; the note after the abstract says full proofs are deferred. For a paper whose central claim is a convergence guarantee, this is a load-bearing omission: the reader cannot check the correctness of the descent inequality, the coupling argument, or the final rate. The manuscript should include complete proofs of these steps, or clearly repackage the claim as a proof sketch with the full proof provided in an appendix or companion document.","section":"§3 and Theorem 4"}],"minor_comments":[{"comment":"The derivation refers to “Lemma 3.1”, but the correct reference appears to be Corollary 1 (Local Value Divergence) rather than Lemma 3. Please fix the cross-reference.","section":"§3.3, Eq. (7)"},{"comment":"The text says “discrepacy” in the second paragraph; it should be “discrepancy”.","section":"§4"},{"comment":"The implementation details are said to be available in an accompanying GitHub repository, but no URL is provided.","section":"§4"},{"comment":"The term “Bayesian interpretation” is a slight misnomer; the expression is simply the law of total probability. Consider rephrasing to avoid confusion.","section":"§2, Eq. (4)"},{"comment":"Reference [22] is a survey on non-IID data and does not obviously contain the claimed convergence proof for FedAvg under full participation; please cite the original analysis (e.g., McMahan et al. [1] or subsequent work) instead.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"This is a theoretical convergence paper whose proofs are almost entirely deferred to a future journal version. For a journal submission, the absence of the main proofs is a serious issue regardless of the technical content. The participation-model mismatch between the abstract and the algorithm is also likely to attract criticism from reviewers familiar with federated learning practice. I recommend insisting on a self-contained proof and a clear statement of the participation model before considering acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this does one genuinely useful thing—it identifies the objective that unweighted FedAvg with random client subsets actually minimizes, namely sum_i p_i f_i(theta) with p_i = sum_{A contains i} q(A)/|A|, and it sketches a standard convex-analysis proof of O(1/sqrt T) convergence. If the full proofs hold up, it gives a clean, natural anchor for FL theory. The sample-to-model inequality (Lemma 4) is the right tool, and the high-level descent argument is conventional.\n\nThe soft spots are real but mostly fixable. First, the proofs are deferred to a forthcoming journal submission, so the displayed lemmas are the only evidence. Second, Lemma 2 states the one-step progress bound with the global variance sigma^2 where per-client sigma_i^2 is needed; as written the inequality is wrong for clients with smaller variance. That's a notation slip, not a conceptual one, but it needs fixing. Third—and this is the one I'd push on—the theorem only covers a specific interpretation of intermittent participation. Algorithm 1 has every client receive the broadcast and perform H local SGD steps every round, with availability affecting only whether the local parameters are transmitted. So Eq. (7)'s use of theta_i^{(T-1)H} = hat theta_{(T-1)H} for all i is valid, but for the common FL reading where unavailable clients are offline and skip local computation, the descent inequality does not follow. The abstract says 'intermittent participation' without pinning down this detail, and the paper never lists the all-clients-update requirement as a limitation. The stress-test note gets this right; I think it's a scope problem rather than a contradiction, but it is a load-bearing one.\n\nThe novelty claims are also a bit strong. Saying no convergence result exists even for fixed-size known-probability sampling is not supported by the citations; the paper's own references include client-sampling analyses that handle known probabilities. The newness is in the unknown-q, variable-size case, and that is enough.\n\nThe empirical section is suggestive but thin: no code, no error bars, five seeds. That is fine for a theory paper.\n\nWho should read it: people working on federated optimization who want a precise statement of what plain averaging optimizes. It deserves a serious referee—the question is natural and the characterization is useful—but the authors should either attach the proofs or honestly scope the theorem to the all-clients-update protocol. My recommendation: send it to review with the explicit requirement that the full proofs be included or accessible, and that the participation assumption be stated in the title or abstract.","headline":"A useful but incomplete characterization of the objective of agnostic FedAvg; the convergence proof is plausible, but the participation assumption is narrower than the abstract suggests.","tokens_in":9498,"tokens_out":4177,"would_cite":true,"duration_ms":43468,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that agnostic Federated Averaging converges at the standard $\\mathcal{O}(1/\\sqrt{T})$ rate for convex losses even when client participation is unknown, non-uniform, and random.","keywords":["federated learning","partial participation","convergence analysis","agnostic FedAvg","convex optimization","client availability distribution","stochastic client sampling","O(1/sqrt(T)) rate"],"falsifier":"Run Algorithm 1 on a convex problem with skewed, non-uniform availability while freezing all clients that are not selected for upload, so they perform no local SGD and do not receive the broadcast; if the expected suboptimality gap does not decrease at the claimed $\\mathcal{O}(1/\\sqrt{T})$ rate or diverges, the theorem's coverage of intermittent participation would be falsified for that regime.","tokens_in":8560,"feed_emoji":"📡","tokens_out":13169,"duration_ms":138950,"temperature":0.7,"pith_summary":"This paper asks whether Federated Averaging can converge when the server has no idea which clients will be available for each aggregation round, in what proportions, or even how many will show up. The authors establish that under convex, possibly nonsmooth losses, agnostic FedAvg—where the server simply averages the parameters of whatever clients are available—converges in expectation at the standard $\\mathcal{O}(1/\\sqrt{T})$ rate. They identify the objective being optimized: a weighted sum of local losses in which each client's weight is its size-adjusted availability probability, so the goal emerges from participation dynamics rather than being imposed by the server. If correct, unweighted averaging is not a fallback to be corrected once participation patterns are known; it is a principled optimization method in its own right.","feed_headline":"Agnostic FedAvg provably converges under unknown client participation","feed_subtitle":"No one needs to estimate who participates: plain averaging of online clients reaches the standard 1/sqrt(T) rate.","key_machinery":"The load-bearing object is the survival distribution $\\{p_i\\}_{i=1}^N$ together with the sample-to-model inequality of Lemma 4. The distribution summarizes a two-stage random experiment: first an availability subset $S_t$ is drawn from $q$, then one client is drawn uniformly from $S_t$, so $p_i$ measures how often client $i$ would be the randomly selected representative of the available group. Lemma 4 shows $\\mathbb{E}[\\lVert \\hat{\\theta}_t-\\theta^*\\rVert^2 \\mid \\mathcal{F}_{t-1}] \\le \\sum_{i=1}^N p_i \\lVert \\theta_i^{t-1}-\\theta^*\\rVert^2$, which is the bridge between the server's unweighted average and a weighted descent on the global objective. Composing this inequality with the per-client progress bounds of Lemmas 2 and 3 yields the recursive descent inequality that produces the $\\mathcal{O}(1/\\sqrt{T})$ rate.","core_discovery":"The central claim is that projected agnostic Federated Averaging (Algorithm 1) minimizes the global objective $\\inf_{\\theta\\in\\Theta}\\sum_{i=1}^N p_i f_i(\\theta)$, where $p_i = \\sum_{A\\subseteq[N], i\\in A} q(A)/|A|$ is the chance that client $i$ is selected uniformly from a realized availability subset $A$, and $q$ is an arbitrary distribution over client subsets. Theorem 4 states that, for convex and possibly nonsmooth losses satisfying bounded-gradient and bounded-variance assumptions, the average of the server models over $T$ aggregation rounds has an expected suboptimality gap of order $\\mathcal{O}(1/\\sqrt{T})$ with step size $\\eta = \\Theta(1/\\sqrt{TH})$. The proof turns the random subset aggregation into a deterministic $p_i$-weighted problem by way of Lemma 4, which bounds the squared error of the unweighted server average by the $p_i$-weighted sum of client squared errors.","pith_inferences":["The proof's broadcast-reset requirement implies a practical deployment constraint: clients absent at upload time must still be reachable for updates; scheduling background local updates for unavailable devices would keep agnostic FedAvg inside the theorem's scope.","Because the implicit objective is availability-weighted, a fairness-oriented deployment could use the same $p_i$ model to quantify how much the global model favors frequent participants, a consequence the paper leaves undeveloped.","The paper's results suggest that correcting participation bias should happen at the sampling-design stage rather than by post-hoc reweighting of aggregates, since the experiments show reweighting made things worse.","A direct extension would vary the availability distribution over time (periodic, Markovian, or bursty) and test whether the same $p_i$-weighted objective and rate persist; the current analysis assumes i.i.d. subsets each round."],"forward_implications":["A server needs no participation statistics: on convex problems, simply averaging the parameters of whichever clients are reachable achieves the standard $\\mathcal{O}(1/\\sqrt{T})$ error rate.","The global objective is availability-weighted: each client's influence is set by how often and in what group sizes it is available, not by its dataset size or label diversity.","The result covers random subset sizes at every round, so variable numbers of participating clients require no special handling or known sampling probabilities.","Weighted aggregation using estimated participation weights can underperform the plain unweighted rule, and the paper's experiments show the gap widens as participation skew grows.","The rate matches the usual $\\mathcal{O}(1/\\sqrt{T})$ of convex stochastic optimization, with the proof's constants absorbing the local steps $H$, the gradient bound $G$, and the Lipschitz constant $\\ell$."],"supporting_citations":[{"why":"Defines the FedAvg algorithm and the local-update/broadcast protocol that Algorithm 1 generalizes to arbitrary availability.","marker":"[1]"},{"why":"Motivates client selection under heterogeneous resource constraints, the practical setting the paper models as random availability subsets.","marker":"[10]"},{"why":"Supplies the known-probability, fixed-size client sampling baseline whose aggregation rule agnostic FedAvg is compared against.","marker":"[13]"},{"why":"Documents the challenges of partial participation and heterogeneous networks that motivate removing full-device participation assumptions.","marker":"[14]"},{"why":"Presents a restricted user-availability model that the paper's general subset distribution subsumes.","marker":"[19]"},{"why":"Provides the prior weighted-aggregation rule under known, uniform availability that agnostic FedAvg outperforms in experiments.","marker":"[22]"}],"fun_headline_variants":["FedAvg converges without knowing who's online","Agnostic FedAvg: convergence with random client drops","Biased client sampling? FedAvg still converges at 1/√T","Proven: FedAvg converges under arbitrary, unknown participation","No participation estimates: FedAvg achieves standard rate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes every client, whether or not it is selected for upload, performs all $H$ local SGD steps and resets its local copy to the server broadcast at every communication round; if non-selected clients are genuinely offline and frozen, the per-client recursion that powers the descent argument no longer holds.","fun_headline_variants_meta":{"raw":{"variants":["FedAvg converges without knowing who's online","Agnostic FedAvg: convergence with random client drops","Biased client sampling? FedAvg still converges at 1/√T","Proven: FedAvg converges under arbitrary, unknown participation","No participation estimates: FedAvg achieves standard rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000225,"raw_usage":{"total_tokens":1467,"prompt_tokens":954,"completion_tokens":513,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":433}},"tokens_in":570,"tokens_out":513,"duration_ms":6041,"temperature":1.0,"reasoning_tokens":433,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:35:07.513806+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a convex problem with skewed, non-uniform availability while freezing all clients that are not selected for upload, so they perform no local SGD and do not receive the broadcast; if the expected suboptimality gap does not decrease at the claimed $\\mathcal{O}(1/\\sqrt{T})$ rate or diverges, the theorem's coverage of intermittent participation would be falsified for that regime.","supporting_citations":[{"cited_title":"Convergence of Agnostic Federated Averaging","cited_arxiv_id":"2507.10325","evidence_quote":"Defines the FedAvg algorithm and the local-update/broadcast protocol that Algorithm 1 generalizes to arbitrary availability."},{"cited_title":"Federated learn- ing with edge computing: A communication-efficient architec- ture,","cited_arxiv_id":null,"evidence_quote":"Motivates client selection under heterogeneous resource constraints, the practical setting the paper models as random availability subsets."},{"cited_title":"A field guide to federated optimization,","cited_arxiv_id":null,"evidence_quote":"Documents the challenges of partial participation and heterogeneous networks that motivate removing full-device participation assumptions."},{"cited_title":"Federated op- timization in heterogeneous networks,","cited_arxiv_id":null,"evidence_quote":"Presents a restricted user-availability model that the paper's general subset distribution subsumes."},{"cited_title":"Fedpaq: A communication-efficient federated learning method with periodic averaging and quantization,","cited_arxiv_id":null,"evidence_quote":"Provides the prior weighted-aggregation rule under known, uniform availability that agnostic FedAvg outperforms in experiments."}],"review_version":1}