alphaFeedback

WorksMathematics

Minimax signal detection in regression under differential privacy

AI contributions
  • OpenAI’s ChatGPT
View details
Ancillary data
1 code link
View

Abstract

We establish minimax separation rates across sparsity levels for regression signal detection under (ε,δ)(ε, δ)-central differential privacy, considering linear regression with an unknown error distribution and generalised linear models (GLMs) with an unknown intercept. Without sparsity restrictions, the separation rates for linear regression and GLMs with binary responses match the private Gaussian mean testing rate up to polylogarithmic factors. For GLMs with more than two possible response outcomes, additional information in the marginal response distribution permits faster detection of sufficiently small signals when the dimension exceeds the sample size nn. Our upper bounds are based on a reduction to private mean testing, tests of dependence between the response and sparse covariate projections, and a response-only test that is adjusted for the unknown intercept. The resulting procedure adapts to unknown sparsity and matches our lower bounds up to polylogarithmic factors. We also construct polynomial-time tests that attain these rates when ε≳n−1/2ε\gtrsim n^{-1/2}, and compare their numerical performance with existing private procedures.

Introduction

Determining whether a collection of covariates is associated with a response is a classical problem in statistical inference. In high-dimensional regression, this question can be formulated as the global hypothesis testing problem

H0: β=0againstH1: ∥β∥2≥r,H_0:\ \beta=0 \qquad\text{against} \qquad H_1:\ \lVert\beta\rVert_2 \ge r,

where β∈Rd\beta\in\mathbb{R}^d is the regression coefficient, and rr measures the signal strength. It is well known that detecting whether a signal is present can be substantially easier than estimating the regression coefficient itself. For example, in the dense isotropic Gaussian linear model with d=o(n)d=o(n) and unit error variance, the minimax ℓ2\ell_2 estimation error is of order d/n\sqrt{d/n}, whereas the minimax separation rate for signal detection is of order d1/4/nd^{1/4}/\sqrt{n} [26].

The gap between testing and estimation makes signal detection particularly relevant in high-dimensional applications, many of which involve sensitive data such as genomic records or consumer transactions. This motivates studying how hypothesis testing can be carried out while protecting individual-level data. A leading framework for privacy is differential privacy (DP) [17], which has been widely used in both industry (e.g. [16]) and government applications (e.g. Abowd and Hawes [1]). At a high level, differential privacy requires the distribution of a released output to be stable under replacement of a single observation.

Intuitively, stronger privacy guarantees require larger signals to reliably distinguish between the null and alternative hypotheses. We study how the minimax separation rate depends on the sample size, dimension, sparsity level, and privacy parameters, as well as on the regression model and its nuisance parameters.

Contributions

We characterise, up to polylogarithmic factors, the minimax separation rates for private signal detection across sparsity levels in linear regression with an unknown error distribution and generalised linear models (GLMs) with an unknown intercept.

  • In the dense regime, the rates for linear regression and GLMs with two response support points match the private Gaussian mean testing rate established by Narayanan [36]. We attain this rate through a transformation that reduces regression testing to mean testing and accommodates the unknown nuisance parameters. In particular, for linear regression, no moment, symmetry or smoothness assumptions on the errors are needed.

  • Our lower bounds identify when nuisance adjustment can absorb changes in the response marginal caused by a regression signal. This affects both the non-private and private detection rates. For GLMs with more than two response support points, the response marginal retains second-order information about the signal despite the unknown intercept, allowing faster detection of sufficiently small signals when d≳nd \gtrsim n. We therefore construct a response-only test that targets this information.

  • To exploit sparsity, we test for non-zero covariances between bounded transformations of the response and sparse covariate projections. Combining the sparse covariance test with the mean-reduction and response-only tests yields a procedure that adapts to the unknown sparsity level. As a byproduct, we characterise the minimax separation rates for private sparse mean testing of sub-Gaussian vectors up to polylogarithmic factors. To our knowledge, this characterisation under central DP is new and we present it in Appendix § 12 as a result of independent interest.

We also construct polynomial-time tests that match the minimax rates up to polylogarithmic factors when ϵ≳n−1/2\epsilon\gtrsim n^{-1/2}, and provide numerical experiments comparing their performance with existing private procedures.

Related work

Non-private regression testing. Without privacy constraints, global hypothesis testing in high-dimensional regression has been studied extensively, so we only list a few examples. Ingster et al. [26] established the asymptotic detection boundaries for Gaussian linear regression across sparsity levels, distinguishing known and unknown error variance, while Carpentier et al. (2022) obtained non-asymptotic separation rates under sub-Gaussian errors with unknown variance. Mukherjee et al. [35] derived analogous detection boundaries in the context of binary regression. For GLMs, Goeman et al. [20] developed asymptotic theory for a low dimensional null against a high dimensional alternative under canonical link functions, allowing for nuisance parameters; this framework was extended in Guo and Chen [23] to accommodate diverging dimension and a broader class of link functions.

