{"id":"0c293d49-256c-4171-b94d-c2a43d628461","arxiv_id":"2608.12710","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"FedCoMuon and FedCoMuon-VR apply Muon-style orthogonalized momentum to federated compositional optimization; FedCoMuon-VR proves O(epsilon^{-3}) sample complexity for epsilon-stationary points under non-convex, non-i.i.d. assumptions.","lead":"The paper develops two federated optimizers that combine Muon-style matrix orthogonalization with compositional gradient tracking, and proves convergence rates for non-convex, non-i.i.d. settings. The variance-reduced variant claims an O(epsilon^{-3}) sample complexity, better than earlier federated Muon methods, and shows empirical gains on robust learning and meta-learning tasks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The convergence theorems assume an exact compact SVD, but the algorithms and experiments use five Newton-Schulz iterations; the missing polar-approximation error can persist as a non-vanishing term in the stationarity bound, so the O(ε^{-3}) claim is unproven for the implemented algorithm.","rationale":"The central claim is the O(ε^{-3}) sample complexity of FedCoMuon-VR, and the proof chain passes through Lemma 2 (exact SVD inequality) and Lemma 14 (descent). The algorithms' line 5 and Appendix C implement Newton-Schulz. This is not a small-constant issue: a fixed number of NS iterations gives an approximate polar factor whose error can be O(1) for ill-conditioned or near-rank-deficient momentum matrices; in the averaged stationarity bound this error survives as an additive constant after telescoping, so the rate cannot be obtained from the given proof without an additional accuracy or spectral-gap argument. The reader's weakest assumption identifies exactly this mismatch; other concerns (initial momentum synchronization, two-seed reporting) are fixable or secondary. Since the gap is in the analysis of the implemented algorithm rather than a refutation of the underlying approach, CONDITIONAL remains appropriate and the paper should be revised to either analyze the NS error or implement and analyze exact SVD and clarify that the claimed complexity applies to that variant.","tokens_in":42108,"tokens_out":13995,"duration_ms":164018,"concrete_test":"Re-derive Lemma 14 for Q_t^k = NS_5(M_t^k) and track the extra term R_T = (2√n/T) Σ_{t=0}^{T-1} (1/K) Σ_{k=1}^K E[||M_t^k - Q_t^k||_F]. Then, for T ∈ {10^2, 10^3, 10^4, 10^5}, feed the five-iteration Newton-Schulz map with M_t = U diag(1, T^{-1/2}, ..., T^{-1/2}) V^T (with random orthogonal U,V) and compute R_T. If R_T does not decay at least as fast as T^{-1/3}, the stationarity bound in Theorem 2 cannot be O(T^{-1/3}) for the NS-implemented Algorithm 2; an exact-SVD rerun of the MNIST experiment would further show whether the reported accuracies depend on this gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithms 1 and 2 (line 5) compute the update direction by 'SVD ... with the Newton-Schulz approach', and Appendix C fixes five Newton-Schulz iterations; however, Lemma 2 and its use in Lemma 6/Lemma 14 require the exact compact SVD M = UΣV^T and the identity <A, U_B V_B^T> ≥ ||A||_F - 2√n||A-B||_F. For the implemented update Q_t^k = NS_5(M_t^k), the lemmas would need <∇F, Q> bounded below by ||∇F||_F minus controlled terms, but the missing error <∇F, Q - U V^T> is not bounded anywhere. With fixed NS iterations, ||Q - UV^T||_F is O(1) for matrices with a wide spread of singular values (e.g., M = diag(1, ε, ..., ε) with small ε), and after telescoping Lemma 14 this produces an additive 2√n (1/T) Σ ||M-Q||_F term that does not vanish as T→∞. Thus Theorem 2's O(ε^{-3}) sample complexity is established only for an idealized exact-SVD update, not for the algorithm whose reported results use five NS iterations; the same gap affects Theorem 1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two federated compositional Muon optimizers, FedCoMuon and its variance-reduced variant FedCoMuon-VR, for matrix-wise objectives of the form (1/K) sum_k E[ f_k(E[g_k(W)]) ]. It claims non-convex, non-i.i.d. convergence guarantees: FedCoMuon finds an epsilon-stationary solution with O(epsilon^-4) per-client sample complexity and O(epsilon^-3) communication complexity, while FedCoMuon-VR achieves O(epsilon^-3) sample and communication complexity. The proof appendix supplies detailed algebraic derivations and explicit parameter choices. The experiments cover robust federated learning on MNIST and WikiText-2, and task-distributed meta-learning on CIFAR-10 with CNN and ViT-Tiny models.","tokens_in":42428,"tokens_out":8013,"duration_ms":98072,"significance":"If the advertised rates hold for the algorithms as implemented, the O(epsilon^-3) per-client sample complexity for federated compositional optimization with an orthogonalized matrix update would be a useful step beyond existing FedMuon and compositional federated baselines. The appendix is thorough: constants are explicit, the parameter tuning is algebraic, and no fitted constants enter the theorems. The main obstacle is that the analysis applies to an exact compact-SVD update, while the algorithms and experiments use five fixed Newton-Schulz iterations; until that gap is closed, the central claim is not established for the implemented method.","major_comments":[{"comment":"The convergence theorems are proven only for an idealized exact compact-SVD update, not for the Newton-Schulz update actually used in the algorithms. Lemma 2 and its use in Lemma 14 require the identity <M, U V^T> = ||M||_* for the exact polar factor of a compact SVD. However, Algorithms 1 and 2 compute the update direction by 'SVD ... with the Newton-Schulz approach', and Appendix C fixes five Newton-Schulz iterations. For the implemented update Q_t^k = NS_5(M_t^k), the proofs would need a lower bound on <grad F, Q_t^k> that controls the approximation error <grad F, Q_t^k - U_t^k(V_t^k)^T>. No such bound appears in Theorem 1 or Theorem 2, and with only five iterations the error ||Q - U V^T||_F can be O(1) for matrices with a wide singular-value spread, e.g. M = diag(1, epsilon, ..., epsilon) with small epsilon. After telescoping in Lemma 14, this would leave a non-vanishing additive term in the stationarity bound. Consequently the claimed O(epsilon^-3) sample complexity of FedCoMuon-VR, and similarly the FedCoMuon rate, is not established for the algorithm whose numerical results are reported. To fix this, the authors should either analyze the actual Newton-Schulz update with a formal error bound, or change the algorithm to use an exact SVD/polar factor and state this explicitly in the theorems.","section":"Section 5 and Appendix B, Lemma 2 (Eq. (12)) and Lemma 14 (Eq. (83)); Algorithms 1 and 2, line 5; Appendix C"},{"comment":"The paper claims that FedCoMuon-VR has a lower sample complexity than existing FedMuon algorithms, but it never states the sample or communication complexities of the cited FedMuon baselines [Takezawa et al., 2026, Liu et al., 2025b, Zhang and Gao, 2025, Qian et al., 2026]. As written, this central comparative claim is not verifiable from the manuscript. I request a quantitative comparison table or explicit cited rates for the baselines.","section":"Abstract and Remark 2"}],"minor_comments":[{"comment":"The theorem immediately following Lemma 14 is labeled 'Theorem 1 (Convergence of FedCoMuon-VR with first-order product tracker)' but it is Theorem 2 of the paper; the numbering should be corrected.","section":"Appendix B, after Lemma 14"},{"comment":"The proof of Lemma 13 refers to 'Lemma C.4' when bounding the client product disagreement; the correct reference appears to be Lemma 11. The appendix contains no Lemma C.4.","section":"Lemma 13 proof"},{"comment":"The pseudocode returns factors (U_t^k, Sigma_t^k, V_t^k) from an operation described as 'SVD ... with the Newton-Schulz approach', which is notationally inconsistent. The authors should either define the approximate polar factor Q_t^k explicitly in the pseudocode or give the Newton-Schulz iteration as a separate subroutine.","section":"Algorithms 1 and 2, line 5"},{"comment":"Lemmas 5 and 13 rely on the convention that after a communication round all clients set W and M to the server averages, but this convention is only stated informally in Section 4. I suggest stating it once before the lemmas to make the proofs self-contained.","section":"Section 5, synchronization convention"},{"comment":"The experiments report averages over only two random seeds and do not show error bars or standard deviations. Given the modest number of runs, statements such as 'achieve the best overall performance' should be interpreted with caution.","section":"Section 6 and Appendix C"}],"recommendation":"major_revision","confidential_remarks":"The central issue is the exact-SVD versus Newton-Schulz gap: the paper's advertised rates are not proven for the implemented algorithm. This is fixable in scope if the authors add a rigorous approximation-error analysis or revise the algorithm, so I do not recommend rejection. The comparative claim against FedMuon baselines also needs explicit quantitative support. If these issues are repaired, the contribution would be within the journal's scope and potentially acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper proposes FedCoMuon and FedCoMuon-VR for federated compositional optimization with matrix parameters, combining compositional gradient tracking with Muon-style orthogonalized momentum. The main claim is that FedCoMuon-VR achieves O(ε^{-3}) per-client sample complexity, beating existing FedMuon algorithms. That rate is new for this problem class, and the proof structure, while intricate, is mostly coherent under the stated assumptions. The experiments show the methods are competitive on robust FL and meta-learning tasks, so there is a real algorithmic contribution here.\n\nThe soft spot is the one that matters. Theorems 1 and 2 are proven for an update direction that is the exact polar factor U V^T from the compact SVD of the momentum matrix. The algorithms, however, compute that direction with five Newton-Schulz iterations, and Appendix C confirms that is what was run. There is no bound anywhere on ||Q_t^k - U_t^k V_t^k^T||, the error between the Newton-Schulz output and the true polar factor. Lemma 2, which supplies the key inner-product inequality, requires the exact polar factor. If you plug in the approximate Q, the descent lemmas in the appendix acquire an unvanishing additive term — essentially the mismatch between the approximate and exact orthogonalization — and the O(ε^{-3}) stationarity bound no longer follows. The stress-test note is right: with fixed NS iterations the error can be O(1) for ill-conditioned matrices, so the theorem describes an idealized algorithm, not the one whose numbers are reported. This is a load-bearing gap, not a cosmetic one.\n\nTwo smaller issues: Theorem 1's analysis implicitly requires the initial momentum matrices to be averaged across clients, but Algorithm 1 starts with local M_k^0 and no initial communication. That's easily fixed by adding one averaging round, but as written the proof's first block is not covered. Also, experiments report only two seeds and no error bars, which makes the \"best reported accuracy\" claims weaker than they sound.\n\nIf the authors either analyze the Newton-Schulz error (e.g., show it vanishes under their parameter choices) or explicitly state and prove convergence for the exact-SVD algorithm and treat NS as an empirical approximation, the paper would be solid. As it stands, the central theoretical claim is unproven for the implemented algorithm. I'd still send it to peer review — the combination is new, the proofs are detailed, and the gap is fixable. But the referee should require that fix before acceptance.","headline":"A solid synthesis of Muon and compositional federated optimization, but the central O(ε^{-3}) claim is proven only for an idealized exact-SVD update, not for the Newton-Schulz algorithm actually run.","tokens_in":42905,"tokens_out":3479,"would_cite":false,"duration_ms":40299,"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":"Muon-style orthogonalized momentum can be extended to federated compositional optimization, where a variance-reduced variant reaches an $\\epsilon$-stationary point with $O(\\epsilon^{-3})$ per-client sample complexity.","keywords":["federated learning","compositional optimization","Muon optimizer","orthogonalized momentum","variance reduction","non-convex optimization","matrix-wise models","Newton-Schulz iterations"],"falsifier":"Compute, over a run, the maximum Frobenius distance between the five-iteration Newton–Schulz output and the exact compact SVD direction; if this error does not shrink with $T$, the theorem's rate cannot apply to the implemented update, and a direct comparison run with exact compact SVD would settle whether the proof's idealization matters.","tokens_in":41912,"feed_emoji":"📉","tokens_out":8640,"duration_ms":78718,"temperature":0.7,"pith_summary":"Federated models whose parameters are matrices—transformers, CNNs—are usually trained on single-level objectives, but many real tasks such as robust federated learning and meta learning have nested objectives: a client loss is an expected value of a function of another expected value. The paper sets out to extend the Muon optimizer, which updates matrix blocks along an orthogonalized momentum direction, to this compositional federated setting. It proposes FedCoMuon, built from compositional gradient tracking plus orthogonalized momentum, and FedCoMuon-VR, which adds momentum-based variance reduction. The central theoretical claim is that FedCoMuon-VR finds an $\\epsilon$-stationary point with per-client sample complexity $O(\\epsilon^{-3})$ and communication complexity $O(\\epsilon^{-3})$, which the authors state is lower than existing FedMuon algorithms. If correct, this would give a Muon-type method with convergence guarantees for distributed nested objectives under non-i.i.d., non-convex conditions, and the experiments show gains on robust learning and meta-learning benchmarks.","feed_headline":"Federated Muon cuts sample cost to 1/epsilon^3","feed_subtitle":"It solves nested federated objectives that single-level FedMuon cannot, with proof and experiments.","key_machinery":"The load-bearing mechanism is the compositional matrix-momentum recursion combined with orthogonalized updates. Each client maintains $M^k_{t+1}=\\beta Z^k_{t+1}+(1-\\beta)M^k_t$, where $Z^k_t$ is the matrix-form stochastic compositional gradient, and then replaces the momentum matrix by its orthogonal factor pair $(U,V)$ obtained from a Newton–Schulz-approximated SVD, updating $W$ by $-\\eta U V^\\top$. The key identity used in the descent analysis is Lemma 2: for a compact SVD $B=U_B\\Sigma_B V_B^\\top$, $\\langle A, U_B V_B^\\top\\rangle \\ge \\|A\\|_F - 2\\sqrt{n}\\|A-B\\|_F$, which converts progress in Frobenius norm into progress along the approximate gradient direction. FedCoMuon-VR wraps this in momentum-based variance-reduced trackers for the inner value, inner Jacobian, and outer gradient, with projections onto bounded balls, so that the estimator error contracts rather than accumulating across iterations.","core_discovery":"On the paper's own terms, the discovery is that the Muon update does not have to be confined to single-level federated objectives: by maintaining a moving-average tracker $u^k_t$ of the inner mapping $g_k(W)$, forming the matrix product estimator $Z^k_t = \\nabla g_k(W^k_t;\\xi)(\\nabla_y f_k(u^k_t;\\zeta)\\otimes I_n)$, and running a momentum recursion on the matrix $M^k_t$, each client obtains an orthogonalized descent direction that still points downhill on the compositional objective. The variance-reduced variant replaces the raw estimators with momentum-based trackers $u$, $v$, and $H$ evaluated on shared fresh samples, and the analysis shows the compositional bias and client drift can be controlled simultaneously. Theorems 1 and 2 quantify this: FedCoMuon needs $O(\\epsilon^{-4})$ per-client samples and $O(\\epsilon^{-3})$ communication rounds for an $\\epsilon$-stationary point, while FedCoMuon-VR lowers the sample complexity to $O(\\epsilon^{-3})$ with the same communication complexity, under Assumptions 1–3, 6, and 7. The experiments on robust federated learning (MNIST, WikiText-2) and task-distributed meta learning (CIFAR-10 with CNN and ViT-Tiny) report that the proposed methods are competitive with compositional baselines and reach the best accuracy in several configurations.","pith_inferences":["If a bound on the Newton–Schulz approximation error can be added to the analysis, the same descent identity would likely extend the rate guarantees to the exact implemented update rather than to the idealized exact-SVD direction.","The $O(\\epsilon^{-3})$ sample complexity suggests the compositional bias, not the orthogonalization, is the bottleneck; a similar rate may hold for other structured optimizers that correct nested gradients with momentum.","A direct experiment comparing five Newton–Schulz iterations against an exact compact SVD on the same tasks would isolate whether the reported empirical gains come from the orthogonalization mechanism or from the variance-reduced compositional tracker.","The framework could plausibly be adapted to federated bilevel or multi-level objectives, where the same tracker-plus-orthogonalization pattern applies, though the paper does not analyze those settings."],"forward_implications":["FedCoMuon finds an $\\epsilon$-stationary point with $O(\\epsilon^{-4})$ per-client samples and $O(\\epsilon^{-3})$ communication rounds; FedCoMuon-VR improves the sample bound to $O(\\epsilon^{-3})$ while keeping $O(\\epsilon^{-3})$ communication.","Muon-style orthogonalized momentum remains convergent when the objective is a nested expectation and client data are non-i.i.d., provided the compositional bias is tracked and variance-reduced.","For matrix-wise models with many parameter blocks, the same update rule works for robust federated learning and task-distributed meta learning, where standard compositional federated methods are worse in the reported experiments.","The claimed improvement over existing FedMuon algorithms applies specifically to the compositional setting: the FedMuon baselines are designed for single-level objectives and do not carry these guarantees."],"supporting_citations":[{"why":"Supplies Muon's orthogonalized momentum and Newton–Schulz mechanism that both proposed algorithms build on.","marker":"[Jordan et al., 2024]"},{"why":"Introduces the federated compositional framework (ComFedL) that FedCoMuon extends with Muon-style updates.","marker":"[Huang and Li, 2021]"},{"why":"Provides the momentum-based variance-reduction technique used by FedCoMuon-VR.","marker":"[Cutkosky and Orabona, 2019]"},{"why":"Foundational compositional stochastic optimization with moving-average inner-function tracking, the basis for the tracker design.","marker":"[Wang et al., 2017]"},{"why":"Federated Muon baseline with bias-corrected LMO updates that the paper compares against and claims to improve upon in sample complexity.","marker":"[Takezawa et al., 2026]"},{"why":"Federated Muon baseline using momentum aggregation and local-global alignment, used as an experimental comparison.","marker":"[Liu et al., 2025b]"},{"why":"Federated Muon baseline with problem-parameter-free hyperparameter choices, used as an experimental comparison.","marker":"[Zhang and Gao, 2025]"},{"why":"FedNest framework for federated bilevel, minimax, and compositional optimization, a baseline and source of standard assumptions.","marker":"[Tarzanagh et al., 2022]"}],"fun_headline_variants":["Federated Muon variant cuts sample cost to ε^{-3}","Compositional Muon in federated learning: ε^{-3} sample complexity","FedCoMuon-VR: lower sample complexity for federated nested objectives","Muon optimizer for matrix models goes federated and compositional"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Theorems 1 and 2 rely on Lemma 2, which requires the exact compact SVD $M=U\\Sigma V^\\top$, while Algorithms 1 and 2 compute the update direction with Newton–Schulz iterations and no term in the theorems bounds the distance between the Newton–Schulz output and the exact $U V^\\top$.","fun_headline_variants_meta":{"raw":{"variants":["Federated Muon variant cuts sample cost to ε^{-3}","Compositional Muon in federated learning: ε^{-3} sample complexity","FedCoMuon-VR: lower sample complexity for federated nested objectives","Muon optimizer for matrix models goes federated and compositional"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000692,"raw_usage":{"total_tokens":3177,"prompt_tokens":1037,"completion_tokens":2140,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":653,"completion_tokens_details":{"reasoning_tokens":2061}},"tokens_in":653,"tokens_out":2140,"duration_ms":17623,"temperature":1.0,"reasoning_tokens":2061,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T01:02:50.655889+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, over a run, the maximum Frobenius distance between the five-iteration Newton–Schulz output and the exact compact SVD direction; if this error does not shrink with $T$, the theorem's rate cannot apply to the implemented update, and a direct comparison run with exact compact SVD would settle whether the proof's idealization matters.","supporting_citations":[],"review_version":1}