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

Chao Yan · 2025

Read An O ~ \tilde{\mbox{O}} ptimal Differentially Private PAC Learner for Concept Classes with VC Dimension 1 by Chao Yan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-06581.txt.

Introduction

Chao Yan wrote a math paper from 2025 on learning from data without leaking private facts. A learner must sort new cases well from a modest set of examples, yet also guard each person's data, a rule called differential privacy. Yan gives the first method for the plainest rich class of rules that needs close to the fewest examples any private method could use. Its count matches a known floor up to a small factor and beats the best prior bound by a wide margin.

Catalog record

CREATORChao Yan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-06581

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An O ~ \tilde{\mbox{O}} ptimal Differentially Private PAC Learner for Concept Classes with VC Dimension 1 Chao Yan Abstract We present the first nearly optimal differentially private PAC learner for any concept class with VC dimension 1 and Littlestone dimension d d . Our algorithm achieves the sample complexity of O ~ ε , δ , α , β ​ ( log ∗ ⁡ d ) \tilde{O}_{\varepsilon,\delta,\alpha,\beta}(\log^{*}d) , nearly matching the lower bound of Ω ⁡ ( log ∗ ⁡ d ) \Omega(\log^{*}d) proved by Alon et al. [ 1 ] [STOC19]. Prior to our work, the best known upper bound is O ~ ​ ( V ​ C ⋅ d 5 ) \tilde{O}(VC\cdot d^{5}) for general VC classes, as shown by Ghazi et al. [ 13 ] [STOC21]. 1 Introduction Machine learning algorithms can access sensitive information from the training dataset. We research the privacy-preserving machine learning technique, introduced by Kasiviswanathan et al. [ 17 ] , that targets to learn a hypothesis while preserving the privacy of individual entries in the dataset. Informally, the goal is to construct a learner that satisfies the requirements of probably approximately correct (PAC) learning [ 22 ] and, simultaneously, differential privacy [ 11 ] . Definition 1 (Differential Privacy [ 11 ] ) . A randomized algorithm M is called (\varepsilon,\delta) -differentially private if for any two dataset S and S^{\prime} that differ on one entry and any event E , it holds that \Pr[M(S)\in E]\leq e^{\varepsilon}\cdot\Pr[M(S^{\prime})\in E]+\delta. Specifically, when \delta=0 , we call it pure-differential privacy. When \delta>0 , we call it approximate-differential privacy In the PAC learning task, the learner is given a set of n points S=(\mathcal{X}\times\{0,1\})^{n} drawn i.i.d. from an unknown distribution \mathcal{D} and labels that are given by an unknown concept c:\mathcal{X}\rightarrow\{0,1\} , where c\in\mathcal{C} and \mathcal{C} is the concept class. The goal is to output a hypothesis h:\mathcal{X}\rightarrow\{0,1\} such that \Pr_{x\sim\mathcal{D}}[c(x)\neq h(x)]\leq\alpha , where \alpha is the parameter of accuray. We call the required dataset size of the learning task the \emph{samplecomplexity} , which is a fundamental question in learning theory. For non-private PAC learning, it is well-known that the sample complexity is linear to the VC dimension of the concept class [ 22 ] . However, the sample complexity is less well understood in the differentially private setting. Kasiviswanathan et al. [ 17 ] give a upper bound O(\log|\mathcal{C}|) , which works for pure differential privacy ( \delta=0 ). In the approximate privacy regime ( \delta>0 ), several works [ 4 , 8 , 3 , 16 , 15 , 9 , 20 ] show that the sample complexity can be significantly lower than that in the pure setting. Alon et al. [ 1 ] and Bun et al. [ 7 ] find that the sample complexity of approximately differentially private learning is related to the Littlestone dimension [ 18 ] of the concept class \mathcal{C} , which characterizes the mistakes bound of online learning [ 18 ] . In detail, for a concept class \mathcal{C} with Littlestone dimension d , Alon et al. [ 1 ] prove a lower bound \Omega(\log^{*}d) 1 1 1 \log^{*}d is the iterated logarithm of d and Bun et al. [ 7 ] provide an upper bound O(2^{O(2^{d})}) . Subsequently, Ghazi et al. [ 13 ] improve the upper bound to \tilde{O}(VC\cdot d^{5}) . This leaves a large gap between the lower bound \Omega(\log^{*}d) and the upper bound \tilde{O}(VC\cdot d^{5}) , even when the VC dimension is as small as 1. The main question is: what is the best dependence on d ? One important example is the halfspaces class, which can be privately learned with poly(VC,\log^{*}d) examples by the work of Nissim et al. [ 20 ] . So it’s natural to conjecture that the tight sample complexity of differentially private learning depends on \log^{*}d . Moreover, the work by Nissim et al. [ 20 ] also shows an upper bound of \tilde{O}(\log^{*}|\mathcal{X}|) (recall |\mathcal{X}| is the input domain size) for any concept class with VC dimension 1. However, |\mathcal{X}| could be arbitrarily larger than d for the general concept class, and a significant gap remained between \log^{*}d and \min\{d^{5},\log^{*}|\mathcal{X}|\} . The remaining question is: Could we privately learn any VC 1 class with sample size poly(\log^{*}d) ? In this work, we give a positive answer to this question and give a nearly tight bound \tilde{\theta}_{\alpha,\beta,\varepsilon,\delta}(\log^{*}d) . 1.1 Our Result Theorem 1 (Improper Learning) . For any concept class \mathcal{C} with VC dimension 1 and Littlestone dimension d , there is an (\varepsilon,\delta) -differentially private algorithm that (\alpha,\beta) -PAC learns \mathcal{C} if the given labeled dataset has size N\geq O\left(\frac{\log^{*}d\cdot\log^{2}(\frac{\log^{*}d}{\varepsilon\beta\delta})}{\varepsilon}\cdot\frac{48}{\alpha}\left(10\log(\frac{48e}{\alpha})+\log(\frac{5}{\beta})\right)\right)=\tilde{O}_{\beta,\delta}\left(\frac{\log^{*}d}{\alpha\varepsilon}\right) Theorem 2 (Proper Learning) . For any concept class \mathcal{C} with VC dimension 1 and Littlestone dimension d , and given labeled dataset with size \begin{array}[]{rl}N&\geq O\left(\frac{\log^{*}d\cdot\log^{2}(\frac{\log^{*}d}{\varepsilon\beta\delta})}{\varepsilon}\cdot\frac{48}{\alpha}\left(10\log(\frac{48e}{\alpha})+\log(\frac{5}{\beta})\right)+\frac{(\log(1/\alpha)+\log(1/\alpha\beta))\cdot\sqrt{\log(1/\delta)}}{\alpha^{2.5}\varepsilon}\right)\\ &=\tilde{O}_{\beta,\delta}\left(\frac{\log^{*}d}{\alpha\varepsilon}+\frac{1}{\alpha^{2.5}\varepsilon}\right)\end{array} there is an (\varepsilon,\delta) -differentially private algorithm that properly (\alpha,\beta) -PAC learns \mathcal{C} . 1.2 Other Related Works Two Well Researched VC 1 Classes The first class is the point functions class (also called the indicator function). It is defined to be f_{t}(x)=1 if x=t and f_{t}(x)=0 if x\neq t . The point functions class has Littlestone Dimension 1, and Beimel et al. [ 4 ] prove it can be privately learned with O(1) examples using the choosing mechanism (Lemma 1 ). The second example is the thresholds class. It is defined to be f_{t}(x)=1 if x\geq t and f_{t}(x)=0 if x<t . The thresholds class has Littlestone dimension \log|\mathcal{X}| . There is a series of works on privately learning thresholds [ 4 , 8 , 15 , 9 ] , and finally been found that we can privately learn thresholds with \tilde{O}(\log^{*}|\mathcal{X}|) examples. The key observation is the equivalence between private learning thresholds and private median (or private interior point), which is observed by Bun et al. [ 8 ] . Proper and Improper Private Learning We call a learner proper if the output hypothesis is in the concept class and improper if the output may not be in the concept class. For pure differential privacy, Beimel et al. [ 2 ] prove a lower bound on the sample complexity of proper learning point functions is \Omega(\log|X|) and an upper bound of improper learning point functions O(1) . It shows a significant separation between proper and improper learning with pure differential privacy. Our result shows that for any VC 1 class, the separation between proper and improper learning with approximate differential privacy cannot be larger than O(\frac{1}{\alpha^{O(1)}}) (ignoring other parameters). 1.3 Overview of Technique 1.3.1 Improper Learning The key observation is the tree structure 2 2 2 The Tree structure of the VC 1 class is mentioned in a lot of papers and is usually researched in the one-inclusion graph context. But most of them only consider the maximum concept classes. The observation by Ben-David can include non-maximum classes. and partial order in the VC 1 class, which is observed by Ben-David [ 5 ] . In the tree structure, each node is a point from the domain \mathcal{X} , and each hypothesis is a path from one node to the tree’s root. Another important idea is that we focus on the thresholds dimension instead of the Littlestone dimension.

Read the complete text