{"id":"bb31f6a4-f271-43f6-9dfb-0d10e482461c","arxiv_id":"2508.07505","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"DPMixSGD injects calibrated Gaussian noise into local gradient estimates to make decentralized nonconvex-strongly-concave min-max optimization differentially private, while claiming to preserve the STORM convergence rate.","lead":"DPMixSGD adds calibrated Gaussian noise to the STORM-based decentralized min-max optimizer DM-HSGD, claiming to preserve its convergence while providing differential privacy. The paper proves convergence bounds with noise terms, claims a (θ,γ)-DP guarantee, and reports experiments on logistic regression and image classification.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Privacy theorem is stated under SC-SC (Assumption 6), contradicting the paper's nonconvex-strongly-concave setting (Assumption 5); the authors' own remark defers a fix, so the DP guarantee is formally unproven for the main claim.","rationale":"The reader's weakest assumption identifies exactly the gap I would flag: the privacy theorem is stated under Assumption 6, which is strictly stronger than the nonconvex-strongly-concave assumption used for convergence. Since the abstract and introduction claim privacy for nonconvex decentralized min-max, and since the paper's own remark admits the restriction and defers a fix, the central claim is not supported by the stated theorems. This is the single most load-bearing issue because it voids the primary contribution — a privacy guarantee in the claimed setting — rather than merely affecting the convergence rate. I also note secondary concerns, including the hidden κ ≤ 1 condition used in Appendix A.2 (where the text says 'by the definition of κ = L/μ ≤ 1') and the informal 'we assume that the maximum value of α_M_t(λ) is no greater than twice the average of its sum' in the moments accountant proof. These strengthen the case for rejection, but the Assumption 6 mismatch is the decisive one. If the re-derivation in the concrete test succeeds, the paper could be repaired by restating the privacy theorem under weaker assumptions; if it fails, the paper's main claim is unproven. Either way, the current manuscript does not support the central claim, so the reader's REJECT verdict stands.","tokens_in":49261,"tokens_out":5115,"duration_ms":53276,"concrete_test":"Independently re-prove Theorem 2 with Assumption 6 replaced by Assumptions 5 and 7 (nonconvex-strongly-concave + bounded gradients). Track every use of ρ-strong convexity in x in Appendix B and in the reduction to Lemma 1. If the proof goes through unchanged, the issue is a repairable theorem statement; if any step fails — e.g., the sensitivity bound or the G-Lipschitz constant requires convexity in x or compactness of iterates that only follows from SC-SC — then the DP guarantee does not cover the claimed setting, confirming the reader's rejection.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing flaw is the mismatch between the convergence and privacy theorems. Theorem 1 is proved under Assumptions 1–5, where f is nonconvex in x and μ-strongly concave in y (Assumption 5). Theorem 2 and the privacy analysis require Assumption 6, which demands ρ-strong-convexity in x as well as strong concavity in y (ρ-SC-SC). The authors explicitly write 'we focus on the ρ−SC−SC problem' in the remark after Assumption 6 and defer clarification to a revised version. Thus the central advertised result — (θ,γ)-DP for nonconvex-strongly-concave decentralized min-max — is not established by the stated theorems. Moreover, the nonconvex regularizer g(x) used in the §6.1 robust logistic regression experiments violates Assumption 6, so even the empirical setting falls outside the theorem's hypothesis. The Appendix B sensitivity calculation may not use strong convexity in a crucial way, but the theorem statement, the Lemma 1 invocation, and the G-Lipschitz derivation rely on Assumption 6 as written; this is not a cosmetic issue. A reader cannot verify the central claim from the paper as-is.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes DPMixSGD, a differentially private variant of the decentralized min-max algorithm DM-HSGD. The algorithm adds Gaussian noise to each agent's STORM-type gradient estimators before network mixing, and the authors claim two main theoretical results: (i) a convergence guarantee for nonconvex-strongly-concave decentralized min-max problems in which the privacy noise appears only as an additive O(σ_x^2 d_1 + σ_y^2 d_2) term, and (ii) an (θ,γ)-differential privacy guarantee for the same algorithm. The paper further claims that, with a suitable choice of privacy budget, the noise does not change the SFO complexity of the non-private DM-HSGD algorithm. Experiments on robust logistic regression and on AUROC/DLG-attack benchmarks are used to support the claims.","tokens_in":49499,"tokens_out":17379,"duration_ms":186459,"significance":"If the theoretical claims were correct, this would be a useful contribution: decentralized differentially private min-max optimization with variance reduction and a convergence rate matching the non-private baseline is an interesting and timely problem. The paper does contain a substantial amount of technical machinery: a noise-aware re-derivation of the DM-HSGD convergence bounds, a moments-accountant/Rényi-divergence privacy analysis, and empirical comparisons including a DLG-attack evaluation. These are useful building blocks. However, the central advertised result — differentially private nonconvex-strongly-concave decentralized min-max with essentially no extra cost — is not established by the theorems as stated. The two most important problems are a formal mismatch between the convergence setting and the privacy-assumption setting, and an internal inconsistency between the privacy noise scale stated in Theorem 2 and the convergence analysis in Theorem 1.","major_comments":[{"comment":"Theorem 2 is stated under Assumption 6, which requires the objective to be ρ-strongly-convex-strongly-concave (ρ-SC-SC) in both x and y. This contradicts the setting of Theorem 1 and of the paper's stated contributions, where f is nonconvex in x and μ-strongly concave in y (Assumption 5). The authors themselves write, immediately after Assumption 6, 'In this paper, we focus on the ρ−SC−SC problem', and defer clarification to a revised version. Thus the (θ,γ)-DP guarantee is not proven for the nonconvex-strongly-concave setting advertised in the abstract and introduction. Moreover, the robust logistic regression objective in Section 6.1 contains a nonconvex regularizer g(x)=λ_2 Σ α x_i^2/(1+α x_i^2), so the experiments do not instantiate Assumption 6 either. This is a load-bearing gap, not a cosmetic one.","section":"Section 5.2, Theorem 2 and Assumption 6"},{"comment":"The privacy noise scale in Theorem 2 is σ_x,σ_y = O( L_g sqrt(8T(T+1)(2T+1)/3 + 4T) log(1/γ)/(2 θ sqrt(m)) ), which is of order O(L_g T^{3/2} log(1/γ)/(θ sqrt(m))). The Remark claims that by choosing θ = Ω(L_g d^{1/2} log(1/γ)^{1/2}/(m^{1/2} ε^4)), the noise-induced error is O(ε^2), citing Eq. (20). But Eq. (20), L_g^2 d log(1/γ)/(θ^2 m ε^6)=O(ε^2), does not involve T at all. Substituting the Theorem 2 value of σ into the convergence bound of Theorem 1 gives a noise term of order T^3 ε^8/m (up to constants and log factors). With the T chosen in Theorem 1, T = 1500κ^3/((1-λ)^2 ε β_x), which for m ≤ 1/ε is O(κ^3/(m ε^3)), this noise term diverges as ε→0 rather than converging as O(ε^2). Therefore the main claim that the DP noise does not change the SFO complexity is not supported by the stated theorems.","section":"Section 5.2, Theorem 2 and Remark (Eqs. (18)-(20))"},{"comment":"The privacy proof compares the distributions P and Q for adjacent datasets using the same state vectors x^(m)_k, y^(m)_k in both worlds. These state vectors are data-dependent outputs of previous iterations; under adjacent datasets they are not equal, and no coupling or trajectory-stability argument is provided. In addition, the derivation treats the differing sample as being used at every iteration (z^(m)_k vs z'^(m)_k for all k), whereas Algorithm 1 samples a fresh z_t at each step. The paper does not analyze subsampling/sampling amplification or the probability that the changed sample actually appears in the minibatch. Consequently the Rényi-divergence bound in Eq. (124) is not established for the actual stochastic mechanism of Algorithm 1. Since this is the technical heart of the DP guarantee, the privacy claim remains unproven as written.","section":"Appendix B, Eqs. (121)-(124)"}],"minor_comments":[{"comment":"Lemma 1 is introduced as the basis for Theorem 2, but Appendix B's proof does not actually use Lemma 1; it uses a moments-accountant/Rényi-divergence argument with a different noise schedule. The relationship between the two should be clarified, and the notation for σ_x^2 vs σ_x should be made consistent.","section":"Section 5.2, Lemma 1"},{"comment":"The DLG-attack experiment fixes σ=1 but does not report the corresponding (θ,γ) privacy budget, so it does not validate the DP guarantee of Theorem 2 or allow a quantitative comparison with the theoretical analysis.","section":"Section 6.2"},{"comment":"The gradient-clipping experiment clips the 'top 20% of gradients' but does not define the clipping operation, threshold, or its effect on the sensitivity bounds used in the privacy proof. This makes the empirical claim of DP harder to interpret.","section":"Appendix C.1"},{"comment":"The bound is written as O(ε^2)+O(mε^2)+O(σ_x^2 d_1+σ_y^2 d_2). Since m≥1, the first two terms are simply O(mε^2). The subsequent SFO-complexity claim depends delicately on whether m≤O(ε^{-1}) or not; this should be stated explicitly rather than leaving the reader to infer it from the remark.","section":"Theorem 1, first display"}],"recommendation":"reject","confidential_remarks":"The paper contains a frank acknowledgement that its privacy analysis is for ρ-SC-SC while its convergence analysis is for nonconvex-strongly-concave, and the authors defer a fix to a revised version. Even setting that mismatch aside, the privacy noise in Theorem 2 scales as T^{3/2}, which cannot be reconciled with the convergence theorem's T ~ ε^{-3} choice if one wants O(ε^2) optimization error. This is not a routine referee request for more experiments; the main theorems, as stated, do not imply the paper's central claims. I would need to see a substantially revised theoretical treatment before reconsidering."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things up front. The algorithm is a real new combination: STORM variance reduction plus per-agent Gaussian noise for decentralized min-max, and the convergence proof actually tracks the extra noise terms through the DM-HSGD machinery. That part is substantial. The problem is the privacy guarantee doesn't cover the setting the paper advertises. Theorem 2 is proved under Assumption 6, which is ρ-SC-SC (strong convexity in x as well as strong concavity in y). The rest of the paper, including Theorem 1 and the experiments, assumes only nonconvex-strongly-concave (Assumption 5). The authors themselves write \"we focus on the ρ−SC−SC problem\" in the remark after Assumption 6 and defer a clarification to a revised version. That is a load-bearing mismatch, not a stylistic one. The central claim—that this algorithm gives (θ,γ)-DP for nonconvex-strongly-concave decentralized min-max—is not established by the stated theorems.\n\nOn the convergence side, there's a second issue: the proof uses κ = L/μ ≤ 1 to simplify bounds, but for a μ-strongly concave and L-smooth problem you typically have μ ≤ L, so κ ≥ 1. That condition is generally false and is used in the simplification. The privacy proof also leans on an informal \"we assume\" about the maximum per-step moment, which is not a rigorous moments accountant argument.\n\nGive credit where due: the noise-aware convergence analysis is a genuine extension of Xian et al., the noise terms are carried through to explicit bounds, and the experiments, while without error bars, show the algorithm works in practice and resists DLG reconstruction. The combination of DP and STORM for decentralized min-max is new and worth having.\n\nBut as it stands, the paper's main advertised theorem cannot be verified from the text. The fix is likely feasible—extend the privacy analysis to the nonconvex-strongly-concave case or explicitly reframe the paper's setting as SC-SC and adjust the convergence proof accordingly—but until then, the claims outrun the proofs.\n\nWho is this for? Researchers working on differentially private distributed optimization. It's a useful pointer to a possible algorithm, and a nice case study in how to check that a privacy theorem's assumptions actually match the optimization setting. I'd bring it to a reading group for that reason. I'd send it to peer review, because the flaws are identifiable and fixable and the topic matters, but I'd expect a major revision that either fixes the privacy theorem or re-scopes the paper honestly.","headline":"A real new algorithm combination, but the privacy theorem's SC-SC assumption contradicts the advertised nonconvex-strongly-concave setting, so the main claim is unproven as written.","tokens_in":50055,"tokens_out":3251,"would_cite":false,"duration_ms":35133,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C47"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that adding noise for differential privacy need not slow decentralized min-max optimization: DPMixSGD keeps the non-private algorithm's convergence rate and query complexity while achieving formal differential privacy.","keywords":["decentralized min-max optimization","differential privacy","STORM variance reduction","nonconvex-strongly-concave","gradient tracking","gradient perturbation","DLG attacks","multi-agent learning"],"falsifier":"Run DPMixSGD on a two-agent version of the paper's own robust-logistic-regression task, whose nonconvex regularizer $g(x)=\\lambda_2\\sum_i \\alpha x_i^2/(1+\\alpha x_i^2)$ violates Assumption 6; with $\\theta,\\gamma$ as in Theorem 2, repeat on adjacent datasets and estimate the total-variation distance between output distributions. Exceeding the claimed $(\\theta,\\gamma)$ bound falsifies the privacy guarantee in the advertised nonconvex-strongly-concave setting. A cheaper algebraic check: substitute Theorem 2's noise level into Theorem 1's additive term $\\sigma_x^2 d_1+\\sigma_y^2 d_2$ at the $T$ va","tokens_in":49048,"feed_emoji":"🔒","tokens_out":28104,"duration_ms":236065,"temperature":0.7,"pith_summary":"This paper asks whether differential privacy can be added to decentralized min-max optimization — the setting where many agents jointly solve $\\min_x \\max_y f(x,y)$ by exchanging gradient-like updates over a network — without degrading the speed of the underlying optimizer. Its answer is yes: DPMixSGD builds on the STORM-based DM-HSGD algorithm and injects calibrated Gaussian noise into each agent's local gradient before communication; the authors prove the average gradient-norm error stays at $O(\\epsilon^2)$ once the privacy budget is set as in Theorem 2, and the non-private algorithm's first-order oracle complexity is unchanged. Why this matters: shared gradient updates over untrusted networks can leak training data, so a method that bounds both privacy loss and optimization error makes min-max workflows (adversarial training, AUC maximization, robust regression) viable in privacy-sensitive domains like healthcare and finance. The paper backs the theory with experiments showing AUROC on par with or better than non-private baselines and visibly degraded gradient-inversion reconstructions.","feed_headline":"Privacy noise costs nothing in this decentralized min-max method","feed_subtitle":"Local gradient noise preserves convergence speed and resists gradient-inversion attacks on shared updates.","key_machinery":"Each agent adds Gaussian noise $n^{(i)}_{x,t}, n^{(i)}_{y,t}$ with variances $\\sigma_x^2 I_{d_1}, \\sigma_y^2 I_{d_2}$ to its STORM gradient estimators; averaged across agents this is $N_{x,t}\\sim\\mathcal{N}(0,\\sigma_x^2 I_{d_1}/m)$, so the mean update $\\bar{x}_{t+1}=\\bar{x}_t-\\eta_x(\\bar{g}_t+N_{x,t})$ sees variance divided by $m$, adding only $O(\\sigma_x^2 d_1+\\sigma_y^2 d_2)$ to the error bound. This averaging keeps the perturbation from destabilizing the saddle-point dynamics. The STORM momentum recursion induces a Lipschitz constant $G\\le L/\\beta_x$ used by the privacy proof, and gradient tracking over the doubly stochastic mixing matrix $W$ (spectral gap $\\lambda$) controls consensus er","core_discovery":"The paper's central claim is that privacy noise can enter a fast decentralized min-max algorithm as a bounded additive perturbation. Theorem 1 states that, under Lipschitz smoothness, bounded variance, $\\mu$-strong concavity in the dual variable, and a spectral gap on the mixing matrix, DPMixSGD's average squared gradient norm of $\\Phi$ is $O(\\epsilon^2)+O(m\\epsilon^2)+O(\\sigma_x^2 d_1+\\sigma_y^2 d_2)$. Theorem 2 sets the noise variances so the algorithm is $(\\theta,\\gamma)$-differentially private; with $\\theta=\\Omega(L_g d^{1/2}\\log^{1/2}(1/\\gamma)/(m^{1/2}\\epsilon^4))$ the noise term shrinks to $O(\\epsilon^2)$. Conclusion: privacy noise does not change the DM-HSGD baseline's oracle complex","pith_inferences":["If the noise-averaging mechanism is right, privacy against gradient-inference attacks should strengthen as the network grows, because the averaged perturbation seen by the mean update has variance $\\sigma^2/m$; the reported $m=5$ to $m=20$ grids show only a weak trend, so a dedicated scaling study would test this directly.","The privacy accounting composes per-round Rényi divergences using the worst-case Lipschitz bound $G\\le L/\\beta_x$; a moment accountant that exploits the geometric decay $(1-\\beta_x)^{t-k}$ in the STORM recursion could reduce the required $\\sigma$ for the same $(\\theta,\\gamma)$, a tightening available within the paper's own proof structure.","The additive-noise argument is architectural: any decentralized variance-reduced method whose mean estimator is an average of local estimators (SARAH/SPIDER-style gradient tracking) should inherit an $O(\\sigma^2 d)$ noise term, so the no-complexity-cost conclusion plausibly transfers beyond STORM.","Because the privacy theorem assumes strong convexity in both variables while the experiments use a nonconvex regularizer, the nonconvex results are best read as stress tests of the algorithm rather than as evidence for the $(\\theta,\\gamma)$ bound itself; the paper's own remark after Assumption 6 flags exactly this gap as the direction to close."],"forward_implications":["At the stated parameter settings, DPMixSGD is $(\\theta,\\gamma)$-differentially private with optimization error $O(\\epsilon^2)$, so the privacy noise does not change the asymptotic accuracy of the non-private optimizer.","For networks of up to $O(\\epsilon^{-1})$ agents the stochastic first-order oracle complexity remains $O(\\kappa^3\\epsilon^{-3})$, identical to DM-HSGD, so the worst-case gradient-query cost does not rise when privacy is enforced.","Privacy is enforced locally, each agent perturbing its own gradient before communication, so no trusted central aggregator is needed, unlike centralized differentially private min-max methods such as DP-SGDA.","In the reported experiments the method matches or surpasses the AUROC of SGDA, DM-HSGD, and DP-SGDA on robust logistic regression over a8a, a9a, and CIFAR-10 and on Fashion-MNIST classification, and its noise visibly degrades DLG gradient-inversion reconstructions at noise level $\\sigma=1$."],"supporting_citations":[{"why":"The DM-HSGD algorithm and its SFO complexity $O(\\kappa^3\\epsilon^{-3})$ that DPMixSGD builds on and must match; its convergence analysis is re-derived with noise terms added.","marker":"[74]"},{"why":"Supplies the STORM momentum variance-reduction estimator that defines the gradient updates $g^{(i)}_t$ and $h^{(i)}_t$ in Algorithm 1.","marker":"[16]"},{"why":"Lemma 1, the single-parameter DP-GD Gaussian-noise bound that Theorem 2 directly adapts to the x and y updates.","marker":"[71]"},{"why":"Lemma 4.3, giving smoothness of $\\Phi(x)=\\max_y f(x,y)$ and $\\kappa$-Lipschitzness of $y^*(\\cdot)$, the basis of the $\\epsilon$-stationary convergence criterion.","marker":"[49]"},{"why":"DP-SGDA, the centralized differentially private min-max baseline the paper contrasts with and must beat in experiments.","marker":"[79]"},{"why":"The moments accountant (composability and tail-bound lemmas) used in the proof of the privacy guarantee.","marker":"[1]"},{"why":"Defines the Rényi divergence used to bound each round's privacy loss in the proof of Theorem 2.","marker":"[10]"},{"why":"Gives the definition of $(\\theta,\\gamma)$-differential privacy that the privacy guarantee is measured against.","marker":"[20]"},{"why":"The DLG gradient-inversion attack used to demonstrate the algorithm's empirical privacy robustness.","marker":"[87]"}],"fun_headline_variants":["Privacy noise doesn't slow this decentralized min-max solver","Adding privacy noise keeps min-max convergence intact","DP noise preserves speed in decentralized min-max","Private decentralized min-max: noise without a slowdown"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The differential-privacy guarantee is proved only under Assumption 6, which requires the objective to be strongly convex in the minimization variable as well as strongly concave in the maximization variable, whereas the convergence analysis and the advertised setting assume nonconvexity in the minimization variable; the paper's own remark after Assumption 6 concedes the mismatch and defers a fix to a revised version.","fun_headline_variants_meta":{"raw":{"variants":["Privacy noise doesn't slow this decentralized min-max solver","Adding privacy noise keeps min-max convergence intact","DP noise preserves speed in decentralized min-max","Private decentralized min-max: noise without a slowdown"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000289,"raw_usage":{"total_tokens":1548,"prompt_tokens":784,"completion_tokens":764,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":528,"completion_tokens_details":{"reasoning_tokens":706}},"tokens_in":528,"tokens_out":764,"duration_ms":6368,"temperature":1.0,"reasoning_tokens":706,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T22:05:08.296127+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run DPMixSGD on a two-agent version of the paper's own robust-logistic-regression task, whose nonconvex regularizer $g(x)=\\lambda_2\\sum_i \\alpha x_i^2/(1+\\alpha x_i^2)$ violates Assumption 6; with $\\theta,\\gamma$ as in Theorem 2, repeat on adjacent datasets and estimate the total-variation distance between output distributions. Exceeding the claimed $(\\theta,\\gamma)$ bound falsifies the privacy guarantee in the advertised nonconvex-strongly-concave setting. A cheaper algebraic check: substitute Theorem 2's noise level into Theorem 1's additive term $\\sigma_x^2 d_1+\\sigma_y^2 d_2$ at the $T$ va","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The DM-HSGD algorithm and its SFO complexity $O(\\kappa^3\\epsilon^{-3})$ that DPMixSGD builds on and must match; its convergence analysis is re-derived with noise terms added."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Lemma 1, the single-parameter DP-GD Gaussian-noise bound that Theorem 2 directly adapts to the x and y updates."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Lemma 4.3, giving smoothness of $\\Phi(x)=\\max_y f(x,y)$ and $\\kappa$-Lipschitzness of $y^*(\\cdot)$, the basis of the $\\epsilon$-stationary convergence criterion."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"DP-SGDA, the centralized differentially private min-max baseline the paper contrasts with and must beat in experiments."},{"cited_title":"Dwork and A","cited_arxiv_id":null,"evidence_quote":"Gives the definition of $(\\theta,\\gamma)$-differential privacy that the privacy guarantee is measured against."}],"review_version":1}