{"id":"294d954c-ca7d-4860-9108-75460d3ba328","arxiv_id":"2505.11126","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"FedDuA sets each round's global learning rate to the average squared client-update norm divided by the aggregated update norm under an adaptive coordinate preconditioner, a rule that is minimax-optimal under an approximate projection condition and convergent for convex objectives.","lead":"This paper introduces FedDuA, a server-side rule that picks the global learning rate in federated learning by looking at both how much clients disagree and how different parameter directions scale. The rule combines two known adaptivity ideas (FedExP and FedOpt) without adding any device-side cost, and it comes with convergence theory and benchmark experiments.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1's minimax proof only covers v_t=Δ̄_t; for the FedDuAdam momentum variant in Algorithm 1 the stated worst-case V(w) is typically infinite when v_t is not parallel to Δ̄_t, so the abstract's unqualified minimax claim is unsupported.","rationale":"The reader's verdict is already CONDITIONAL, and the reader's rationale explicitly flags the momentum minimax overstatement; I agree with that flag. However, the reader's identified weakest assumption is the realism of A.P.C., whereas the more decisive and verifiable gap is that Theorem 4.1's proof—and, in fact, the minimax objective itself—does not cover the momentum update direction v_t when v_t is not parallel to Δ̄_t. With H defined via A.P.C., the worst-case distance difference is typically infinite for FedDuAdam, so the minimax claim is not merely overbroad but mathematically ill-posed under the stated hypotheses. This strengthens the case for a conditional accept with a narrowed minimax claim, without changing the verdict level: the non-momentum minimax theorem appears sound, the convergence theorem is unaffected, and the empirical contribution remains intact. No code or machine-checked proof is provided, so an independent re-derivation of the momentum minimax statement is the appropriate verification step.","tokens_in":19432,"tokens_out":16805,"duration_ms":178421,"concrete_test":"Construct a two-dimensional counterexample. Take w^t=0, Δ̄^t=(1,0), G_t=I, m_t=1, and a momentum state v_t=(-1,1) (achievable with suitable previous updates and β1<1). Then H={w*∈R^2 : ⟨(1,0), -w*⟩+1 ≤ 0} = {w*_x ≥ 1}, which is nonempty and unbounded. For any η>0, FedDuA's candidate is w=η v_t=(-η,η), and with ψ_t(w)=1/2||w||² we have D_ψ(w*|w)−D_ψ(w*|0)=−⟨w,w*⟩+1/2||w||²=η w*_x − η w*_y + η². Taking w*=(s,1)∈H and letting s→∞ makes this expression tend to +∞. Hence V(w)=∞ for every η>0, including FedDuAdam's chosen η, so no finite η minimizes V. Running this 2-D check (analytically or by grid evaluation of sup_{w*∈H}) settles whether Theorem 4.1 covers the momentum rule: it does not.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that FedDuA's step-size rule is minimax optimal is not established for the momentum variant, which is a main experimental workhorse. Theorem 4.1 and its proof in Appendix C use the dual-feasibility condition θ_t−θ+λΔ̄_t=0 and conclude that the minimizer is w=∇φ(θ_t+η_gΔ̄_t). This handles only v_t=Δ̄_t. For FedDuAdam, Algorithm 1 uses v_t=β1 v_{t−1}+(1−β1)Δ̄_t, and the proof never replaces Δ̄_t with v_t. This is not a cosmetic omission. With H={w* : (1/M)∑_i ||w^t+Δ_i^t−w*||² ≤ ||w^t−w*||²}, the affine functional D_ψt(w*|w)−D_ψt(w*|w^t) has linear coefficient θ_t−θ = −η_t v_t. For the supremum over H to be finite, this coefficient must lie in the dual cone generated by −Δ̄_t; if v_t has any component outside span(Δ̄_t), the worst-case distance difference is +∞ for every η_t>0, so no finite η minimizes V. Thus Theorem 4.1 cannot extend to the momentum rule merely by a change of notation. Theorem 3.3 gives a lower bound under strong A.P.C., but a lower bound does not imply minimax optimality, and the strong-A.P.C. condition is not the hypothesis of Theorem 4.1. The abstract's and Section 4.1's unqualified 'minimax optimal' claim is therefore unsupported for exactly the FedDuAdam variant emphasized in the experiments. The A.P.C. realism concern raised by the reader is related, but the missing momentum case is the sharper, internally checkable gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes FedDuA, a server-side federated learning update rule that combines coordinate-wise preconditioning (via FedAdagrad/FedAdam style matrices G_t) with a heterogeneity-adaptive global learning rate eta_t^g = m_t / (||v_t||^2_{G^{-1}_t} + epsilon_g), where m_t measures the average squared norm of local updates. The update is derived from a mirror-descent formulation of the server step: lower bounds on the optimal step size are proven under an approximate projection condition (Theorems 3.2 and 3.3), a minimax optimality claim is made (Theorem 4.1), and a convex convergence bound is proven under full-batch, full-participation assumptions (Theorem 4.3), with a dimension-dependent rate analysis for FedDuAdagrad (Corollary 4.4 and Appendix F). Experiments on synthetic data, CIFAR-10/100, FEMNIST, and Shakespeare compare FedDuA with FedAvg, FedExP, FedOpt, and their momentum variants.","tokens_in":19869,"tokens_out":11552,"duration_ms":101470,"significance":"The paper has several genuine strengths: the mirror-descent perspective provides a clean way to unify coordinate-wise adaptivity and client-heterogeneity adaptivity without any extra client-side cost; the lower-bound derivations are careful; the non-momentum convergence analysis is nontrivial and the experimental study is extensive, including robustness checks and combination with SCAFFOLD. The conditional minimax result for the non-momentum case v_t = Delta_bar_t is a credible contribution beyond FedExP. However, the headline claim in the abstract and Section 4.1 that the doubly adaptive step-size rule is minimax optimal is not actually proven for the momentum variant FedDuAdam, which is the main experimental workhorse. Because the proofs of Theorems 4.1 and 4.3 both assume v_t = Delta_bar_t, the manuscript currently overclaims its theoretical scope. The issue is fixable by restricting the claims or by supplying a genuinely different argument, but it is load-bearing for the paper's central message.","major_comments":[{"comment":"The theorem as stated covers FedDuA defined in Eq. (3) with a general v_t, and the abstract's 'minimax optimal' claim is unqualified. The proof, however, only treats v_t = Delta_bar_t: the dual-feasibility condition theta_t - theta + lambda Delta_bar_t = 0 leads to w = grad phi(theta_t + lambda Delta_bar_t), and the lambda-optimality condition uses h_t(lambda) with Delta_bar_t. For FedDuAdam in Algorithm 1, v_t = beta_1 v_{t-1} + (1 - beta_1) Delta_bar_t is generally not parallel to Delta_bar_t. With H defined by the A.P.C. inequality, which is the half-space <Delta_bar_t, w* - w^t> >= (1/(2M)) sum_i ||Delta_i^t||^2, the worst-case distance difference V(w) has linear coefficient theta_t - theta_w = -eta_t^g v_t in w*. For the supremum over H to be finite, this coefficient must lie in the cone generated by -Delta_bar_t; when v_t has a component outside span(Delta_bar_t), V(w) = +infinity for every eta_t^g > 0 and no finite minimizer exists. The lower bound in Theorem 3.3 does not repair this gap, because a lower bound on a minimizer does not establish minimax optimality. The abstract and Section 4.1 must restrict the minimax claim to v_t = Delta_bar_t (i.e., FedDuAdagrad) or provide a proof for the momentum rule under a different, explicitly stated uncertainty set.","section":"Section 4.1, Theorem 4.1 and Appendix C"},{"comment":"The theorem statement says 'generated by FedDuA' without restricting v_t, but the proof again assumes v_t = Delta_bar_t: the first display writes phi_t(theta_{t+1}) - phi_t(theta_t) - eta_t^g <w*, Delta_bar_t> and defines H_t with Delta_bar_t. Thus the convergence guarantee has not been established for the FedDuAdam variant used extensively in the experiments, and the 'with and without momentum' discussion in Section 3 is not backed by this theorem. Please either state Theorem 4.3 for FedDuAdagrad only, extend the proof to the momentum case with appropriate additional assumptions, or explicitly state that the momentum analysis in Section 4 is limited to the lower bound in Theorem 3.3.","section":"Section 4.2, Theorem 4.3 and Appendix D"}],"minor_comments":[{"comment":"The assumption says 'w_s is updated as Eq. (3) with eta_s^g <= h^{-1}_s(m_s)', but Eq. (3) already defines eta_s^g := h^{-1}_s(m_s); the inequality should be stated as an explicit separate assumption or the equality in Eq. (3) should be relaxed.","section":"Section 3, Theorem 3.3"},{"comment":"In the displayed line 'D_t(w*|w^{t+1}) - D_t(w*|w^{t+1}) <= ...', the second occurrence of D_t(w*|w^{t+1}) should be D_t(w*|w^t); as printed the left-hand side is identically zero and the inequality is vacuous.","section":"Appendix D, proof of Theorem 4.3"},{"comment":"The displayed sum sum_{t=0}^{T-1} (D_t(w*|w^t) - D_{t-1}(w*|w^t)) does not match the numerator from Theorem 4.3, which is D_0(w*|w^0) + sum_{t=1}^{T-1} (D_t(w*|w^t) - D_{t-1}(w*|w^t)); the final D^2 tr(G_{T-1}) bound is plausible, but the displayed algebra should be corrected.","section":"Appendix E, proof of Corollary 4.4"},{"comment":"The symbol 'w*_{t+1}' is used for the minimizer of V(w), which is not the global optimum w*; renaming it (for example, widetilde{w}_{t+1}) would avoid confusion.","section":"Section 4.1, Theorem 4.1"},{"comment":"Table 2 reports 'last iterate' accuracy while the text says the last two iterates are averaged; please clarify which quantity is actually reported.","section":"Section 5, Table 2"}],"recommendation":"major_revision","confidential_remarks":"The mismatch between the unqualified minimax claim and the actual proof for v_t = Delta_bar_t is the main obstacle to acceptance. The paper is otherwise a solid contribution with a simple, useful algorithm and extensive experiments, and the fix (restricting the scope of the claims or adding a new argument for momentum) appears feasible within a revision. I would not recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The bottom line: this is a genuinely useful extension of FedExP to the preconditioned FedOpt family. Formulating the server update as mirror descent and deriving the doubly adaptive step size m_t / ||v_t||^2_{G^{-1}_t} is natural and well executed. The lower bounds (Theorems 3.2 and 3.3) and the convex convergence bound (Theorem 4.3) look correct for the non-momentum case; the telescoping in Corollary 4.4 checks out. The empirical study is extensive and shows real gains across datasets, and the SCAFFOLD combination is a nice touch.\n\nThe main problem is the minimax claim. Theorem 4.1's proof explicitly uses the dual feasibility condition θ_t − θ + λΔ̄_t = 0, so it covers only v_t = Δ̄_t. For FedDuAdam, v_t is a momentum average, and then the condition becomes −η v_t + λΔ̄_t = 0, which has no solution unless v_t is parallel to Δ̄_t. Because H (defined by the A.P.C.) has a recession cone that includes directions orthogonal to Δ̄_t, the worst-case distance difference V(w) is typically +∞ for every η > 0 when v_t is not parallel to Δ̄_t. So the abstract's unqualified \"minimax optimal\" claim is not supported for the momentum variant, which is the main workhorse in the experiments. Theorem 4.3's proof also uses Δ̄_t, so the convergence analysis likewise does not cover the momentum variant. This is fixable by narrowing the claims to FedDuAdagrad and describing the momentum rule as heuristic or backed only by the lower bound, but as written the overstatement is substantial.\n\nOther soft spots are minor by comparison. The paper reports \"validation accuracy\" in Table 2 but \"test accuracy\" in Figure 1; the protocol should be clarified. No code is released, which hurts reproducibility. The theory assumes full-batch and full participation, honestly acknowledged in the limitations.\n\nThe core algorithmic idea survives these issues. The step-size rule is sensible, the FedDuAdagrad analysis is solid, and the experiments consistently support the practical value. This paper deserves a serious referee, but it needs a revision that scopes the minimax and convergence claims correctly, clarifies the evaluation, and ideally releases code.","headline":"Useful extension of FedExP to the preconditioned FedOpt family, with a clean mirror-descent derivation and a correct one-step minimax argument for the non-momentum case, but the momentum variant's minimax claim is unsupported and needs qualification.","tokens_in":20388,"tokens_out":7258,"would_cite":true,"duration_ms":68214,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"One formula chooses the global learning rate in federated learning and is minimax optimal under an approximate projection condition.","keywords":["federated learning","adaptive optimization","mirror descent","global learning rate","client heterogeneity","gradient heterogeneity","minimax optimality","FedDuA"],"falsifier":"Test Theorem 4.1 directly: in a convex overparameterized problem where A.P.C. holds, compute both FedDuA's update and the exact minimizer of $\\sup_{w^*\\in H} [D_{\\psi_t}(w^*|w)-D_{\\psi_t}(w^*|w^t)]$; any disagreement refutes the minimax claim. Separately, on a real task, measure per round whether $(1/M)\\sum_i \\lVert w^t+\\Delta_i^t-w^*\\rVert^2 \\le \\lVert w^t-w^*\\rVert^2$; if it typically fails while FedDuA still converges, the empirical success is not explained by the minimax theorem.","tokens_in":19224,"feed_emoji":"📡","tokens_out":7234,"duration_ms":60506,"temperature":0.7,"pith_summary":"FedDuA claims that the server-side global learning rate in federated learning can be chosen from the local updates themselves rather than tuned by hand, and that the right choice is $\\eta_t^g = m_t / (\\lVert v_t \\rVert^2_{G_t^{-1}} + \\epsilon_g)$ where $m_t$ is half the average squared norm of client updates and $G_t$ is the coordinate-wise preconditioner borrowed from FedAdagrad/FedAdam. The paper derives this rule as a lower bound on the step size that minimizes Bregman distance to an optimum, and proves it is minimax optimal under an approximate projection condition. It also proves convergence for convex smooth objectives with full-batch local SGD and full participation. The reason this matters is that it unifies two previously separate kinds of adaptivity, coordinate-wise and inter-client, inside a single formula that costs the server nothing extra.","feed_headline":"One formula chooses the global learning rate in federated learning","feed_subtitle":"Server uses client-update norms and coordinate statistics, adding no client cost beyond FedAvg.","key_machinery":"The machinery is the mirror-descent reformulation of the server update: the distance-generating function $\\psi_t(x)=\\tfrac12 x^\\top G_t x$ induces a Bregman divergence $D_{\\psi_t}(w^*|w)$, and the dual update $\\theta^{t+1}=\\theta^t+\\eta_t^g v_t$ lets the step size be chosen in the dual space. The approximate projection condition (A.P.C.) says local training does not move the average client model farther from $w^*$; under it, the optimal step size is lower-bounded by $m_t/\\lVert v_t\\rVert^2_{G_t^{-1}}$, and Theorem 4.1 shows that taking exactly this lower bound minimizes the worst-case distance over all optima consistent with A.P.C. With momentum, $m_t$ is replaced by its exponentially weighted version, so the same formula covers both FedDuAdagrad and FedDuAdam.","core_discovery":"The paper's central claim is that the FedDuA update $w^{t+1} = w^t + \\eta_t^g G_t^{-1} v_t$, with $\\eta_t^g = m_t / (\\lVert v_t \\rVert^2_{G_t^{-1}} + \\epsilon_g)$, is the unique minimizer of the worst-case Bregman distance to any optimum consistent with the approximate projection condition (Theorem 4.1). Under that condition, partially adaptive rules, coordinate-wise only like FedOpt or client-heterogeneity only like FedExP, are suboptimal because the minimizer is unique. For convex $L$-smooth losses with full-batch local SGD and full participation, the averaged iterate satisfies $F(\\bar w_T)-F(w^*) = O\\bigl(D_{\\psi_0}(w^*|w^0) / \\sum_t \\eta_t^g \\eta_l \\tau\\bigr) + O(\\eta_l \\tau \\sigma_*^2) + O(\\eta_l^2 \\tau(\\tau-1) L \\sigma_*^2)$ (Theorem 4.3), where the bias terms are independent of the mirror map.","pith_inferences":["If the approximate projection condition is violated in practice by minibatch SGD or partial participation, the minimax theorem no longer pins down the correct step size; one can test how often A.P.C. holds on real FL runs and whether the empirical gains persist when it fails.","The mirror-descent derivation is generic: replacing $G_t$ with another strongly convex preconditioner should yield a new doubly adaptive rule by the same lower-bound argument.","The dimension-free bound hints that FedDuA-type rates could be most valuable in very wide or transformer-like models, consistent with the paper's ViT experiment.","Extending the convergence analysis to partial participation would require treating $\\eta_t^g$ as stochastic, and the minimax optimality may or may not survive in expectation; that is a concrete open question."],"forward_implications":["FedDuA changes only the server's aggregation step, and the quantities it needs, norms of the already-received local updates and the preconditioner, are server-side, so no extra client cost arises.","The formula is hyperparameter-free at $\\epsilon_g=0$, and the experiments show that $\\epsilon_g=0$ works, so the method removes the need to tune a global learning rate.","On anisotropic problems, FedDuAdagrad's initialization error term is dimension-free, unlike FedExP and FedAvg, so the advantage should grow with model dimension.","FedDuA composes with local-training modifications: combining it with SCAFFOLD-type local updates outperforms vanilla SCAFFOLD on CIFAR-100.","Under the stated assumptions, minimax optimality is strict: any update rule differing from FedDuA is suboptimal for some optimum consistent with the approximate projection condition."],"supporting_citations":[{"why":"supplies FedExP and the approximate projection condition that FedDuA generalizes to the mirror-descent setting.","marker":"Jhunjhunwala et al. [2023]"},{"why":"supplies FedOpt, FedAdagrad, and FedAdam, the coordinate-wise preconditioner framework FedDuA builds on.","marker":"Reddi et al. [2021]"},{"why":"provides the mirror-descent interpretation of adaptive methods that motivates the Bregman-divergence formulation.","marker":"Duchi et al. [2011]"},{"why":"defines FedAvg and the local-update protocol whose server side FedDuA modifies.","marker":"McMahan et al. [2017]"},{"why":"provides SCAFFOLD, whose local-update variant FedDuA combines with to show orthogonality.","marker":"Karimireddy et al. [2020b]"},{"why":"supplies the Bregman-divergence duality used to move between primal and dual forms in the step-size derivation.","marker":"Nielsen et al. [2007]"}],"fun_headline_variants":["Doubly adaptive global learning rate beats FedAvg baselines","Adaptive step size for federated learning: one formula fits all","Client and coordinate heterogeneity guide a single learning-rate rule","Federated learning: a minimax-optimal adaptive step size","One formula sets global learning rate, robust to hyperparameters"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that after each round of local training, the client models are on average no farther from some global optimum than before the round; with real minibatch SGD and partial participation this condition can fail.","fun_headline_variants_meta":{"raw":{"variants":["Doubly adaptive global learning rate beats FedAvg baselines","Adaptive step size for federated learning: one formula fits all","Client and coordinate heterogeneity guide a single learning-rate rule","Federated learning: a minimax-optimal adaptive step size","One formula sets global learning rate, robust to hyperparameters"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00084,"raw_usage":{"total_tokens":3651,"prompt_tokens":924,"completion_tokens":2727,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":540,"completion_tokens_details":{"reasoning_tokens":2643}},"tokens_in":540,"tokens_out":2727,"duration_ms":17917,"temperature":1.0,"reasoning_tokens":2643,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:00:14.817233+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Test Theorem 4.1 directly: in a convex overparameterized problem where A.P.C. holds, compute both FedDuA's update and the exact minimizer of $\\sup_{w^*\\in H} [D_{\\psi_t}(w^*|w)-D_{\\psi_t}(w^*|w^t)]$; any disagreement refutes the minimax claim. Separately, on a real task, measure per round whether $(1/M)\\sum_i \\lVert w^t+\\Delta_i^t-w^*\\rVert^2 \\le \\lVert w^t-w^*\\rVert^2$; if it typically fails while FedDuA still converges, the empirical success is not explained by the minimax theorem.","supporting_citations":[],"review_version":1}