Research map / Federated learning and privacy / Differential privacy

An Õptimal Differentially Private PAC Learner for Concept Classes with VC Dimension 1

NeurIPS 2026 · Federated learning and privacy › Differential privacy · approach: Private online and user-level learning

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.

Gives a nearly optimal (log*d sample complexity) approximate-DP PAC learner, improper and proper, for any VC-dimension-1 concept class with Littlestone dimension d, via a tree structure, private median, and choosing mechanism.

Problem

Determining the sample complexity of approximately differentially private PAC learning for VC-dimension-1 concept classes as a function of Littlestone dimension d; prior upper bounds were poly(d) while the lower bound is Omega(log* d).

Approach

Exploits the partial-order tree structure of VC-1 classes (after fixing a reference concept f so that the f-representation is well-behaved) and the fact that tree height is bounded by the thresholds dimension (at most 2^{d+1}); partitions the sample into subsets, privately selects a "good length" via private median and then a "good path" via the choosing mechanism, yielding log*d sample complexity

Key results

• Improper (², ε,δ)-DP PAC learner for any VC-1 class with sample size Õ(log*d/(αε)), matching the Ω(log*d) lower bound up to polylog factors and polynomial dependence on ε, δ, α, β.
• Proper learner with sample size Õ(log*d/(αε) + 1/(α^{2.5}ε)), giving a proper-improper separation of at most O(1/α^{O(1)}) for VC-1 classes under approximate DP.
• Prior best upper bound was Õ(VC·d^5) (Ghazi et al.), so the paper improves the dependence on d from polynomial to log*d.

Surprising findings

• Proper and improper approximate-DP sample complexities for VC-1 classes differ by at most a factor depending only on 1/α, not on d.

Limitations

• Only for VC dimension 1 classes; extension to higher VC left open.
• Proper learner has an extra 1/α^{2.5} term and depends on sqrt(log(1/δ)) and privacy parameter rescaling.
• Polylogarithmic factors (log^2 terms and log*d) and hidden dependence on ε, δ, β are not tight.

Experimental setup

Metrics: sample complexity

Baselines: Ghazi et al. STOC21 (O~(VC·d^5)) Nissim et al. (O~(log*|X|) for VC-1) Bun et al. (O(2^{O(2^d)}))

Builds on: Alon et al. STOC19 (Littlestone dimension and private learning) Bun et al. private interior point / thresholds Ghazi et al. STOC21 Nissim et al. private halfspaces/thresholds Beimel et al. choosing mechanism

Closest papers by meaning

• Multiclass versus Binary Differentially Private PAC Learning (NeurIPS 2021 · similarity 0.92)
• Oracle-Efficient Differentially Private Learning with Public Data (NeurIPS 2024 · similarity 0.86)
• Surprises in Proper Positive-Only Learning (NeurIPS 2026 · similarity 0.85)
• Improved Sample Complexity for Multiclass PAC Learning (NeurIPS 2024 · similarity 0.85)
• On the Computational Landscape of Replicable Learning (NeurIPS 2024 · similarity 0.84)
• Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings (NeurIPS 2025 · similarity 0.84)