Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers

No abstract is available for this paper.

• Publication year

  1993

• Venue

  Annual Conference Computational Learning Theory

• Publication date

  1993-08-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1023/A:1022847329178
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximate matching of polygonal shapes

  1995cited by this paper
• Localization vs. Identification of Semi-Algebraic Sets

  1993cited by this paper
• Finiteness results for sigmoidal “neural” networks

  1993cited by this paper
• A View of Computational Learning Theory

  1993cited by this paper
• On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part I: Introduction. Preliminaries. The Geometry of Semi-Algebraic Sets. The Decision Problem for the Existential Theory of the Reals

  1992cited by this paper
• Machine Learning: A Theoretical Approach

  1992cited by this paper
• Feedforward Nets for Interpolation and Classification

  1992cited by this paper
• Vapnik-Chervonenkis classes of definable sets

  1992cited by this paper
• PAC-learning geometrical figures

  1992cited by this paper
• Computational learning theory: an introduction

  1992cited by this paper
• Approximate Matching of Polygonal Shapes (Extended Abstract)

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

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

  1989cited by this paper
• Some new Vapnik-Chervonenkis classes

  1989cited by this paper
• A general lower bound on the number of examples needed for learning

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

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

  1988cited by this paper
• Occam's Razor

  1987cited by this paper
• A theory of the learnable

  1984cited by this paper
• A Linear Time Algorithm for the Hausdorff Distance Between Convex Polygons

  1983cited by this paper
• Lower bounds for algebraic computation trees

  1983cited by this paper
• Lower Bounds for Algebraic Decision Trees

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

  1981cited by this paper
• Central Limit Theorems for Empirical Measures

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

  1971cited by this paper
• Lower bounds for approximation by nonlinear manifolds

  1968cited by this paper
• On the Betti numbers of real varieties

  1964cited by this paper

• The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching

  2026cites this paper
• Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function

  2026influential citation
• On the Generalization Behavior of Deep Residual Networks From a Dynamical System Perspective

  2026cites this paper
• Scalable Utility-Aware Multiclass Calibration

  2025influential citation
• f-divergence Analysis of Generative Adversarial Network

  2025cites this paper
• Sharp lower bounds on interpolation by deep ReLU neural networks at irregularly spaced data

  2025cites this paper
• Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Size

  2025cites this paper
• Provably data-driven projection method for quadratic programming

  2025cites this paper
• Erzeugunsgrad, VC-Dimension and Neural Networks with rational activation function

  2025cites this paper
• Gradient Descent with Provably Tuned Learning-rate Schedules

  2025cites this paper
• Strassen Attention, Split VC Dimension and Compositionality in Transformers

  2025influential citation
• Optimal robust Memorization with ReLU Neural Networks

  2024cites this paper
• Algorithm Configuration for Structured Pfaffian Settings

  2024influential citation
• VC dimension of Graph Neural Networks with Pfaffian activation functions

  2024cites this paper
• Generalizability of Memorization Neural Networks

  2024cites this paper
• Learning accurate and interpretable tree-based models

  2024cites this paper
• Lower bounds on transformers with infinite precision

  2024influential citation
• On Rank-Dependent Generalisation Error Bounds for Transformers

  2024cites this paper
• On the Optimal Memorization Capacity of Transformers

  2024influential citation
• Skewed Pivot-Blend Modeling with Applications to Semicontinuous Outcomes

  2024influential citation
• Expressivity of Spiking Neural Networks

  2023cites this paper
• 2023 O PTIMAL A PPROXIMATION R ATES FOR D EEP R E LU N EURAL N ETWORKS ON S OBOLEV S PACES

  2023cites this paper
• Exploring the Complexity of Deep Neural Networks through Functional Equivalence

  2023cites this paper
• On the Role of Noise in the Sample Complexity of Learning Recurrent Neural Networks: Exponential Gaps for Long Sequences

  2023cites this paper
• Simplified and Improved Bounds on the VC-Dimension for Elastic Distance Measures

  2023cites this paper
• Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming

  2023influential citation
• Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Data

  2023cites this paper
• Nearly-tight Bounds for Deep Kernel Learning

  2023cites this paper
• Nearly Optimal VC-Dimension and Pseudo-Dimension Bounds for Deep Neural Network Derivatives

  2023cites this paper
• New Bounds for Hyperparameter Tuning of Regression Problems Across Instances

  2023cites this paper
• Reinforcement Learning in Low-Rank MDPs with Density Features

  2023influential citation
• Semisupervised Manifold Regularization via a Subnetwork-Based Representation Learning Model

  2022cites this paper
• Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation

  2022influential citation
• Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces

  2022cites this paper
• Streaming Algorithms for High-Dimensional Robust Statistics

  2022cites this paper
• On Rademacher Complexity-based Generalization Bounds for Deep Learning

  2022cites this paper
• Faster Approximate Covering of Subcurves under the Fréchet Distance

  2022cites this paper
• A general approximation lower bound in Lp norm, with applications to feed-forward neural networks

  2022influential citation
• Generalization Bounds for Data-Driven Numerical Linear Algebra

  2022cites this paper
• Estimation of Non-Crossing Quantile Regression Process with Deep ReQU Neural Networks

  2022influential citation
