- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies asymptotic anytime-valid inference for Polyak–Ruppert averages of synchronized Local-SGD iterates under full participation and deterministic intermittent communication. Its main result is an almost-sure Gaussian approximation on the variance clock v_T, retaining the exact schedule factor nu_T. Gaussian boundaries and a strongly consistent fresh-sample sandwich estimator yield asymptotic confidence sequences with fixed positive inflation. Validation uses three regression models, schedule and heterogeneity studies, and a BRFSS logistic-regression application.
Critical strengths
-
Theoretical contribution: Theorem 1 and Lemmas 3–5 explicitly control accumulated local drift and noise-freezing errors. This addresses the pathwise control needed for repeated monitoring beyond a fixed-horizon CLT.
-
Correct schedule accounting: Keeping nu_T = t_T v_T / T^2 avoids replacing a finite-schedule quantity by its limit. Table B.5 demonstrates its practical importance: using the reference normalization raises Log-schedule failure from 2.6% to 57.8%.
-
Substantial sensitivity analysis: The experiments include 500-replication main studies, oracle versus plug-in covariance, monitoring starts, heterogeneity, participation, and covariance cost. The BRFSS application reports 358,927 cleaned records and 50 clients, providing a substantial real-data illustration.
Critical weaknesses
-
Coverage guarantee versus evaluated procedure: Corollary 2 requires a fixed delta > 0, but all reported regions use delta = 0 (pp. 7–8). Definition 1 also supplies no usable finite monitoring start. Table B.2 reports 11.0% failure [7.9%, 15.0%] at nominal 5% for K = 50, h = 0 under the fixed total budget. This does not contradict the asymptotic theorem, but shows that the experiments do not establish reliable calibration for the procedure users would run.
-
Covariance estimator mismatch: Proposition 1 proves consistency with independent fresh samples, whereas Section 3.1 and Appendix B.6 reuse the first training observation of each round. The reported agreement with oracle covariance does not establish strong consistency of this implemented estimator, which is required by Corollary 2. A proof for the reuse construction or experiments with the proved construction would close this gap.
-
Restricted participation guarantee: The theory requires full participation and deterministic schedules. Table B.3 shows that applying the full-participation calibration at q = 0.5 produces 51.2% pathwise failure; the q-adjusted alternative has only empirical support. Although acknowledged, this restriction materially limits applicability to federated systems with client availability variation.
-
Limited evidence for scalable inference: Most simulations use d = 5, and the dimension study stops at d = 30. Table B.4 already reports a covariance-estimation cost ratio of 8.19 times training-only cost at d = 30. The suggested Hessian-vector and low-dimensional-functional alternatives are not evaluated, and communication cost is not quantified. Thus efficient deployment beyond small regression models remains unsubstantiated.
-
Real-data validation does not assess coverage: Appendix B.2 compares intervals with a centralized estimator fitted on the same data, rather than a known population target. It also does not clearly specify whether local observations are sampled with replacement, without replacement, or reused, which matters for the independent-stream assumptions. The dataset is sizeable, but containing the centralized benchmark is not evidence of nominal population coverage.
Questions for authors
Clarifications that could change my assessment:
-
Does the sample-reuse estimator in Section 3.1 satisfy the almost-sure consistency condition of Corollary 2? Please provide the corresponding argument or results for the fresh-sample construction.
-
How do fixed positive inflation values affect coverage and width in the undercoverage settings of Table B.2? Can you give a defensible rule for choosing the monitoring start?
-
In BRFSS, what is the precise sampling/reuse protocol and inferential target: the empirical-distribution optimizer or a population parameter? How is this protocol connected to the stated assumptions?
6 comments
In the -round setting, the noncoverages occur in the early monitored rounds, where the initialization bias of is still large relative to the radius: the bias decays as , whereas the radius decays as (see also our response to Reviewer C5pb, W1). We also evaluate averaging after a warm-up to reduce the effect of initialization. The variance clock and plug-in covariance estimator use the same rounds as the average. We provide an asymptotic guarantee when the number of warm-up rounds remains fixed as . The 5% warm-up and 10% monitoring start are practical choices examined in Table R3.
At , failure after warm-up averaging is at most 3.8% in the main simulations and 4.6% in the settings of Table B.2; with the oracle covariance the maxima are 3.6% and 4.2%. Relative to the full average, the terminal half-width changes by between under Log and under in the main simulations, where LIL-UB failure is at most 0.6% for every reported .
Table R3. Representative results for averaging after the warm-up (plug-in covariance, GM boundary, , 500 replications). For the main simulations, , , and . The rows are Linear settings and use for and for , with the geometric mean of at and at . The average, variance clock and plug-in covariance all start after the warm-up rounds. The columns headed by report failure (%), which denotes at least one noncoverage after the 10% monitoring start. Terminal half-widths are in units of and are multiplied by exactly at .
| Model/schedule or | Half-width, | |||
|---|---|---|---|---|
| Linear/ | 3.8 | 1.6 | 0.8 | 15.639 |
| Linear/ | 0.6 | 0.2 | 0.0 | 7.004 |
| Linear/Log | 0.0 | 0.0 | 0.0 | 4.956 |
| Logistic/ | 3.2 | 1.0 | 0.4 | 15.500 |
| Poisson/ | 3.2 | 1.4 | 0.8 | 5.713 |
| 4.2 | 2.2 | 1.0 | 4.587 | |
| 2.4 | 1.4 | 1.0 | 6.803 | |
| 2.2 | 0.6 | 0.4 | 2.051 | |
| 3.4 | 2.0 | 0.4 | 6.801 | |
| 4.6 | 2.0 | 1.0 | 6.487 |
Q2. Table R2 above reports positive inflation in the undercoverage settings of Table B.2: for , increasing from 0 to 0.05 and 0.10 reduces oracle failure from 9.6% to 6.4% and 4.0%, and plug-in failure from 8.0% to 5.2% and 2.4%, while multiplying each half-width by exactly . We recommend fixing by the acceptable extra width before training and setting the monitoring start to the application's first inspection or release round. When that round is unspecified, we use , with the planned number of rounds, as described in W1.
W3. Our theoretical guarantee covers full participation with deterministic communication schedules (see the abstract and Section 4). Extending it to partial participation requires accounting for client-selection variance and new strong-approximation bounds for local drift and noise freezing under sampling. Appendices A.6 and B.5 examine an empirical adjustment in this setting.
With a fraction of clients participating, fewer independent client contributions are averaged, increasing the data-noise covariance from to in the uniform-sampling setting of Appendix B.5. Client heterogeneity introduces an additional source of variation: the client population gradients cancel at the global optimum under full participation, while a randomly selected subset has a fluctuating aggregate gradient. This produces the selection component , giving the leading terminal covariance . The omitted data-noise inflation and selection variation explain the 51.2% pathwise failure of full-participation calibration at in Table B.3. At , the participation-adjusted GM calibration using gives 4.6% failure; the adjusted failure rates at and are 1.8% and 2.8%, respectively. These experiments provide empirical evidence for participation-aware calibration in the settings examined. Establishing theory under varying client availability and relaxing deterministic communication remain directions for future work.
We will clarify this empirical scope in Appendix B.5. We refer to the partial-participation covariance , computed from the known and , as the PP oracle. The -adjusted GM calibration uses only : accumulates on the clock and on the clock (Appendix A.6), so their combination generally has a time-varying matrix on the scalar GM clock. We use the PP oracle at the terminal round.
W4. We have run and and will add these results to the appendix. Table R4 reports the Logistic model under , and Table R5 shows representative Linear results.
Table R4. Error and volume cells list oracle/plug-in values. Time-uniform type-I error (%) and average confidence-set volume in the Logistic setting (, , , 500 replications). Error is measured after the 10% monitoring start, with nominal level 5%; the volume root at is in units of . The average starts after a warm-up of 2,500 rounds, and .
| /boundary | Error | Avg CS Volume$^{1/d}$ |
|---|---|---|
| 50/Fixed | 67.8/69.2 | 6.94/6.94 |
| 50/LIL-UB | 0.0/0.0 | 16.24/16.24 |
| 50/GM | 0.0/0.0 | 8.14/8.15 |
| 100/Fixed | 85.4/87.2 | 6.79/6.80 |
| 100/LIL-UB | 0.2/0.0 | 16.64/16.65 |
| 100/GM | 0.0/0.0 | 7.76/7.77 |
LIL-UB and GM stay below the nominal level, with GM giving smaller regions, whereas the fixed-time boundary fails far more often. Oracle and plug-in covariance give similar results, and the Linear model behaves similarly.
Table R5. Error and volume cells list oracle/plug-in values. Representative Linear results at , with the same design as Table R4. Time-uniform type-I error is in percent; the volume root at is in units of .
| Schedule/boundary | Error | Avg CS Volume$^{1/d}$ |
|---|---|---|
| /Fixed | 44.6/37.4 | 63.89/64.52 |
| /LIL-UB | 0.0/0.0 | 157.80/159.35 |
| /GM | 0.6/0.4 | 73.34/74.06 |
| /Fixed | 43.4/47.6 | 28.50/28.54 |
| /LIL-UB | 0.0/0.0 | 69.85/69.94 |
| /GM | 0.0/0.0 | 32.57/32.61 |
| Log/Fixed | 68.4/76.2 | 16.56/16.56 |
| Log/LIL-UB | 0.0/0.0 | 40.33/40.34 |
| Log/GM | 0.0/0.0 | 22.36/22.37 |
The margin below the nominal level comes from the boundaries: under with , simulating the Gaussian limit of Theorem 1 on the same clock and window gives GM failure of 0.46% at and 0.41% at , against 0.8% and 0.4% with the plug-in. For GM, exceeds the terminal clock under and Log, so the boundary stays above its minimum, and the inflation required by Corollary 2 adds to the margin; for LIL-UB, the margin comes from the finite-LIL constants. The norm of a Gaussian vector concentrates as grows, so a small increase in the radius lowers failure sharply, and at the GM radius, inflation included, is only 14% above the fixed-time radius.
For the reported cost ratio, the cost drops substantially if the covariance is refactorized periodically. Corollary 2 requires an -measurable, strongly consistent estimator; we will add the following remark to the paper. Let be the largest point not exceeding of a deterministic increasing grid. Then is -measurable and converges to almost surely, so Corollary 2 applies with the positive-definite fallback of , with the statistic evaluated at every round. Table R6 reports new timings for the Logistic model under ; with a refresh every 100 rounds the cost ratio is at .
Table R6. Training-plus-covariance/training-only time, both including data generation (same definition as Table B.4); columns give the refactorization interval. Logistic , 10 trajectories, 2,000 rounds, median of 3 paired runs, on a different host from Table B.4.
| Every round | Every 100 rounds | |
|---|---|---|
| 30 | 4.61 | 1.29 |
| 50 | 8.96 | 1.36 |
| 100 | 23.47 | 1.69 |
We now evaluate Hessian-vector products and low-dimensional functionals. For a contrast , the one-dimensional interval needs only the scalar variance with , and can be solved online from Hessian-vector products, giving a matrix-free implementation. The server broadcasts , and each client returns its Hessian-vector product and its score projected on the running average . The server updates , averages from 1% of the rounds, and estimates the variance by the average of from 2% of the rounds. Each round, every client returns one Hessian-vector product and one score projection. Table R7 reports the type-I error of the resulting interval for a zero coefficient (), a nonzero coefficient () and the direction of .
Thank you for your time and valuable comments. We respond to each point below.
W2 / Q1. We will revise Assumption 5, Proposition 1 and its proof to establish strong consistency for the completed-round sample-reuse construction of Section 3.1; the revised statement and proof are given in our response to Reviewer EeQq (W1). Under Assumptions 1–5, the positive-definite fallback is measurable with respect to completed-round information, is positive definite at every round and converges almost surely to the target covariance. It therefore supplies the covariance-estimation condition of Corollary 2 under the other stated assumptions of that corollary.
W1. Corollary 2 is stated for a fixed δ>0, whereas the regions reported in Section 3 use δ=0 to evaluate the first-order construction. On every sample path, a larger δ gives a larger region and multiplies every half-width by exactly 1+δ, so failure (the time-uniform type-I error) is nonincreasing in δ. We have added experiments with positive inflation δ∈0.01,0.02,0.05,0.10 to quantify this trade-off. Table R1 shows representative results from the main simulations with the plug-in covariance. Failure stays below the nominal level for every δ, and its maximum across the main simulations falls from 4.8% at δ=0 to 1.0% at δ=0.10.
Table R1. Time-uniform type-I error (%) and width under positive inflation in the main simulations (plug-in covariance, K=10, T=50,000, d=5, 500 replications, GM boundary, n0=20,000). Each cell lists failure (%) / terminal projection half-width (units of 10−3).
We also evaluated positive inflation in the settings of Table B.2 on 500 new replications. Table R2 includes the settings with failure above 5% and the corresponding longer run. Failure decreases with δ. At δ=0.05, failure is below the nominal level in every evaluated setting except (K,h,T)=(50,0,4,000), where the excess comes from the early monitored rounds and decreases with a later start (see also our response to Reviewer EeQq, W3).
Table R2. Each numeric cell lists oracle/plug-in values. Representative positive-inflation results in the Linear C5 setting (d=5, 500 replications, GM boundary, zero initialization). Failure (%) denotes at least one noncoverage after the 10% monitoring start. Terminal half-widths are in units of 10−3 and are multiplied by exactly 1+δ at δ>0.
Corollary 2 holds for any fixed δ>0; in the proof, δ absorbs coupling, Brownian interpolation and covariance-estimation errors that vanish almost surely. In finite samples, δ multiplies every half-width by exactly 1+δ, so a larger δ is more conservative. We therefore recommend a small δ, chosen by the extra width that is acceptable and fixed before training together with the monitoring start. We have clarified this choice.
Definition 1 is a limit as T0→∞. In practice, T0 is set by the application: it is the first round at which the global model is inspected or released (Waudby-Smith et al., 2024; Bibaut et al., 2022). With the estimator and boundary fixed, a later T0 shortens the monitoring window and preserves the width at every round, so failure is nonincreasing. When no inspection round is specified, we use T0=⌈0.10H⌉+1, where H is the planned number of rounds. We describe this practical choice in Section 2.3.
We also report failure in the same main simulations when monitoring starts at 5%, 10% or 20% of the rounds, at δ=0. Failure is at most 4.8% for every start, and moving the start from 5% to 20% of the rounds changes it by at most 0.6 percentage points. At δ=0.05, the maxima are 2.8%, 2.8% and 2.6%, respectively. This is consistent with an initialization bias that is small relative to the radius once monitoring starts, so that the earliest monitored rounds contribute few noncoverages.