Private regression inference. Early work developed private procedures for ordinary least squares (OLS), including confidence intervals and approximations to classical tt-statistics [41, 7]. Alabi and Vadhan [4] constructed differentially private FF-tests for testing linear relationships and mixtures, while Peña and Barrientos (2024) studied likelihood-based hypothesis testing and model comparison for Gaussian linear regression. Bias-corrected coefficient estimates and asymptotic confidence intervals were considered in Lin et al. [32]. For MM-estimators more generally, Avella-Medina [5] developed asymptotic theory for private analogues of the Wald, score and likelihood ratio tests. Bayesian approaches for private inference have been developed for linear regression [8] and for logistic and Poisson regression [30]. Hung and Yu [25] consider private hypothesis testing with censored survival data in the Cox regression model. For high-dimensional sparse linear regression, Cai et al. [10] developed differentially private methods for debiased inference on regression coefficients and multiple testing with false discovery rate control. These contributions primarily study private analogues of classical inferential procedures and their validity. Recent work also studies minimax support recovery in sparse linear regression with bounded covariates (Gu and Cai, 2026).

Optimality in private hypothesis testing. Another line of work develops finite-sample private tests together with optimality results. Canonne et al. [11] characterised the sample complexity of private testing between simple hypotheses, while Awan and Slavković [6] derived uniformly most powerful private tests for binomial data. For distribution testing, Acharya et al. [2] established optimal rates for identity testing of discrete distributions and closeness testing in the sparse regime. Canonne et al. [12] developed identity tests for high-dimensional product Bernoulli distributions and Gaussians with known covariance, and the Gaussian sample complexity bounds were sharpened by Narayanan [36]. More recently, private nonparametric testing has been studied through minimax analysis of permutation tests [29] and smooth two-sample testing [28]. The central DP rate for the white-noise-with-drift model follows as a special case of the federated DP framework of Cai et al. [9]. In the local model of DP, minimax testing has also been studied for simple hypotheses (e.g. Pensia et al., [39]) and for goodness-of-fit testing in discrete and continuous settings (e.g. Lam-Weil et al., [31]).

Hence, to the best of our knowledge, minimax separation rates for private signal detection in regression remain largely unresolved.

Organisation and notation

Section 2 introduces the models and states the main results. Sections 3 and 4 develop the lower bounds and corresponding tests. Section 5 presents polynomial-time implementations and numerical experiments, and Section 6 discusses future directions. Additional technical details are deferred to the appendices.

We use the following notation. For a positive integer nn, we write [n]:={1,2,…,n}[n] := \{1,2,\ldots,n\}. For x∈Rx \in\mathbb{R} and a≤ba \le b, we define the clipping operator [x]ab:=min⁡{b,max⁡{a,x}}[x]^b_a := \min\{b,\max\{a,x\}\}. For a vector v∈Rdv \in\mathbb{R}^d, we write ∥v∥2\lVert v\rVert_2 for its Euclidean norm, and write ∥v∥0:=∣{j∈[d]:vj≠0}∣\lVert v\rVert_0 := |\{j \in[d] : v_j \ne0\}| for its number of non-zero coordinates. We say a random variable X∈RX \in\mathbb{R} is sub-Gaussian if ∥X∥ψ2:=inf⁡{c>0:E[exp⁡(X2/c2)]≤2}<∞\lVert X\rVert_{\psi_2} := \inf\{c > 0 : \mathbb{E}[\exp(X^2/c^2)] \le2\} < \infty, and we say a random vector X∈RdX \in\mathbb{R}^d is sub-Gaussian if ∥X∥ψ2:=sup⁡u:∥u∥2≤1∥u⊤X∥ψ2<∞\lVert X\rVert_{\psi_2} := \sup_{u:\lVert u\rVert_2 \le1}\lVert u^\top X\rVert_{\psi_2} < \infty. For a distribution PP, we write P⊗nP^{\otimes n} to denote its nn-fold product. We use CC, cc, c1,…c_1,\ldots to denote positive constants that may depend only on the fixed constants in our assumptions but not on nn, dd, s∗s^*, ϵ\epsilon or δ\delta. Their values may change from line to line unless otherwise specified. For two non-negative sequences {an}\{a_n\} and {bn}\{b_n\}, we write an≲bna_n \lesssim b_n if there exists a constant C>0C > 0 such that an≤Cbna_n \le Cb_n for all nn, and we write an≍bna_n \asymp b_n if both an≲bna_n \lesssim b_n and bn≲anb_n \lesssim a_n. We use ≲log⁡\lesssim_{\log} and ≍log⁡\asymp_{\log} for the corresponding comparisons up to polylogarithmic factors. We also write an=O(bn)a_n = O(b_n) if ∣an∣≲bn|a_n| \lesssim b_n, and an=o(bn)a_n = o(b_n) if an/bn→0a_n/b_n \to0 as n→∞n \to\infty, where bn>0b_n > 0. We denote by Lap⁡(b)\operatorname{Lap}(b) the centred Laplace distribution with scale bb, and use DTVD_{\mathrm{TV}}, DKLD_{\mathrm{KL}} and DHamD_{\mathrm{Ham}} for total variation distance, Kullback–Leibler divergence, and Hamming distance, respectively.