• Global Convergence of Federated Learning for Mixed Regression

  2022cites this paper
• Clifford Circuits can be Properly PAC Learned if and only if RP=NP

  2022cites this paper
• When are Local Queries Useful for Robust Learning?

  2022influential citation
• Upper bounds on the Natarajan dimensions of some function classes

  2022cites this paper
• Benefits of Additive Noise in Composing Classes with Bounded Capacity

  2022cites this paper
• Using Existential Theory of the Reals to Bound VC Dimension

  2022cites this paper
• Learning bounds for quantum circuits in the agnostic setting

  2021cites this paper
• Coresets for $(k, \ell)$-Median Clustering under the Fr\'echet Distance

  2021influential citation
• On the Optimal Memorization Power of ReLU Neural Networks

  2021influential citation
• De-randomized PAC-Bayes Margin Bounds: Applications to Non-convex and Non-smooth Predictors

  2020cites this paper
• Multiplicative Gaussian Particle Filter

  2020cites this paper
• Pseudo-dimension of quantum circuits

  2020cites this paper
• Coin Flipping in Dynamic Programming Is Almost Useless

  2020influential citation
• Deep Networks as Logical Circuits: Generalization and Interpretation

  2020cites this paper
• Duality of Width and Depth of Neural Networks

  2020cites this paper
• E(cid:30)cient Synthesis with Probabilistic Constraints

  2020cites this paper
• On Sharpness of Error Bounds for Univariate Approximation by Single Hidden Layer Feedforward Neural Networks

  2020cites this paper
• Reasoning about Measures of Unmeasurable Sets

  2020cites this paper
• Recent advances in deep learning theory

  2020cites this paper
• Elementos da teoria de aprendizagem de máquina supervisionada

  2019cites this paper
• Sample Complexity Bounds for Recurrent Neural Networks with Application to Combinatorial Graph Problems

  2019cites this paper
• The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances

  2019cites this paper
• The effect of artificial subclass induction on classification performance

  2019cites this paper
• Efficient Synthesis with Probabilistic Constraints

  2019cites this paper
• The phase diagram of approximation rates for deep neural networks

  2019cites this paper
• Limiting Network Size within Finite Bounds for Optimization

  2019cites this paper
• Revisiting generalization for deep learning: PAC-Bayes, flat minima, and generative models

  2019cites this paper
• Marginal Singularity, and the Benefits of Labels in Covariate-Shift

  2018cites this paper
• Optimal approximation of continuous functions by very deep ReLU networks

  2018influential citation
• Model Complexity Control in Straight Line Program Genetic Programming

  2018cites this paper
• Computational Learning Theory FoPPS Logic and Learning School

  2018cites this paper
• On Sharpness of Error Bounds for Single Hidden Layer Feedforward Neural Networks

  2018cites this paper
• Coin Tossing in Dynamic Programming Is Almost Useless

  2018influential citation
• Fast generalization error bound of deep learning from a kernel perspective

  2018cites this paper
• Derandomizing Dynamic Programming and Beyond

  2018cites this paper
• Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks

  2017cites this paper
• Fast learning rate of deep learning via a kernel perspective

  2017cites this paper
• Nearly-tight VC-dimension bounds for piecewise linear neural networks

  2017cites this paper
• Error bounds for approximations with deep ReLU networks

  2016cites this paper
• Large Margin Deep Neural Networks: Theory and Algorithms

  2015cites this paper
• On the Depth of Deep Neural Networks: A Theoretical View

  2015cites this paper
• Implicit image annotation by using gaze analysis

  2012cites this paper
• Discretized-Vapnik-Chervonenkis Dimension for Analyzing Complexity of Real Function Classes

  2012cites this paper
• Complexity-Based Approach to Calibration with Checking Rules

  2011cites this paper
• Indexability, concentration, and VC theory

  2010cites this paper
• On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations

  2009influential citation
• Designing neural networks for tackling hard classification problems

  2009cites this paper
• Neural networks and multimedia datasets: estimating the size of neural networks for achieving high classification accuracy

  2009cites this paper
• AN OVERVIEW OF NEURAL NETWORKS RESULTS FOR SYSTEMS AND CONTROL

  2009cites this paper
• A New Linear Genetic Programming Approach Based on Straight Line Programs: Some Theoretical and Experimental Aspects

  2009cites this paper
• Lower Bounds on Performance of Metric Tree Indexing Schemes for Exact Similarity Search in High Dimensions

  2008cites this paper
• VC Dimension Bounds for Analytic Algebraic Computations

  2008cites this paper
• VCD Bounds for some GP Genotypes

  2008cites this paper
• Bregman Voronoi Diagrams

  2007cites this paper
• Electronic Colloquium on Computational Complexity Agnostic Pac-learning of Functions on Analog Neural Nets

  2007cites this paper
• Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations

  2007influential citation
• Learning by Canonical Smooth Estimation, Part II: Learning and Choice of Model Complexity (cid:3)y

  2007cites this paper
• Finiteness Properties of Some Families of GP-Trees

  2007cites this paper
• Neural Networks

  2007cites this paper
• Estimating the Size of Neural Networks from the Number of Available Training Data

  2007cites this paper