Decision theoretic generalizations of the PAC model for neural net and other learning applications

1992/09/01 by David Haussler · 1 voice · 38 citations
Computer Science · #Machine Learning and Algorithms #Machine Learning and Data Classification #Neural Networks and Applications

paper · doi:10.1016/0890-5401(92)90010-d

crossref issued 1992/09/01 · crossref published 1992/09/01 · crossref published-print 1992/09/01 · openalex publication_date 1992/09/01 · crossref created 2004/12/02 · crossref deposited 2019/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02 · crossref indexed 2026/07/13

Cited by

• Risk bounds for reservoir computing
• Sample-Optimal PAC Learning of Halfspaces with Malicious Noise
• Actively Avoiding Nonsense in Generative Models
• Distribution-Independent PAC Learning of Halfspaces with Massart Noise
• Uncoupled Regression from Pairwise Comparison Data
• Degree-d Chow Parameters Robustly Determine Degree-d PTFs (and\n Algorithmic Applications)
• Outcome Indistinguishability
• Generalization Below the Edge of Stability: The Role of Data Geometry
• Fast Agnostic Learners in the Plane
• Learning-Theoretic Foundations of Algorithm Configuration for\n Combinatorial Partitioning Problems
• Agnostic Learning of Disjunctions on Symmetric Distributions
• PAC learning with stable and private predictions
• Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings
• Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity
• Neural Networks and the Bias/Variance Dilemma
• Online Learning via Sequential Complexities
• √(n)-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
• Privacy-preserving Prediction
• Near-Optimal Statistical Query Hardness of Learning Halfspaces with\n Massart Noise
• Improved scalability under heavy tails, without strong convexity
• Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle
• A Survey of Quantum Learning Theory
• Adaptive algorithms in sampling recovery
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals
• On the Learnability of Distribution Classes with Adaptive Adversaries
• Learning Coverage Functions and Private Release of Marginals
• Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks
• Differentially Private Clustering: Tight Approximation Ratios
• Sparse learning with CART
• Agnostic learning with unknown utilities
• Robustly Learning Monotone Single-Index Models
• Active Learning Using Smooth Relative Regret Approximations with\n Applications
• On Generalization Bounds of a Family of Recurrent Neural Networks
• Probably Approximately Correct Causal Discovery
• Statistical Learning under Nonstationary Mixing Processes
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability
• Descriptive Dimensionality and Its Characterization of MDL-based Learning and Change Detection

Discussions

• Learning theory people, I need your help: in the definition of (agnostic) PAC learning, is the learning alg allowed to depend on epsilon and delta? Literature seems to say 'no' (www.cs.huji.ac.il/~sha [bsky, 5 points, 2 comments]