{"id":"1b680451-58f3-4f3d-85b4-191951a5158a","arxiv_id":"2505.10631","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper introduces DGTA and DSGTA, decentralized gradient tracking algorithms for nonconvex strongly concave min-max problems with per-agent y variables, and proves O(κ²/ε²) iteration and O(κ³/ε⁴) sample complexity, though the headline rates omit spectral-gap factors.","lead":"This paper proposes two decentralized gradient-tracking algorithms for min-max optimization where each agent optimizes its own maximization variable. The authors derive convergence rates that they claim match centralized methods up to network-dependent terms.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 4.1.2's b=1 sample complexity is unsupported: the variance floor in Theorem 4.1 is O(1) under the stated step sizes, so the O(kappa^2 epsilon^-4) claim does not follow.","rationale":"I read the paper as establishing convergence rates for a novel decentralized min-max formulation. The core DGTA and large-batch DSGTA results appear structurally coherent: the Lyapunov function couples the descent, delta, consensus, and tracking recursions, and the rates in Tables 1 and 2 are consistent with Theorem 4.1 up to spectral-gap factors. The abstract's O(kappa^2 epsilon^-2) and O(kappa^3 epsilon^-4) phrasing is defensible if the spectral gap is treated as a graph-dependent constant, so I do not rest the objection on that wording. The reader's weakest assumption (compact Y_i) is not a defect: Assumption 2.3 explicitly assumes compactness, and unbounded sets are outside the paper's scope. The concrete flaw is in Corollary 4.1.2. Under its T-dependent step sizes, both eta_x and eta_y are Theta(T^{-1/2}), so the variance-floor term in Theorem 4.1 involving 1/(eta_y^2 mu^2) is asymptotically O(1), not o(1). The proof of Corollary 4.1.2 replaces this floor with an O(1/T) term; this replacement would require eta_y mu bounded below by a positive constant, which contradicts the chosen eta_y as T grows. Thus the b=1 sample complexity O(kappa^2 epsilon^-4), independent of the graph, is not supported by the presented analysis. The main theorems may survive, but Corollary 4.1.2 and Remarks 4.3 and 4.5 need correction or qualification; hence the conditional verdict.","tokens_in":23307,"tokens_out":28954,"duration_ms":253411,"concrete_test":"Specialize to n=1, lambda=0, L=mu=1, kappa=1, D=sigma=Delta_Phi=1, b=1 (centralized SGDA). Substitute the Corollary 4.1.2 step sizes eta_x = 1/(sqrt(T)+gamma), eta_y = 1/(18+sqrt(3T)). Evaluate the floor term F_1 = 64 eta_x^2 kappa^2 L^2 sigma^2 / (eta_y^2 mu^2) from (4.1) at T=10^4 and T=10^8. It does not decay to zero; asymptotically it approaches 192. If F_1 is O(1), the averaged-gradient bound in (4.1) cannot be driven below epsilon^2 for arbitrarily small epsilon, so the b=1 sample complexity in Remark 4.3 is unsupported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The load-bearing issue is in Corollary 4.1.2 (constant batch size b=1). Theorem 4.1's bound (4.1) contains the additive variance floor F = [1/(n eta_y^2 mu^2) + 225/(1-lambda^2)^3 + 54 eta_x^2 kappa^2 L^2/(n(1-lambda^2) eta_y mu)] * 64 eta_x^2 kappa^2 L^2 sigma^2 / b. For the b=1 step sizes of Corollary 4.1.2, eta_y = 1/(9(L+mu)sqrt(1-lambda^2)+sqrt(3T sigma^2/D^2)) and eta_x = 1/(sqrt(L kappa sigma^2 T/(n Delta_Phi)) + gamma), so both eta_x and eta_y are Theta(T^{-1/2}) for large T. Consequently the first term of F is asymptotically positive and independent of T: it equals 192 kappa^2 sigma^2 Delta_Phi/(mu D^2) in the leading asymptotics (up to the constants in Corollary 4.1.2). Hence the right-hand side of (4.1) has a positive limit, and the claim of O(kappa^2 epsilon^-4) sample complexity with b=1 (Remark 4.3) is not established. In the proof of Corollary 4.1.2, this floor is replaced by an O(1/T) expression; that replacement requires eta_y mu to be bounded below by a positive constant, which is false for the stated T-dependent eta_y as T grows. The abstract's spectral-gap wording is a separate presentation concern; the b=1 proof gap is more concrete.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the decentralized min-max problem (1.1), in which agents jointly minimize a shared variable x while maximizing their own local variables y_i over possibly heterogeneous constraint sets Y_i, under nonconvex-strongly-concave (NC-SC) smooth objectives. Two algorithms are proposed: DGTA, which uses full gradients with gradient tracking, and DSGTA, which uses mini-batched stochastic gradients. The authors claim that DGTA reaches an ε-first-order stationary point in O(κ^2 ε^{-2}) iterations and that DSGTA has sample complexity O(κ^3 ε^{-4}) with large batches and O(κ^2 ε^{-4}) with constant batch size b=1, matching centralized GDA/SGDA up to network-dependent constants. The analysis is based on a Lyapunov function combining the primal descent, the errors δ^t = sum_i ||\\hat y_i(\\bar x^t) - y_i^t||^2, the consensus error, and the gradient-tracking error. Numerical experiments on an empirical Wasserstein robustness model with MNIST data compare DGTA with GT/DA and study DSGTA under different step sizes. The appendix contains detailed proofs of the lemmas and corollaries.","tokens_in":23671,"tokens_out":13901,"duration_ms":130760,"significance":"The paper's formulation with heterogeneous y_i and Y_i is a genuine extension of the common decentralized min-max formulation, and the proposed algorithms avoid bounded-heterogeneity assumptions on stochastic gradients. The Lyapunov analysis is systematic, and the appendix provides full finite-time proofs for the deterministic and large-batch stochastic results. If the advertised constant-batch (b=1) complexity were correct, it would be a notable improvement in the dependence on the network spectral gap. However, the proof of Corollary 4.1.2 contains a substantial gap: a variance term that is asymptotically a positive constant is bounded as if it were O(1/T). In addition, the abstract's κ-only rates omit explicit spectral-gap factors that appear in the paper's own tables and corollaries. These issues affect central claims and must be fixed before the paper is suitable for publication.","major_comments":[{"comment":"The claimed O(κ^2 ε^{-4}) sample complexity with b=1 is not established. Under the step sizes stated in Corollary 4.1.2, for large T one has η_y ≈ D/√(3σ^2 T) and η_x ≈ √(n Δ_Φ/(L κ σ^2 T)). Substituting these into the first additive variance term of (4.1), namely (1/(n η_y^2 μ^2)) · 64 η_x^2 κ^2 L^2 σ^2, gives an asymptotic constant of order Δ_Φ κ L σ^2/(μ^2 D^2), not a vanishing term. Hence the right-hand side of (4.1) has a positive limit as T→∞, so the bound cannot imply E‖∇Φ(\\bar x^t)‖^2 ≤ ε^2 with T = O(κ^2 ε^{-4}). In the proof of Corollary 4.1.2 this term is replaced by a multiple of n Δ_Φ κ L / T; that replacement requires 1/(η_y^2 μ^2) = O(1), whereas the chosen η_y satisfies η_y^2 μ^2 = O(1/T). Because the b=1 row of Table 2 and Remark 4.3 depend directly on this step, the proof must be corrected or the step-size choices revised.","section":"Corollary 4.1.2 / Theorem 4.1"},{"comment":"The abstract and Section 1.2 state that DGTA achieves O(κ^2 ε^{-2}) and that both algorithms match centralized counterparts up to constant factors related to the communication network. However, Corollary 4.1.1 and Remark 4.2, as well as Table 1, give rates containing explicit factors such as 1/(1−λ)^2 and 1/√(1−λ). For sparse graphs 1/(1−λ) can grow as O(n^2), so these factors are not bounded by a constant independent of the network size. The headline complexity statements should either explicitly include the spectral-gap dependence or clearly specify the class of graphs over which the stated constants are uniform.","section":"Abstract / Remark 4.2 / Table 1"}],"minor_comments":[{"comment":"In the statement of Lemma 3.5, Eq. (3.4), and the final display of Appendix A.5, the expression ∇Φ(\\bar x^2) should be ∇Φ(\\bar x^t); the superscript t is missing.","section":"Lemma 3.5 and Appendix A.5"},{"comment":"The sentence before Lemma 3.4 says 'whose recursion is stated in Lemma 3.3' but should refer to Lemma 3.4.","section":"End of Section 3"},{"comment":"The heading of Corollary 4.1.1 says 'DSGT' instead of 'DGTA'.","section":"Corollary 4.1.1"},{"comment":"In the discussion of Figure 1b, the sentence 'since the full gradient computation requires.' is incomplete and should be finished.","section":"Section 5"},{"comment":"The claim that (4.9) reduces to O(Δ_Φ L κ σ^2/(n ε^4) + D^2 σ^2 L^2 κ^2/ε^4) when ε is small should state the threshold condition on ε relative to the other terms in the bound.","section":"Remark 4.3, Eq. (4.9)"}],"recommendation":"major_revision","confidential_remarks":"The b=1 result is a headline contribution in the abstract and Table 2, and the current proof of Corollary 4.1.2 contains a concrete asymptotic error that cannot be patched by wording alone. The deterministic and large-batch portions of the analysis appear sound, so the paper is likely fixable, but the authors should be asked to re-derive the constant-batch tuning or to remove the claim if a valid tuning cannot be found. The spectral-gap overstatement in the abstract is also worth addressing explicitly in the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The new formulation in Problem (1.1) is real: letting each agent have its own y_i and its own constraint set Y_i is a meaningful departure from the consensus-y setup in earlier decentralized min-max papers, and it fits applications like distributed GANs and WRM. The deterministic algorithm DGTA is also well designed: single-loop, gradient tracking on x, projected ascent on each local y, and the Lyapunov analysis in Section 3 is coherent and detailed. I believe the deterministic rate in Corollary 4.1.1, with its explicit 1/(1-λ) factors, is essentially correct. The large-batch stochastic result (Corollary 4.1.3) also looks like a valid consequence of Theorem 4.1 when η_y is constant and b = O(κσ²/ε²), giving the advertised O(κ³ε⁻⁴) sample complexity. That part is worth a serious referee.\n\nThe soft spots are real and one is load-bearing. First, the abstract overclaims: it says O(κ²ε⁻²) and O(κ³ε⁻⁴) matching centralized methods, but the theorems carry spectral-gap terms 1/(1-λ) and 1/(1-λ)². For sparse graphs with 1-λ ~ 1/n², those are not constant factors. The tables in the body are honest, but the abstract and Remark 4.3 should be aligned with the theorems. Second, and more concretely, Corollary 4.1.2 (b = 1) is not established. Theorem 4.1 contains the variance floor F = [1/(nη_y²μ²) + ...] · 64η_x²κ²L²σ²/b. Under the b = 1 step sizes, both η_x and η_y decay as T^{-1/2}, so the 1/(nη_y²μ²) term times η_x² is O(1), not O(1/T). The proof of Corollary 4.1.2 replaces this expression with O(1/T) terms, and to do that it needs a lower bound on η_y μ that is false for large T. So the constant-batch-size O(κ²ε⁻⁴) sample complexity does not follow. The typos (e.g., ∇Φ(¯x²) in Lemma 3.5) and the missing error bars and code are minor by comparison.\n\nMy bottom line: the paper deserves peer review because the deterministic contribution and the large-batch stochastic analysis are valuable and likely correct, and the new formulation is worth citing. But the b = 1 result should be corrected, weakened, or removed, and the abstract should state the network dependence. I would send it to referees with that expectation.","headline":"A genuinely new per-agent-y formulation with a solid deterministic analysis, but the constant-batch-size stochastic claim is not supported by the paper's own bound.","tokens_in":24178,"tokens_out":5083,"would_cite":true,"duration_ms":40041,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C47","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Decentralized min-max optimization matches centralized convergence rates.","keywords":["decentralized min-max optimization","gradient tracking","nonconvex strongly concave","stochastic gradient method","iteration complexity","sample complexity","heterogeneous constraint sets"],"falsifier":"Use Corollary 4.1.1 to compute the iteration bound on a family of graphs with shrinking spectral gap (e.g., rings of increasing size). If the number of iterations to reach $\\|\\nabla\\Phi(\\bar{x})\\|^2 \\le \\varepsilon^2$ scales like $\\kappa^2/\\varepsilon^2$ times a constant independent of $n$, the headline claim is exactly right; if it scales like $n^2\\kappa^2/\\varepsilon^2$, then the graph dependence is a genuine factor, not a constant. This is a direct check from the displayed bounds in the paper.","tokens_in":23091,"feed_emoji":"🌐","tokens_out":8211,"duration_ms":68890,"temperature":0.7,"pith_summary":"This paper proposes a distributed formulation of min-max optimization in which each agent optimizes its own maximization variable under its own constraint set, while agents coordinate only on the shared minimization variable. The authors present two gradient-tracking algorithms—DGTA with full gradients and DSGTA with stochastic gradients—and prove that, for nonconvex strongly concave objectives, they reach an $\\varepsilon$-first-order stationary point with iteration complexity $O(\\kappa^2\\varepsilon^{-2})$ and sample complexity $O(\\kappa^3\\varepsilon^{-4})$, matching centralized gradient descent ascent up to network-dependent constants. If correct, decentralized training can accommodate heterogeneous local adversaries or data domains without giving up centralized convergence guarantees.","feed_headline":"Decentralized min-max matches centralized speed","feed_subtitle":"Two gradient-tracking methods let each agent keep its own adversary variable—and still converge at centralized rates.","key_machinery":"The engine is the gradient tracker, updated in DGTA by $g_i^{t+1} = \\sum_{j \\in \\mathcal{N}_i} w_{ij}(g_j^t + \\nabla_x f_i(x_i^{t+1}, y_i^{t+1}) - \\nabla_x f_i(x_i^t, y_i^t))$, which lets every agent estimate the average of the local $x$-gradients without a coordinator. Around it, the paper builds the Lyapunov function $\\mathcal{L}^t = \\Phi(\\bar{x}^t) - \\Phi^* + \\frac{300\\kappa^2 L^2 \\eta_x}{n(1-\\lambda^2)}\\|x^t - \\bar{x}^t\\|^2 + \\frac{8\\eta_x L^2}{n\\eta_y \\mu}\\delta^t + \\frac{2400\\eta_x^3\\kappa^2 L^2}{n(1-\\lambda^2)^3}\\|g^t - \\bar{g}^t\\|^2$. The coefficients are chosen so that Lemmas 3.1–3.4 combine into a single contraction (Lemma 3.5), turning the four coupled error terms into one step-size-dependent descent on the smoothed function $\\Phi$.","core_discovery":"The central claim is that problem (1.1) — $\\min_x \\max_{\\{y_i\\}} \\frac{1}{n} \\sum_{i=1}^n f_i(x,y_i)$ with agent-specific $y_i$ and constraint sets $Y_i$ — can be solved by a single-loop decentralized method in which only $x$ is averaged over the network while each $y_i$ is updated by one projected gradient ascent step and never communicated. The paper proves this through a Lyapunov analysis: the gradient tracker keeps each agent's $g_i$ close to the average $x$-gradient, and the coupled recursions for the function value, consensus gap, maximizer gap $\\delta^t = \\sum_i \\|\\hat{y}_i(\\bar{x}^t) - y_i^t\\|^2$, and tracker disagreement all contract together. The resulting rates match the centralized GDA/SGDA results in [17] up to factors involving the spectral gap $1-\\lambda$ of the mixing matrix, and the analysis requires no bounded-heterogeneity or bounded-second-moment assumptions.","pith_inferences":["I infer that the advertised 'match up to constant factors' should be read with the spectral gap in mind: Corollary 4.1.1 contains $1/(1-\\lambda)^2$ terms, so on a sparse ring with $1-\\lambda = O(1/n^2)$ the complexity can degrade like $n^2\\kappa^2/\\varepsilon^2$, which is more than a constant-factor gap.","I infer the heterogeneous-$y_i$ formulation is a natural fit for personalized federated learning and multi-domain GANs, where a single shared discriminator variable is unrealistic; the single-loop projected ascent on $y_i$ is what makes the method practical.","A testable extension is to replace the deterministic projection step with variance-reduced stochastic updates for $y_i$; the Lyapunov recursion suggests $O(\\varepsilon^{-3})$ sample complexity might be reachable.","Because the paper's $b=1$ sample complexity loses the $1/(1-\\lambda)$ factor, I infer that in communication-heavy regimes small or moderate batch sizes are preferable even if iteration counts rise."],"forward_implications":["DGTA attains iteration complexity $O(\\kappa^2\\varepsilon^{-2})$ for full gradients, the same order as centralized GDA, with the network entering only through spectral-gap factors.","DSGTA with batch size $b = \\kappa\\sigma^2/\\varepsilon^2$ attains sample complexity $O(\\kappa^3\\varepsilon^{-4})$, matching centralized SGDA.","With batch size $b=1$, DSGTA attains sample complexity $O(\\kappa^2\\varepsilon^{-4})$ for small $\\varepsilon$, independent of the graph and better in $\\kappa$ than the large-batch regime.","The methods handle heterogeneous constraint sets $Y_i$ across agents without consensus constraints on $y$ and without bounded gradient dissimilarity.","A trade-off emerges: large batches reduce iteration count, while small batches reduce dependence on the communication graph."],"supporting_citations":[{"why":"supplies the centralized GDA/SGDA iteration and sample complexity baselines that DGTA and DSGTA are claimed to match.","marker":"[17]"},{"why":"provides the distributed gradient tracking technique whose tracker recursion and analysis the proposed algorithms build on.","marker":"[27]"},{"why":"the existing decentralized GT/DA method for the consensus-y formulation; the paper's DGTA is compared with it and removes its inner y-loop.","marker":"[32]"},{"why":"supplies the lemma that each $\\Phi_i$ is $2\\kappa L$-smooth with a $\\kappa$-Lipschitz argmax, which turns the min-max problem into smooth minimization.","marker":"[19]"},{"why":"used for the projection theorem that justifies the projected gradient ascent step on each convex set $Y_i$ in the Lyapunov analysis.","marker":"[2]"},{"why":"defines the empirical Wasserstein robustness model used as the numerical testbed and as a motivation for heterogeneous $y_i$.","marker":"[31]"}],"fun_headline_variants":["Min-max without sharing your adversary","Each agent keeps its own adversary, still converges fast","Decentralized min-max: local y, global x, optimal rates","Single-loop decentralized min-max matches centralized"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that every local constraint set $Y_i$ is convex, compact, and has a common finite diameter $D$; if any $Y_i$ were unbounded, the initial distance from $y_i^0$ to its argmax could be infinite and the finite-time bound would not close.","fun_headline_variants_meta":{"raw":{"variants":["Min-max without sharing your adversary","Each agent keeps its own adversary, still converges fast","Decentralized min-max: local y, global x, optimal rates","Single-loop decentralized min-max matches centralized"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000214,"raw_usage":{"total_tokens":1398,"prompt_tokens":890,"completion_tokens":508,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":506,"completion_tokens_details":{"reasoning_tokens":460}},"tokens_in":506,"tokens_out":508,"duration_ms":5169,"temperature":1.0,"reasoning_tokens":460,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:05:48.290667+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Use Corollary 4.1.1 to compute the iteration bound on a family of graphs with shrinking spectral gap (e.g., rings of increasing size). If the number of iterations to reach $\\|\\nabla\\Phi(\\bar{x})\\|^2 \\le \\varepsilon^2$ scales like $\\kappa^2/\\varepsilon^2$ times a constant independent of $n$, the headline claim is exactly right; if it scales like $n^2\\kappa^2/\\varepsilon^2$, then the graph dependence is a genuine factor, not a constant. This is a direct check from the displayed bounds in the paper.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the centralized GDA/SGDA iteration and sample complexity baselines that DGTA and DSGTA are claimed to match."},{"cited_title":"P U AND A","cited_arxiv_id":null,"evidence_quote":"provides the distributed gradient tracking technique whose tracker recursion and analysis the proposed algorithms build on."},{"cited_title":"T SAKNAKIS , M","cited_arxiv_id":null,"evidence_quote":"the existing decentralized GT/DA method for the consensus-y formulation; the paper's DGTA is compared with it and removes its inner y-loop."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the lemma that each $\\Phi_i$ is $2\\kappa L$-smooth with a $\\kappa$-Lipschitz argmax, which turns the min-max problem into smooth minimization."}],"review_version":1}