{"id":"c77f901b-9986-45fc-aacf-9adeea7153f9","arxiv_id":"2505.22703","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"RaCO-DP is a differentially private SGDA algorithm that enforces arbitrary prediction-rate constraints, such as group fairness and false negative rate limits, using a private histogram per mini-batch while retaining non-convex convergence guarantees.","lead":"This paper introduces RaCO-DP, an algorithm that trains machine learning models under differential privacy while enforcing constraints on prediction rates, such as group fairness limits. It lets practitioners set fairness or false-negative targets directly, and reports better accuracy-fairness trade-offs than prior private fair learning methods.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Convergence guarantee covers only the no-clipping algorithm, while the actual released procedure clips per-sample gradients (Algorithm 1 Line 8), so Theorem 5.2 as stated does not apply to the evaluated method.","rationale":"The reader's weakest_assumption is exactly the gap I would stress: Theorem D.1 (and hence Theorem 5.2) is stated for Algorithm 1 run without clipping, while Algorithm 1 Line 8 and all experiments use clipping. The manuscript itself flags this in the Limitations paragraph and Figure 6, where clipping bias alone breaks a strict FNR constraint for small C. I do not see a deeper internal inconsistency in the privacy accounting (Theorem 4.1/B.1 follows the standard Laplace+Gaussian composition, and Theorem D.3 gives a Lipschitz-based accountant that supports the no-clipping guarantee). The novelty claim (first general DP framework for arbitrary rate constraints) is structurally supported by the histogram-based decomposition, and the experiments, while lacking released code and error bars, do show a Pareto improvement over the reported DP-FERMI numbers. None of the secondary issues (no code, no error bars, uncompensated hyperparameter tuning, soft-vs-hard constraints in the dual update) is as load-bearing as the clipping mismatch, because each is either standard practice in the field or clearly disclosed. So CONDITIONAL is the right verdict, and the condition should be: close the clipping gap or restate the theorem and soften the claim. The reader's CONDITIONAL with moderate confidence is appropriate; I would not move to ACCEPT or REJECT on the basis of this concern alone.","tokens_in":30460,"tokens_out":1684,"duration_ms":16985,"concrete_test":"Re-run the experiments of Figure 3/Figure 6 with the no-clipping variant that Theorem D.1 actually assumes (set C = infinity, i.e. remove Line 8's clipping while retaining the privacy noise and the fixed sensitivity argument of Theorem D.3), and compare the resulting accuracy/fairness/FNR trade-offs to the clipped runs. If the no-clipping variant fails to satisfy constraints or loses accuracy, the empirical 'Pareto-dominance' claim is owed to pruning/clipping bias and the theorem's assumption cannot be dismissed as a benign technicality. Conversely, if the no-clipping variant matches the clipped numbers, the gap is largely cosmetic and can be closed by a short remark; either outcome settles whether Theorem 5.2 covers the evaluated algorithm.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The strongest claim (Theorem 5.2, informal) is that Algorithm 1 converges to an (alpha, alpha)-stationary point of Phi with the stated rate, but the formal statement in Appendix D.2 (Theorem D.1) explicitly assumes Algorithm 1 is run without clipping, and the proof's gradient-error bound (Lemma D.4) does not account for the clipping operation in Line 8. The implemented algorithm always clips: Algorithm 1 Line 8 computes clip(g_{x,theta}, C/(r|D|)), and every experiment uses clipping (Section 6, Appendix E). The paper's own Limitations paragraph and Figure 6 show that clipping bias alone, at sigma=0 and b=infinity, can push the FNR constraint violation above 0.6 for C<=2 on Adult, i.e. far outside the feasible set. Therefore the theorem's conclusion is not established for the algorithm that is analyzed in experiments; the central claim of a first general DP rate-constrained method with a proven convergence guarantee rests on an assumption the authors themselves demonstrate is empirically violated. This is an internally documented gap, not a dispute with the community consensus, and it is addressable: either prove convergence with clipping (which Koloskova et al. 2023 suggests is hard because clipping bias persists at vanishing step sizes), or state the theorem for the no-clipping variant and soften the main-text claim to match the formal result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces RaCO-DP, a differentially private stochastic gradient descent-ascent method for minimizing an empirical loss subject to rate constraints, with group fairness constraints as the main application. The method reformulates the constrained problem through a Lagrangian, uses a generalized rate-constraint structure based on a global partition of the dataset, and privately estimates a per-mini-batch histogram at each step; the histogram is then post-processed to compute both the primal per-sample gradients and the dual constraint gradients. The paper states a privacy guarantee (Theorem 4.1), a formal convergence analysis for non-convex objectives under bias in the gradient estimates (Appendix D, Theorem D.1 and Theorem D.5), and experiments on demographic parity and false-negative-rate constraints across several tabular benchmarks, reporting Pareto improvements over DP-FERMI and near-non-private performance.","tokens_in":30766,"tokens_out":10992,"duration_ms":140893,"significance":"If the claimed convergence result were established for the actual algorithm, this would be a meaningful contribution: RaCO-DP would be the first general DP framework for arbitrary rate constraints, not just fairness, with formal privacy and convergence guarantees and a favorable empirical privacy-utility-fairness trade-off. The paper also has several genuine strengths: the histogram-based mechanism is a clean way to avoid per-constraint privacy composition; the convergence analysis is self-contained, does not rely on fitted constants, and explicitly attempts to handle biased gradient estimates; and the limitations discussion is unusually honest, including a direct demonstration that clipping bias can break constraint satisfaction. The main reason the paper cannot be accepted in its current form is that the central convergence theorem is proven only for a no-clipping variant of the algorithm, while Algorithm 1, the experiments, and the abstract all refer to the clipping-based method.","major_comments":[{"comment":"The main-text convergence claim is stated for Algorithm 1, but the formal theorem in Appendix D.2, Theorem D.1, is explicitly for 'Algorithm 1 run without clipping,' while Algorithm 1 as defined clips every per-sample gradient at Line 8 and all reported experiments use clipping. The gradient-error bound in Lemma D.4 does not model the clipping operation at all, so the proof does not establish convergence to an approximate stationary point for the algorithm whose results are actually reported. This is not a purely cosmetic mismatch: Figure 6 and the Limitations section show that clipping bias alone, with sigma=0 and b=infinity, pushes the FNR constraint violation above 0.6 for C<=2 on Adult, i.e., far outside the feasible set, and the cited work of Koloskova et al. indicates that such bias does not vanish with vanishing step sizes. The paper should either prove convergence with clipping, explicitly bound the clipping bias and its effect on the stationarity and feasibility guarantees, or formally restrict the main theorem to the no-clipping variant and correspondingly qualify the abstract, the informal Theorem 5.2, and the experimental claims.","section":"Appendix D.5, Lemma D.4; Section 4.2, Eq. (10)"},{"comment":"The notation H in Lemma D.4 needs clarification. In Section 4, H^{(t)} is defined as the mini-batch histogram (Eq. (8)), and the per-sample gradient in Eq. (10) uses H^{(t)} as the mini-batch histogram, with sum over k of H_{i,k} equal to |B∩I|. In the proof of the primal gradient error, the first term in the regularizer difference sums over x in D while normalizing by sum_{i in I, k} H_{i,k}; if H is the mini-batch histogram, this term is not the full-batch gradient ∇θR(θ,λ). If H is instead intended to be a full-batch histogram for the purposes of the proof, that should be stated explicitly and consistently. As written, the proof does not transparently derive the claimed bound relating the full-batch gradient to the private mini-batch estimator, and this gap is load-bearing for Theorem D.1.","section":"Appendix D.5, Lemma D.4; Section 4.2, Eq. (10)"}],"minor_comments":[{"comment":"The sentence 'This leads to the following result for Algorithm 1 run without clipping' should be incorporated into the theorem statement itself, so that the informal Theorem 5.2 cannot be read as applying to the clipping-based Algorithm 1 defined in Section 4.","section":"Section 5, before Theorem 5.2"},{"comment":"Please define all symbols (H versus \\widehat H, full-batch versus mini-batch histograms) before the proof, and make the decomposition of the primal regularizer error explicit: sampling error, private-histogram denominator error, and loss sampling error should be separated.","section":"Appendix D.5, Lemma D.4"},{"comment":"The statement 'we do not account for privacy loss from hyperparameter tuning' means that the reported ε values are not end-to-end privacy guarantees for the models selected via validation on the training data. This is standard in parts of the literature, but it should be stated more prominently and preferably discussed in the Limitations section.","section":"Section 6, Experimental setup"},{"comment":"The comparison with DP-FERMI uses results reported in prior work while reserving 15% of the training set for validation in the current setup. Please clarify how this difference in training-set size affects comparability, since the baseline numbers were generated under a different pipeline.","section":"Section 6, Baselines and experimental setup"},{"comment":"There are several typos and notation inconsistencies, including 'Langrangian' in Section 4.1, inconsistent use of ε versus ϵ, and the informal theorem statement referring to 'Algorithm 1' rather than 'Algorithm 1 run without clipping.' These should be corrected in a revision.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The clipping-versus-no-clipping gap is acknowledged by the authors in the Limitations section and in Figure 6, which is a genuine strength of the paper's honesty. However, the gap is central: the main convergence theorem does not apply to the algorithm whose results are reported. I recommend major revision rather than rejection because the issue is addressable by either analyzing clipping bias or explicitly restructuring the claims around the no-clipping variant. The second major comment about Lemma D.4 is partly a notation problem, but it also affects the rigor of the gradient-error bound and should be fixed in the same revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The paper has a genuinely new and useful formulation: generalized rate constraints expressed through histograms, and a DP algorithm that privatizes a single histogram per mini-batch and reuses it for both primal and dual SGDA updates. The convergence analysis for biased SGDA with a linear dual is a real theoretical contribution (T^{-1/4} instead of the earlier T^{-1/6}), and the experiments show clear Pareto gains over DP-FERMI, plus dramatic speedups. That is the good part.\n\nThe soft spot is the one the stress-test note identifies. The formal convergence theorem (D.1) is stated only for Algorithm 1 run without clipping. But the algorithm in the paper clips every per-sample gradient, and every experiment clips. The authors know this; their limitations section and Figure 6 show that clipping bias alone, with no DP noise, can push a strict FNR constraint far out of feasibility for small C. So the guarantee does not apply to the method that is actually run and evaluated. The informal theorem in the main text says \"Algorithm 1\" without the no-clipping caveat, so the abstract and intro overclaim on a casual read. This is a real, addressable gap: either analyze the clipped algorithm (hard, because the bias persists) or state the theorem for the unclipped variant and soften the claims. The paper should not present itself as proving convergence for the clipped method until that is done.\n\nMinor issues: no released code, no confidence intervals despite \"20 runs\", and the privacy cost of validation-based hyperparameter tuning is not counted. These are common in the literature and not fatal.\n\nOverall, this is a strong submission that deserves serious refereeing. The formulation and the biased-SGDA analysis stand on their own. I would recommend major revision: make the theorem statement match the actual algorithm, or explicitly scope the claim.","headline":"New rate-constrained DP formulation with solid theory for the unclipped case, but the main theorem does not cover the clipped algorithm actually evaluated.","tokens_in":31315,"tokens_out":3722,"would_cite":true,"duration_ms":42254,"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":"The paper introduces RaCO-DP, a differentially private training method that enforces arbitrary rate constraints—group fairness, false-negative limits, and more—by reducing their cost to a private histogram per mini-batch.","keywords":["differential privacy","rate constraints","group fairness","stochastic gradient descent-ascent","Lagrangian duality","private histograms","non-convex optimization","false negative rate constraints"],"falsifier":"Run Algorithm 1 exactly as written—with the Line 8 gradient clipping and with the parameter choices of Theorem D.1—on a logistic-regression task with the strict false-negative constraint FNR=0 used in the paper's Figure 6, in the noise-free setting (sigma=0, b=infinity). If for a small clipping norm such as C=2 the iterates never approach the feasible set, as the paper's own figure shows, then the claimed convergence to an (alpha,alpha)-stationary point of Phi does not hold for the actual (clipped) algorithm; a complete argument would need a bound on the clipping bias.","tokens_in":30239,"feed_emoji":"🔒","tokens_out":9360,"duration_ms":95482,"temperature":0.7,"pith_summary":"This paper asks whether constrained machine learning can be made differentially private when the constraints depend on statistics of prediction rates across subpopulations—demographic parity, equality of odds, false-negative limits—rather than on per-example losses. The authors' answer is RaCO-DP, a stochastic gradient descent-ascent algorithm that solves the Lagrangian formulation of the constrained problem and whose only extra privacy cost is a private histogram of each mini-batch. They prove that, under Lipschitz and smoothness assumptions, the algorithm converges to an approximate stationary point of the min-max objective, with the approximation error set by the privacy budget. The reported experiments show RaCO-DP meeting specified fairness and false-negative targets while Pareto-dominating the previous state of the art in the fairness-utility trade-off. If the central claim holds, rate constraints are no longer an obstacle to private learning but a standard, privacy-compatible objective.","feed_headline":"Private learning now handles any rate constraint, not just fairness","feed_subtitle":"RaCO-DP privatizes constraints with one histogram per batch, proves convergence, and beats prior fair-learners.","key_machinery":"The machinery is the generalized rate constraint form Gamma_j($\\theta$) = sum_{I in I_j} sum_{k in [K]} alpha_{j,I,k} P_k(union_{i in I} D_i; $\\theta$), where {D_1,...,D_Q} is a single public partition of the dataset and each constraint recombines these parts. This form guarantees that the only non-decomposable statistics are the counts used to normalize each rate, and those counts are exactly the entries of a private histogram H-$hat^{{(t)}}$ with L1-sensitivity 1. The optimization engine is SGDA on the Lagrangian: a projected gradient-ascent update on the dual variable $\\lambda$ whose gradient is the private constraint violation, and a per-sample clipped-and-noised gradient descent update on $\\theta$ that uses the same private histogram through post-processing. The proof machinery that carries the convergence argument is the linear structure of the dual update, which lets the analysis rely on an L-infinity bound on the dual gradient error instead of L2, and which yields a 1/$T^{{1/4}}$ rate rather than the 1/$T^{{1/6}}$ rate of the standard nonconvex-concave GDA analysis.","core_discovery":"The paper's central claim is that arbitrary rate constraints can be folded into differentially private optimization without weakening the privacy guarantee. It defines generalized rate constraints as weighted sums of prediction rates over unions of parts of a fixed partition of the dataset, and observes that all quantities needed for both the primal and dual updates—constraint values and their per-sample gradients—can be read off a single histogram of softmax predictions over that partition. Because each data point touches exactly one part and its class probabilities sum to one, the histogram has L1-sensitivity at most one, so Laplace noise suffices to privatize it. The primal update then applies DP-SGD-style clipping and Gaussian noise to per-sample Lagrangian gradients, while the dual update uses the private histogram's post-processed values and therefore costs no additional privacy budget. The mathematical payload is a convergence analysis of SGDA with biased gradients: exploiting the linearity of the Lagrangian in the dual parameter, the analysis shows that with suitable parameters some iterate is an ($\\alpha$, $\\alpha$)-stationary point of the value function Phi($\\theta$) = max_{$\\lambda$ in Lambda} L($\\theta$, $\\lambda$), with $\\alpha$ scaling like (d log(JKn/rho) log(n/delta)/(n eps))^{1/3} plus $K^{{1/4}}$-dependent terms, and with a faster rate in T than previously known for nonconvex-concave SGDA. The paper presents this as the first general differentially private treatment of rate-constrained optimization, with group fairness as a prominent application.","pith_inferences":["If the clipping-norm bias shown in the paper's Figure 6 is the dominant obstacle, a natural testable extension is to let the clipping norm grow during training, which might reconcile the implemented algorithm with the no-clipping theory while preserving privacy accounting.","The histogram route suggests that other aggregate statistics that are bounded per example—such as calibration or coverage constraints—could be brought into DP optimization by the same mechanism, since their evaluation reduces to a low-sensitivity histogram.","Once clipping is included in the analysis as a fixed bias term, the effective stationarity error alpha would degrade by roughly the bias magnitude, implying a three-way trade-off between privacy, feasibility, and utility that the current bound does not display explicitly."],"forward_implications":["Group fairness constraints such as demographic parity and equalized odds become compatible with standard (epsilon,delta)-differential privacy, with the fairness-related cost reduced to a private histogram per step rather than per-example decomposition.","Practitioners can specify the maximum allowed disparity or false-negative rate directly through the slack gamma and obtain it, instead of tuning an indirect penalty coefficient as in prior fairness methods.","The improved SGDA analysis—1/T^{1/4} convergence using the linear structure of the dual and an L-infinity dual-gradient error—applies to any nonconvex-linear min-max problem with bounded gradient errors, beyond rate constraints.","For a privacy budget (epsilon,delta), the optimal number of iterations balances optimization progress against noise, yielding the stated error scale alpha = O((d log(JKn/rho) log(n/delta)/(n eps))^{1/3} + K^{1/4}(log(n/delta) log(JKn/rho))^{1/4}/(n eps)^{1/4})."],"supporting_citations":[{"why":"Defines differential privacy and the Laplace mechanism, which the paper uses to privatize the mini-batch histogram.","marker":"[22]"},{"why":"Formulates rate constraints for binary classification and shows fairness metrics fit that form; the paper generalizes this to multiclass and privacy.","marker":"[15]"},{"why":"Introduces the dataset-constraint formulation that rate constraints are built on.","marker":"[28]"},{"why":"Provides the nonconvex-concave SGDA convergence analysis that the paper improves to a faster rate using the linear dual structure.","marker":"[41]"},{"why":"Is the previous state-of-the-art private fair-learning method (DP-FERMI) that RaCO-DP compares against and claims to Pareto-dominate.","marker":"[43]"},{"why":"Shows that gradient clipping biases SGD, the basis of the paper's stated limitation that clipping can push iterates outside the feasible set.","marker":"[38]"},{"why":"Supplies the per-sample clipping and noise techniques for private ERM that the primal update of RaCO-DP uses.","marker":"[9]"},{"why":"Provides the privacy amplification by subsampling result used to account for Poisson-sampled mini-batches in the privacy proof.","marker":"[5]"}],"fun_headline_variants":["DP for any rate constraint via one histogram per batch","RaCO-DP: private rate constraints with provable convergence","Privacy meets arbitrary rate constraints: RaCO-DP wins","One histogram privatizes any rate constraint in DP learning","Beyond fairness: private rate constraints made practical"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convergence guarantee is proved for the algorithm run without gradient clipping, whereas the algorithm as stated and as run clips every per-sample gradient; if the bias introduced by clipping is not controlled, the advertised guarantee does not cover the method actually used.","fun_headline_variants_meta":{"raw":{"variants":["DP for any rate constraint via one histogram per batch","RaCO-DP: private rate constraints with provable convergence","Privacy meets arbitrary rate constraints: RaCO-DP wins","One histogram privatizes any rate constraint in DP learning","Beyond fairness: private rate constraints made practical"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000179,"raw_usage":{"total_tokens":1348,"prompt_tokens":1040,"completion_tokens":308,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":656,"completion_tokens_details":{"reasoning_tokens":231}},"tokens_in":656,"tokens_out":308,"duration_ms":4354,"temperature":1.0,"reasoning_tokens":231,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:03:31.681834+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 exactly as written—with the Line 8 gradient clipping and with the parameter choices of Theorem D.1—on a logistic-regression task with the strict false-negative constraint FNR=0 used in the paper's Figure 6, in the noise-free setting (sigma=0, b=infinity). If for a small clipping norm such as C=2 the iterates never approach the feasible set, as the paper's own figure shows, then the claimed convergence to an (alpha,alpha)-stationary point of Phi does not hold for the actual (clipped) algorithm; a complete argument would need a bound on the clipping bias.","supporting_citations":[{"cited_title":"Calibrating Noise to Sensitivity in Private Data Analysis","cited_arxiv_id":null,"evidence_quote":"Defines differential privacy and the Laplace mechanism, which the paper uses to privatize the mini-batch histogram."},{"cited_title":"Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals","cited_arxiv_id":null,"evidence_quote":"Formulates rate constraints for binary classification and shows fairness metrics fit that form; the paper generalizes this to multiclass and privacy."},{"cited_title":"Satisfying real-world goals with dataset constraints","cited_arxiv_id":null,"evidence_quote":"Introduces the dataset-constraint formulation that rate constraints are built on."},{"cited_title":"On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems","cited_arxiv_id":null,"evidence_quote":"Provides the nonconvex-concave SGDA convergence analysis that the paper improves to a faster rate using the linear dual structure."},{"cited_title":"Stochastic Differentially Private and Fair Learning","cited_arxiv_id":null,"evidence_quote":"Is the previous state-of-the-art private fair-learning method (DP-FERMI) that RaCO-DP compares against and claims to Pareto-dominate."},{"cited_title":"RevisitingGradientClipping:Stochastic bias and tight convergence guarantees","cited_arxiv_id":null,"evidence_quote":"Shows that gradient clipping biases SGD, the basis of the paper's stated limitation that clipping can push iterates outside the feasible set."},{"cited_title":"Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds","cited_arxiv_id":null,"evidence_quote":"Supplies the per-sample clipping and noise techniques for private ERM that the primal update of RaCO-DP uses."},{"cited_title":"Privacy amplification by subsampling: Tight analyses via couplings and divergences","cited_arxiv_id":null,"evidence_quote":"Provides the privacy amplification by subsampling result used to account for Poisson-sampled mini-batches in the privacy proof."}],"review_version":1}