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.

  • 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 listed
    Computational learning theory states that many classes of boolean formulas are learnable in polynomial time.
  • 25 Mar 2025 1 repository listed
    We formalize the generalization error bound using Rademacher complexity in the Lean 4 theorem prover.
  • 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.
  • 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 listed
    We propose bounded fitting as a scheme for learning description logic concepts in the presence of ontologies.
  • 1 Nov 2022 1 repository listed
    We 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 listed
    We 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 listed
    Izdebski et al. posed an open question on whether we can boost quantum weak learners that output non-binary hypothesis.
  • 12 Oct 2020 1 repository listed
    Our 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 listed
    Despite 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 listed
    Introduction 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-hardness
    17 Jul 2025 0 repositories listed
    A 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 Learning
    19 Jun 2025 0 repositories listed
    The 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 learning
    5 Jun 2025 0 repositories listed
    Machine 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 Models
    27 May 2025 0 repositories listed
    We 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 Rate
    27 May 2025 0 repositories listed
    Attribute-efficient learning of sparse halfspaces has been a fundamental problem in machine learning theory.
  • A packing lemma for VCNₖ-dimension and learning high-dimensional data
    21 May 2025 0 repositories listed
    Recently, 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 objects
    1 Apr 2025 0 repositories listed
    We 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 integration
    13 Mar 2025 0 repositories listed
    NeuralODE 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 Voting
    5 Mar 2025 0 repositories listed
    We 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 Improvements
    5 Mar 2025 0 repositories listed
    One 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 Generalizability
    5 Mar 2025 0 repositories listed
    Recent 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 Noise
    25 Feb 2025 0 repositories listed
    Contrastive learning has emerged as a powerful paradigm for self-supervised representation learning.
  • Towards Efficient Contrastive PAC Learning
    21 Feb 2025 0 repositories listed
    We study contrastive learning under the PAC learning framework.
  • Bandit Multiclass List Classification
    13 Feb 2025 0 repositories listed
    We 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 Regime
    13 Feb 2025 0 repositories listed
    Binary 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 Tolerance
    11 Feb 2025 0 repositories listed
    Adversarially 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 Learning
    10 Feb 2025 0 repositories listed
    We study the problem of computable multiclass learnability within the Probably Approximately Correct (PAC) learning framework of Valiant (1984).
  • Data-Driven Neural Certificate Synthesis
    8 Feb 2025 0 repositories listed
  • Efficient Optimal PAC Learning
    5 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 Halfspaces
    31 Jan 2025 0 repositories listed
  • Ehrenfeucht-Haussler Rank and Chain of Thought
    22 Jan 2025 0 repositories listed
  • The working principles of model-based GAs fall within the PAC framework: A mathematical theory of problem decomposition
    18 Jan 2025 0 repositories listed
  • A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
    16 Jan 2025 0 repositories listed
  • Identifying Information from Observations with Uncertainty and Novelty
    16 Jan 2025 0 repositories listed
  • Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
    16 Jan 2025 0 repositories listed
  • A Closer Look at the Learnability of Out-of-Distribution (OOD) Detection
    15 Jan 2025 0 repositories listed
  • Monotonic Learning in the PAC Framework: A New Perspective
    9 Jan 2025 0 repositories listed
  • Ensuring superior learning outcomes and data security for authorized learner
    1 Jan 2025 0 repositories listed
  • Of Dice and Games: A Theory of Generalized Boosting
    11 Dec 2024 0 repositories listed
  • Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models
    23 Nov 2024 0 repositories listed
  • Effective Littlestone Dimension
    22 Nov 2024 0 repositories listed
  • Probably Approximately Precision and Recall Learning
    20 Nov 2024 0 repositories listed
  • Learning multivariate Gaussians with imperfect advice
    19 Nov 2024 0 repositories listed
  • Reliable Learning of Halfspaces under Gaussian Marginals
    18 Nov 2024 0 repositories listed
  • Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set
    12 Nov 2024 0 repositories listed
  • Screw Geometry Meets Bandits: Incremental Acquisition of Demonstrations to Generate Manipulation Plans
    23 Oct 2024 0 repositories listed
  • Enhancing PAC Learning of Half spaces Through Robust Optimization Techniques
    21 Oct 2024 0 repositories listed
  • Learning Linear Attention in Polynomial Time
    14 Oct 2024 0 repositories listed
  • Measurability in the Fundamental Theorem of Statistical Learning
    14 Oct 2024 0 repositories listed
  • Strategic Classification With Externalities
    10 Oct 2024 0 repositories listed
  • Agnostic Smoothed Online Learning
    7 Oct 2024 0 repositories listed
  • Fill In The Gaps: Model Calibration and Generalization with Synthetic Data
    7 Oct 2024 0 repositories listed
  • Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate
    2 Oct 2024 0 repositories listed
  • Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
    2 Oct 2024 0 repositories listed
  • Derandomizing Multi-Distribution Learning
    26 Sep 2024 0 repositories listed
  • Fast decision tree learning solves hard coding-theoretic problems
    19 Sep 2024 0 repositories listed
  • A Practical Theory of Generalization in Selectivity Learning
    11 Sep 2024 0 repositories listed
  • Revisiting Agnostic PAC Learning
    29 Jul 2024 0 repositories listed
  • Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem
    10 Jul 2024 0 repositories listed
  • Superconstant Inapproximability of Decision Tree Learning
    1 Jul 2024 0 repositories listed
  • Distribution Learnability and Robustness
    25 Jun 2024 0 repositories listed
  • Credit Attribution and Stable Compression
    22 Jun 2024 0 repositories listed
  • Fast Rates for Bandit PAC Multiclass Classification
    18 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 Learning
    14 Jun 2024 0 repositories listed
  • Weak Robust Compatibility Between Learning Algorithms and Counterfactual Explanation Generation Algorithms
    31 May 2024 0 repositories listed
  • On the Computational Landscape of Replicable Learning
    24 May 2024 0 repositories listed
  • Distribution Learning Meets Graph Structure Sampling
    13 May 2024 0 repositories listed
  • Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks
    11 May 2024 0 repositories listed
  • Is Transductive Learning Equivalent to PAC Learning?
    8 May 2024 0 repositories listed
  • Error Exponent in Agnostic PAC Learning
    1 May 2024 0 repositories listed
  • On the Power of Interactive Proofs for Learning
    11 Apr 2024 0 repositories listed
  • On the Learnability of Out-of-distribution Detection
    7 Apr 2024 0 repositories listed
  • Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
    31 Mar 2024 0 repositories listed
  • Hardness of Learning Boolean Functions from Label Proportions
    28 Mar 2024 0 repositories listed
  • List Sample Compression and Uniform Convergence
    16 Mar 2024 0 repositories listed
  • Majority-of-Three: The Simplest Optimal Learner?
    12 Mar 2024 0 repositories listed
  • Proper vs Improper Quantum PAC learning
    5 Mar 2024 0 repositories listed
  • High-arity PAC learning via exchangeability
    22 Feb 2024 0 repositories listed
  • Collaborative Learning with Different Labeling Functions
    16 Feb 2024 0 repositories listed
  • Private PAC Learning May be Harder than Online Learning
    16 Feb 2024 0 repositories listed
  • Transductive Learning Is Compact
    15 Feb 2024 0 repositories listed
  • The sample complexity of multi-distribution learning
    7 Dec 2023 0 repositories listed
  • ε-fractional Core Stability in Hedonic Games
    18 Nov 2023 0 repositories listed
  • Information-theoretic generalization bounds for learning from quantum data
    9 Nov 2023 0 repositories listed
  • Low-Rank MDPs with Continuous Action Spaces
    6 Nov 2023 0 repositories listed
  • A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs
    18 Oct 2023 0 repositories listed
  • PAC Learning Linear Thresholds from Label Proportions
    16 Oct 2023 0 repositories listed
  • Overview of AdaBoost : Reconciling its views to better understand its dynamics
    6 Oct 2023 0 repositories listed
  • Distributional PAC-Learning from Nisan's Natural Proofs
    5 Oct 2023 0 repositories listed
  • Inference for Gaussian Processes with Matern Covariogram on Compact Riemannian Manifolds
    21 Sep 2023 0 repositories listed
  • Inference for Gaussian Processes with Matern Covariogram on Compact Riemannian Manifolds
    21 Sep 2023 0 repositories listed
  • User-Level Differential Privacy With Few Examples Per User
    21 Sep 2023 0 repositories listed
  • Provable learning of quantum states with graphical models
    17 Sep 2023 0 repositories listed
  • Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings
    19 Aug 2023 0 repositories listed
  • Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials
    24 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