Problem setup and main results

We observe nn independent and identically distributed (i.i.d.) pairs {(Xi,Yi)}i=1n\{(X_i,Y_i)\}_{i=1}^n taking values in Rd×Y\mathbb{R}^d \times\mathcal{Y}. The conditional distribution of YY given X=xX = x is specified by the linear predictor xTβx^{\mathsf T}\beta and an unknown nuisance parameter ν∈N\nu\in\mathcal{N}. Here, β∈Rd\beta\in\mathbb{R}^d is the regression coefficient of interest, and ν\nu may differ under the null and alternative hypotheses. We consider testing

H0:β=0againstH1(r,R):r≤∥β∥2≤R(1)H_0 : \beta= 0 \qquad\text{against} \qquad H_1(r,R) : r \le\lVert\beta\rVert_2 \le R \tag*{(1)}

for 0<r≤R≤∞0 < r \le R \le\infty. Taking R=r0R = r_0, where r0>0r_0 > 0 is a sufficiently small model-dependent constant, restricts the alternatives to a neighbourhood of zero.

Assumption 1 (Covariate distribution). Fix constants 0<λ‾≤λ‾0 < \underline{\lambda} \le\overline{\lambda} and CX≥8λ/3C_X \ge\sqrt{8\lambda/3}. We assume the covariate distribution satisfies E[X]=0\mathbb{E}[X] = 0, λ‾Id⪯E[XXT]⪯λ‾Id\underline{\lambda} I_d \preceq\mathbb{E}[XX^{\mathsf T}] \preceq\overline{\lambda} I_d, and ∥X∥ψ2≤CX\lVert X\rVert_{\psi_2} \le C_X.

The restriction on CXC_X ensures that the covariate class contains N(0,λ‾Id)N(0,\underline{\lambda} I_d), which we use in the lower-bound construction.

Model classes

We focus on two classes of regression models, which have different nuisance parameters.

Linear regression. We consider the model

Y=XTβ+ξ,ξ⊥X(2)Y = X^{\mathsf T}\beta+ \xi,\qquad\xi\perp X \tag*{(2)}

where the distribution of ξ\xi is unknown.

Assumption 2 (Linear regression error). There exist fixed constants Mξ>0M_\xi> 0 and pξ∈(0,1)p_\xi\in(0,1) such that P(∣ξ∣≤Mξ)≥pξ\mathbb{P}(|\xi| \le M_\xi) \ge p_\xi.

Assumption 2 only requires that errors have bounded magnitude with a fixed positive probability. In particular, it imposes no smoothness, symmetry, or tail assumptions on the error distribution.

Generalised linear models. We consider GLMs based on a fixed non-degenerate, one-parameter natural exponential family, with open natural parameter space Θ\Theta. Conditional on its covariates X=xX = x, the response distribution is given by

pβ,γ(y∣x)=h(y)exp⁡{yϑ(γ+xTβ)−b(ϑ(γ+xTβ))}.(3)p_{\beta,\gamma}(y \mid x) = h(y)\exp\left\{y\vartheta(\gamma+ x^{\mathsf T}\beta) - b\left(\vartheta(\gamma+ x^{\mathsf T}\beta)\right)\right\}. \tag*{(3)}

Here, h:Y→R≥0h : \mathcal{Y} \to\mathbb{R}_{\ge0} is the base density, ϑ:R→Θ\vartheta: \mathbb{R} \to\Theta maps the linear predictor to the natural parameter, bb is the log-partition function, and γ∈Γ\gamma\in\Gamma is an unknown nuisance intercept.

