A Distributional-Lifting Theorem for PAC Learning

• URL: http://arxiv.org/abs/2506.16651v1
• Date: Thu, 19 Jun 2025 23:28:38 GMT
• Title: A Distributional-Lifting Theorem for PAC Learning
• Authors: Guy Blanc, Jane Lange, Carmen Strassle, Li-Yang Tan,
• Abstract summary: Distributional assumptions facilitate the design of efficient algorithms but limit their reach and relevance.<n>Recent work of Blanc, Lange, Malik, and Tan considered the special case of lifting uniform-distribution learners.<n>We show that their approach is information-theoretically intractable with access only to random examples.<n>We then take a different approach that sidesteps the need to learn $Dstar$, yielding a lifter that works in the standard PAC model.
• Score: 16.985620991607345
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The apparent difficulty of efficient distribution-free PAC learning has led to a large body of work on distribution-specific learning. Distributional assumptions facilitate the design of efficient algorithms but also limit their reach and relevance. Towards addressing this, we prove a distributional-lifting theorem: This upgrades a learner that succeeds with respect to a limited distribution family $\mathcal{D}$ to one that succeeds with respect to any distribution $D^\star$, with an efficiency overhead that scales with the complexity of expressing $D^\star$ as a mixture of distributions in $\mathcal{D}$. Recent work of Blanc, Lange, Malik, and Tan considered the special case of lifting uniform-distribution learners and designed a lifter that uses a conditional sample oracle for $D^\star$, a strong form of access not afforded by the standard PAC model. Their approach, which draws on ideas from semi-supervised learning, first learns $D^\star$ and then uses this information to lift. We show that their approach is information-theoretically intractable with access only to random examples, thereby giving formal justification for their use of the conditional sample oracle. We then take a different approach that sidesteps the need to learn $D^\star$, yielding a lifter that works in the standard PAC model and enjoys additional advantages: it works for all base distribution families, preserves the noise tolerance of learners, has better sample complexity, and is simpler.

Related papers

• SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups [14.925722398371498]
  We introduce a novel discrete diffusion model that simplifies the task of learning a complicated distribution over $S_n$.<n>We provide empirical guidelines for selecting the diffusion length based on the theory of random walks on finite groups.<n>Our model achieves state-of-the-art or comparable performances on solving tasks including sorting 4-digit images, jigsaw puzzles, and traveling salesman problems.
  arXiv  Detail & Related papers  (2024-10-03T19:37:40Z)
• Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
  conditional distributions is a central problem in machine learning.<n>We propose a new paradigm that integrates both paired and unpaired data.<n>We show that our approach can theoretically recover true conditional distributions with arbitrarily small error.
  arXiv  Detail & Related papers  (2024-10-03T16:12:59Z)
• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also found applications in differential privacy, mildly, and quantum learning theory.
  arXiv  Detail & Related papers  (2024-09-17T23:09:25Z)
• Universal Batch Learning Under The Misspecification Setting [4.772817128620037]
  We consider the problem of universal em batch learning in a misspecification setting with log-loss. We derive the optimal universal learner, a mixture over the set of the data generating distributions, and get a closed form expression for the min-max regret.
  arXiv  Detail & Related papers  (2024-05-12T11:16:05Z)
• Testable Learning with Distribution Shift [9.036777309376697]
  We define a new model called testable learning with distribution shift. We obtain provably efficient algorithms for certifying the performance of a classifier on a test distribution. We give several positive results for learning concept classes such as halfspaces, intersections of halfspaces, and decision trees.
  arXiv  Detail & Related papers  (2023-11-25T23:57:45Z)
• Do PAC-Learners Learn the Marginal Distribution? [19.54058590042626]
  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$.<n>This work revisits the connection between PAC learning, uniform convergence, and density estimation beyond the distribution-free setting.
  arXiv  Detail & Related papers  (2023-02-13T11:42:58Z)
• 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)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• Learning Algorithm Generalization Error Bounds via Auxiliary Distributions [16.44492672878356]
  Generalization error bounds are essential for comprehending how well machine learning models work. In this work, we suggest a novel method, i.e., the Auxiliary Distribution Method, that leads to new upper bounds on expected generalization errors.
  arXiv  Detail & Related papers  (2022-10-02T10:37:04Z)
• Distributional Reinforcement Learning via Moment Matching [54.16108052278444]
  We formulate a method that learns a finite set of statistics from each return distribution via neural networks. Our method can be interpreted as implicitly matching all orders of moments between a return distribution and its Bellman target. Experiments on the suite of Atari games show that our method outperforms the standard distributional RL baselines.
  arXiv  Detail & Related papers  (2020-07-24T05:18:17Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

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.