{"id":"83c5b55a-e3f5-4a6c-837d-7cddbd7cee35","arxiv_id":"2411.09365","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"Provides stability-based generalization and population risk bounds for Local-SGDA and Local-DSGDA under a unified Distributed-SGDA framework, revealing a generalization-optimization trade-off.","lead":"This paper develops a unified stability-based generalization analysis for distributed minimax algorithms with local updates, covering both centralized Local-SGDA and decentralized Local-DSGDA. It derives bounds on generalization gaps and population risk under convex-concave, PL-strongly-concave, and nonconvex-nonconcave settings, plus experiments on GAN and AUC maximization.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central stability proof conflates squared and unsquared consensus error, so Theorem 2's bound is not derived as stated.","rationale":"The reader's rejected verdict is supported, but the single most load-bearing obstacle is somewhat different from the reader's stated weakest assumption. The reader points to Theorem 10's unstated condition on the potential-function coefficient \\(b\\), which indeed invalidates the PL-SC population-risk claim as stated. I agree that this is a real defect. However, an even more direct defect sits in the central SC-SC stability theorem: the proof of Theorem 2 relies on Lemma 6 and Lemma 7, and the consensus quantity used in the stability recursion is inconsistent with the paper's definition. Since Theorem 2 feeds into Theorem 4 and into the SC-SC generalization and population-risk bounds that are among the paper's headline contributions, this consistency failure is at least as load-bearing as the Theorem 10 condition. The paper may be salvageable by redefining the consensus term throughout, but as written the main quantitative rates are not derivable from the presented proof. Therefore the reader's REJECT verdict remains appropriate, and no verdict change is needed.","tokens_in":49650,"tokens_out":20663,"duration_ms":199511,"concrete_test":"Re-derive Lemma 7 and the recursion leading to Eq. (16) while honoring the printed definition of \\(\\Delta_t^k\\) as the squared average deviation. Check whether the affine term is \\(2\\eta L E[\\Delta_t^k]\\) or \\(2\\eta L E[\\sqrt{\\Delta_t^k}]\\) (equivalently \\(\\frac{2\\eta L}{m}\\sum_i E\\|z_{i,k}-\\bar{z}_k\\|\\)). Then redo the summation in Theorem 2(i) with the corrected consensus contribution. If Lemma 6 only supplies a bound for \\(\\sqrt{\\Delta_t^k}\\), the displayed \\(O(\\eta K^2 + K/n)\\) argument-stability rate requires a different proof, and the \\(\\lambda\\)-dependence may change; if the proof is amended by redefining \\(\\Delta_t^k\\), all theorem statements and the main-text definitions must be updated consistently.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2 is the load-bearing result for all (S)C-(S)C claims, but its proof does not go through under the paper's own definitions. The paper defines the consensus term as a squared deviation, \\(\\Delta_t^k = \\frac1m \\sum_i \\|(x_{i,k}-\\bar{x}_k,\\, y_{i,k}-\\bar{y}_k)\\|^2\\). Lemma 7, however, obtains a term of the form \\(\\eta L \\cdot \\frac1m \\sum_i (\\|z_{i,k}-\\bar{z}_k\\| + \\|\\dot{z}_{i,k}-\\bar{\\dot{z}}_k\\|)\\) from the difference between local and averaged gradients, and then replaces it by \\(2\\eta L E[\\Delta_t^k]\\). This replacement is valid only if \\(\\Delta_t^k\\) denotes an average of norms, not a squared norm. Lemma 6 then proves a bound of the form \\(\\eta G \\sqrt{ \\frac{1}{1-\\lambda}(k^2 + \\frac{2\\lambda}{1-\\lambda^2}K^2) }\\), which is homogeneous to a distance, not to a squared distance. If the printed definition is taken literally, Lemma 6 bounds the square root of the quantity that enters the stability recursion, so Theorem 2's recurrence does not follow. If an unsquared consensus term is intended, then the definition and the theorem statements using it must be amended. Either way, Theorem 2 and the derived generalization and population-risk bounds for Local-SGDA and Local-DSGDA are not established as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a unified Distributed-SGDA framework that covers Local-SGDA and Local-DSGDA and studies their stability-based generalization. For (strongly) convex--(strongly) concave losses it proves argument-stability bounds and converts them into weak PD generalization and population-risk bounds; for PL--strongly-concave losses it proves primal stability and excess primal population risk; for nonconvex--nonconcave losses it proves weak stability and derives weak PD generalization bounds. The paper also reports preliminary GAN and AUC-maximization experiments. The high-level contribution is a stability-based generalization analysis for local-update and decentralized minimax algorithms, with rates summarized in Tables 1 and 2.","tokens_in":50052,"tokens_out":27699,"duration_ms":258523,"significance":"If the bounds were correct, this would be a useful first systematic stability-based generalization analysis for local-update distributed minimax optimization. The connection theorem between algorithmic stability and the weak PD / excess-primal generalization gaps is a valuable structural contribution, and the paper explicitly identifies the trade-off between generalization gap and optimization error. The analysis is derivation-based rather than parameter-fitting, and the special-case reductions to prior SGDA/DSGDA results are a reasonable consistency check. However, the main stability proofs as written contain a definitional inconsistency and several unstated conditions; until these are repaired, the claimed rates in the tables are not established.","major_comments":[{"comment":"The consensus term is defined as a squared deviation, Δ_t^k = (1/m)Σ_i ||(x_{i,k}−xbar_k, y_{i,k}−ybar_k)||^2, but the proof of Lemma 7 bounds a sum of first powers of such deviations by 2η_t^k L E[Δ_t^k], and the proof of Lemma 6 explicitly writes Δ_t^k as (1/m)Σ_i||...|| without the square before applying Cauchy--Schwarz. Taken literally, Lemma 6 bounds the square root of the quantity that enters the stability recursion, so Theorem 2's recurrence (16) is not derived from the printed definitions. The intended quantity appears to be the average norm, in which case the Cauchy--Schwarz step is acceptable and the final linear-in-η rate is consistent; the definition and all subsequent uses of Δ_t^k must be amended to one convention. Because Theorem 4 and the (S)C-(S)C rows of Tables 1 and 2 all depend on Theorem 2, this inconsistency is load-bearing rather than cosmetic.","section":"Section 4, Lemma 6, Lemma 7, and Theorem 2"},{"comment":"The potential-function coefficient b = 2μ³L²/(μ⁴−32L²) is used with the requirement b ≤ (ρ−μ/4)μ³/(16L²(L+L²/μ)). This requires μ⁴ > 32L² and ρ > μ/4, but these restrictions are not stated in Theorem 10, in Theorem 7, or in the PL-SC rows of Tables 1 and 2. Since Theorem 7's excess-primal population-risk bound invokes Theorem 10, the PL-SC results are established only under an unstated and quite restrictive parameter regime. The theorem statements should either include these assumptions explicitly and discuss their scope, or the proof should be reworked with a potential function that does not impose them.","section":"Theorem 10 and Appendix D.2.1"},{"comment":"In the decaying-learning-rate proof, the summation bounds for the three series are justified only under the condition Lμ/(L+μ)(1 + K^{1−α}/(1−α)) > 1. This condition is not stated in Theorem 2(ii) or in Remark 6. Without it, the displayed bound for decaying learning rates does not follow for all admissible K and parameter values. The theorem should state the condition, or the proof should be modified to avoid it.","section":"Theorem 2(ii), Appendix C.1"}],"minor_comments":[{"comment":"The notation E[F(x,y′)] in the weak PD population risk is ambiguous; the expectation should be made explicit over the randomness of the algorithm and the dataset S.","section":"Definition 2"},{"comment":"In the chain proving the weak PD generalization gap, one of the two terms is written with Ay(S(r)) on both sides; this appears to be a typo and should read Ay(S) versus Ay(S(r)).","section":"Proof of Theorem 1(i), Appendix B"},{"comment":"The tilde-O notation eO is used in the table captions and in Remark 6 but is not formally defined; please define it and explicitly state the λ-dependent constants λ1 and λ2 in one place.","section":"Tables 1 and 2"},{"comment":"The sample index notation ξ_{i,j_t^k(i)} is used but j_t^k(i) is never defined; please clarify the sampling mechanism for the local stochastic gradients.","section":"Algorithm 1"},{"comment":"The experiments are described as preliminary; please state the number of independent runs used to produce the curves, report error bars or confidence intervals, and specify the exact mixing matrices used for the topologies in Figure 2.","section":"Experiments, Section 5.2"}],"recommendation":"major_revision","confidential_remarks":"I am less pessimistic than the outside reader: the consensus-term issue is a definitional inconsistency rather than a fundamental scaling error, because with the average-norm interpretation the Cauchy--Schwarz step and the linear-in-η bound are coherent. The more serious substantive issue is the unstated parameter regime in Theorem 10, which propagates into the PL-SC claims. If the authors correct the definition of Δ, explicitly state the conditions needed in Theorem 2(ii) and Theorem 10, and re-verify the derived rates, the paper could become acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things before you invest time. The paper targets a genuine gap: nobody has stability-based generalization bounds for Local-SGDA or Local-DSGDA with K > 1 local steps, and the unified Distributed-SGDA framing is a sensible way to cover both the centralized and decentralized cases in one analysis. The second thing is that the central stability proof does not go through. The consensus term is defined as a squared deviation, Delta_t^k = (1/m) sum_i ||z_{i,k} - zbar_k||^2, but Lemma 6's proof bounds the mean of the norms: the final Cauchy-Schwarz step turns a bound on sum ||.||^2 into a bound on (1/m) sum ||.||, which is homogeneous to a distance, not a squared distance. The recursion in Lemma 7 feeds E[Delta_t^k] into the argument-stability recurrence, so Theorem 2 and everything downstream, including Theorem 4's population risk, the eta ~ 1/(TK) choice, and the claimed O((sqrt(lambda1)+sqrt(lambda2))K/T + K/n) rates, is not established as written. The stress-test note holds up against a close reading of the appendix. This is the load-bearing joint, and fixing it changes the eta-scaling of the rates.\n\nCredit where it is due. Theorem 1's connections between stability and the three generalization gaps are standard leave-one-out machinery applied cleanly to the distributed neighbor definition; the K=1 limit reduces to the earlier DSGDA bound, which is genuine consistency. The qualitative trade-off story is plausible, and the experiments match its directions (larger learning rates and more local steps hurt stability, more samples help), though they do not test the specific rates.\n\nSecondary soft spot: Theorem 10's condition on the coefficient b, namely b <= (rho - mu/4) mu^3 / (16 L^2 (L + L^2/mu)), forces mu^4 > 32 L^2 and rho > mu/4. The inequality is printed, but the restriction it places on the PL and strong-concavity parameters is never surfaced, so Theorem 7's PL-SC population risk bound holds only in a regime the summaries never mention.\n\nWho this is for: someone who wants the framework and the connection theorems and will treat the quantitative bounds as unverified. It deserves a serious referee, because the gap is real and the main error looks fixable, but as written I would reject, and I would not cite the rates. If you engage, ask the referee to check Lemma 6 against the definition of Delta_t^k before reading anything else.","headline":"Targets a real gap in stability-based generalization for local-update distributed SGDA, but the consensus-term proof conflates squared and unsquared deviations and the headline rates do not follow as written.","tokens_in":50498,"tokens_out":8389,"would_cite":false,"duration_ms":78554,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","90C47","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Distributed minimax learners generalize when they are stable, and this paper gives the rates.","keywords":["minimax optimization","algorithmic stability","generalization gap","population risk","distributed learning","Local-SGDA","Local-DSGDA","consensus"],"falsifier":"Run Distributed-SGDA on a synthetic PL-strongly-concave minimax problem with parameters chosen so that $\\mu^4 \\le 32L^2$ or $\\rho \\le \\mu/4$ and measure the excess primal population risk under the paper's decaying schedule; if the stated rate still holds, the hidden condition is unnecessary, and if it does not, the theorem is confined to that regime. Separately, with fixed $\\eta$ and varying $K$, measure argument stability on neighbouring datasets to test the predicted $O(\\eta K^2)$ growth.","tokens_in":49480,"feed_emoji":"⚖️","tokens_out":15043,"duration_ms":128516,"temperature":0.7,"pith_summary":"The paper sets out to prove that distributed minimax algorithms generalize when they are algorithmically stable, and to quantify the stability in terms of communication topology, number of local steps, and dataset size. It unifies Local-SGDA and Local-DSGDA inside a single Distributed-SGDA model and derives stability bounds that, through a connection theorem, become bounds on the generalization gap and population risk. The rates reveal a concrete trade-off between generalization and optimization error, with an explicit learning-rate schedule that minimizes population risk. Such bounds matter because they predict how a model trained on finite local data will behave on unseen data, addressing a gap left by convergence-focused analyses of federated minimax methods.","feed_headline":"Stability controls generalization in distributed minimax training","feed_subtitle":"New rates show when Local-SGDA and Local-DSGDA learn to unseen data, and how to balance the learning rate.","key_machinery":"The load-bearing object is the consensus term $\\Delta_t^k = \\frac{1}{m}\\sum_{i=1}^m \\left\\|\\left(\\begin{smallmatrix} x_{i,k}^t - \\bar{x}_k^t \\\\ y_{i,k}^t - \\bar{y}_k^t \\end{smallmatrix}\\right)\\right\\|^2$, which measures how far local models drift from the global average during the $K$ local update steps. The proof bounds $\\Delta_t^k$ using the spectral gap of the mixing matrix (through $\\lambda$) and the contraction factor $1 - \\eta L\\mu/(L+\\mu)$ of a single gradient descent-ascent step, then feeds the bound into a recursion that accumulates the effect of neighbouring datasets over all $T$ communication rounds. Theorem 1 is the bridge that converts the resulting argument, primal, or weak stability into the corresponding generalization gap, so the whole population-risk analysis reduces to controlling $\\Delta_t^k$ and the stability recursion.","core_discovery":"The central discovery is that the stability of the averaged distributed model can be bounded by a recurring contraction argument whose main input is the consensus term, and that the resulting stability is exactly what controls the generalization gap. Concretely, Theorem 1 proves that $\\epsilon$-argument stability implies a weak primal-dual generalization gap at most $\\sqrt{2}G\\epsilon$, and Theorem 2 proves that under $\\mu$-SC-SC local losses with fixed learning rate the argument stability of Distributed-SGDA is at most $\\frac{2G(L+\\mu)}{L\\mu}\\left[\\eta L\\sqrt{\\frac{1}{1-\\lambda}}\\frac{K^2}{2} + \\eta L\\sqrt{\\frac{2\\lambda}{(1-\\lambda)(1-\\lambda^2)}}K^2 + \\frac{K}{n}\\right]$, so with $\\eta \\sim 1/(TK)$ the stability is $O((\\sqrt{\\lambda_1}+\\sqrt{\\lambda_2})K/T + K/n)$. The same connection yields, under PL-strong-concavity, an excess primal generalization gap and population risk bounded by $O(1/(mn) + (\\sqrt{\\lambda_1}+\\sqrt{\\lambda_2})K^{(1+\\alpha)/2}/\\sqrt{T})$ for $1/2<\\alpha<1$, and under nonconvex-nonconcave losses a weak stability bound of $eO((1/n+\\sqrt{\\lambda_1}+\\sqrt{\\lambda_2}K^{1/2})^{1/5}(m/n)^{4/5}T^{1/5}K^{3/5})$.","pith_inferences":["Because the proof is modular, the same consensus-plus-expansiveness route should extend to other distributed minimax algorithms such as variance-reduced or momentum variants, provided analogous consensus and contractivity lemmas hold.","The paper's trade-off analysis implies that hyperparameter search for minimax models should target whichever term dominates the population risk decomposition, a testable prescription for federated GAN training.","The PL-strongly-concave population-risk result rests on an unstated geometric restriction ($\\mu^4 > 32L^2$ and $\\rho > \\mu/4$); checking whether the stated rates hold outside this regime would delimit or extend Theorem 7.","Stability bounds of this form typically compose with differential-privacy noise, so a private variant of Local-DSGDA should inherit the same generalization gap plus a privacy term."],"forward_implications":["With fixed learning rate $\\eta$, argument stability of Distributed-SGDA is $O((\\sqrt{\\lambda_1}+\\sqrt{\\lambda_2})\\eta K^2 + K/n)$, and taking $\\eta \\sim 1/(TK)$ yields $O((\\sqrt{\\lambda_1}+\\sqrt{\\lambda_2})K/T + K/n)$.","In the PL-strongly-concave case, the excess primal generalization gap and population risk are both $O(1/(mn) + (\\sqrt{\\lambda_1}+\\sqrt{\\lambda_2})K^{(1+\\alpha)/2}/\\sqrt{T})$ for $1/2<\\alpha<1$, and the generalization gap dominates the population risk.","Under nonconvex-nonconcave losses, the weak stability bound of $eO((1/n+\\sqrt{\\lambda_1}+\\sqrt{\\lambda_2}K^{1/2})^{1/5}(m/n)^{4/5}T^{1/5}K^{3/5})$ directly implies a weak PD generalization gap via the connection theorem.","Local-SGDA, obtained by setting $\\lambda=0$, recovers the corresponding rates with $\\sqrt{\\lambda_1}=1$ and $\\sqrt{\\lambda_2}=0$; Decentralized-SGDA (K=1) matches the earlier rates of Zhu et al. (2023)."],"supporting_citations":[{"why":"Establishes the stability-to-generalization connection for stochastic minimax algorithms (SGDA) that the paper extends to the distributed setting, and supplies the comparison SGDA bounds in Tables 1 and 2.","marker":"Lei et al. (2021)"},{"why":"Develops the stability and generalization analysis for decentralized SGDA, providing the gradient-map contractivity lemma and the baseline DSGDA bounds that Distributed-SGDA generalizes.","marker":"Zhu et al. (2023)"},{"why":"Gives the convergence analysis of Local-SGDA in SC-SC and NC-SC settings whose rates the paper's population-risk bounds are compared against.","marker":"Deng and Mahdavi (2021)"},{"why":"Introduces the excess primal generalization gap, the metric used in the PL-SC section.","marker":"Ozdaglar et al. (2022)"},{"why":"Provides the smoothness and Lipschitz-continuity properties of the primal function via the maximizer, a key ingredient in the excess primal gap proof.","marker":"Lin et al. (2020)"},{"why":"Supplies the spectral bound on powers of the mixing matrix that underpins the consensus-term estimates.","marker":"Wang and Joshi (2021)"}],"fun_headline_variants":["Stability controls generalization in distributed minimax","Consensus contraction fixes distributed SGDA's gap","Stable averaging: distributed minimax generalization","New rates tie stability to unseen data accuracy","Distributed SGDA: stability drives generalization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The PL-strongly-concave population-risk bound rests on a hidden condition on the function geometry: the proof requires $\\mu^4 > 32L^2$ and $\\rho > \\mu/4$, and if either fails, the excess primal empirical risk bound that feeds Theorem 7 is not established.","fun_headline_variants_meta":{"raw":{"variants":["Stability controls generalization in distributed minimax","Consensus contraction fixes distributed SGDA's gap","Stable averaging: distributed minimax generalization","New rates tie stability to unseen data accuracy","Distributed SGDA: stability drives generalization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000177,"raw_usage":{"total_tokens":1368,"prompt_tokens":1093,"completion_tokens":275,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":709,"completion_tokens_details":{"reasoning_tokens":208}},"tokens_in":709,"tokens_out":275,"duration_ms":3734,"temperature":1.0,"reasoning_tokens":208,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T20:43:40.963367+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Distributed-SGDA on a synthetic PL-strongly-concave minimax problem with parameters chosen so that $\\mu^4 \\le 32L^2$ or $\\rho \\le \\mu/4$ and measure the excess primal population risk under the paper's decaying schedule; if the stated rate still holds, the hidden condition is unnecessary, and if it does not, the theorem is confined to that regime. Separately, with fixed $\\eta$ and varying $K$, measure argument stability on neighbouring datasets to test the predicted $O(\\eta K^2)$ growth.","supporting_citations":[],"review_version":1}