An $\tilde{O}$ptimal Differentially Private Learner for Concept Classes with VC Dimension 1

Chao Yan
5/10/2025
cs.LGcs.CR

No confident code implementation found for this paper.

Abstract

We present the first nearly optimal differentially private PAC learner for any concept class with VC dimension 1 and Littlestone dimension $d$. Our algorithm achieves the sample complexity of $\tilde{O}_{\varepsilon,δ,α,δ}(\log^* d)$, nearly matching the lower bound of $Ω(\log^* d)$ proved by Alon et al. [STOC19]. Prior to our work, the best known upper bound is $\tilde{O}(VC\cdot d^5)$ for general VC classes, as shown by Ghazi et al. [STOC21].

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Private PAC Learning May be Harder than Online Learning

82% match2024

Differentially Private Learning Beyond the Classical Dimensionality Regime

78% match2024

Uniform Computability of PAC Learning

78% match2026

Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem

78% match2024

A Unified Characterization of Private Learnability via Graph Theory

78% match2023

Private List Learnability vs. Online List Learnability

77% match2025

Cite this paper

@article{yan2025tildeoptimal,
  title  = {An $\tilde{O}$ptimal Differentially Private Learner for Concept Classes with VC Dimension 1},
  author = {Chao Yan},
  year   = {2025},
  eprint = {2505.06581},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2505.06581v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2505.06581.svg)](https://codeofpaper.com/paper/2505.06581)

Discussion