{"id":"d98b39f2-f7d4-45e9-8c32-acee57042f5a","arxiv_id":"2505.05099","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"An age-of-information Markov scheduling policy that balances client selection intervals is claimed to speed up federated learning convergence by 7.5-20% over random selection.","lead":"This paper proposes a scheduling rule for federated learning that makes clients take turns more evenly, based on how long it has been since each client last updated the model. It reports faster convergence (7.5-20%) than standard random client selection on image benchmarks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reported convergence gains may be a weighting artifact: random selection with uniform weights is never evaluated, so the AoI scheduling policy is not isolated.","rationale":"The paper's mechanism is plausible: minimize Var[X] to balance participation and reduce Sigma. But the central claim is empirical, and the experiment design does not isolate the selection policy. The authors compare a data-size-weighted random baseline against uniform-weight Markov policies. Their own theory predicts that uniform-weight random selection should perform nearly identically to Markov optimal, because Sigma for uniform-weight random selection (1/m - 1/n, approximately 0.0567) matches the reported Markov Sigma of 0.055. This makes the missing baseline fatal to the attribution. The proof mismatch (fixed |S| in Theorem 2 versus random |S| in the evaluated Markov policy) is a separate but reinforcing issue; it means the theoretical support also does not currently cover the method. I agree with the reader's weakest_assumption and with the REJECT verdict: the paper needs a clean baseline and a proof for random |S| before the convergence claims can be accepted. The concrete test above would settle the empirical attribution.","tokens_in":22121,"tokens_out":4800,"duration_ms":47967,"concrete_test":"Rerun the Section V experiments (MNIST, CIFAR-10, CIFAR-100, IID and non-IID partitions, 100 clients, 15 per round, same optimizer and accuracy targets) with an additional baseline: random selection without replacement of exactly 15 clients, aggregated with uniform weights omega_i = 1/m = 1/15. If this baseline reaches the target accuracy in approximately the same number of rounds as Markov Optimal (e.g., within 5%), then the reported 7.5-20% improvements are a weighting artifact and the central AoI claim is unsupported. If it is slower by the original margins, the AoI scheduling explanation survives. Also report standard errors across at least 5 random seeds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim (abstract; Section V, Figures 5-7) is that the optimal Markov AoI policy converges 7.5-20% faster than the FedAvg/random-selection baseline. The comparison, however, changes two variables simultaneously. Policy 1 aggregates with data-size-proportional weights (Section III-B.1: omega_i = d_i / sum_{j in S} d_j), while Policies 3 and 4 aggregate uniformly (Section III-B.3 and Theorem 5: omega_i = 1/|S|). Theorem 2 and Remark 1 state that convergence speed is controlled by Sigma = sum_i Var[omega_i]. For n=100, m=15, a random selection rule with uniform weights has Sigma = 1/m - 1/n = 1/15 - 1/100 = 0.0567, essentially identical to the reported Markov optimal Sigma = 0.055 (Figure 2). Hence the Sigma reduction attributed to AoI scheduling is already achieved by switching the aggregation weights to uniform under random selection. Without a random-selection/uniform-weight baseline, the reported speedup cannot be attributed to the age-of-information Markov policy; it may be entirely a weighting artifact. A reinforcing gap: Theorem 2 assumes |S| = m (Eq. 11), whereas the Markov policy has random |S| with a forced-selection modification (Theorem 5), so the theory does not cover the evaluated algorithm.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an Age-of-Information-based client selection policy for federated learning. Clients are modeled by a Markov chain on their age, and age-dependent selection probabilities are chosen to minimize the variance of the inter-selection interval X. The authors prove a convergence bound (Theorem 2) showing that FL convergence depends on Sigma = sum_i Var[omega_i] and on selection skew rho, derive Sigma for random-with-data-size weighting, probabilistic data-size sampling, and Markov age-based policies (Theorems 3-5), and report image-classification experiments (MNIST, CIFAR-10, CIFAR-100) claiming 7.5-20% faster convergence for the optimal Markov policy over FedAvg/random selection.","tokens_in":22359,"tokens_out":10200,"duration_ms":98729,"significance":"If the claims are established, the paper offers a low-overhead decentralized selection rule and a clean theoretical link between aggregation-weight variance and FL convergence. The explicit variance formulas in Theorems 3-5, the convergence bound in Theorem 2, and the Markov construction are genuine strengths, and the optimality theorem is not circular because it is imported from the authors' prior work [27] rather than fitted to the simulation data. However, as submitted, the main empirical claim is not isolated: the baseline and the proposed policies differ in aggregation weights as well as in the selection rule, and the convergence theorem assumes a fixed number of selected clients while the evaluated Markov policy has a random batch size. These issues must be resolved before the contribution can be assessed.","major_comments":[{"comment":"The comparison that supports the abstract's 7.5-20% speedup changes two variables at once. Policy 1 (Section III-B.1, Eq. (28)) weights each selected client by d_i / sum_{j in S} d_j, while Policies 3 and 4 (Section III-B.3, Theorem 5, Eq. (32)) weight uniformly as 1/|S|. Since Theorem 2 and Remark 1 identify Sigma = sum_i Var[omega_i] as the driver of convergence, the lower Sigma reported for the Markov policies (0.055 and 0.061 vs. 0.204 for Policy 1 in Figure 2) may be entirely due to the uniform weighting, not to age-based scheduling. In fact, by Theorem 3 and Remark 4, a random-selection baseline with uniform weights has Sigma = 1/m - 1/n = 1/15 - 1/100 = 0.0567 for n=100, m=15, essentially identical to the reported optimal Markov value of 0.055. A uniform-weight random-selection baseline must be run, and the convergence comparison repeated, before the AoI scheduling effect can be attributed to the selection policy.","section":"Section V (Figs. 5-7); Section III-B.1 and III-B.3; Theorem 2 and Remark 1"},{"comment":"The convergence proof assumes that the number of selected clients is a constant m (Eq. (11)), but the evaluated Markov policy has random |S|, modeled in Theorem 5 as Binomial(n, p_avg). The bounds in Lemma 2 and Lemma 3 use the fixed quantity m (e.g., the factor 1/m in Eq. (38) and the m(Sigma+1) in Lemma 3), so Theorem 2 does not apply to Policy 3 as evaluated. The authors should either extend the convergence analysis to random |S| or evaluate a fixed-size version of the Markov policy whose m is constant.","section":"Section IV, Eq. (11); Theorem 5; Lemmas 2-3"}],"minor_comments":[{"comment":"The notation is inconsistent: the Figure 2 caption uses k=15 for the number of selected clients and 'maximum client age of m=10', while the body uses m for the number of selected clients and m' for the maximum age; please align the notation throughout.","section":"Section V, Figure 2 caption"},{"comment":"Theorem 1 is stated without proof and is the basis for the optimal Markov policy; state explicitly that it is proved in [27] and, if space permits, include a self-contained proof in the appendix.","section":"Section IV, Theorem 1"},{"comment":"Reconcile the exponent of K in the variance term: Eqs. (72)-(73) give eta_t^2 m K^2 sigma^2, whereas the theorem statement in Eq. (27) has m K sigma^2; one of these is a typo.","section":"Section IV, Theorem 2 proof"},{"comment":"The table reports rho as an 'average' over rounds, but Definition 1 uses minima and maxima over states, client subsets, and model parameters; clarify how the reported values are computed so the table can be reproduced.","section":"Section IV, Definition 1 and Table II"},{"comment":"The target accuracy thresholds differ across datasets (97% on MNIST, 75% on CIFAR-10, 30% on CIFAR-100), so the percentage speedups are not comparable across datasets unless this is explicitly stated.","section":"Section V, Figures 5-7"},{"comment":"The abstract's phrase 'FedAvg selection approach' is imprecise: FedAvg is an aggregation algorithm, and the baseline is random client selection with data-size-proportional weights (Policy 1).","section":"Abstract and Section III-B.1"}],"recommendation":"major_revision","confidential_remarks":"The paper overlaps substantially with the authors' GLOBECOM 2024 paper [27], from which Theorem 1 is reproduced; the editor may wish to ask the authors to state the incremental contribution clearly. The main experimental confound is fixable by adding a uniform-weight random-selection baseline, but if that baseline matches the Markov policies' convergence, the central claim that AoI scheduling accelerates convergence should be withdrawn."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: the stress-test note lands. The paper's headline claim is that the optimal Markov AoI policy converges 7.5–20% faster than FedAvg/random selection, but the comparison changes two variables at once. Policy 1 uses data-size-weighted aggregation; Policies 3 and 4 use uniform weights. For n=100, m=15, random selection with uniform weights has Sigma = 1/15 - 1/100 = 0.0567, essentially identical to the reported Markov optimal Sigma = 0.055. So the reported speedup could be entirely from switching aggregation weights, not from AoI-based scheduling. The missing uniform-weight random baseline is load-bearing, not a small omission.\n\nWhat is genuinely useful: the paper formalizes load balancing through the variance of the inter-selection interval, adapts a Markov age-based selection model to FL, computes Sigma for several policies, and gives a convergence bound in the spirit of Fraboni et al. and Cho et al. The optimal Markov transition probabilities are borrowed from the authors' prior GLOBECOM paper, but they say so, and the derivation is parameter-free. The empirical interval histograms do show that the Markov policy produces more regular participation, which is a real load-balancing benefit independent of convergence.\n\nSoft spots beyond the main confound: Theorem 2 and Lemma 2 assume a fixed |S| = m, but the Markov policy has random |S|; the forced-selection modification is not integrated into the proof. The claim of being the first to apply AoI to FL client selection is contradicted by their own reference [22], which is exactly age-based scheduling for FL. There is also a notational/indexing slip in Lemma 2 and no code or error bars, though those are minor.\n\nMy take: the core idea deserves engagement, but as submitted the central contribution is unverified. The fix is straightforward: rerun random selection with uniform weights, and either extend the proof to random |S| or restrict the claim to a fixed-m variant. If the speedup disappears under the uniform random baseline, the paper becomes a load-balancing study with a much weaker convergence claim.\n\nI would send this to peer review rather than desk reject: the problem is real, the formalization is coherent, and a serious referee can require the correct baseline and a proof that covers the evaluated policy. I would not cite the convergence results until those are supplied.","headline":"Plausible AoI scheduling idea, but the reported convergence gains are likely a weighting artifact and the theory does not cover the evaluated random-size policy.","tokens_in":22919,"tokens_out":3642,"would_cite":false,"duration_ms":38519,"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":"Age-of-information client selection makes federated learning converge faster and fairer.","keywords":["federated learning","client selection","age of information","load balancing","Markov scheduling","convergence analysis","non-IID data","FedAvg"],"falsifier":"Run the identical experimental setup (100 clients, 15 per round, same datasets and optimizer) but replace the random baseline's data-size weighting with the same uniform aggregation weights used by the Markov policies. If random selection with uniform weights reaches the target accuracy as fast as the optimal Markov policy, then the central claim that AoI scheduling improves convergence is not supported. A second check: compare the optimal Markov policy against deterministic round-robin; if round-robin matches it, the benefit comes from low selection-interval variance, not from the Markov structure itself.","tokens_in":21870,"feed_emoji":"⏱️","tokens_out":5332,"duration_ms":50364,"temperature":0.7,"pith_summary":"The paper claims that in federated learning, how evenly the server spaces out each client's turns matters as much as which clients get picked, and that age-of-information (AoI) scheduling can enforce even spacing with almost no central oversight. Instead of selecting clients uniformly at random each round, each client runs a small Markov chain on its own age (rounds since last update) and becomes more likely to be selected the older its update is; the optimal transition probabilities make the gaps between a client's selections nearly constant. The authors prove a convergence bound in which federated averaging's error depends on the variance of the aggregation weights, and they show that the AoI policy drives that variance down. In simulations on MNIST, CIFAR-10, and CIFAR-100, the optimal Markov policy reaches target accuracy in fewer rounds than random FedAvg selection, with reported gains of 7.5% and up to 20% in IID and non-IID settings. The reason a reader should care is that communication rounds are the bottleneck in federated learning, so a parameter-free rule that spreads participation evenly could make training faster and fairer without changing the learning algorithm.","feed_headline":"Age-based scheduling cuts federated learning rounds by up to 20%","feed_subtitle":"A decentralized Markov rule spaces out each client's turns, reaching target accuracy in fewer rounds than random FedAvg.","key_machinery":"The engine of the method is a finite Markov chain whose states are a client's age a ∈ {0,1,...,m′}: in each round a client at age a is selected with probability p_a, resetting to state 0, or with probability 1−p_a advances to age a+1 (staying at m′ if already maximal). The load metric X is the peak age, and Theorem 1 gives the p_a that minimize Var[X] for a given selection rate m/n: a threshold schedule that keeps p_a = 0 until near the target interval and then selects almost surely, with a single fractional step when the target interval is not an integer. This Markov policy is what carries the argument: it turns the vague goal of 'balanced participation' into an explicit variance-minimization problem, it can be run by clients independently without the server tracking anyone, and its effect on learning is then visible in the convergence bound through Σ, the summed variance of the aggregation weights, and the selection skew ρ.","core_discovery":"On its own terms, the central discovery is that client-selection load imbalance is a first-order cause of slow federated learning convergence, and that it can be removed by an age-based Markov policy. The paper defines the load metric X as the number of rounds between successive selections of a client, observes that X is the peak age from age-of-information theory, and formulates the goal as minimizing Var[X] subject to each client having the same per-round selection probability m/n. The optimal solution, carried over from the authors' earlier work, is a threshold policy: do not select a client until it reaches a fixed age, then select it with probability one at that age or with one fractional probability near the threshold. The theoretical contribution is Theorem 2, a convergence bound for federated averaging under biased selection in which the error contains a term proportional to Σ = sum_i Var[ω_i], the variance of the aggregation weights, and inversely related to the selection skew ρ. Because the Markov policy makes selection intervals nearly deterministic, it makes each client's long-run weight stable and markedly reduces Σ relative to random selection; the simulations show this translates into reaching the same accuracy in up to 20% fewer rounds, with steadier progress. The paper also computes closed-form Σ for random, data-size-proportional, and Markov policies (Theorems 3–5), so the variance reduction is quantified rather than asserted.","pith_inferences":["My reading: the headline comparison is not fully controlled. The random baseline uses data-size weighting during aggregation while the Markov policies use uniform weights, so part of the reported gain could come from removing weight variance rather than from age-based spacing; rerunning random selection with uniform weights would isolate the scheduling effect.","An extension the authors leave implicit: the same Markov-age machinery could be applied to client availability and energy budgets, where 'age' is replaced by time since a client's last participation and the threshold adapts to heterogeneous participation costs.","A testable prediction of their variance story: any policy that equalizes inter-selection intervals, such as deterministic round-robin, should produce convergence close to the optimal Markov policy on the same task, because it also drives Σ toward zero.","The convergence bound suggests selection skew ρ matters separately from Σ; a policy that biases selection toward high-loss clients could be combined with the age threshold to get the variance benefit and the skew benefit at once, which the paper does not explore."],"forward_implications":["If the convergence bound is correct, any client selection policy reduces the error bound by shrinking Σ = sum_i Var[ω_i], so making selection intervals regular is not just a fairness nicety but a convergence accelerator.","The optimal Markov policy reaches the same target accuracy in fewer communication rounds than random FedAvg selection: e.g., 39 vs 45 rounds for 97% accuracy on IID MNIST, 95 vs 108 rounds for 75% accuracy on IID CIFAR-10, and up to 20% fewer on CIFAR-100 non-IID.","Because the policy is decentralized and depends only on each client's own age, it can be deployed with minimal server-side bookkeeping and no extra coordination messages.","The non-optimal increasing-p_a Markov policy also beats random selection but trails the optimal threshold, indicating that the variance-minimizing choice of p_a, not just age-aware selection, is what buys the speedup."],"supporting_citations":[{"why":"Defines the FedAvg federated learning algorithm and random client selection that serves as the baseline the paper compares against.","marker":"[1]"},{"why":"Introduces Age of Information as the elapsed-time metric that the paper's load variable X is related to.","marker":"[4]"},{"why":"Provides the concept of peak age, which the paper identifies with its load metric X, the inter-selection interval.","marker":"[5]"},{"why":"Supplies the power-of-choice biased selection analysis and the convergence framework the paper generalizes with selection skew.","marker":"[25]"},{"why":"Gives the general client-sampling theory linking convergence speed to aggregation weight variance, which the paper's Theorem 2 builds on.","marker":"[26]"},{"why":"States the optimal age-dependent transition probabilities for minimizing Var[X] that Theorem 1 of this paper relies on.","marker":"[27]"}],"fun_headline_variants":["Age-of-Information balances clients, cuts FL rounds by up to 20%","Markov AoI policy speeds federated learning by up to 20%","Decentralized AoI scheduling speeds FL convergence by 20%","Fair client turns via AoI: up to 20% fewer FL rounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the reported convergence speedup is caused by the age-based scheduling rule; but the experiments change the aggregation weighting scheme at the same time, so the gains may be partly or wholly due to using uniform weights rather than to the AoI policy.","fun_headline_variants_meta":{"raw":{"variants":["Age-of-Information balances clients, cuts FL rounds by up to 20%","Markov AoI policy speeds federated learning by up to 20%","Decentralized AoI scheduling speeds FL convergence by 20%","Fair client turns via AoI: up to 20% fewer FL rounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000971,"raw_usage":{"total_tokens":4169,"prompt_tokens":1029,"completion_tokens":3140,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":645,"completion_tokens_details":{"reasoning_tokens":3058}},"tokens_in":645,"tokens_out":3140,"duration_ms":20603,"temperature":1.0,"reasoning_tokens":3058,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:13:48.780874+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the identical experimental setup (100 clients, 15 per round, same datasets and optimizer) but replace the random baseline's data-size weighting with the same uniform aggregation weights used by the Markov policies. If random selection with uniform weights reaches the target accuracy as fast as the optimal Markov policy, then the central claim that AoI scheduling improves convergence is not supported. A second check: compare the optimal Markov policy against deterministic round-robin; if round-robin matches it, the benefit comes from low selection-interval variance, not from the Markov structure itself.","supporting_citations":[{"cited_title":"Real-time status: how often should one update?","cited_arxiv_id":null,"evidence_quote":"Introduces Age of Information as the elapsed-time metric that the paper's load variable X is related to."},{"cited_title":"Age of Information with packet management","cited_arxiv_id":null,"evidence_quote":"Provides the concept of peak age, which the paper identifies with its load metric X, the inter-selection interval."},{"cited_title":"A general theory for client sam- pling in federated learning","cited_arxiv_id":null,"evidence_quote":"Gives the general client-sampling theory linking convergence speed to aggregation weight variance, which the paper's Theorem 2 builds on."}],"review_version":1}