Research map / Federated learning and privacy / Differential privacy
Private Truly-Everlasting Robust-Prediction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends private everlasting prediction (PEP) to robustness against out-of-distribution queries (PERP), relaxes delta to a time-dependent privacy definition so sample complexity is independent of time horizon, and gives efficient PERP constructions for axis-aligned rectangles and decision stumps with linear-in-dimension sample complexity.
Problem
Private everlasting prediction requires all queries to come from the target distribution, and its privacy parameter delta must shrink with the time horizon T, so sample complexity grows with polylog T; prior constructions are also quadratic in VC dimension and computationally inefficient.
Approach
Introduce robustness to a gamma fraction of adversarial queries in the utility definition, a time-indexed privacy parameter delta(i) with summable total delta*, and efficient evolving-hypothesis constructions (RectanglesPERP built from RSC, ChallengeBT, Stopper, BetweenThresholds) that keep a single evolving hypothesis instead of many full hypotheses.
Key results
- Generic PERP extends PEP with sample complexity ~VC^2/(alpha^2 gamma eps^2) at a 1/(alpha gamma) price over the non-robust construction.
- RectanglesPERP in d dimensions uses sample complexity ~ d/(alpha eps^2) polylog(...) and is computationally efficient.
- DecisionPERP for d-dimensional decision stumps uses sample complexity ~ log(d)/(alpha eps) + polylog/(alpha eps^2), matching the VC dimension scaling.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Extend generic PEP to tolerate a (1-γ) fraction of adversarial queries | Generic PEP · General concept class | sample complexity: \frac{\operatorname{\rm VC}^2(C)}{\alpha\cdot \varepsilon^2} -> \frac{\operatorname{\rm VC}^2(C)}{\alpha^2\cdot \gamma\c | Hurt |
| Use RectanglesPERP for axis-aligned rectangles instead of the generic robust construction | Generic PERP · Axis-aligned rectangles in d dimensions | sample complexity: quadratic in the VC dimension -> linear in the dimension | Helped |
| Use DecisionPERP for decision-stumps | Generic PERP · d-dimensional decision-stumps | sample complexity: linear in d -> linear in \log(d) | Helped |
| Make the privacy parameter δ decrease over time, with total budget δ* | PEP · Unbounded prediction-query horizon | sample complexity dependence on time horizon: grows with \mathop{\rm polylog} T -> independent from T | Helped |
Limitations
- Generic PERP construction is computationally inefficient and has quadratic VC-dimension sample complexity.
- Robust results are shown only for specific concept classes (rectangles, decision stumps), with a super-constant d analysis caveat (stripes of weight alpha/d).
- Robustness parameter gamma is fixed throughout execution in the definition.
Experimental setup
Metrics: sample complexity error bound alpha robustness parameter gamma
Baselines: generic PEP construction of Naor et al. 2023
Builds on: Private Everlasting Prediction (Naor et al. 2023) Sparse Vector Technique / AboveThreshold Reorder-Slice-Compute BetweenThresholds
Closest papers by meaning
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.88)
- Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacy (NeurIPS 2026 · similarity 0.87)
- Private Prediction via Shrinkage (NeurIPS 2026 · similarity 0.87)
- Auditing Private Prediction (ICML 2024 · similarity 0.86)
- Oracle-Efficient Differentially Private Learning with Public Data (NeurIPS 2024 · similarity 0.86)
- The Limits of Differential Privacy in Online Learning (NeurIPS 2024 · similarity 0.86)
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.