Assumption 3 (GLM regularity). We assume that ϑ\vartheta is either non-decreasing or non-increasing on R\mathbb{R}. The intercept parameter space Γ\Gamma is a compact interval with non-empty interior, and there exists an open interval U⊃ΓU \supset\Gamma such that ϑ∈C3(U)\vartheta\in C^3(U) and inf⁡a∈U∣ϑ′(a)∣>0\inf_{a \in U} |\vartheta'(a)| > 0.

The conditions in Assumption 3 hold for Bernoulli regression with logit or probit links, and Poisson and exponential regression with log links, among others. The global monotonicity condition ensures that the effect of the linear predictor does not reverse outside the intercept region. The remaining conditions provide the smoothness needed for local likelihood expansions and ensure that the response distribution remains locally sensitive to changes in the linear predictor.

Preliminaries on differential privacy

References

  1. [1]Abowd, J. M. and Hawes, M. B. (2022). Confidentiality protection in the 2020 U.S. Census of Population and Housing. Technical Report CED-WP-2022-003, U.S. Census Bureau.DOI
  2. [2]Acharya, J., Sun, Z., and Zhang, H. (2018). Differentially private testing of identity and closeness of discrete distributions. In Advances in Neural Information Processing Systems, volume 31.arxiv.org/abs/1707.05128
  3. [3]Acharya, J., Sun, Z., and Zhang, H. (2021). Differentially private Assouad, Fano, and Le Cam. In Algorithmic Learning Theory, pages 48–78. PMLR.arxiv.org/abs/2004.06830
  4. [4]Alabi, D. G. and Vadhan, S. P. (2023). Differentially private hypothesis testing for linear regression. Journal of Machine Learning Research, 24(361):1–50.arxiv.org/abs/2206.14449
  5. [5]Avella-Medina, M. (2021). Privacy-preserving parametric inference: a case for robust statistics. Journal of the American Statistical Association, 116(534):969–983.
  6. [6]Awan, J. and Slavković, A. (2018). Differentially private uniformly most powerful tests for binomial data. In Advances in Neural Information Processing Systems, volume 31.arxiv.org/abs/1805.09236
  7. [7]Barrientos, A. F., Reiter, J. P., Machanavajjhala, A., and Chen, Y. (2019). Differentially private significance tests for regression coefficients. Journal of Computational and Graphical Statistics, 28(2):440–453.arxiv.org/abs/1705.09561
  8. [8]Bernstein, G. and Sheldon, D. R. (2019). Differentially private Bayesian linear regression. In Advances in Neural Information Processing Systems, volume 32.arxiv.org/abs/1910.13153
  9. [9]Cai, T. T., Chakraborty, A., and Vuursteen, L. (2024). Federated nonparametric hypothesis testing with differential privacy constraints: optimal rates and adaptive tests. arXiv preprint arXiv:2406.06749.arxiv.org/abs/2406.06749
  10. [10]Cai, Z., Li, S., Xia, X., and Zhang, L. (2026). Differentially private estimation and inference in high-dimensional regression with FDR control. Journal of Machine Learning Research, 27(81):1–54.
  11. [11]Canonne, C. L., Kamath, G., McMillan, A., Smith, A., and Ullman, J. (2019). The structure of optimal private tests for simple hypotheses. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 310–321.arxiv.org/abs/1811.11148
  12. [12]Canonne, C. L., Kamath, G., McMillan, A., Ullman, J., and Zakynthinou, L. (2020). Private identity testing for high-dimensional distributions. In Advances in Neural Information Processing Systems, volume 33, pages 10099–10111.arxiv.org/abs/1905.11947
  13. [14]Chaudhuri, K., Loh, P.-L., Pandey, S., and Sarkar, P. (2024). On differentially private U statistics. In Advances in Neural Information Processing Systems.arxiv.org/abs/2407.04945
  14. [15]Chernozhukov, V., Chetverikov, D., Demirer, M., Duflo, E., Hansen, C., Newey, W., and Robins, J. (2018). Double/debiased machine learning for treatment and structural parameters. The Econometrics Journal, 21(1):C1–C68.
  15. [16]Ding, B., Kulkarni, J., and Yekhanin, S. (2017). Collecting telemetry data privately. In Advances in Neural Information Processing Systems, volume 30.
  16. [17]Dwork, C. (2006). Differential privacy. In Automata, Languages and Programming (ICALP 2006), Part II, volume 4052 of Lecture Notes in Computer Science, pages 1–12. Springer.
  17. [18]Dwork, C. and Roth, A. (2014). The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407.
  18. [19]Georgiev, K. and Hopkins, S. B. (2022). Privacy induces robustness: information-computation gaps and sparse mean estimation. In Advances in Neural Information Processing Systems, volume 35, pages 6829–6842.arxiv.org/abs/2211.00724
  19. [20]Goeman, J. J., van Houwelingen, H. C., and Finos, L. (2011). Testing against a high-dimensional alternative in the generalized linear model: asymptotic type I error control. Biometrika, 98(2):381–390.DOI
  20. [21]Gu, J. (2016). Neyman’s C(α) test for unobserved heterogeneity. Econometric Theory, 32(6):1483–1522.DOI
  21. [23]Guo, B. and Chen, S. X. (2016). Tests for high dimensional generalized linear models. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 78(5):1079–1102.arxiv.org/abs/1402.4882
  22. [24]Hopkins, S. B., Kamath, G., Majid, M., and Narayanan, S. (2023). Robustness implies privacy in statistical estimation. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 497–506.arxiv.org/abs/2212.05015
  23. [25]Hung, E. K. H. and Yu, Y. (2026). Differentially private hypothesis testing in survival analysis. arXiv preprint arXiv:2605.16906.arxiv.org/abs/2605.16906
  24. [26]Ingster, Y. I., Tsybakov, A. B., and Verzelen, N. (2010). Detection boundary in sparse regression. Electronic Journal of Statistics, 4:1476–1526.arxiv.org/abs/1009.1706
  25. [27]Kazan, Z., Shi, K., Groce, A., and Bray, A. P. (2023). The test of tests: a framework for differentially private hypothesis testing. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 16131–16151. PMLR.arxiv.org/abs/2302.04260
  26. [28]Kim, I. (2026). Sharp minimax rates for smooth two-sample testing under central differential privacy. arXiv preprint arXiv:2607.23974.arxiv.org/abs/2607.23974
  27. [29]Kim, I. and Schrab, A. (2026). Differentially private permutation tests. Journal of the American Statistical Association. Published online.
  28. [30]Kulkarni, T., Jälkö, J., Koskela, A., Kaski, S., and Honkela, A. (2021). Differentially private Bayesian inference for generalized linear models. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5838–5849. PMLR.arxiv.org/abs/2011.00467
  29. [31]Lam-Weil, J., Laurent, B., and Loubes, J.-M. (2022). Minimax optimal goodness-of-fit testing for densities and multinomials under a local differential privacy constraint. Bernoulli, 28(1):579–600.
  30. [32]Lin, S., Slavkovic, A., and Bhoomireddy, D. R. (2026). Differentially private linear regression and synthetic data generation with statistical guarantees. In Proceedings of the 29th International Conference on Artificial Intelligence and Statistics, volume 300 of Proceedings of Machine Learning Research, pages 4168–4176. PMLR.arxiv.org/abs/2510.16974
  31. [33]Marton, K. (1986). A simple proof of the blowing-up lemma. IEEE Transactions on Information Theory, 32(3):445–446.DOI
  32. [34]McShane, E. J. (1934). Extension of range of functions. Bulletin of the American Mathematical Society, 40(12):837–842.DOI
  33. [35]Mukherjee, R., Pillai, N. S., and Lin, X. (2015). Hypothesis testing for high-dimensional sparse binary regression. The Annals of Statistics, 43(1):352–381.DOI
  34. [36]Narayanan, S. (2022). Private high-dimensional hypothesis testing. In Conference on Learning Theory, pages 3979–4027. PMLR.arxiv.org/abs/2203.01537
  35. [37]Nissim, K., Raskhodnikova, S., and Smith, A. (2007). Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 75–84.
  36. [39]Pensia, A., Asadi, A. R., Jog, V., and Loh, P.-L. (2023). Simple binary hypothesis testing under local differential privacy and communication constraints. In Proceedings of the 36th Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 3229–3230. PMLR.arxiv.org/abs/2301.03566
  37. [40]Serfling, R. J. (1980). Approximation theorems of mathematical statistics. Wiley, New York.
  38. [41]Sheffet, O. (2017). Differentially private ordinary least squares. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3105–3114. PMLR.
  39. [42]Tsybakov, A. B. (2009). Introduction to nonparametric estimation. Springer, New York.
  40. [43]Vershynin, R. (2026). High-dimensional probability: an introduction with applications in data science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2 edition.
  41. [44]Voigtlaender, F. (2021). A general version of Price’s theorem: a tool for bounding the expectation of nonlinear functions of Gaussian random vectors. Journal of Theoretical Probability, 34:1474–1485.

Paper details

vlnc:W_y9a3nah4
v1 · latestHistory (1)

published · Fresh — added to the Hub within the last 30 days

added ·

Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Mathematics

OpenAI’s ChatGPT · View statement →

Looking for related papers…
Contents