{"id":"0d5fd556-b9fa-47bb-b18c-02929d2ce08d","arxiv_id":"2506.02563","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A noise-cancellation mechanism makes partial-participation private federated learning optimal in accuracy and linear in time.","lead":"This paper presents a new method for private federated learning when only some devices join each training round. It achieves the best possible accuracy for a given privacy budget with linear computation, closing a gap left by earlier work.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Convergence proof for term (C) in Appendix E.2 replaces the random last-participation event by its marginal probability inside an inner product with dependent future iterates; this step is unjustified, so the claimed optimal linear-time rate is not yet established.","rationale":"The reader identified the uniform-i.i.d. participation assumption as the weakest point. That is an external-validity concern, and the paper states it explicitly. Within the stated model, the more serious issue is internal: the proof of the central convergence theorem (5.2) contains an unjustified step in bounding term (C). The noise-cancellation mechanism makes the effective noise Y_t a mixture of past noises with geometric lifetimes; the proof replaces the 'last participation' indicator by its marginal probability inside an expectation with w_{tau+1}, although the indicator and the iterates are dependent. Getting this step wrong changes the magnitude of the privacy term and can even make it appear to beat a known lower bound, so it is load-bearing. This supports the reader's CONDITIONAL verdict: the result is promising and likely repairable, but the manuscript does not yet rigorously establish the headline rate. Hence verdict_should_be is UNCHANGED (still conditional), with agreement partial: the reader's flagged participation assumption is a real scope limit, but the dominant concern is the unproven proof step under that assumption.","tokens_in":32091,"tokens_out":34699,"duration_ms":307071,"concrete_test":"Independently re-derive the upper bound for term (C) in Appendix E.2 without replacing the random last-participation indicator by its marginal probability inside the inner product with w_{tau+1}. Concretely, use the law of total expectation: condition on the participation indicators, then evaluate the Gaussian expectation of <y_{s,i}, w_s−w_{tau+1}> using the exact linear dependence of w on y_{s,i} (e.g., on an unconstrained quadratic objective with known optimum). Check whether the resulting bound matches the proof's final O(S^2 eta T d(1+logT)/(rho^2 m p^2)(pT+1)) or differs by a factor of M/m or a log factor. If it differs, the claimed O(1/sqrt(n)+sqrt(Md)/(epsilon n)) rate in Theorem 5.2 is not established; if it matches, the gap is repairable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—optimal O(1/sqrt(n)+sqrt(Md)/(epsilon n)) excess loss with linear gradient complexity in the untrusted-server partial-participation setting—rests on Theorem 5.2. Its proof bounds the correlated-noise term (C) = sum_{tau=1}^t E<Y_tau, x*−w_{tau+1}> in Appendix E.2. For each machine i, Y_{tau,i} is the last noise generated up to time tau. The proof rewrites (C) as (1/m) sum_i sum_tau sum_{s<=tau} p(1−p)^{tau−s} E<y_{s,i}, x*−w_{tau+1}>, i.e., it replaces the indicator that s is the last participation time by its marginal geometric probability inside an expectation involving w_{tau+1}. But w_{tau+1} depends on exactly those participation indicators: they determine how long y_{s,i} remains in the server's aggregate and therefore how strongly it steers the iterates. Thus E[1_{last=s} <y_s, w_s−w_{tau+1}>] is not equal to p(1−p)^{tau−s} E[<y_s, w_s−w_{tau+1}>]; the left side is larger because the noise has a longer active window when the event occurs. This is not cosmetic: the geometric weighting is what produces the m in the denominator of the final sqrt(Md)/(rho m T) privacy term, and an incorrect treatment could either introduce an extra M/m factor or produce sqrt(d/M)/(rho T), which would contradict the known lower bound. The proof is labeled a sketch, and as written this step is invalid; a rigorous derivation of (C) is required before the optimal-rate claim can be accepted.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies differentially private federated stochastic convex optimization under partial participation. It proposes Algorithm 1, a variant of the μ2-SGD technique in which each participating machine sends a corrected gradient increment plus a 'last noise' cancellation term, and the server uses the aggregate to update a weighted iterate. The stated contributions are: a trusted-server algorithm with rate O(1/√n + √d/(ε n)) and linear gradient complexity; an untrusted-server algorithm with rate O(1/√n + √(Md)/(ε n)), matching the lower bound of Lowy and Razaviyayn (2023); and a noise scheduling rule σ²_{t,i} ∝ N_{t,i} proportional to the machine's participation count. The appendix contains proofs of privacy and convergence, and the experiments report MNIST logistic-regression results comparing the new method with Noisy SGD and with Lowy-Razaviyayn.","tokens_in":32453,"tokens_out":13122,"duration_ms":124916,"significance":"If the central claim were fully proven, this would be a substantial advance: an optimal excess population loss with O(n) gradient computations in the untrusted-server partial-participation setting, improving on the n^{3/2} and n^{9/8} methods of Lowy-Razaviyayn and Gao et al. The noise-cancellation mechanism and the participation-dependent noise schedule are natural and interesting ideas, and the claimed rates match known lower bounds. However, the main convergence theorem (Theorem 5.2) is not established by the proof as written because of an invalid correlation step in the handling of term (C); the appendix also contains an incorrect proof of a standard composition lemma. The paper is therefore not yet publishable in its current form.","major_comments":[{"comment":"The derivation of term (C) replaces the indicator that machine i's last participation before time τ was at time s with its marginal probability p(1−p)^{τ−s} inside the expectation E⟨y_{s,i}, x*−w_{τ+1}⟩. This step is not justified: w_{τ+1} is a function of the participation indicators and of y_{s,i} whenever that indicator is one, so the event and the iterate are dependent. The geometric weighting is what produces the m in the denominator of the final privacy-related term in Theorem 5.2, so this is not a cosmetic issue. A valid proof of Theorem 5.2 needs either a martingale or conditional-expectation argument that keeps the indicator inside the expectation, or a different bound on ∑_{τ=1}^{t} E⟨Y_τ, x*−w_{τ+1}⟩.","section":"Appendix E.2, term (C)"},{"comment":"The induction step in the proof of the composition lemma splits log E[XY] as log E[X] + log E[Y] for the two likelihood-ratio factors. This identity would require X and Y to be independent, which is not established; conditional independence of A_{k+1} given the previous outputs does not make the two factors independent under the joint expectation. The lemma itself is standard, so the fix is easy (cite Mironov or Bun–Steinke), but as printed the proof is incorrect and should be replaced by a correct proof or a citation.","section":"Appendix A.3, proof of Lemma A.3"},{"comment":"The proof uses the inequality 1/p = M/m ≤ T to replace T + 1/p by O(T). This inequality is not among the hypotheses of Theorem 5.2 and can fail when the number of machines exceeds the total number of samples used (for example, M = 10^6, m = 100, T = 100). Without that assumption the final privacy term carries an extra M/(mT) factor and the claimed optimal rate is not obtained. The theorem should either state M ≤ mT explicitly or carry the exact dependence in the bound.","section":"Appendix E.2, final bounding step after Theorem A.7"}],"minor_comments":[{"comment":"The text repeatedly refers to 'Theorem 4.2' when the displayed statement in Section 4.3 is labeled 'Lemma 4.2'; please unify the numbering across the main text and appendix.","section":"Section 5.1 and Appendix E.1"},{"comment":"The uniform i.i.d. participation model is essential for the proof, but the abstract and introduction present the result as applying to partial participation generally. Please state prominently that the optimality claim is for the uniform, independent-per-round participation model and not for adversarial or correlated device availability.","section":"Theorem 5.2 statement"},{"comment":"Algorithm 1 lists a dataset {z_{1,i},…,z_{T,i}} for every machine i, while the introduction says the total number of samples used is n = mT. Please clarify that unselected machines' samples are not used in training and explain the relationship between M, m, T, and the total data size n.","section":"Algorithm 1 input description"},{"comment":"The comparison with 'Other Work' is not on equal footing because that baseline reuses samples while the proposed method makes a single pass over the data; the text acknowledges this but should state it as a limitation of the experimental comparison before drawing conclusions about accuracy.","section":"Section 5.3, experiments"},{"comment":"The claimed rates O(1/√n + √(Md)/(ε n)) are stated without mentioning the logarithmic factor (1+log T) that appears in Theorem 5.2. Please use O-tilde notation or explicitly state that the matching to the lower bound is up to logarithmic factors.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a solid, genuinely useful paper on an open problem in private federated optimization, but the main convergence claim currently rests on a proof step that doesn't go through as written. The noise-cancellation mechanism is the real contribution: each machine adds fresh noise and subtracts the previous noise, so the server's aggregate noise stays bounded without full participation. That idea is new and, I think, correct in spirit. The paper achieves the target rate O(1/sqrt(n) + sqrt(Md)/(epsilon n)) with O(n) gradient computations, matching the lower bound of Lowy-Razaviyayn. The trusted-server case is also handled cleanly.\n\nThe soft spot is in the proof of Theorem 5.2, specifically the bound on term (C) in Appendix E.2. The authors replace the random last-participation time with its marginal geometric probability inside an inner product with w_{tau+1}. That is not justified: w_{tau+1} depends on exactly those participation indicators, so the indicator and the iterate are correlated. The step is what produces the nice m in the denominator of the privacy term, so this is not cosmetic. The proof is explicitly a sketch, and the authors say the bound on the parts of Y_t is harder, but they don't supply the missing argument. A rigorous control of term (C) is needed before the optimal-rate claim is established. I don't see an obvious contradiction, and the result may well be true, but the written proof doesn't nail it.\n\nThere are smaller issues. The proof of the composition lemma A.3 splits an expectation of a product into a product of expectations, which is incorrect; the lemma itself is standard and fixable, but the proof should be corrected. The privacy proof for Theorem 5.1 is also a sketch, though the sensitivity bound looks data-independent and should be repairable.\n\nThe experiments are minimal: no code, no error bars, and only MNIST logistic regression. They are supportive but not convincing on their own.\n\nWho should read this: anyone working on DP federated learning with partial participation. If the proof gap is closed, this will become a standard baseline. I'd send it to review, but I'd make a rigorous treatment of term (C) a hard requirement for acceptance. It's an honest, well-written paper that addresses a real gap, but the central theorem needs work.","headline":"A genuine new mechanism for partial-participation DP-FL with an optimal-looking rate, but the main proof has a gap in the noise-correlation term that needs closing before the claim is solid.","tokens_in":32999,"tokens_out":4704,"would_cite":true,"duration_ms":39222,"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":"The paper claims a noise-cancellation mechanism achieves optimal excess population loss for differentially private federated convex optimization under partial participation, matching known lower bounds while using only a linear number of…","keywords":["differential privacy","federated learning","partial participation","stochastic convex optimization","noise cancellation","untrusted server","linear-time optimization","population loss"],"falsifier":"Run Algorithm 1 on a synthetic convex problem with M=2 machines, m=1 participant per round, identical data, and compare independent fair-coin participation against deterministic alternation (machine 1 on odd rounds, machine 2 on even rounds). The proof's bound on the correlated-noise term assumes a Bernoulli participation process, so the alternating schedule invalidates that step; if the measured excess loss under alternation exceeds the uniform-schedule loss by an amount that grows with the number of rounds, the uniformity assumption is essential to the claimed rate.","tokens_in":31878,"feed_emoji":"🔒","tokens_out":15048,"duration_ms":139317,"temperature":0.7,"pith_summary":"This paper claims that private federated learning can have it both ways: even when only a random subset of machines participates in each round, and even when the server cannot be trusted with raw gradients, a differentially private algorithm can reach the optimal population-error rate—the best rate allowed by known lower bounds—for both homogeneous and heterogeneous data distributions, while using only a linear number of gradient computations. The obstacle is that a machine sitting out a round still holds a noise value the server's aggregate depends on, making the injected noise correlated across rounds. The paper's noise-cancellation scheme addresses this: each participating machine adds fresh noise and subtracts its previous noise, so the server's cumulative view is one noise per machine normalized by the participating subset size. The stated rates are O(1/√n + √d/(ε n)) for a trusted server and O(1/√n + √(M d)/(ε n)) for an untrusted server, matching established lower bounds while using two gradient evaluations per sample.","feed_headline":"Noise cancellation makes private federated learning optimal and fast","feed_subtitle":"The same optimal error as prior work, but with linear-time computation instead of super-linear.","key_machinery":"The load-bearing object is the noise-cancellation mechanism combined with the µ2-SGD double-momentum update. Each machine i that participates at round t broadcasts s_{t,i} = α_t ∇f(x_t; z_{t,i}) − α_{t−1}∇f(x_{t−1}; z_{t,i}) plus the difference Y_{t,i} − Y_{t−1,i} of fresh and previous Gaussian noise; machines that do not participate keep their previous noise Y_{t,i} = Y_{t−1,i}. Telescoping makes the server's noisy cumulative estimate satisfy q̃_t = q_t + (1/m) Σ_{i=1}^M Y_{t,i}, so the effective injected noise is a sum of M independent noises normalized by m, rather than growing with the number of rounds participated. The variance σ²_{t,i} of each fresh noise is scaled by N_{t,i}, the number of rounds machine i has participated so far; the harmonic sum Σ 1/N_{t,i} ≤ 1+log T makes the total privacy budget (ρ²/2)-zCDP independent of the participation pattern, while the convergence proof bounds the correlated-noise term using a geometric-weight argument with participation probability p = m/M.","core_discovery":"Under convex, G-Lipschitz, and L-smooth losses with i.i.d. samples per machine, Algorithm 1 is claimed to be (ρ²/2)-zCDP (a concentrated differential privacy guarantee) for each machine and, after T rounds with m participants each, to have expected excess population loss whose order is O(1/√n + √(M d)/(ε n)) for the untrusted-server case and O(1/√n + √d/(ε n)) for the trusted-server case, where n=mT is the total number of samples used and ε is the converted DP level. These match the known lower bounds for the two settings. Each participating machine uses one fresh sample per round and performs two gradient evaluations on it, so the total number of gradient computations is linear in n, the same order as ordinary non-private SGD. The central assertion is that privacy, partial participation, optimal statistical error, and linear-time computation are simultaneously attainable.","pith_inferences":["The noise-cancellation structure is presented for convex SCO; a natural extension would be to apply the same add-fresh-subtract-last noise update to non-convex losses or adaptive-gradient methods, where the sensitivity bound on the correction term would need to be rederived.","The uniform-random-participation assumption could likely be relaxed to any schedule with known participation probabilities, but the proof's geometric-weight bound degrades with the schedule's autocorrelation; device-availability logs could be used to measure how far a real deployment is from the Bernoulli ideal.","The method's single-pass property suggests it fits settings where on-device data cannot be stored or revisited; a practical stress test would run the algorithm with participation driven by real device-availability traces and compare against the bound.","If the lower bound is tight, any further improvement in this model would have to change the threat model or the communication model—for example secure aggregation or trusted hardware—rather than the optimization algorithm."],"forward_implications":["Partial participation no longer forces a multiplicative √(M/m) slowdown: the untrusted-server excess loss matches the known lower bound for the setting.","A deployment with M machines and m participants per round can train with the same order of gradient computations as standard SGD while keeping per-machine differential privacy against an untrusted server.","The trusted-server variant reaches the plain DP-SCO lower bound with the same linear-time budget, so the extra √M privacy penalty is tied to hiding data from the server, not to partial participation.","Because each sample is used once, the algorithm is single-pass; it avoids the mega-batch resampling that made prior optimal methods require O(n^{3/2}) or O(n^{9/8}) work.","Heterogeneous data distributions are absorbed through the bounded-heterogeneity parameters, so the optimal rate does not require identical machines."],"supporting_citations":[{"why":"Supplies the µ2-SGD double-momentum update whose variance shrinks over time; Algorithm 1's update rule is built on it.","marker":"Levy, 2023"},{"why":"Provides the full-participation private federated extension that this paper adapts to partial participation.","marker":"Reshef & Levy, 2024"},{"why":"Establishes the untrusted-server lower bound the paper matches and gives the super-linear mega-batch baseline to outperform.","marker":"Lowy & Razaviyayn, 2023"},{"why":"Supplies the trusted-server DP-SCO lower bound matched by the trusted-server variant.","marker":"Bassily et al., 2014"},{"why":"Shows optimal DP-SCO rates are achievable with large batches but at super-linear cost, motivating the linear-time goal.","marker":"Bassily et al., 2019"},{"why":"Demonstrates that optimal DP-SCO rates are possible in linear time outside federated partial participation, the target extended here.","marker":"Feldman et al., 2020"},{"why":"Provides the anytime online-to-batch inequality used to decompose regret into gradient, noise, and error terms.","marker":"Cutkosky, 2019"},{"why":"Supplies Rényi differential privacy composition and conversion to (ε,δ)-DP used in the privacy accounting.","marker":"Mironov, 2017"}],"fun_headline_variants":["Private federated learning hits optimal error at linear speed","Noise cancellation unlocks fast private federated learning","Optimal privacy and speed in federated learning via noise tricks","Federated learning: privacy, optimality, and linear time all at once","Linear-time DP federated learning with optimal error"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the subset of machines participating in each round is chosen uniformly at random from all subsets of size m, independently across rounds; if device availability is data-dependent, adversarial, or correlated over time, the proof's calculation of how the accumulated noise grows stops working and the claimed optimal rate is not established.","fun_headline_variants_meta":{"raw":{"variants":["Private federated learning hits optimal error at linear speed","Noise cancellation unlocks fast private federated learning","Optimal privacy and speed in federated learning via noise tricks","Federated learning: privacy, optimality, and linear time all at once","Linear-time DP federated learning with optimal error"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00064,"raw_usage":{"total_tokens":2905,"prompt_tokens":859,"completion_tokens":2046,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":475,"completion_tokens_details":{"reasoning_tokens":1964}},"tokens_in":475,"tokens_out":2046,"duration_ms":12958,"temperature":1.0,"reasoning_tokens":1964,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:23:38.521035+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a synthetic convex problem with M=2 machines, m=1 participant per round, identical data, and compare independent fair-coin participation against deterministic alternation (machine 1 on odd rounds, machine 2 on even rounds). The proof's bound on the correlated-noise term assumes a Bernoulli participation process, so the alternating schedule invalidates that step; if the measured excess loss under alternation exceeds the uniform-schedule loss by an amount that grows with the number of rounds, the uniformity assumption is essential to the claimed rate.","supporting_citations":[{"cited_title":"$\\mu^2$-SGD: Stable Stochastic Optimization via a Double Momentum Mechanism","cited_arxiv_id":"2304.04172","evidence_quote":"Supplies the µ2-SGD double-momentum update whose variance shrinks over time; Algorithm 1's update rule is built on it."},{"cited_title":"and Levy, K","cited_arxiv_id":null,"evidence_quote":"Provides the full-participation private federated extension that this paper adapts to partial participation."},{"cited_title":"D., and Thakurta, A","cited_arxiv_id":null,"evidence_quote":"Supplies the trusted-server DP-SCO lower bound matched by the trusted-server variant."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows optimal DP-SCO rates are achievable with large batches but at super-linear cost, motivating the linear-time goal."},{"cited_title":"Private stochastic convex optimization: optimal rates in linear time","cited_arxiv_id":null,"evidence_quote":"Demonstrates that optimal DP-SCO rates are possible in linear time outside federated partial participation, the target extended here."},{"cited_title":"R \\' e nyi differential privacy","cited_arxiv_id":null,"evidence_quote":"Supplies Rényi differential privacy composition and conversion to (ε,δ)-DP used in the privacy accounting."}],"review_version":1}