A general lower bound on the number of examples needed for learning

No abstract is available for this paper.

• Publication year

  1988

• Venue

  Annual Conference Computational Learning Theory

• Publication date

  1988-12-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0890-5401(89)90002-3
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Learning in the presence of malicious errors

  1993cited by this paper
• Computational complexity of machine learning

  1990cited by this paper
• Learnability and the Vapnik-Chervonenkis dimension

  1989cited by this paper
• What Size Net Gives Valid Generalization?

  1989cited by this paper
• Crytographic limitations on learning Boolean formulae and finite automata

  1989cited by this paper
• Results on learnability and the Vapnik-Chervonenkis dimension

  1988cited by this paper
• Learnability by fixed distributions

  1988cited by this paper
• Learning in parallel

  1988cited by this paper
• Computational limitations on learning from examples

  1988cited by this paper
• Non-Learnable Classes of Boolean Formulae That Are Closer Under Variable Permutation

  1988cited by this paper
• Quantifying Inductive Bias: AI Learning Algorithms and Valiant's Learning Framework

  1988cited by this paper
• Predicting (0, 1)-functions on randomly drawn points

  1988cited by this paper
• On learning Boolean functions

  1987cited by this paper
• On the learnability of Boolean formulae

  1987cited by this paper
• ɛ-nets and simplex range queries

  1987cited by this paper
• Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

  1987cited by this paper
• Epsilon-nets and simplex range queries

  1986cited by this paper
• Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension

  1986cited by this paper
• A theory of the learnable

  1984cited by this paper
• A new polynomial-time algorithm for linear programming

  1984cited by this paper
• Some special vapnik-chervonenkis classes

  1981cited by this paper
• Occam's razor

  1980cited by this paper
• A polynomial algorithm in linear programming

  1979cited by this paper
• Fast probabilistic algorithms for hamiltonian circuits and matchings

  1977cited by this paper
• Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities

  1971cited by this paper
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

  1952cited by this paper

• The Sample Complexity of Replicable Realizable PAC Learning

  2026cites this paper
• Learning with Monotone Adversarial Corruptions

  2026cites this paper
• Learning Conditional Averages

  2026cites this paper
• Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs

  2025cites this paper
• A Characterization of List Language Identification in the Limit

  2025cites this paper
• Samplability makes learning easier

  2025cites this paper
• On Agnostic PAC Learning in the Small Error Regime

  2025cites this paper
• On the Computability of Multiclass PAC Learning

  2025cites this paper
• Theoretical analysis of divide-and-conquer ERM: From the perspective of multi-view

  2024cites this paper
• Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization

  2024cites this paper
• Revisiting Agnostic PAC Learning

  2024cites this paper
• High-probability minimax lower bounds

  2024influential citation
• Machine learning-based variable selection for clustered credit risk modeling

  2024cites this paper
• On the ERM Principle in Meta-Learning

  2024cites this paper
• Bagging is an Optimal PAC Learner (Extended Abstract)

  2024cites this paper
• When is Agnostic Reinforcement Learning Statistically Tractable?

  2023cites this paper
• Learning to Abstain From Uninformative Data

  2023cites this paper
• Uncovering Neural Scaling Laws in Molecular Representation Learning

  2023cites this paper
• Optimal PAC Bounds without Uniform Convergence

  2023cites this paper
• On the computational complexity of ethics: moral tractability for minds and machines

  2023cites this paper
• Learning Spatial Distribution of Long-Term Trackers Scores

  2023cites this paper
• PAC-Based Formal Verification for Out-of-Distribution Data Detection

  2022cites this paper
• A Theory of PAC Learnability under Transformation Invariances

  2022cites this paper
• Time Series Data Prediction and Feature Analysis of Sports Dance Movements Based on Machine Learning

  2022cites this paper
• On-Demand Sampling: Learning Optimally from Multiple Distributions

  2022cites this paper
• Bagging is an Optimal PAC Learner

  2022cites this paper
• KI-Engineering – AI Systems Engineering

  2022cites this paper
• Geometric decision procedures and the VC dimension of linear arithmetic theories

  2022cites this paper
• Optimal Weak to Strong Learning

  2022cites this paper
• Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization

  2022cites this paper
• Sample complexity of rank regression using pairwise comparisons

  2022cites this paper
• ENSIGHTS: Intelligent Monitoring of Electric Power Transmission Assets

  2022cites this paper
• The Learning and Communication Complexity of Subsequence Containment

  2021cites this paper
• A Theoretical-Empirical Approach to Estimating Sample Complexity of DNNs

  2021cites this paper
• Learning the Preferences of Uncertain Humans with Inverse Decision Theory

  2021cites this paper
• Limits of Probabilistic Safety Guarantees when Considering Human Uncertainty

  2021influential citation
• On the Sample Complexity of Rank Regression from Pairwise Comparisons

  2021cites this paper
• Toward a General Theory of Online Selective Sampling: Trading Off Mistakes and Queries

  2021cites this paper
• A Theory of PAC Learnability of Partial Concept Classes

  2021cites this paper
