# pac-learning Published articles for pac-learning. This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles. ## Marginal-Nonuniform Multiclass Learning DevFeed: [Marginal-Nonuniform Multiclass Learning]() Original publisher: [Read original article]() Author: Nataly Brukhim, Steve Hanneke, Amirreza Shaeiri, Maximilian Thiessen Published: 2026-11-09T05:00:00Z Content type: article Language: en Sources: [arXiv: Machine Learning]() Topics: [Machine learning](), [concept-learning]() Tags: [characterization](), [classification](), [cs-lg](), [dimension](), [distribution](), [learning](), [linear](), [machine-learning](), [pac-learning](), [stat-ml]() ### AI overview Marginal-nonuniform multiclass learning permits learning-rate constants to depend on the unlabeled-data marginal, but not on the target concept. The work places this setting between classical PAC learning, whose constants depend on neither, and universal learning, whose constants may depend on both. It characterizes optimal rates as a trichotomy: exponential, linear, or arbitrarily slow, witnessed by the uncentered DS-eluder dimension. Its upper-bound proofs use new distributional exhaustion lemmas that exploit the dimension's sequential structure. ### Source excerpt arXiv:2611.09543v1 Announce Type: new Abstract: We study the problem of multiclass classification within the framework of marginal-nonuniform learning, where the constants in the learning rate may depend on the unknown marginal distribution generating the unlabeled data, but not on the target concept. This notion naturally lies between classical PAC learning, where the constants are independent of both the marginal distribution and the target concept, and more recent universal learning, where the constants may depend on both. We give a complete characterization of the optimal marginal-nonuniform learning rates, establishing a fundamental trichotomy: exponential, linear, and arbitrarily slow rates. This characterization is witnessed by a new combinatorial dimension, termed the uncentered DS-eluder dimension. A key ingredient in the upper-bound proofs is a set of new distributional exhaustion lemmas that exploit the sequential nature of this dimension and may be of independent interest. ## PAC Learning with Multiple Correct Answers DevFeed: [PAC Learning with Multiple Correct Answers]() Original publisher: [Read original article]() Author: Steve Hanneke, Farnam Mansouri, Alireza F. Pour, Amirreza Shaeiri, Kun Wang Published: 2026-11-04T05:00:00Z Content type: article Language: en Sources: [arXiv: Machine Learning]() Topics: [Machine learning](), [generalization in machine learning]() Tags: [bandit](), [cs-lg](), [machine-learning](), [pac-learning]() ### AI overview With at most ℓ correct labels per example, learning from a demonstrator's single chosen label can be harder than learning from full label sets or bandit feedback, in both learnability and sample complexity. For finite label spaces, generalized Natarajan dimension characterizes full-set and bandit learnability in realizable and agnostic settings. Realizable learning from demonstrations instead holds exactly when intersections of up to ℓ+1 hypotheses are learnable from full sets; when it holds, Õ(ε⁻ℓ) demonstrations suffice, and that exponent is generally necessary. For countable labels with ℓ >= 2, a packed dimension characterizes full-set learnability, while demonstration learning again reduces to intersections. Agnostic demonstration learning is not characterized by the same intersection-class dimensions, and without a uniform bound on correct labels no dimension based on finite subclasses can characterize learnability. ### Source excerpt arXiv:2611.05133v1 Announce Type: new Abstract: We study PAC learning when each example comes with a set of at most $\ell$ correct labels and a prediction is correct if it belongs to this set. Training may reveal the full set, only whether a proposed label is correct (bandit feedback), or one correct label chosen by a demonstrator (emonstrations). Our main finding is that demonstrations can be much harder than full sets, and even than bandit feedback, both in which classes can be learned and in how many examples are needed. For finite label spaces, a generalized Natarajan dimension characterizes learnability from full sets and from bandit feedback, in both the realizable and the agnostic setting. From demonstrations, however, a class is realizably learnable if and only if the intersections of at most $\ell+1$ of its hypotheses are learnable from full sets. Already with three labels, this condition can fail for a class learnable from a single full-set example or even a single bandit answer. When the condition holds, we show that $\widetilde O(\varepsilon^{-\ell})$ demonstrations suffice, and the exponent $\ell$ cannot be improved in general, even for classes learnable from $\widetilde O(1/\varepsilon)$ full sets or bandit answers. For countable label spaces and $\ell \geq 2$, our packed dimension, which asks for many disjoint groups of at most $\ell+1$ hypotheses with no common label, characterizes full-set learnability, and demonstrations still reduce to intersections. Agnostic learning from demonstrations, already for finite label spaces, is not determined by the dimensions of the intersection class that characterize realizable learning. Finally, we show that the uniform bound $\ell$ on the number of correct labels is essential. Without this bound, it is impossible to characterize learnability by any dimension determined by finite subclasses. ## New Lower Bounds for Private PAC Learning DevFeed: [New Lower Bounds for Private PAC Learning]() Original publisher: [Read original article]() Author: Prathamesh Dharangutte, Amartya Sanyal Published: 2026-11-02T05:00:00Z Content type: article Language: en Sources: [arXiv: Machine Learning]() Topics: [Machine learning](), [concept-learning]() Tags: [complexity](), [convex](), [cs-lg](), [differential-privacy](), [dimensions](), [learning](), [lower-bounds](), [machine-learning](), [pac-learning](), [private](), [sample](), [study](), [union](), [vc]() ### AI overview The paper introduces Independent Class Packing (ICP) to derive sample-complexity lower bounds for realizable PAC learning under approximate differential privacy. It shows that matching VC and Littlestone dimensions do not guarantee matching private sample complexity, even for improper learners. For a class H, every (ε, δ)-DP, (α, β)-PAC learner requires Ω(ICP(H,G)/(αε)) examples. The framework gives tight lower bounds for axis-aligned rectangles, unions of intervals, and linear subspaces, and improved bounds for halfspaces and convex polygons. For product classes, and more generally when the relevant classes pack into H and cover its domain so target labels can be used directly, ICP characterizes private sample complexity up to logarithmic factors. ### Source excerpt arXiv:2610.41980v1 Announce Type: new Abstract: We study realizable PAC learning under approximate differential privacy, and give a framework for proving lower bounds on its sample complexity. We construct classes with identical VC and Littlestone dimensions but different private sample complexities at common privacy and accuracy parameters, showing that these dimensions do not determine the sample complexity, even for improper learners. To address this we introduce the Independent Class Packing (ICP) parameter, the largest total sample complexity of classes in $\mathcal{G}$ that can be packed independently into a class $\mathcal{H}$, and prove that every $(\varepsilon, \delta)$-DP, $(\alpha, \beta)$-PAC learner for $\mathcal{H}$, possibly improper, uses $\Omega\left(\mathrm{ICP}(\mathcal{H}, \mathcal{G})/(\alpha\varepsilon)\right)$ examples. Using this framework we prove tight lower bounds for axis-aligned rectangles, union of intervals and linear subspaces and improved lower bounds for halfspaces and convex polygons. Finally we also show that for product classes, and more generally when the same classes pack into $\mathcal{H}$ and cover its domain so that target labels can be used directly, ICP characterizes private PAC sample complexity up to logarithmic factors. ## Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries DevFeed: [Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries]() Original publisher: [Read original article]() Author: Natsuto Isogai, Satoshi Yoshida, Mio Murao Published: 2026-10-28T04:00:00Z Content type: article Language: en Sources: [arXiv: Machine Learning]() Topics: [Machine learning](), [concept-learning](), [computational complexity](), [quantum mechanics]() Tags: [algorithm](), [complexity](), [cs-lg](), [dimensions](), [distribution](), [learner](), [learning](), [lower-bounds](), [machine-learning](), [pac-learning](), [physics](), [quant-ph](), [quantum](), [quantum-machine-learning](), [quantum-physics](), [queries](), [query](), [reduction](), [sample](), [simulator](), [stat-ml](), [state](), [training]() ### AI overview In worst-case quantum PAC learning, forward-only access to a state-preparation unitary provides no asymptotic sample-complexity advantage: for both realizable and agnostic learning, optimal query complexity matches, up to constant factors, the optimal sample complexity using classical examples or copies of quantum examples. The result is taken over compatible preparation unitaries and their dimensions. The authors prove it by simulating a forward-only algorithm's Haar-averaged output with as many prepared-state copies as the algorithm makes queries. Thus, inverse access is essential to the known improvement in accuracy dependence in this setting. The reduction also transfers lower bounds for state copies to query lower bounds for forward-only preparation-unitary access. ### Source excerpt arXiv:2609.38403v2 Announce Type: replace-cross Abstract: Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement. In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries. ## Near-Optimal List Replicability from Littlestone Dimension DevFeed: [Near-Optimal List Replicability from Littlestone Dimension]() Original publisher: [Read original article]() Author: Ari Blondal, Pooya Hatami, Chavdar Lalov, Sivan Tretiak Published: 2026-10-26T04:00:00Z Content type: article Language: en Sources: [arXiv: Machine Learning]() Topics: [Machine learning](), [concept-learning]() Tags: [class](), [cs-lg](), [dimension](), [domain](), [list](), [lower-bound](), [pac-learning](), [private]() ### AI overview For realizable PAC learning over countable domains, the paper bounds list replicability by LR(H) ≤ 2^{O(d min{log d, v*)}}, where d is the Littlestone dimension and v* the dual VC dimension. The authors say this is within a logarithmic factor in the exponent of the worst-case lower bound and exponentially improves the prior 2^{2^{O(d)}} upper bound; unlike cited earlier bounds for fixed accuracy, it is independent of ε. The 2^{O(d log d)} result uses an inductive framework based on irreducibility from differentially private learning. The 2^{O(dv*)} result uses a globally stable learner formed by majority vote over multiple empirical risk minimizers, with stability shown using stable regularity. ### Source excerpt arXiv:2610.32853v1 Announce Type: new Abstract: We study the list replicability number in the realizable PAC learning framework and prove that every concept class $H$ over a countable domain with Littlestone dimension $d$ and dual VC dimension $v^*$ satisfies \[ \mathrm{LR}(H)\leq 2^{O(d\min\{\log d,v^*\})}. \] This matches the worst-case lower bound of $2^{\Omega(d)}$ up to a logarithmic factor in the exponent and exponentially improves the previous best upper bound $\mathrm{LR}(H)\le 2^{2^{O(d)}}$ of Bun, Livni, and Moran [FOCS 2020]. Unlike earlier bounds of $2^{O_\epsilon(d^2)}$ for fixed accuracy $\epsilon>0$ implied by the work of Ghazi, Golowich, Kumar, and Manurangsi [STOC 2021] and Lyu [STOC 2026], our bound is independent of $\epsilon$. The $2^{O(d\log d)}$ bound follows from a new inductive framework for bounding list replicability that builds on the recent notion of irreducibility from differentially private learning. The $2^{O(dv^*)}$ bound follows from a simple globally stable learner that takes the majority vote of multiple empirical risk minimizers, with stability established using tools from stable regularity. ## PAC Learning with Query Feedback DevFeed: [PAC Learning with Query Feedback]() Original publisher: [Read original article]() Author: Chase Hutton, Adam Melrod, Han Shao Published: 2026-10-21T04:00:00Z Content type: article Language: en Sources: [arXiv: Machine Learning]() Topics: [Machine learning](), [concept-learning]() Tags: [cs-lg](), [feedback](), [learning](), [pac-learning](), [query]() ### AI overview In realizable multiclass PAC learning with query feedback, each example yields one binary answer about whether its true label lies in a queried subset. The paper introduces the query dimension, which accounts for both the hypothesis class and how well the fixed query family distinguishes labels; with singleton queries it recovers the bandit DS dimension. The sample complexity is bounded below by Ω(D/ε) and above by Õ(D²/ε), up to polylogarithmic factors in the number of labels and failure probability. If queries can split every candidate set into two comparably sized parts, the upper bound improves to Õ(D/ε), matching the lower bound up to logarithmic factors. ### Source excerpt arXiv:2610.24332v1 Announce Type: new Abstract: We study realizable multiclass PAC learning with query feedback, where each training example provides a single binary response indicating whether its true label belongs to a chosen subset from a fixed query family. Our main contribution is the query dimension, a combinatorial parameter that captures both the structure of the hypothesis class and the ability of the available queries to distinguish labels. This parameter generalizes the bandit DS dimension, which it recovers under singleton queries. We establish a sample-complexity lower bound of $\Omega(D/\varepsilon)$ and an upper bound of $\widetilde{O}(D^2/\varepsilon)$, suppressing factors polylogarithmic in the number of labels and the failure probability. When the available queries can split every candidate set into two parts of comparable size, we improve the upper bound to $\widetilde{O}(D/\varepsilon)$, yielding a characterization up to logarithmic factors. ## Weak Learning, Boosting, and the AdaBoost algorithm DevFeed: [Weak Learning, Boosting, and the AdaBoost algorithm]() Original publisher: [Read original article]() Published: 2015-05-18T09:00:00Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Algorithms](), [Learning]() Tags: [algorithm](), [better](), [boosting](), [classification](), [distribution](), [efficiently](), [function](), [learner](), [learning](), [models](), [number](), [pac-learning](), [re](), [runtime]() ### AI overview This article introduces learning models in the context of Probably Approximately Correct (PAC) learning and compares the usual PAC model with weak PAC learning. It explains that weak learning requires accuracy only slightly better than random guessing and states that weak and strong learning are equivalent. ### Source excerpt When addressing the question of what it means for an algorithm to learn, one can imagine many different models, and there are quite a few. This invariably raises the question of which models are "the same" and which are "different," along with a precise description of how we're comparing models. We've seen one learning model so far, called Probably Approximately Correct (PAC), which espouses the following answer to the learning question: ## Occam's Razor and PAC-learning DevFeed: [Occam's Razor and PAC-learning]() Original publisher: [Read original article]() Published: 2014-09-19T10:00:47Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Occam's razor machine learning](), [Learning](), [data]() Tags: [chernoff](), [chernoff-bound](), [computational-learning-theory](), [learning-theory](), [occam-s-razor](), [pac-learning](), [vc-dimension]() ### AI overview This tutorial develops a simple PAC-learning theorem for a finite hypothesis class. It explains that if a hypothesis consistent with observed data can always be found, the class can be learned efficiently, and it uses the Chernoff-Hoeffding bound to quantify the sample requirement for achieving low error. ### Source excerpt So far our discussion of learning theory has been seeing the definition of PAC-learning, tinkering with it, and seeing simple examples of learnable concept classes. We've said that our real interest is in proving big theorems about what big classes of problems can and can't be learned. One major tool for doing this with PAC is the concept of VC-dimension, but to set the stage we're going to prove a simpler theorem that gives a nice picture of PAC-learning when your hypothesis class is small. ## A problem that is not (properly) PAC-learnable DevFeed: [A problem that is not (properly) PAC-learnable]() Original publisher: [Read original article]() Published: 2014-04-21T10:00:16Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Learning](), [Mathematics](), [Math and Logic]() Tags: [algorithm](), [boolean](), [boolean-satisfiability](), [classes](), [computational-complexity](), [computational-learning-theory](), [learning-theory](), [logical](), [math](), [mathematics](), [misconceptions](), [np](), [np-completeness](), [pac-learning](), [reduction](), [rp]() ### AI overview This technical learning-theory article presents a standard example of a problem that is not learnable under the previously introduced PAC model, then explains how a more expressive hypothesis class changes that result. Its addendum clarifies that 3-term DNF formulas are not shown to be unlearnable under the standard PAC definition, only under the earlier restricted definition. ### Source excerpt In a previous post we introduced a learning model called Probably Approximately Correct (PAC). We saw an example of a concept class that was easy to learn: intervals on the real line (and more generally, if you did the exercise, axis-aligned rectangles in a fixed dimension). One of the primary goals of studying models of learning is to figure out what is learnable and what is not learnable in the various models. ## Probably Approximately Correct -- a Formal Theory of Learning DevFeed: [Probably Approximately Correct -- a Formal Theory of Learning]() Original publisher: [Read original article]() Published: 2014-01-02T18:45:51Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Learning](), [Artificial Intelligence](), [Machine learning](), [Computer science](), [Mathematics]() Tags: [learning](), [learning-theory](), [machine-learning](), [mathematics](), [occam-s-razor](), [pac-learning](), [theory]() ### AI overview A mathematical introduction to PAC learning, a foundational framework in computational learning theory. The article develops basic definitions, explains PAC-learnability through interval examples, and places the theory in its historical context. ### Source excerpt In tackling machine learning (and computer science in general) we face some deep philosophical questions. Questions like, "What does it mean to learn?" and, "Can a computer learn?" and, "How do you define simplicity?" and, "Why does Occam's Razor work? (Why do simple hypotheses do well at modelling reality?)" In a very deep sense, learning theorists take these philosophical questions -- or at least aspects of them -- give them fleshy mathematical bodies, and then answer them with theorems and proofs.