Browse State-of-the-Art › PAC learning › Papers, page 2

PAC learning

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 2 of 3: papers 101 to 200 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. Abstracts are on each paper's page.

• The Sample Complexity of Multi-Distribution Learning for VC Classes
  22 Jul 2023 0 repositories listed
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning
  7 Jul 2023 0 repositories listed
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
  2 Jul 2023 0 repositories listed
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise
  28 Jun 2023 0 repositories listed
• Learnability with PAC Semantics for Multi-agent Beliefs
  8 Jun 2023 0 repositories listed
• On the Role of Entanglement and Statistics in Learning
  5 Jun 2023 0 repositories listed
• Agnostic Multi-Group Active Learning
  2 Jun 2023 0 repositories listed
• Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise
  1 Jun 2023 0 repositories listed
• On the Role of Noise in the Sample Complexity of Learning Recurrent Neural Networks: Exponential Gaps for Long Sequences
  28 May 2023 0 repositories listed
• Policy Synthesis and Reinforcement Learning for Discounted LTL
  26 May 2023 0 repositories listed
• A Parameterized Theory of PAC Learning
  27 Apr 2023 0 repositories listed
• Probably Approximately Correct Federated Learning
  10 Apr 2023 0 repositories listed
• Online Learning and Disambiguations of Partial Concept Classes
  30 Mar 2023 0 repositories listed
• Lifting uniform learners via distributional decomposition
  27 Mar 2023 0 repositories listed
• Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
  22 Mar 2023 0 repositories listed
• Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression
  8 Mar 2023 0 repositories listed
• On the complexity of PAC learning in Hilbert spaces
  3 Mar 2023 0 repositories listed
• Do PAC-Learners Learn the Marginal Distribution?
  13 Feb 2023 0 repositories listed
• Tree Learning: Optimal Algorithms and Sample Complexity
  9 Feb 2023 0 repositories listed
• Find a witness or shatter: the landscape of computable PAC learning
  6 Feb 2023 0 repositories listed
• PAC learning and stabilizing Hedonic Games: towards a unifying approach
  31 Jan 2023 0 repositories listed
• Optimal lower bounds for Quantum Learning via Information Theory
  5 Jan 2023 0 repositories listed
• A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning
  6 Dec 2022 0 repositories listed
• Bagging is an Optimal PAC Learner
  5 Dec 2022 0 repositories listed
• PAC Verification of Statistical Algorithms
  28 Nov 2022 0 repositories listed
• Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
  16 Nov 2022 0 repositories listed
• On Proper Learnability between Average- and Worst-case Robustness
  10 Nov 2022 0 repositories listed
• A Characterization of List Learnability
  7 Nov 2022 0 repositories listed
• Is Out-of-Distribution Detection Learnable?
  26 Oct 2022 0 repositories listed
• Learning versus Refutation in Noninteractive Local Differential Privacy
  26 Oct 2022 0 repositories listed
• SQ Lower Bounds for Learning Single Neurons with Massart Noise
  18 Oct 2022 0 repositories listed
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing
  12 Oct 2022 0 repositories listed
• Unified Algorithms for RL with Decision-Estimation Coefficients: PAC, Reward-Free, Preference-Based Learning, and Beyond
  23 Sep 2022 0 repositories listed
• Analyzing Robustness of Angluin's L* Algorithm in Presence of Noise
  21 Sep 2022 0 repositories listed
• On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data
  17 Sep 2022 0 repositories listed
• Fine-Grained Distribution-Dependent Learning Curves
  31 Aug 2022 0 repositories listed
• Cryptographic Hardness of Learning Halfspaces with Massart Noise
  28 Jul 2022 0 repositories listed
• Generalization Bounds for Data-Driven Numerical Linear Algebra
  16 Jun 2022 0 repositories listed
• PAC Generalization via Invariant Representations
  30 May 2022 0 repositories listed
• Bézier Flow: a Surface-wise Gradient Descent Method for Multi-objective Optimization
  23 May 2022 0 repositories listed
• Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks
  12 May 2022 0 repositories listed
• Clifford Circuits can be Properly PAC Learned if and only if RP=NP
  13 Apr 2022 0 repositories listed
• Active-learning-based non-intrusive Model Order Reduction
  8 Apr 2022 0 repositories listed
• Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability
  9 Mar 2022 0 repositories listed
• A Characterization of Multiclass Learnability
  3 Mar 2022 0 repositories listed
• Adversarially Robust Learning with Tolerance
  2 Mar 2022 0 repositories listed
• On Learning and Enforcing Latent Assessment Models using Binary Feedback from Human Auditors Regarding Black-Box Classifiers
  16 Feb 2022 0 repositories listed
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability
  11 Feb 2022 0 repositories listed
• Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks
  10 Feb 2022 0 repositories listed
• Monotone Learning
  10 Feb 2022 0 repositories listed
