PAC learning

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.

Most implemented papers archive 2025-07-28

13 shown of 13 papers with code (289 tagged with this task in all), ordered by repositories listed in the archive, not by stars (the archive holds no stars, so PwC's “Social” and “Latest” sorts cannot be reproduced). Papers without a page here are shown as plain text.

• VICE: Variational Interpretable Concept Embeddings
  2 May 2022 2 repositories listed Syntology ran 7 of 10 samples · 3 unverified · 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.
• Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models
  13 Sep 2020 2 repositories listed
  Computational learning theory states that many classes of boolean formulas are learnable in polynomial time.
• Lean Formalization of Generalization Error Bound by Rademacher Complexity
  25 Mar 2025 1 repository listed
  We formalize the generalization error bound using Rademacher complexity in the Lean 4 theorem prover.
• Prospective Learning: Learning for a Dynamic Future
  31 Oct 2024 1 repository listed Syntology ran 0 of 11 samples · 11 unverified · 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.
• Optimistic Rates for Learning from Label Proportions
  1 Jun 2024 1 repository listed Syntology ran 0 of 1 samples · 1 unverified · 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.
• Towards a theory of model distillation
  14 Mar 2024 1 repository listed Syntology ran 8 of 8 samples · 0 unverified · 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].
• SAT-Based PAC Learning of Description Logic Concepts
  15 May 2023 1 repository listed
  We propose bounded fitting as a scheme for learning description logic concepts in the presence of ontologies.
• Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation
  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…
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
  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.
• Quantum Boosting using Domain-Partitioning Hypotheses
  25 Oct 2021 1 repository listed
  Izdebski et al.
• SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory
  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.
• Regression Equilibrium
  4 May 2019 1 repository listed
  Despite their centrality in the competition between online companies who offer prediction-based products, the \textit{strategic} use of prediction algorithms remains unexplored.
• Introduction to Machine Learning: Class Notes 67577
  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…

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. Read from the graph 2026-09-24.