Do PAC-Learners Learn the Marginal Distribution?

• URL: http://arxiv.org/abs/2302.06285v3
• Date: Tue, 18 Feb 2025 23:50:17 GMT
• Title: Do PAC-Learners Learn the Marginal Distribution?
• Authors: Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan,
• Abstract summary: The Fundamental Theorem of PAC Learning asserts that learnability of a concept class $H$ is equivalent to the $textituniform convergence$ of empirical error in $H$. This work revisits the connection between PAC learning, uniform convergence, and density estimation beyond the distribution-free setting.
• Score: 19.54058590042626
• License:
• Abstract: The Fundamental Theorem of PAC Learning asserts that learnability of a concept class $H$ is equivalent to the $\textit{uniform convergence}$ of empirical error in $H$ to its mean, or equivalently, to the problem of $\textit{density estimation}$, learnability of the underlying marginal distribution with respect to events in $H$. This seminal equivalence relies strongly on PAC learning's `distribution-free' assumption, that the adversary may choose any marginal distribution over data. Unfortunately, the distribution-free model is known to be overly adversarial in practice, failing to predict the success of modern machine learning algorithms, but without the Fundamental Theorem our theoretical understanding of learning under distributional constraints remains highly limited. In this work, we revisit the connection between PAC learning, uniform convergence, and density estimation beyond the distribution-free setting when the adversary is restricted to choosing a marginal distribution from a known family $\mathscr{P}$. We prove that while the traditional Fundamental Theorem indeed fails, a finer-grained connection between the three fundamental notions continues to hold: 1. PAC-Learning is strictly sandwiched between two refined models of density estimation, differing only in whether the learner $\textit{knows}$ the set of well-estimated events in $H$. 2. Under reasonable assumptions on $H$ and $\mathscr{P}$, density estimation is equivalent to $\textit{uniform estimation}$, a relaxation of uniform convergence allowing non-empirical estimators. Together, our results give a clearer picture of how the Fundamental Theorem extends beyond the distribution-free setting and shed new light on the classically challenging problem of learning under arbitrary distributional assumptions.

Related papers

• Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension [17.485243410774814]
  In traditional models of supervised learning, the goal of a learner is to output a hypothesis that is competitive (to within $epsilon$) of the best fitting concept from some class. We introduce a smoothed-analysis framework that requires a learner to compete only with the best agnostic. We obtain the first algorithm forally learning intersections of $k$-halfspaces in time.
  arXiv  Detail & Related papers  (2024-07-01T04:58:36Z)
• Beyond Expectations: Learning with Stochastic Dominance Made Practical [88.06211893690964]
  dominance models risk-averse preferences for decision making with uncertain outcomes. Despite theoretically appealing, the application of dominance in machine learning has been scarce. We first generalize the dominance concept to enable feasible comparisons between any arbitrary pair of random variables. We then develop a simple and efficient approach for finding the optimal solution in terms of dominance.
  arXiv  Detail & Related papers  (2024-02-05T03:21:23Z)
• Differentially-Private Bayes Consistency [70.92545332158217]
  We construct a Bayes consistent learning rule that satisfies differential privacy (DP) We prove that any VC class can be privately learned in a semi-supervised setting with a near-optimal sample complexity.
  arXiv  Detail & Related papers  (2022-12-08T11:57:30Z)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  We study two basic statistical tasks in non-interactive local differential privacy (LDP): learning and refutation. Our main result is a complete characterization of the sample complexity of PAC learning for non-interactive LDP protocols.
  arXiv  Detail & Related papers  (2022-10-26T03:19:24Z)
• When are Local Queries Useful for Robust Learning? [25.832511407411637]
  We study learning models where the learner is given more power through the use of local queries. We give the first distribution-free algorithms that perform robust empirical risk minimization. We finish by giving robust learning algorithms for halfspaces on $0,1n$ and then obtaining robustness guarantees for halfspaces in $mathbbRn$ against precision-bounded adversaries.
  arXiv  Detail & Related papers  (2022-10-12T11:04:22Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints. We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates. The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
  arXiv  Detail & Related papers  (2022-09-16T09:38:38Z)
• A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
  Binary density ratio estimation (DRE) provides the foundation for many state-of-the-art machine learning algorithms. We develop a general framework from the perspective of Bregman minimization divergence. We show that our framework leads to methods that strictly generalize their counterparts in binary DRE.
  arXiv  Detail & Related papers  (2021-12-07T01:23:20Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  We study the problem of learning revenue-optimal multi-bidder auctions from samples when the samples of bidders' valuations can be adversarially corrupted or drawn from distributions that are adversarially perturbed. We propose new algorithms that can learn a mechanism whose revenue is nearly optimal simultaneously for all true distributions'' that are $alpha$-close to the original distribution in Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2021-07-13T17:37:21Z)
• Measuring Model Fairness under Noisy Covariates: A Theoretical Perspective [26.704446184314506]
  We study the problem of measuring the fairness of a machine learning model under noisy information. We present a theoretical analysis that aims to characterize weaker conditions under which accurate fairness evaluation is possible.
  arXiv  Detail & Related papers  (2021-05-20T18:36:28Z)
• Arbitrary Conditional Distributions with Energy [11.081460215563633]
  A more general and useful problem is arbitrary conditional density estimation. We propose a novel method, Arbitrary Conditioning with Energy (ACE), that can simultaneously estimate the distribution $p(mathbfx_u mid mathbfx_o)$. We also simplify the learning problem by only learning one-dimensional conditionals, from which more complex distributions can be recovered during inference.
  arXiv  Detail & Related papers  (2021-02-08T18:36:26Z)
• Beyond $\mathcal{H}$-Divergence: Domain Adaptation Theory With Jensen-Shannon Divergence [21.295136514836788]
  We reveal the incoherence between the widely-adopted empirical domain adversarial training and its generally-assumed theoretical counterpart based on $mathcalH$-divergence. We establish a new theoretical framework by directly proving the upper and lower target risk bounds based on joint distributional Jensen-Shannon divergence.
  arXiv  Detail & Related papers  (2020-07-30T16:19:59Z)

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.