• On Alternation, VC-dimension and k-fold Union of Sets

  2021cites this paper
• Single-Index Models in the High Signal Regime

  2021cites this paper
• Sharper Generalization Bounds for Clustering

  2021cites this paper
• Uncertain Decisions Facilitate Better Preference Learning

  2021cites this paper
• Learning to Limit Data Collection via Scaling Laws: Data Minimization Compliance in Practice

  2021cites this paper
• Optimistic bounds for multi-output prediction

  2020influential citation
• On the falsifiability and learnability of decision theories

  2020cites this paper
• Risk Analysis of Divide-and-Conquer ERM

  2020cites this paper
• Proper Learning, Helly Number, and an Optimal SVM Bound

  2020influential citation
• Reducing Adversarially Robust Learning to Non-Robust PAC Learning

  2020cites this paper
• A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere

  2020cites this paper
• Theoretical Analysis of Divide-and-Conquer ERM: Beyond Square Loss and RKHS

  2020cites this paper
• On the Complexity of Proper Distribution-Free Learning of Linear Classifiers

  2020cites this paper
• Fault Classification Driven by Maintenance Management for Smart Maintenance Applications

  2020cites this paper
• Machine Learning in Hardware Security

  2020cites this paper
• Near-Tight Margin-Based Generalization Bounds for Support Vector Machines

  2020cites this paper
• Media Classification with Bayesian Optimization and Vapnik-Chervonenkis (VC) Bounds

  2020cites this paper
• Improving random forest algorithm by Lasso method

  2020cites this paper
• A theory of universal learning

  2020cites this paper
• An Analysis of the Adaptation Speed of Causal Models

  2020cites this paper
• Marketing Meets Data Science: Bridging the Gap

  2019cites this paper
• On the Approximation Resiliency of Logic Locking and IC Camouflaging Schemes

  2019cites this paper
• DISENTANGLE CAUSAL MECHANISMS

  2019cites this paper
• Optimality of SVM: Novel proofs and tighter bounds

  2019cites this paper
• Logic Extraction for Explainable AI

  2019cites this paper
• Margin-Based Generalization Lower Bounds for Boosted Classifiers

  2019cites this paper
• Trust, Resilience and Interpretability of AI Models

  2019cites this paper
• A Meta-Transfer Objective for Learning to Disentangle Causal Mechanisms

  2019cites this paper
• Characterizing the Sample Complexity of Pure Private Learners

  2019cites this paper
• Intelligible models for learning categorical data via generalized fourier spectrum

  2019cites this paper
• An Introduction to Compressed Sensing

  2019cites this paper
• VC Classes are Adversarially Robustly Learnable, but Only Improperly

  2019cites this paper
• A tractable ellipsoidal approximation for voltage regulation problems

  2019cites this paper
• Learning under p-tampering poisoning attacks

  2019cites this paper
• The information-theoretic value of unlabeled data in semi-supervised learning

  2019influential citation
• Statistical learnability of nuclear masses

  2019cites this paper
• Precision-Recall versus Accuracy and the Role of Large Data Sets

  2019cites this paper
• The Cost of a Reductions Approach to Private Fair Optimization

  2019cites this paper
• Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks

  2019cites this paper
• Decision list compression by mild random restrictions

  2019cites this paper
• Explaining AI Decisions Using Efficient Methods for Learning Sparse Boolean Formulae

  2018cites this paper
• A Proposed Hierarchy of Deep Learning Tasks

  2018cites this paper
• SMT Attack: Next Generation Attack on Obfuscated Circuits with Capabilities and Performance Beyond the SAT Attacks

  2018cites this paper
• A Relational Framework for Classifier Engineering

  2018cites this paper
• Tight Bounds for Collaborative PAC Learning via Multiplicative Weights

  2018cites this paper
• Learnability and Models of Decision Making under Uncertainty

  2018cites this paper
• Learning under p-Tampering Attacks

  2018cites this paper
• An introduction to domain adaptation and transfer learning

  2018cites this paper
• (Machine) Learning Parameter Regions ∗

  2018cites this paper
• Impact of Gradient Ascent and Boosting Algorithm in Classification

  2018influential citation
• Local Feature Descriptor Learning with Adaptive Siamese Network

  2017cites this paper
• Having no mathematical model may not secure PUFs

  2017cites this paper
• AppSAT: Approximately deobfuscating integrated circuits

  2017cites this paper
• Testing Piecewise Functions

  2017cites this paper
• Combining boosting machine learning and swarm intelligence for real time object detection and tracking: towards new meta-heuristics boosting classifiers

  2017cites this paper
• Naive Bayes Data Complexity and Characterization of Optima of the Unsupervised Expected Likelihood

  2017cites this paper
• String Matching: Communication, Circuits, and Learning

  2017cites this paper
• Deep Learning Scaling is Predictable, Empirically

  2017cites this paper
• Halfway to Halfspace Testing

  2017cites this paper
• Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem

  2017cites this paper
• New insights into olivo-cerebellar circuits for learning from a small training sample.

  2017cites this paper