Pure-DP Statistical Query Release at the Conjectured Square-Root Rate

• URL: http://arxiv.org/abs/2607.20418v1
• Date: Wed, 22 Jul 2026 17:54:46 GMT
• Title: Pure-DP Statistical Query Release at the Conjectured Square-Root Rate
• Abstract summary: Nikolov and Ullman asked whether k statistical queries on a universe of size T can be released under pure differential privacy with expected worst-coordinate error at the square-root rate suggested by known lower bounds.<n>We prove their conjectured upper bound.<n>A companion Lean 4 development machine-checks the finite construction, pure privacy after deterministic decoding, and the displayed all-regimes upper bound.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nikolov and Ullman asked whether k statistical queries on a universe of size T can be released under pure differential privacy with expected worst-coordinate error at the square-root rate suggested by known lower bounds. We prove their conjectured upper bound. For every database size n and privacy parameter $\varepsilon>0$, there is an $\varepsilon$-differentially private mechanism with expected error $O(\min\{1,\sqrt{\log(2T)\log(2k)/(\varepsilon n)}\})$. This matches the lower-bound dependence in the standard high-dimensional regimes where those bounds apply; the shifted logarithms and outer minimum make the upper bound valid without additional parameter assumptions. The construction starts from a selection-only private multiplicative weights transcript, then replaces its probability mass function by a distance-penalized likelihood envelope. To prove that the modification preserves accuracy, a likelihood-level Maurey argument upper-bounds each Hamming-ball maximum by a small family of auxiliary PMW laws. Renyi moment bounds control nearby balls, a direct mixture bound controls distant balls, and grouping radii at the privacy scale prevents an additional $1/\varepsilon$ factor in the error. The mechanism is information-theoretic. A companion Lean 4 development machine-checks the finite construction, pure privacy after deterministic decoding, and the displayed all-regimes upper bound.

Related papers

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy [38.10483249859454]
  Minimax risk and regret are expectation-based criteria and do not capture rare but consequential failures.<n>We develop a $$-explicit minimax-quantile theory for interactive statistical decision making.
  arXiv  Detail & Related papers  (2026-06-22T09:41:48Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• On the Gradient Complexity of Private Optimization with Private Oracles [51.044364532408345]
  We study running time, in terms of first order oracle queries, of differentially private empirical/population risk of Lipschitz losses.<n>We show that expected running time $(minfracsqrtd2, fracdlog(1/))$ is necessary to achieve $$ excess risk on problems of dimension $d when $dgeq 1/2$.
  arXiv  Detail & Related papers  (2025-11-17T23:58:11Z)
• Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression [66.93988594607842]
  Under privacy constraints, the complexity of private linear regression is emphnot captured by the usual covariance matrix.<n>We introduce an Information-Weighted Regression method that attains the optimal rates.<n> Notably, our results demonstrate that joint privacy comes at almost no additional cost.
  arXiv  Detail & Related papers  (2025-02-18T18:35:24Z)
• On Differentially Private U Statistics [25.683071759227293]
  We propose a new thresholding-based approach using emphlocal H'ajek projections to reweight different subsets of the data. This leads to nearly optimal private error for non-degenerate U-statistics and a strong indication of near-optimality for degenerate U-statistics.
  arXiv  Detail & Related papers  (2024-07-06T03:27:14Z)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints. We derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$.
  arXiv  Detail & Related papers  (2024-01-17T09:23:25Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• Contraction of Locally Differentially Private Mechanisms [8.547801169402923]
  We derive tight bounds on the divergence between $PK$ and $QK$ output distributions of an $epsilon$-LDP mechanism $K$. We then utilize these bounds to establish locally private versions of the van Trees inequality, Le Cam's, Assouad's, and the mutual information methods.
  arXiv  Detail & Related papers  (2022-10-24T16:38:12Z)
• New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma [10.176795938619417]
  We prove new lower bounds for statistical estimation tasks under the constraint of $(varepsilon, delta)$-differential privacy. We show that estimating the Frobenius norm requires $Omega(d2)$ samples, and in spectral norm requires $Omega(d3/2)$ samples, both matching upper bounds up to logarithmic factors.
  arXiv  Detail & Related papers  (2022-05-17T17:55:10Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Robust Estimation of Discrete Distributions under Local Differential Privacy [1.52292571922932]
  We consider the problem of estimating a discrete distribution in total variation from $n$ contaminated data batches under a local differential privacy constraint. We show that combining the two constraints leads to a minimax estimation rate of $epsilonsqrtd/alpha2 k+sqrtd2/alpha2 kn$ up to a $sqrtlog (1/epsilon)$ factor.
  arXiv  Detail & Related papers  (2022-02-14T15:59:02Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  We show how to construct variance-aware confidence sets for linear bandits and linear mixture Decision Process (MDP) For linear bandits, we obtain an $widetildeO(mathrmpoly(d)sqrt1 + sum_i=1Ksigma_i2) regret bound, where $d is the feature dimension. For linear mixture MDP, we obtain an $widetildeO(mathrmpoly(d)sqrtK)$ regret bound, where
  arXiv  Detail & Related papers  (2021-01-29T18:57:52Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.