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

• URL: http://arxiv.org/abs/2505.06581v2
• Date: Tue, 29 Jul 2025 16:55:08 GMT
• Title: An $\tilde{O}$ptimal Differentially Private Learner for Concept Classes with VC Dimension 1
• Authors: Chao Yan,
• Abstract summary: We present the first nearly optimal differentially private PAC learner for any concept class with VC dimension 1 and Littlestone dimension achieves $d$.<n>Our algorithm the sample complexity of $tildeO_varepsilon,delta,alpha,delta(log* d)$, nearly matching the lower bound of $Omega(log* d)$ proved by Alon et al.<n>Prior to our work, the best known upper bound is $tildeO(VCcdot d5)$ for general VC classes, as shown by
• Score: 4.834749573193387
• License: http://creativecommons.org/publicdomain/zero/1.0/
• 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,\delta,\alpha,\delta}(\log^* d)$, nearly matching the lower bound of $\Omega(\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].

Related papers

• Lower Bounds for Greedy Teaching Set Constructions [12.186950360560145]
  We prove lower bounds on the performance of a greedy algorithm for small $k$.<n>Most consequentially, our lower bound extends up to $k le lceil c d rceil$ for small constant $c>0$.
  arXiv  Detail & Related papers  (2025-05-06T06:30:01Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory.<n>We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds.<n>We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
  arXiv  Detail & Related papers  (2025-02-25T19:08:26Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• The Sample Complexity of Multi-Distribution Learning for VC Classes [25.73730126599202]
  Multi-distribution learning is a generalization of PAC learning to settings with multiple data distributions. There remains a significant gap between the known upper and lower bounds for PAC-learnable classes. We discuss recent progress on this problem and some hurdles that are fundamental to the use of game dynamics in statistical learning.
  arXiv  Detail & Related papers  (2023-07-22T18:02:53Z)
• \~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization [23.547605262139957]
  The problem of learning threshold functions is a fundamental one in machine learning. We provide a nearly tight upper bound of $tildeO(log* |X|)1.5)$ by Kaplan et al. We also provide matching upper and lower bounds of $tildeTheta(2log*|X|)$ for the additive error of private quasi-concave (a related and more general problem)
  arXiv  Detail & Related papers  (2022-11-11T18:16:46Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  Modern machine learning algorithms aim to extract fine-grained information from data to provide accurate predictions, which often conflicts with the goal of privacy protection. This paper addresses the practical and theoretical importance of developing privacy-preserving machine learning algorithms that ensure good performance while preserving privacy.
  arXiv  Detail & Related papers  (2022-09-09T08:54:13Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Private Query Release Assisted by Public Data [96.6174729958211]
  We study the problem of differentially private query release assisted by access to public data. We show that we can solve the problem for any query class $mathcalH$ of finite VC-dimension using only $d/alpha$ public samples and $sqrtpd3/2/alpha2$ private samples.
  arXiv  Detail & Related papers  (2020-04-23T02:46:37Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  We present a differentially private learner for halfspaces over a finite grid $G$ in $mathbbRd$ with sample complexity $approx d2.5cdot 2log*|G|$. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem.
  arXiv  Detail & Related papers  (2020-04-16T16:12:10Z)
• Closure Properties for Private Classification and Online Prediction [31.115241685486392]
  We derive closure properties for online learning and private PAC learning. We show that any private algorithm that learns a class of functions $cH$ in the realizable case can be transformed to a private algorithm that learns the class $cH$ in the case.
  arXiv  Detail & Related papers  (2020-03-10T02:34:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.