Browse State-of-the-Art › PAC learning
PAC learning
13 papers with code · 0 benchmarks · 0 datasets archive 2025-07-28
Probably Approximately Correct (PAC) learning analyzes machine learning mathematically using probability bounds.
Description from the archive archive 2025-07-28.
Benchmarks archive 2025-07-28
No benchmark for this task in the archive.
Libraries
Not in the archive: the export carries no per-task library table, so there is nothing to show at snapshot 2025-07-28.
Datasets archive 2025-07-28
No dataset record in the archive lists this task.
Subtasks archive 2025-07-28
No subtask under this task in the archive's task tree.
Papers archive 2025-07-28
archive papers tagged: 289 · with a code link: 13 · where Syntology ran a sample: 3 (3 with a run with no instrument failure, 0 where every run was a failure of Syntology's instrument) Syntology
Show: all tagged papersonly where code ran (3 of 289 tagged: 3 with a run with no instrument failure, 0 where every run was a failure of Syntology's instrument)
Page 1 of 3: papers 1 to 100 of 289, in archive order: by repositories listed in the archive (most first), then newest first, not by stars (the archive holds no stars, so PwC's “Social” and “Latest” sorts cannot be reproduced). Papers that list no repository come after every paper that lists one.
Papers without a page here are shown as plain text. A Syntology line reads “N ran (of which C constructed an object rather than computing a result; K with no instrument failure: H honoured, V violated, P with no contract checked; I where Syntology's instrument failed) · U unverified”; the figure “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. When the archive marks a repository official for the paper, the line starts with that repository's state (the archive's flag, not a verdict on who wrote the code); hover it for the repositories the samples that ran came from. The first sentence of the abstract is shown for the first 30 papers; every abstract is on its paper's page.
-
2 May 2022 2 repositories listed Syntology official (archive's flag): 2 ran · 7 ran (of which 0 constructed an object rather than computing a result; 5 with no instrument failure: 0 honoured, 0 violated, 5 with no contract checked; 2 where Syntology's instrument failed) · 3 unverified (of 10 harvested samples) · 10 pointer-only (licence)This paper introduces Variational Interpretable Concept Embeddings (VICE), an approximate Bayesian method for embedding object concepts in a vector space using data collected from humans in a triplet odd-one-out task.
-
13 Sep 2020 2 repositories listedComputational learning theory states that many classes of boolean formulas are learnable in polynomial time.
-
25 Mar 2025 1 repository listedWe formalize the generalization error bound using Rademacher complexity in the Lean 4 theorem prover.
-
31 Oct 2024 1 repository listed Syntology official (archive's flag): 9 ran · 9 ran (of which 0 constructed an object rather than computing a result; 7 with no instrument failure: 2 honoured, 1 violated, 4 with no contract checked; 2 where Syntology's instrument failed) · 2 unverified (of 11 harvested samples) · 11 pointer-only (licence)We show that standard ERM as done in PAC learning, without incorporating time, can result in failure to learn when distributions are dynamic.
-
1 Jun 2024 1 repository listed Syntology official: harvested, nothing ran · 0 ran · 1 unverified (of 1 harvested sample) · 1 pointer-only (licence)We consider a weakly supervised learning problem called Learning from Label Proportions (LLP), where examples are grouped into ``bags'' and only the average label within each bag is revealed to the learner.
-
14 Mar 2024 1 repository listed Syntology official (archive's flag): 8 ran · 8 ran (of which 0 constructed an object rather than computing a result; 6 with no instrument failure: 2 honoured, 0 violated, 4 with no contract checked; 2 where Syntology's instrument failed) · 0 unverified (of 8 harvested samples) · 8 pointer-only (licence)Distillation is the task of replacing a complicated machine learning model with a simpler model that approximates the original [BCNM06, HVD15].
-
15 May 2023 1 repository listedWe propose bounded fitting as a scheme for learning description logic concepts in the presence of ontologies.
-
1 Nov 2022 1 repository listedWe establish a simple connection between robust and differentially-private algorithms: private mechanisms which perform well with very high probability are automatically robust in the sense that they retain accuracy…
-
5 Jan 2022 1 repository listedWe show that PYGON can recover cliques of sizes Θ(√(n)), where n is the size of the background graph, comparable with the state of the art.
-
25 Oct 2021 1 repository listedIzdebski et al. posed an open question on whether we can boost quantum weak learners that output non-binary hypothesis.
-
12 Oct 2020 1 repository listedOur theoretical and experimental results shed light on the conditions required for efficient probably approximately correct (PAC) learning of the Kalman filter from partially observed data.
-
4 May 2019 1 repository listedDespite their centrality in the competition between online companies who offer prediction-based products, the strategic use of prediction algorithms remains unexplored.
-
23 Apr 2009 1 repository listedIntroduction to Machine learning covering Statistical Inference (Bayes, EM, ML/MaxEnt duality), algebraic and spectral methods (PCA, LDA, CCA, Clustering), and PAC learning (the Formal model, VC dimension, Double…
-
Computational-Statistical Tradeoffs from NP-hardness17 Jul 2025 0 repositories listedA central question in computer science and statistics is whether efficient algorithms can achieve the information-theoretic limits of statistical problems.
-
A Distributional-Lifting Theorem for PAC Learning19 Jun 2025 0 repositories listedThe apparent difficulty of efficient distribution-free PAC learning has led to a large body of work on distribution-specific learning.
-
Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning5 Jun 2025 0 repositories listedMachine learning is now ubiquitous in societal decision-making, for example in evaluating job candidates or loan applications, and it is increasingly important to take into account how classified agents will react to…
-
Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models27 May 2025 0 repositories listedWe study the complexity of learning real-valued Multi-Index Models (MIMs) under the Gaussian distribution.
-
Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate27 May 2025 0 repositories listedAttribute-efficient learning of sparse halfspaces has been a fundamental problem in machine learning theory.
-
A packing lemma for VCNₖ-dimension and learning high-dimensional data21 May 2025 0 repositories listedRecently, the authors introduced the theory of high-arity PAC learning, which is well-suited for learning graphs, hypergraphs and relational structures.
-
From learnable objects to learnable random objects1 Apr 2025 0 repositories listedWe consider the relationship between learnability of a "base class" of functions on a set X, and learnability of a class of statistical functions derived from the base class.
-
Numerical and statistical analysis of NeuralODE with Runge-Kutta time integration13 Mar 2025 0 repositories listedNeuralODE is one example for generative machine learning based on the push forward of a simple source measure with a bijective mapping, which in the case of NeuralODE is given by the flow of a ordinary differential…
-
A Linear Theory of Multi-Winner Voting5 Mar 2025 0 repositories listedWe introduces a general linear framework that unifies the study of multi-winner voting rules and proportionality axioms, demonstrating that many prominent multi-winner voting rules-including Thiele methods, their…
-
PAC Learning with Improvements5 Mar 2025 0 repositories listedOne of the most basic lower bounds in machine learning is that in nearly any nontrivial setting, it takes at least 1/ϵ samples to learn to error ϵ (and more, if the classifier being learned is complex).
-
Towards Understanding Multi-Round Large Language Model Reasoning: Approximability, Learnability and Generalizability5 Mar 2025 0 repositories listedRecent advancements in cognitive science and multi-round reasoning techniques for Large Language Models (LLMs) suggest that iterative thinking processes improve problem-solving performance in complex tasks.
-
Contrastive Learning with Nasty Noise25 Feb 2025 0 repositories listedContrastive learning has emerged as a powerful paradigm for self-supervised representation learning.
-
Towards Efficient Contrastive PAC Learning21 Feb 2025 0 repositories listedWe study contrastive learning under the PAC learning framework.
-
Bandit Multiclass List Classification13 Feb 2025 0 repositories listedWe study the problem of multiclass list classification with (semi-)bandit feedback, where input examples are mapped into subsets of size m of a collection of K possible labels, and the feedback consists of the predicted…
-
On Agnostic PAC Learning in the Small Error Regime13 Feb 2025 0 repositories listedBinary classification in the classic PAC model exhibits a curious phenomenon: Empirical Risk Minimization (ERM) learners are suboptimal in the realizable case yet optimal in the agnostic case.
-
Simplifying Adversarially Robust PAC Learning with Tolerance11 Feb 2025 0 repositories listedAdversarially robust PAC learning has proved to be challenging, with the currently best known learners [Montasser et al., 2021a] relying on improper methods based on intricate compression schemes, resulting in sample…
-
On the Computability of Multiclass PAC Learning10 Feb 2025 0 repositories listedWe study the problem of computable multiclass learnability within the Probably Approximately Correct (PAC) learning framework of Valiant (1984).
-
Data-Driven Neural Certificate Synthesis8 Feb 2025 0 repositories listed
-
Efficient Optimal PAC Learning5 Feb 2025 0 repositories listed
-
PAC Learning is just Bipartite Matching (Sort of)2 Feb 2025 0 repositories listed
-
Distribution-Specific Agnostic Conditional Classification With Halfspaces31 Jan 2025 0 repositories listed
-
Ehrenfeucht-Haussler Rank and Chain of Thought22 Jan 2025 0 repositories listed
-
The working principles of model-based GAs fall within the PAC framework: A mathematical theory of problem decomposition18 Jan 2025 0 repositories listed
-
A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise16 Jan 2025 0 repositories listed
-
Identifying Information from Observations with Uncertainty and Novelty16 Jan 2025 0 repositories listed
-
Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random16 Jan 2025 0 repositories listed
-
A Closer Look at the Learnability of Out-of-Distribution (OOD) Detection15 Jan 2025 0 repositories listed
-
Monotonic Learning in the PAC Framework: A New Perspective9 Jan 2025 0 repositories listed
-
Ensuring superior learning outcomes and data security for authorized learner1 Jan 2025 0 repositories listed
-
Of Dice and Games: A Theory of Generalized Boosting11 Dec 2024 0 repositories listed
-
Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models23 Nov 2024 0 repositories listed
-
Effective Littlestone Dimension22 Nov 2024 0 repositories listed
-
Probably Approximately Precision and Recall Learning20 Nov 2024 0 repositories listed
-
Learning multivariate Gaussians with imperfect advice19 Nov 2024 0 repositories listed
-
Reliable Learning of Halfspaces under Gaussian Marginals18 Nov 2024 0 repositories listed
-
Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set12 Nov 2024 0 repositories listed
-
Screw Geometry Meets Bandits: Incremental Acquisition of Demonstrations to Generate Manipulation Plans23 Oct 2024 0 repositories listed
-
Enhancing PAC Learning of Half spaces Through Robust Optimization Techniques21 Oct 2024 0 repositories listed
-
Learning Linear Attention in Polynomial Time14 Oct 2024 0 repositories listed
-
Measurability in the Fundamental Theorem of Statistical Learning14 Oct 2024 0 repositories listed
-
Strategic Classification With Externalities10 Oct 2024 0 repositories listed
-
Agnostic Smoothed Online Learning7 Oct 2024 0 repositories listed
-
Fill In The Gaps: Model Calibration and Generalization with Synthetic Data7 Oct 2024 0 repositories listed
-
Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate2 Oct 2024 0 repositories listed
-
Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians2 Oct 2024 0 repositories listed
-
Derandomizing Multi-Distribution Learning26 Sep 2024 0 repositories listed
-
Fast decision tree learning solves hard coding-theoretic problems19 Sep 2024 0 repositories listed
-
A Practical Theory of Generalization in Selectivity Learning11 Sep 2024 0 repositories listed
-
Revisiting Agnostic PAC Learning29 Jul 2024 0 repositories listed
-
Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem10 Jul 2024 0 repositories listed
-
Superconstant Inapproximability of Decision Tree Learning1 Jul 2024 0 repositories listed
-
Distribution Learnability and Robustness25 Jun 2024 0 repositories listed
-
Credit Attribution and Stable Compression22 Jun 2024 0 repositories listed
-
Fast Rates for Bandit PAC Multiclass Classification18 Jun 2024 0 repositories listed
-
Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?17 Jun 2024 0 repositories listed
-
On the Computability of Robust PAC Learning14 Jun 2024 0 repositories listed
-
Weak Robust Compatibility Between Learning Algorithms and Counterfactual Explanation Generation Algorithms31 May 2024 0 repositories listed
-
On the Computational Landscape of Replicable Learning24 May 2024 0 repositories listed
-
Distribution Learning Meets Graph Structure Sampling13 May 2024 0 repositories listed
-
Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks11 May 2024 0 repositories listed
-
Is Transductive Learning Equivalent to PAC Learning?8 May 2024 0 repositories listed
-
Error Exponent in Agnostic PAC Learning1 May 2024 0 repositories listed
-
On the Power of Interactive Proofs for Learning11 Apr 2024 0 repositories listed
-
On the Learnability of Out-of-distribution Detection7 Apr 2024 0 repositories listed
-
Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs31 Mar 2024 0 repositories listed
-
Hardness of Learning Boolean Functions from Label Proportions28 Mar 2024 0 repositories listed
-
List Sample Compression and Uniform Convergence16 Mar 2024 0 repositories listed
-
Majority-of-Three: The Simplest Optimal Learner?12 Mar 2024 0 repositories listed
-
Proper vs Improper Quantum PAC learning5 Mar 2024 0 repositories listed
-
High-arity PAC learning via exchangeability22 Feb 2024 0 repositories listed
-
Collaborative Learning with Different Labeling Functions16 Feb 2024 0 repositories listed
-
Private PAC Learning May be Harder than Online Learning16 Feb 2024 0 repositories listed
-
Transductive Learning Is Compact15 Feb 2024 0 repositories listed
-
The sample complexity of multi-distribution learning7 Dec 2023 0 repositories listed
-
ε-fractional Core Stability in Hedonic Games18 Nov 2023 0 repositories listed
-
Information-theoretic generalization bounds for learning from quantum data9 Nov 2023 0 repositories listed
-
Low-Rank MDPs with Continuous Action Spaces6 Nov 2023 0 repositories listed
-
A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs18 Oct 2023 0 repositories listed
-
PAC Learning Linear Thresholds from Label Proportions16 Oct 2023 0 repositories listed
-
Overview of AdaBoost : Reconciling its views to better understand its dynamics6 Oct 2023 0 repositories listed
-
Distributional PAC-Learning from Nisan's Natural Proofs5 Oct 2023 0 repositories listed
-
Inference for Gaussian Processes with Matern Covariogram on Compact Riemannian Manifolds21 Sep 2023 0 repositories listed
-
Inference for Gaussian Processes with Matern Covariogram on Compact Riemannian Manifolds21 Sep 2023 0 repositories listed
-
User-Level Differential Privacy With Few Examples Per User21 Sep 2023 0 repositories listed
-
Provable learning of quantum states with graphical models17 Sep 2023 0 repositories listed
-
Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings19 Aug 2023 0 repositories listed
-
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials24 Jul 2023 0 repositories listed
Syntology lines on 4 of the papers shown; no Syntology record for the others (a paper without an arXiv id cannot be joined to the graph, and absence from the graph layer is not a recorded non-run). “Ran” means the sample executed on a synthesized fixture, not that the paper's result was reproduced; each line links to that paper's sample list. Syntology's record for this page last changed ; when this build read Syntology's graph is in the build record. For agents: get_harvested_code_for_paper(arxiv_id) lists each paper's samples; how to connect.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections