Research map / Learning theory and algorithms / Sample complexity
Query Complexity of Bayesian Private Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Replicated Bisection instead of a single bisection search | Bayesian Private Learning · one-dimensional target estimation with privacy level L | query complexity: L\log(1/\veps) - L(\log L -1)-1 | Mixed |
| Require privacy level L while maintaining ε-accuracy | Bayesian Private Learning · one-dimensional target estimation | query complexity lower bound: L\log(1/\veps) - L\log(2/\delta)- 3L\log\log(\delta/\veps) | Hurt |
| Increase privacy level L | Bayesian Private Learning · fixed δ as ε → 0 | query complexity: N(\veps, \delta, L) \sim L\log(1/\veps) | Hurt |
| Use a proportional-sampling adversary estimator, sampling intervals in proportion to their query counts | Bayesian Private Learning lower-bound analysis · discrete target estimation | adversary probability of correct estimation: \frac{1}{n}\lt[ (1-\nu) \log(\delta/\veps) - h(\nu)\rt] | Helped |
| Extend replicated search to d-dimensional hyperplane queries | Bayesian Private Learning · d-dimensional target estimation | query complexity: dL\log(1/\veps) - L\log L + dL^{1/d} \leq dL\log(1/\veps) - L(\log L -1) | Mixed |
| Apply the one-dimensional proportional-sampling lower-bound argument to hyperplane queries | Bayesian Private Learning · d-dimensional target estimation | query complexity lower bound: c_1 \delta^{d-1} L \log(\delta/\veps) - c_2 L | Hurt |
| Allow the adversary to observe only a partial or perturbed version of the queries | Bayesian Private Learning · partial adversary observation | query complexity lower bound | Hurt |
Closest papers by meaning
- Private Prediction via Shrinkage (NeurIPS 2026 · similarity 0.87)
- Computationally Efficient Replicable Learning of Parities and Applications (NeurIPS 2026 · similarity 0.86)
- Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph (NeurIPS 2025 · similarity 0.86)
- Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings (NeurIPS 2025 · similarity 0.86)
- Perturb-and-Project: Differentially Private Similarities and Marginals (ICML 2024 · similarity 0.85)
- Oracle-Efficient Differentially Private Learning with Public Data (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.