{"id":"0bdf97a8-1171-4096-9c7e-d3f8eb1ce95e","arxiv_id":"2505.09004","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The paper establishes finite-sample lower bounds on the true MMSE of sensitive feature inference, expressed as empirical MSE minus finite-sample and approximation error terms, with closed-form approximation bounds for linear models.","lead":"This paper derives theoretical lower bounds on how accurately an adversary can infer a sensitive attribute from noisy data, using the minimum mean-squared error of a limited model class. The bounds combine the model's empirical error with finite-sample and approximation error terms, and the authors provide closed-form estimates for several distribution families.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's validation bound has a sign error: (22) defines ϵG = MSEtrain − E[·], but the proof requires E[·] − MSEtrain; hence Proposition 2 bounds the wrong quantity and the advertised validation lower bound is not established as written.","rationale":"The reader's stated weakest assumption is that the framework requires population-level quantities such as ϵA and the sample variance of W based on h∗H, making the advertised finite-sample bound not directly computable from n samples. That is a real and important limitation, but the paper is explicit about it (Section V, 'Computability of bounds') and it does not contradict the mathematical correctness of Theorem 1. The sign inconsistency in Theorem 2 is different in kind: it is an internal mathematical error in a newly claimed contribution, and the validation lower bound is one of the paper's advertised novelties. I therefore regard the sign error as the more load-bearing concern for correctness, even though the reader did flag it in passing in the rationale. The concrete check is straightforward: substitute the paper's own definition (22) into the Appendix B proof and compare the resulting inequality with the theorem statement. The discrepancy would be visible in an overfitting example, which is exactly the regime the validation bound was designed to handle. A fix is plausible—redefine ϵG as E[(S−ĥH)²] − MSEtrain(ĥH), or use |ϵG| with a two-sided generalization bound—so the appropriate disposition remains conditional acceptance with a mandatory fix, matching the reader's verdict. I do not see a reason to move the verdict to reject, because the core Theorem 1 and the closed-form approximation-error results are not affected by this sign error and appear sound.","tokens_in":35719,"tokens_out":9149,"duration_ms":91838,"concrete_test":"Re-derive equation (71) by substituting definitions (21)–(22) verbatim; the displayed chain should end with −ϵG + ϵC, not ϵG + ϵC. To confirm the consequence, construct a deliberately overfit example: take n small, H rich enough to drive MSEtrain(ĥH) ≈ 0 while E[(S−ĥH)²] > 0 (so ϵG < 0), and compute I = E[(S−ĥH)²] − MMSEH along with ϵC. If I > ϵC + ϵG, Theorem 2's final inequality is falsified by that instance. Alternatively, rerun the Figure 9 pipeline with ϵG redefined as E[·] − MSEtrain and check whether the validation bound changes sign; a non-vacuous (or correctly signed) bound under the redefinition confirms the inconsistency.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central new validation-based claim is Theorem 2, but its proof is internally inconsistent. In Appendix B, the term I = E[(S−ĥH(Xσ))²] − MMSEH(S|Xσ) is decomposed by adding and subtracting MSEtrain(ĥH): I = [E[(S−ĥH)²] − MSEtrain(ĥH)] + [MSEtrain(ĥH) − MSEtrain(h∗H)] + [MSEtrain(h∗H) − MMSEH]. The proof then drops the middle (nonpositive) term and writes the first bracket as ϵG + ϵC. However, equation (22) defines ϵG := MSEtrain(ĥH) − E[(S−ĥH)²], so the first bracket is −ϵG, not ϵG. The correct chain is I ≤ ϵC − ϵG. In the overfitting regime that the validation bound is specifically intended to address, ϵG ≤ 0 (training loss below population loss), so ϵC + ϵG can be strictly smaller than ϵC − ϵG; the claimed inequality MMSE ≥ MSEval − ϵ̃C − ϵG − ϵC − ϵA therefore does not follow. Proposition 2 compounds this: it states an upper bound on ϵG, which is vacuous when ϵG is negative; what is needed is an upper bound on −ϵG (equivalently on E[(S−ĥH)²] − MSEtrain(ĥH)). Thus the validation-bound contribution is unproven as written, though it is likely repairable by redefining ϵG with the opposite sign and applying the compression bound to the population-minus-training gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a framework for lower-bounding the minimum mean-squared error (MMSE) with which a sensitive attribute S in [0,1] can be inferred from a noisy release Xσ = X + σZ, using a finite sample of (Xσ,S) pairs and a restricted hypothesis class H. The central result (Theorem 1) decomposes the gap between the empirical training MSE of an ERM ĥH and the true MMSE into a concentration term ϵC and an approximation term ϵA = ||ησ - h*H||², yielding MMSE ≥ MSEtrain(ĥH) - ϵC - ϵA. A second result (Theorem 2) attempts the same with the validation MSE, at the cost of an additional generalization term ϵG controlled by a compression-based bound. For sigmoid-composed-with-linear models, the paper derives closed-form bounds on ϵA for several generative models (binary symmetric channel, equal- and unequal-covariance class-conditional Gaussians), including noise-rate and dimension dependence. Experiments on BSC, CCG, and Gaussian-mixture data compare linear and neural-network evaluators, document that validation-based bounds are vacuous in practice, and show that the analytic ϵA bounds are loose for small σ. The paper explicitly acknowledges several limitations, including the population-level nature of ϵA and the looseness of the analytic bounds.","tokens_in":36086,"tokens_out":23793,"duration_ms":221526,"significance":"If the results held as written, this would be a useful, inexpensive privacy-auditing tool: it converts the training or validation MSE of a simple model into a finite-sample lower bound on the inference power of an unrestricted adversary, with closed-form approximation-error bounds for several important generative models. Genuine strengths: Theorem 1 is correct and its proof is clean, relying on a clever pointwise decomposition that avoids generalization bounds; the closed-form approximation-error bounds for class-conditional Gaussians (Theorem 4, Corollary 1) are substantial and appear correct, including the explicit dimension dependence; and the empirical evaluation is unusually honest, reporting the vacuousness of the compression-based validation bounds, the looseness of the analytic bounds at small σ, and the overfitting of neural networks. However, the new validation-based claim (Theorem 2) is not proven as written because of a sign error, and the BSC bound (Theorem 3) is a formal asymptotic rather than a rigorous theorem.","major_comments":[{"comment":"The proof of the validation lower bound has a sign inconsistency that invalidates the theorem as stated. Equation (22) defines ϵG := MSEtrain(ĥH) - E[(S - ĥH)²], but in the chain in Eq. (71) the proof substitutes E[(S - ĥH)²] - MSEtrain(ĥH) = ϵG; the correct identity is E[(S - ĥH)²] - MSEtrain(ĥH) = -ϵG. The resulting correct chain is I ≤ ϵC - ϵG, so Δval ≤ ϵ̃C + ϵC - ϵG + ϵA and hence MMSE ≥ MSEval - ϵ̃C - ϵC + ϵG - ϵA. The claimed inequality (20) follows only when ϵG ≥ 0; in the overfitting regime ϵG < 0, which is precisely the regime the validation bound is introduced to address, the claimed bound is stronger than what the proof establishes. Proposition 2 compounds the problem: it states a high-probability upper bound on ϵG under the definition (22), but the proof requires an upper bound on -ϵG (equivalently, on E[(S - ĥH)²] - MSEtrain(ĥH)); a compression bound of the type quoted in (24) controls the population-minus-training gap in the opposite direction and is vacuous for the needed quantity when ϵG < 0. The error appears repairable by redefining ϵG with the opposite sign, which also matches the conventional meaning of 'generalization error' used in Remark 3, and then restating Theorem 2, Proposition 2, and the related discussion consistently.","section":"Section III, Theorem 2 / Eq. (22) and Appendix B, Eq. (71)"},{"comment":"The stated bound on ϵA for the BSC is not a proven inequality for any fixed σ. Expression (33) contains two O(·) remainder terms with unspecified constants C1(p,pN) and C2(p,pN), and Appendix D computes only the first few terms of formal power-series expansions, with no justification of termwise integration of the series in (86) and (104), no convergence radius, and no explicit remainder estimate. As written, (33) is a formal asymptotic expansion, and a reader cannot verify that ϵA ≤ ϵABSC for any particular value of σ. Since the abstract and the contribution list advertise closed-form bounds for binary symmetric channels, the authors should either derive explicit bounds with computable constants that hold for all σ (or for a quantified range), or restate Theorem 3 as an asymptotic statement with explicit remainder control. Note also that Figure 3 evaluates only the first four terms of (33), which is not covered by the theorem as it stands; Section IV-A correctly acknowledges loosness at small σ, but that concession does not cure the formal gap in the theorem statement.","section":"Section IV, Theorem 3, Eq. (33)"},{"comment":"The advertised finite-sample nature of the lower bounds is only partially realized, as the paper itself acknowledges. The bound in Theorem 1 contains ϵA = ||ησ - h*H||², a population quantity not computable from the n training samples without knowledge of the true conditional expectation ησ; the tighter Bernstein form of Proposition 1 also requires h*H (Remark 2); and Theorem 2 inherits both requirements. In the experiments, ϵA, ησ, and h*H are estimated using 1M samples together with knowledge of the generative model, while only MSEtrain and MSEval are computed from the advertised finite sample. The paragraph 'Computability of bounds' correctly notes that ϵA can be made small by choosing a rich H at the price of more training samples, but the abstract and contribution statements still describe the results as finite-sample lower bounds. I recommend that the paper state precisely which components of (13) and (20) are computable from the n (and m) samples alone, which require distributional knowledge, and under what conditions the bound becomes a fully data-driven guarantee.","section":"Section V ('Computability of bounds'), Sections II-III"}],"minor_comments":[{"comment":"The sentence 'In constrast to these approaches, we problem we consider here differs in two ways' is garbled and should be rewritten.","section":"Section I-A"},{"comment":"The matrix index 'y' in 'Σ̃1/2 y A Σ̃1/2 y' should be 's' to be consistent with the surrounding notation.","section":"Theorem 4, Eq. (38)"},{"comment":"The notation 'pNpN', 'qq', and 'pNp' is hard to parse; I suggest introducing explicit symbols such as p̄N := 1-pN and q̄ := 1-q throughout the theorem and its proof.","section":"Theorem 3 and Appendix D"},{"comment":"The statement that h*H(x) = s(θ*L(x)) for θ*L minimizing ||θσ - θL||² is not generally true, since minimizing E[(S - s(θL))²] over linear θL need not coincide with s of the linear projection of θσ; the bound (30) remains valid without this equality, but the proof should present (30) as an inequality rather than an equality.","section":"Proposition 3, proof"},{"comment":"Because the central validation bound relies on [2, Thm. 3.1], a recent preprint, the paper should restate the precise conditions of that theorem and the coding scheme used so that Proposition 2 is self-contained.","section":"Proposition 2"},{"comment":"The header states 'Manuscript received October 26, 2023; revised December 8, 2023,' which is inconsistent with an April 2025 submission; the dates should be updated.","section":"Manuscript header"},{"comment":"The phrase 'new Bernstein-style bound' overstates the novelty: the bound is an application of the empirical Bernstein inequality of Maurer and Pontil [34] to the quantity ϵC; the wording should be adjusted.","section":"Proposition 1"},{"comment":"The protocol should clarify that the estimates of ησ, h*H, and ϵA are oracle quantities that use knowledge of the generative model, in contrast to MSEtrain and MSEval, which use only the finite sample; this distinction is currently stated only implicitly.","section":"Section V, experimental protocol"}],"recommendation":"major_revision","confidential_remarks":"A large fraction of the technical content, including Theorem 1, Propositions 3-4, Theorem 3, Theorem 4, and Corollary 1, is stated by the authors to have appeared in [1], an ISIT 2025 paper by the same group. If that is the case, the genuinely new technical contribution of this journal version is Theorem 2, the full proofs of previously sketched results, and the expanded experiments; the sign error in Theorem 2 therefore falls exactly on the newest load-bearing claim. I would ask the editor to confirm that the overlap with [1] and the timing of the two submissions are handled consistently with the journal's dual-submission and prior-publication policies. The BSC remainder issue and the computability caveat are substantive but fixable within the manuscript's scope, so I see this as a major revision rather than a rejection. The paper includes an acknowledgment of the loss of a co-author during the project; the wording is respectful and I flag it only so the editor is aware, not because any action is needed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line first: this paper contributes a clean and correct decomposition (Theorem 1) that deserves to be known, but its advertised new validation-based bound (Theorem 2) is not proven as written because of a sign error. The rest of the package is solid, with limitations the authors largely admit.\n\nWhat's new and good: Theorem 1 is a clean estimation-approximation decomposition, stated and proved properly. It gives a finite-sample lower bound on the true MMSE in terms of training MSE minus a concentration term and an approximation term. The concentration bounds (Hoeffding and empirical Bernstein) are standard but cleanly presented. For linear hypothesis classes, the closed-form approximation-error bounds for the binary symmetric channel and class-conditional Gaussians are genuinely useful, with full proofs in the appendix and explicit dimension dependence in Corollary 1. The experiments are honest: they compare linear models with small neural networks, show overfitting behavior, and explicitly note that the validation bounds are vacuous in practice.\n\nNow the soft spots, in proportion. The sign error in the proof of Theorem 2 (Appendix B): the term E[(S - hH)^2] - MSEtrain(hH) is identified as epsilon_G, but (22) defines epsilon_G as the opposite sign. The correct decomposition gives MSEval - tilde_epsilon_C - epsilon_G + epsilon_C, not the stated +epsilon_G. In the overfitting regime (which the validation bound is intended to address), epsilon_G is negative, so the claimed inequality fails. Proposition 2 does not fix this; it bounds epsilon_G, but the proof needs a bound on its negative. Likely repairable by redefining epsilon_G with the opposite sign, but as written Theorem 2 is unproven.\n\nThe BSC bound (Theorem 3) is asymptotic: it uses a truncated series with O() remainders and unspecified constants C1,C2. That is acceptable if clearly labeled, but the theorem states an exact inequality. It needs an explicit non-asymptotic remainder or an explicit statement that it is an asymptotic approximation. The practical computability caveat: Theorem 1's epsilon_A is a population quantity; the paper estimates it with 1M samples and knowledge of the true distribution, so the advertised finite-sample bound is not directly computable from n samples. The authors acknowledge this and note that a sufficiently rich hypothesis class can make epsilon_A negligible; that is a reasonable path, but it limits the framework's use in settings where such a class is unavailable.\n\nWho is this for: researchers in information-theoretic privacy, statistical learning, and adversarial evaluation. The core decomposition and the closed-form bounds are worth having. Send it to peer review; a competent referee can get the sign error fixed and ask for the asymptotic nature of Theorem 3 to be made explicit. With those repairs, this becomes a solid contribution.","headline":"A useful lower-bound framework with a clean training-loss result and solid closed-form bounds for linear models, but the new validation-loss bound has a sign error and is unproven as written; worth a conditional accept after fixes.","tokens_in":36632,"tokens_out":3655,"would_cite":true,"duration_ms":35138,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves finite-sample lower bounds on the mean-squared error of any adversary inferring a sensitive feature from a noisy data release, with closed-form bounds for linear predictors.","keywords":["minimum mean-squared error","adversarial evaluation","sensitive feature inference","finite-sample bounds","approximation error","Gaussian noise mechanism","linear hypothesis class","validation-based bounds"],"falsifier":"For the binary symmetric channel with p = pN = 1/2, take n = 10, δ = 0.05, and use the analytic MMSE as ground truth; compute the Theorem 1 bound with the true ϵA and the sample-variance-based ϵC, and check that the bound never exceeds the analytic MMSE. A single parameter regime where the bound is violated with probability greater than δ refutes the theorem.","tokens_in":35511,"feed_emoji":"🛡️","tokens_out":9729,"duration_ms":88401,"temperature":0.7,"pith_summary":"The paper establishes a finite-sample auditing bound for sensitive-feature inference: when a data release Xσ is a Gaussian-noised version of features X correlated with a sensitive feature S∈[0,1], no adversary—even one who knows the true joint distribution—can infer S with mean-squared error below an empirically computable floor. The floor is the training error of any restricted hypothesis class H, minus a concentration penalty for using n samples and minus the approximation error of H against the true conditional expectation ησ. The authors prove this for general H and then specialize to the class of sigmoid-composed-with-linear models, where the approximation error admits closed-form bounds decaying as the noise variance grows. A red team armed only with n labeled pairs can therefore certify a lower bound on adversarial inference quality and test whether a noise mechanism sufficiently obfuscates S.","feed_headline":"Finite-sample bounds certify a floor on sensitive-feature inference","feed_subtitle":"Red teams can audit noise mechanisms from n labeled pairs; for linear models the bound is tight at high noise.","key_machinery":"The load-bearing identity is the orthogonal decomposition of the restricted-class MMSE: for any H with best-in-class predictor h*_H, E[(S−h(Xσ))²] = MMSE(S|Xσ) + ∥ησ−h∥², so the gap between empirical training error and true MMSE splits into a concentration term plus the approximation error ϵA = ∥ησ − h*_H∥². Since ησ = s(θσ) is the sigmoid of the log-likelihood ratio θσ and s is 1/4-Lipschitz, ϵA ≤ (1/4)∥θσ − θ*_L∥², which reduces the approximation error to the residual variance of a linear regression of θσ(Xσ) on Xσ, Var(θσ(Xσ)) − Cov(θσ(Xσ),Xσ)Var(Xσ)⁻¹Cov(Xσ,θσ(Xσ)). The concentration term is controlled for bounded losses by standard large-deviation inequalities, and the whole construction turns an adversarial-inference question into finite-sample regression statistics that a red team can compute.","core_discovery":"The central result (Theorem 1) is that for every hypothesis class H of functions into [0,1] and sensitive feature S∈[0,1], MMSE(S|Xσ) ≥ MSEtrain(ĥH) − ϵC − ϵA, where MSEtrain(ĥH) is the training mean-squared error of the empirical risk minimizer, ϵC is a concentration term controlled by standard large-deviation bounds on bounded losses, and ϵA = ∥ησ − h*_H∥² is the population gap between the best-in-class predictor and the true conditional expectation. The proof splits the gap into a finite-sample term and an approximation term, and a companion validation-based bound (Theorem 2) replaces part of the training error with validation error at the cost of a generalization term. For linear models under the sigmoid link, ϵA is bounded in closed form through a variance decomposition of the optimal logit θσ(Xσ), giving ϵA=0 for linear or equal-covariance Gaussian relationships, O(1/σ²) decay for the binary symmetric channel, and O(1/σ⁴) decay for class-conditional Gaussians with unequal covariances, where the bound grows quadratically with dimension. The message is that a simple finite-capacity linear model run by a red team yields non-vacuous guarantees on the strongest adversary, provided the noise level is not too small.","pith_inferences":["Beyond the paper, the same decomposition should hold for any additive noise mechanism, not just Gaussian, since it relies only on boundedness of S and of the hypothesis outputs; re-deriving the concentration term for other noise distributions would extend the audit framework without new conceptual machinery.","The quadratic growth of the linear-model approximation error in dimension suggests a practical design rule: for high-dimensional releases, either raise the noise level σ, increase the evaluation sample size, or switch to a neural network class whose approximation error is negligible once overfitting is controlled.","A direct testable extension is to run the training bound on a real dataset using only the n labeled pairs to estimate every term—without the paper's 1M auxiliary samples—and compare against a high-fidelity Monte Carlo MMSE; the paper's synthetic results predict the bound stays non-negative and tight for moderate n.","If a non-vacuous generalization bound for square loss were found, the validation bound (Theorem 2) would become the preferred audit tool; the paper's negative finding indicates that the coding-length complexity term, not the framework, is the current bottleneck."],"forward_implications":["For binary S, the MMSE lower bound transfers to a lower bound on the probability of misclassification, so the framework certifies a floor on adversarial accuracy, not just on squared error.","When S is a linear function of X or the classes share a covariance matrix, ϵA = 0 and the only gap is the concentration term, which shrinks as n grows; the training bound then becomes an arbitrarily tight audit of the noise mechanism.","For the binary symmetric channel and unequal-covariance Gaussian classes, the closed-form approximation bounds decay at rate O(1/σ²) and O(1/σ⁴) respectively, so at large noise a linear red-team model estimates the true MMSE almost exactly.","The validation-based bound allows richer hypothesis classes such as neural networks, but the experiments show the compression-based generalization bound is vacuous at realistic sizes, so the training-based bound is currently the practically reliable one."],"supporting_citations":[{"why":"prior version of this work whose training-loss bound Theorem 1 extends and whose omitted proofs are completed here","marker":"[1]"},{"why":"supplies the compression-based generalization bound used to control the generalization term in Theorem 2","marker":"[2]"},{"why":"provides the range-based concentration inequality for bounded random variables used in the finite-sample term","marker":"[33]"},{"why":"provides the sample-variance-based concentration inequality used as the tighter alternative for the finite-sample term","marker":"[34]"},{"why":"gives the optimal quadratic form of the class-conditional Gaussian classifier that Theorem 4 starts from","marker":"[37]"},{"why":"supplies the moments of quadratic forms of Gaussian vectors used to derive the closed-form approximation error","marker":"[40]"}],"fun_headline_variants":["Finite-sample floor on sensitive-feature inference","Lower bounds certify inference limits from finite data","Red-team audits bound sensitive-feature leakage","MMSE lower bound for adversarial feature inference","Finite-sample MMSE guarantees for linear adversaries"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The red team must be able to obtain the population-level quantities ϵA and the variance of the squared-loss variable, or have them be negligible; in practice these require either knowing the true data-generating distribution or using very large auxiliary samples, so the advertised finite-sample bound is not directly computable from the n training pairs alone.","fun_headline_variants_meta":{"raw":{"variants":["Finite-sample floor on sensitive-feature inference","Lower bounds certify inference limits from finite data","Red-team audits bound sensitive-feature leakage","MMSE lower bound for adversarial feature inference","Finite-sample MMSE guarantees for linear adversaries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000242,"raw_usage":{"total_tokens":1573,"prompt_tokens":1042,"completion_tokens":531,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":658,"completion_tokens_details":{"reasoning_tokens":463}},"tokens_in":658,"tokens_out":531,"duration_ms":5421,"temperature":1.0,"reasoning_tokens":463,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:42:45.645234+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the binary symmetric channel with p = pN = 1/2, take n = 10, δ = 0.05, and use the analytic MMSE as ground truth; compute the Theorem 1 bound with the true ϵA and the sample-variance-based ϵC, and check that the bound never exceeds the analytic MMSE. A single parameter regime where the bound is violated with probability greater than δ refutes the theorem.","supporting_citations":[{"cited_title":"Auditing privacy of additive noise mechanisms using linear predictive models,","cited_arxiv_id":null,"evidence_quote":"prior version of this work whose training-loss bound Theorem 1 extends and whose omitted proofs are completed here"},{"cited_title":"Empirical bernstein bounds and sample variance penalization,","cited_arxiv_id":null,"evidence_quote":"provides the sample-variance-based concentration inequality used as the tighter alternative for the finite-sample term"},{"cited_title":"Hastie, R","cited_arxiv_id":null,"evidence_quote":"gives the optimal quadratic form of the class-conditional Gaussian classifier that Theorem 4 starts from"},{"cited_title":"Mathai and S","cited_arxiv_id":null,"evidence_quote":"supplies the moments of quadratic forms of Gaussian vectors used to derive the closed-form approximation error"}],"review_version":1}