• Efficiently Learning One Hidden Layer ReLU Networks From Queries
  1 Dec 2021 0 repositories listed
• Exponential Separation between Two Learning Models and Adversarial Robustness
  1 Dec 2021 0 repositories listed
• On computable learning of continuous features
  24 Nov 2021 0 repositories listed
• PAC-Learning Uniform Ergodic Communicative Networks
  21 Nov 2021 0 repositories listed
• Realizable Learning is All You Need
  8 Nov 2021 0 repositories listed
• Active Learning for Contextual Search with Binary Feedbacks
  3 Oct 2021 0 repositories listed
• Towards a theory of out-of-distribution learning
  29 Sep 2021 0 repositories listed
• Learning the hypotheses space from data through a U-curve algorithm
  8 Sep 2021 0 repositories listed
• Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
  19 Aug 2021 0 repositories listed
• Is Nash Equilibrium Approximator Learnable?
  17 Aug 2021 0 repositories listed
• Statistically Near-Optimal Hypothesis Selection
  17 Aug 2021 0 repositories listed
• On the Power of Differentiable Learning versus PAC and SQ Learning
  9 Aug 2021 0 repositories listed
• Multiclass versus Binary Differentially Private PAC Learning
  22 Jul 2021 0 repositories listed
• A Theory of PAC Learnability of Partial Concept Classes
  18 Jul 2021 0 repositories listed
• Forster Decomposition and Learning Halfspaces with Noise
  12 Jul 2021 0 repositories listed
• Semi-verified PAC Learning from the Crowd
  13 Jun 2021 0 repositories listed
• Supervising the Transfer of Reasoning Patterns in VQA
  10 Jun 2021 0 repositories listed
• Multi-group Agnostic PAC Learnability
  20 May 2021 0 repositories listed
• Incentive-aware PAC learning
  18 May 2021 0 repositories listed
• Learning and Certification under Instance-targeted Poisoning
  18 May 2021 0 repositories listed
• Broadly Applicable Targeted Data Sample Omission Attacks
  4 May 2021 0 repositories listed
• Symbolic Abstractions From Data: A PAC Learning Approach
  28 Apr 2021 0 repositories listed
• PAC-learning gains of Turing machines over circuits and neural networks
  23 Mar 2021 0 repositories listed
• Robust learning under clean-label attack
  1 Mar 2021 0 repositories listed
• Private learning implies quantum stability
  14 Feb 2021 0 repositories listed
• Fairness-Aware PAC Learning from Corrupted Data
  11 Feb 2021 0 repositories listed
• On Agnostic PAC Learning using ℒ₂-polynomial Regression and Fourier-based Algorithms
  11 Feb 2021 0 repositories listed
• Sample-Optimal PAC Learning of Halfspaces with Malicious Noise
  11 Feb 2021 0 repositories listed
• Adversarial Robustness: What fools you makes you stronger
  10 Feb 2021 0 repositories listed
• On the Hardness of PAC-learning Stabilizer States with Noise
  9 Feb 2021 0 repositories listed
• Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
  22 Jan 2021 0 repositories listed
• From Local Pseudorandom Generators to Hardness of Learning
  20 Jan 2021 0 repositories listed
• The Price is (Probably) Right: Learning Market Equilibria from Samples
  29 Dec 2020 0 repositories listed
• Communication-Aware Collaborative Learning
  19 Dec 2020 0 repositories listed
• Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise
  17 Dec 2020 0 repositories listed
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models
  14 Dec 2020 0 repositories listed
• Sample-efficient proper PAC learning with approximate differential privacy
  7 Dec 2020 0 repositories listed
• VC Dimension and Distribution-Free Sample-Based Testing
  7 Dec 2020 0 repositories listed
• PAC-Learning for Strategic Classification
  6 Dec 2020 0 repositories listed
• Towards a Combinatorial Characterization of Bounded-Memory Learning
  1 Dec 2020 0 repositories listed
• Efficient PAC Learning from the Crowd with Pairwise Comparisons
  2 Nov 2020 0 repositories listed
• Reducing Adversarially Robust Learning to Non-Robust PAC Learning
  22 Oct 2020 0 repositories listed
• Learning, compression, and leakage: Minimising classification error via meta-universal compression principles
  14 Oct 2020 0 repositories listed
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
  4 Oct 2020 0 repositories listed
• Learning from Mixtures of Private and Public Populations
  1 Aug 2020 0 repositories listed
• A Computational Separation between Private Learning and Online Learning
  11 Jul 2020 0 repositories listed
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
  22 Jun 2020 0 repositories listed
• An Optimal Elimination Algorithm for Learning a Best Arm
  20 Jun 2020 0 repositories listed
• Learning Halfspaces with Tsybakov Noise
  11 Jun 2020 0 repositories listed
• List Learning with Attribute Noise
  11 Jun 2020 0 repositories listed