On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

DOI10.1137/1116025zbMath0247.60005OpenAlexW4238284510WikidataQ29011890 ScholiaQ29011890MaRDI QIDQ5660314

Vladimir Vapnik, A. Ya. Chervonenkis

Publication date: 1971

Published in: Theory of Probability & Its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1116025

Mathematics Subject Classification ID

Strong limit theorems (60F15) Axioms; other general questions in probability (60A05)

Related Items

Concentration inequalities of the cross-validation estimator for empirical risk minimizer ⋮ Learning and Convergence of the Normalized Radial Basis Functions Networks ⋮ Deep learning: a statistical viewpoint ⋮ Probability estimates for the distribution of Kolmogorov distance in the worst direction ⋮ Forecasting Inflation with the Influence of Globalization using Artificial Neural Network-based Thin and Thick Models ⋮ Parameter selection in modified histogram estimates ⋮ Consistency of Ridge Function Fields for Varying Nonparametric Regression ⋮ Approximation bounds for norm constrained neural networks with applications to regression and GANs ⋮ Rates of the strong uniform consistency for the kernel-type regression function estimators with general kernels on manifolds ⋮ Improved bounds for the expected number of \(k\)-sets ⋮ Purity and Separation for Oriented Matroids ⋮ HyperBench ⋮ From undecidability of non-triviality and finiteness to undecidability of learnability ⋮ The explanation game: a formal framework for interpretable machine learning ⋮ Sample Compression Schemes for Balls in Graphs ⋮ A smoothed \(p\)-value test when there is a nuisance parameter under the alternative ⋮ Interview with Andrei Raigorodskii ⋮ VC-dimensions for graphs (extended abstract) ⋮ Remarks on the NIP in a model ⋮ Impact of barren plateaus countermeasures on the quantum neural network capacity to learn ⋮ Exploring implications of trace (inversion) formula and Artin algebras in extremal combinatorics ⋮ Approximate subgroups with bounded VC-dimension ⋮ Four-vertex traces of finite sets ⋮ Support vector machines and Radon's theorem ⋮ The \textsc{Red-Blue Separation} problem on graphs ⋮ Approximating length-restricted means under dynamic time warping ⋮ On Learning and Convergence of RBF Networks in Regression Estimation and Classification ⋮ Theory of graph neural networks: representation and learning ⋮ Concentration Inequalities for Samples without Replacement ⋮ Representing Objects, Relations, and Sequences ⋮ Regularizing portfolio optimization ⋮ Visual Categorization with Random Projection ⋮ Short-Term Memory Capacity in Networks via the Restricted Isometry Property ⋮ Combinatorial bounds of overfitting for threshold classifiers ⋮ MULTIVALUED GENERALIZATIONS OF THE FRANKL–PACH THEOREM ⋮ Transit sets of two-point crossover ⋮ Regularity lemmas for stable graphs ⋮ Transit sets of -point crossover operators ⋮ On Vapnik‐Chervonenkis density over indiscernible sequences ⋮ Application of Discriminant, Classification Tree and Neural Network Analysis to Differentiate between Potential Glaucoma Suspects with and without Visual Field Defects ⋮ Learning nested differences in the presence of malicious noise ⋮ Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond ⋮ Asymptotic consistency of median regression trees ⋮ A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension ⋮ Centerpoints: A Link between Optimization and Convex Geometry ⋮ A lower bound for families of Natarajan dimension \(d\) ⋮ Closure properties of uniform convergence of empirical means and PAC learnability under a family of probability measures. ⋮ Optimal schedules for monitoring anytime algorithms ⋮ Improved bounds on the sample complexity of learning ⋮ Simultaneous partitions of measures by \(k\)-fans ⋮ Randomized algorithms for robust controller synthesis using statistical learning theory ⋮ Probabilistic solutions to some NP-hard matrix problems ⋮ From a $(p,2)$-Theorem to a Tight $(p,q)$-Theorem ⋮ The communication complexity of enumeration, elimination, and selection ⋮ Regularization and statistical learning theory for data analysis. ⋮ Variance-based regularization with convex objectives ⋮ Plug-in L₂-upper error bounds in deconvolution, for a mixing density estimate in R^d and for its derivatives, via the L₁-error for the mixture ⋮ Comments on: Support vector machines maximizing geometric margins for multi-class classification ⋮ Computing a maximum clique in geometric superclasses of disk graphs ⋮ An Improved Algorithm Finding Nearest Neighbor Using Kd-trees ⋮ Unnamed Item ⋮ Discussion on: ``Why is resorting to fate wise? A critical look at randomized algorithms in systems and control ⋮ EPISTEMOLOGY OF COMPUTATIONAL BIOLOGY: MATHEMATICAL MODELS AND EXPERIMENTAL PREDICTION AS THE BASIS OF THEIR VALIDITY ⋮ Unnamed Item ⋮ Shatter Functions with Polynomial Growth Rates ⋮ VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Real-time market microstructure analysis: online transaction cost analysis ⋮ Unnamed Item ⋮ Safe Multi-Agent Pathfinding with Time Uncertainty ⋮ Some Themes Around First Order Theories Without the Independence Property ⋮ O-PCF algorithm for one-class classification ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Agnostically Learning Boolean Functions with Finite Polynomial Representation ⋮ RTNI—A symbolic integrator for Haar-random tensor networks ⋮ Testing geometric objects ⋮ Rates of growth and sample moduli for weighted empirical processes indexed by sets ⋮ Efficient distribution-free learning of probabilistic concepts ⋮ Nonuniform learnability ⋮ A review of combinatorial problems arising in feedforward neural network design ⋮ Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements ⋮ Some best possible bounds concerning the traces of finite sets ⋮ \(\epsilon\)-nets and simplex range queries ⋮ A theory for memory-based learning ⋮ Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension ⋮ Covering with Latin transversals ⋮ Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis ⋮ The central limit theorem for empirical processes on V-Č classes: A majorizing measure approach ⋮ Inclusion-exclusion complexes for pseudodisk collections ⋮ VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states ⋮ Convergence of stochastic empirical measures ⋮ On the asymptotic properties of smoothed estimators of the classification error rate ⋮ A confidence interval for Monte Carlo methods with an application to simulation of obliquely reflecting Brownian motion ⋮ Convergence of depth contours for multivariate datasets ⋮ Quantifying inductive bias: AI learning algorithms and Valiant's learning framework ⋮ The VC-dimension of set systems defined by graphs ⋮ A sufficient condition for polynomial distribution-dependent learnability ⋮ Functional central limit theorems for triangular arrays of function-indexed processes under uniformly integrable entropy conditions ⋮ Characterizing rational versus exponential learning curves ⋮ Learning distributions by their density levels: A paradigm for learning without a teacher ⋮ Inclusion-exclusion: exact and approximate ⋮ On the complexity of learning from drifting distributions ⋮ Sperner families of bounded VC-dimension ⋮ Guarding galleries where every point sees a large area ⋮ Learning faster than promised by the Vapnik-Chervonenkis dimension ⋮ Universal smoothing factor selection in density estimation: theory and practice. (With discussion) ⋮ Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes ⋮ On the value of partial information for learning from examples ⋮ The Perceptron algorithm versus Winnow: linear versus logarithmic mistake bounds when few input variables are relevant ⋮ Efficient learning with virtual threshold gates ⋮ On convergence proofs in system identification -- a general principle using ideas from learning theory ⋮ Approximate testing and its relationship to learning ⋮ Learning nested differences in the presence of malicious noise ⋮ PAC-learning from general examples ⋮ PAC learning of concept classes through the boundaries of their items ⋮ Query complexity of membership comparable sets. ⋮ Learning from examples with unspecified attribute values. ⋮ Some special Vapnik-Chervonenkis classes ⋮ Bounds for the uniform deviation of empirical measures ⋮ Cutting hyperplane arrangements ⋮ Accuracy of the approximation of an empirical process by a Brownian bridge ⋮ On rates of convergence and asymptotic normality in the multiknapsack problem ⋮ Equivalence of models for polynomial learnability ⋮ Almost tight bounds for \(\epsilon\)-nets ⋮ Decision theoretic generalizations of the PAC model for neural net and other learning applications ⋮ Inverse regression method in data structure analysis ⋮ Efficient partition trees ⋮ A note on the consistent estimator of nonparametric regression constructed by splines ⋮ Bounding sample size with the Vapnik-Chervonenkis dimension ⋮ Cutting hyperplanes for divide-and-conquer ⋮ Uniform convergence of Vapnik-Chervonenkis classes under ergodic sampling ⋮ \(k\)-Fold unions of low-dimensional concept classes ⋮ A general approach for cache-oblivious range reporting and approximate range counting ⋮ Existence of submatrices with all possible columns ⋮ Active sampling for multiple output identification ⋮ A notion of task relatedness yielding provable multiple-task learning guarantees ⋮ Balls in \(\mathbb{R}^k\) do not cut all subsets of \(k+2\) points ⋮ Interval predictor models: identification and reliability ⋮ Entropy conditions for \(L_{r}\)-convergence of empirical processes ⋮ Gaussian approximation of the empirical process under random entropy conditions ⋮ Multiple pass streaming algorithms for learning mixtures of distributions in \(\mathbb R^d\) ⋮ A graph-theoretic generalization of the Sauer-Shelah lemma ⋮ Scale-sensitive dimensions and skeleton estimates for classification ⋮ The degree of approximation of sets in euclidean space using sets with bounded Vapnik-Chervonenkis dimension ⋮ The capacity of monotonic functions ⋮ Fluctuation bounds for sock-sorting and other stochastic processes ⋮ Strongly consistent model selection for densities ⋮ General bounds on statistical query learning and PAC learning with noise via hypothesis boosting ⋮ Optimal mistake bound learning is hard ⋮ Learning with restricted focus of attention ⋮ \(l\)-trace \(k\)-Sperner families of sets ⋮ Uniform approximation by neural networks ⋮ An introduction to some statistical aspects of PAC learning theory ⋮ Learning dynamical systems in a stationary environment ⋮ Approximating hyper-rectangles: Learning and pseudorandom sets ⋮ Guarding galleries where no point sees a small area. ⋮ Noise-tolerant parallel learning of geometric concepts ⋮ Rademacher complexity in Neyman-Pearson classification ⋮ Separable partitions ⋮ Maximal width learning of binary functions ⋮ Hitting sets when the VC-dimension is small ⋮ On the transversal number and VC-dimension of families of positive homothets of a convex body ⋮ Equipartitioning by a convex 3-fan ⋮ The VC-dimension of Sperner systems ⋮ Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete ⋮ On the range of a regenerative sequence ⋮ An optimal convex hull algorithm in any fixed dimension ⋮ Combinatorics and connectionism ⋮ Komlós-Major-Tusnády approximation for the general empirical process and Haar expansions of classes of functions ⋮ A result of Vapnik with applications ⋮ Associative structures for vision ⋮ Discrepancy and approximations for bounded VC-dimension ⋮ On sparse approximations to randomized strategies and convex combinations ⋮ Bounding the vertex cover number of a hypergraph ⋮ Density results for uniform families ⋮ Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs ⋮ Embeddings and the trace of finite sets ⋮ Objective and subjective foundations for multiple priors ⋮ The VC dimension of \(k\)-fold union ⋮ Pairwise intersections and forbidden configurations ⋮ An algorithmic theory of learning: robust concepts and random projection ⋮ The VC-dimension of graphs with respect to \(k\)-connected subgraphs ⋮ On the VC-dimension of uniform hypergraphs ⋮ Estimation of a time-dependent density ⋮ Complexity of hyperconcepts ⋮ On ordinal VC-dimension and some notions of complexity ⋮ Smoothed maximum score change-point estimation in binary response model ⋮ A Glivenko-Cantelli theorem for almost additive functions on lattices ⋮ Learning with side information: PAC learning bounds ⋮ On minimum saturated matrices ⋮ Discriminant analysis based on statistical depth ⋮ An oracle inequality for regularized risk minimizers with strongly mixing observations ⋮ Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy ⋮ Exploiting label dependencies for improved sample complexity ⋮ On combinatorial testing problems ⋮ On the generalization error of fixed combinations of classifiers ⋮ Maximum score change-point estimation in binary response model ⋮ Bin width selection in multivariate histograms by the combinatorial method ⋮ Some recent results on Ramsey-type numbers ⋮ Information dependency: strong consistency of Darbellay-Vajda partition estimators ⋮ Shattering, graph orientations, and connectivity ⋮ Repeated columns and an old chestnut ⋮ PAC learning, VC dimension, and the arithmetic hierarchy ⋮ Clique versus independent set ⋮ On the hardness of learning intersections of two halfspaces ⋮ Connecting deterministic and stochastic metapopulation models ⋮ Vapnik-Chervonenkis density on indiscernible sequences, stability, and the maximum property ⋮ Approximate aggregation for tracking quantiles and range countings in wireless sensor networks ⋮ Robust cutpoints in the logical analysis of numerical data ⋮ Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension ⋮ Languages as hyperplanes: grammatical inference with string kernels ⋮ On the convergence of Shannon differential entropy, and its connections with density and entropy estimation ⋮ The class cover problem with boxes ⋮ Aspects in classification learning -- review of recent developments in learning vector quantization ⋮ Generalization error bounds for the logical analysis of data ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ Lower bounds for comparison based evolution strategies using VC-dimension and sign patterns ⋮ Improved approximation for guarding simple galleries from the perimeter ⋮ Low-contention data structures ⋮ Learning from hints in neural networks ⋮ Piercing quasi-rectangles-on a problem of Danzer and Rogers ⋮ A tree-based regressor that adapts to intrinsic dimension ⋮ Forbidden configurations and repeated induction ⋮ Construction of \(\epsilon\)-nets ⋮ Multiclass classification with potential function rules: margin distribution and generalization ⋮ Margin-adaptive model selection in statistical learning ⋮ A statistical learning theory approach for uncertain linear and bilinear matrix inequalities ⋮ Cover-based combinatorial bounds on probability of overfitting ⋮ Using the doubling dimension to analyze the generalization of learning algorithms ⋮ Algebraic methods proving Sauer's bound for teaching complexity ⋮ Linear algebra methods for Forbidden configurations ⋮ Feasibility of numerical modelling: Information aspect ⋮ Kernel methods in machine learning ⋮ A non-linear lower bound for planar epsilon-nets ⋮ Generalization performance of bipartite ranking algorithms with convex losses ⋮ Set families with forbidden subposets ⋮ \(\varepsilon\)-approximations of \(k\)-label spaces ⋮ On intersecting a point set with Euclidean balls ⋮ Rigorous learning curve bounds from statistical mechanics ⋮ Radial basis function networks: Generalization in over-realizable and unrealizable scenarios ⋮ Constrained versions of Sauer's Lemma ⋮ The Glivenko-Cantelli problem, ten years later ⋮ Uniform convergence rates for halfspace depth ⋮ On pseudorandomness of families of binary sequences ⋮ VC-sets and generic compact domination ⋮ Double-fold localized multiple matrixized learning machine ⋮ Forbidden configurations and Steiner designs ⋮ Structural multiple empirical kernel learning ⋮ On \(k\)-partite hypergraphs with the induced \(\epsilon \)-density property ⋮ Analysis of the consistency of a mixed integer programming-based multi-category constrained discriminant model ⋮ An asymptotic statistical analysis of support vector machines with soft margins ⋮ Density estimation by the penalized combinatorial method ⋮ Monte Carlo algorithms for optimal stopping and statistical learning ⋮ Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis ⋮ Analysis of a multi-category classifier ⋮ Learning in the limit with lattice-structured hypothesis spaces ⋮ Maximal pattern complexity, dual system and pattern recognition ⋮ Kernel estimators of density function of directional data ⋮ Information divergence estimation based on data-dependent partitions ⋮ Testing conditional independence in supervised learning algorithms ⋮ Alternative second-order cone programming formulations for support vector classification ⋮ Two proofs for shallow packings ⋮ Multi-category classifiers and sample width ⋮ Covering nearly surface-embedded graphs with a fixed number of balls ⋮ Learning commutative deterministic finite state automata in polynomial time ⋮ A deterministic view of random sampling and its use in geometry ⋮ Results on learnability and the Vapnik-Chervonenkis dimension ⋮ Prediction-preserving reducibility ⋮ On signal representations within the Bayes decision framework ⋮ Two-dimensional partial cubes ⋮ Strong consistency of nearest neighbor regression function estimators ⋮ Uniform and universal Glivenko-Cantelli classes ⋮ Learnability with respect to fixed distributions ⋮ Theory revision with queries: Horn, read-once, and parity formulas ⋮ Maximizing agreements and coagnostic learning ⋮ Unlabeled sample compression schemes and corner peelings for ample and maximum classes ⋮ Optimal approximations made easy ⋮ Shattering and more: Extending the complete object ⋮ On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations ⋮ Model selection by bootstrap penalization for classification ⋮ Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms ⋮ Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond ⋮ Calibration of the empirical likelihood for high-dimensional data ⋮ On the maximal number of columns of a \(\varDelta \)-modular matrix ⋮ A uniform version of a theorem by Dvir and Moran ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ Boundary classes for graph problems involving non-local properties ⋮ \(L_{p}\)-norm Sauer-Shelah lemma for margin multi-category classifiers ⋮ The \textsc{red-blue separation} problem on graphs ⋮ Uniform concentration bounds for frequencies of rare events ⋮ What convex geometries tell about shattering-extremal systems ⋮ Complete statistical theory of learning ⋮ On the approximability of digraph ordering ⋮ Deep neural networks for texture classification -- a theoretical analysis ⋮ The Vapnik-Chervonenkis dimension of graph and recursive neural networks ⋮ Randomized algorithms for tracking distributed count, frequencies, and ranks ⋮ Erdős-Hajnal conjecture for graphs with bounded VC-dimension ⋮ Feature selection for linear SVM with provable guarantees ⋮ From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem ⋮ Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location ⋮ Quantitative bounds for concentration-of-measure inequalities and empirical regression: the independent case ⋮ Investigation of generalization ability of a trained stochastic kinetic model of neuron ⋮ The minimax learning rates of normal and Ising undirected graphical models ⋮ Statistical performance of support vector machines ⋮ Free resolutions of function classes via order complexes ⋮ Worst-case violation of sampled convex programs for optimization with uncertainty ⋮ Rates of convergence in active learning ⋮ Complexity parameters for first order classes ⋮ Average case recovery analysis of tomographic compressive sensing ⋮ Uniform convergence rates for the approximated halfspace and projection depth ⋮ A Sauer-Shelah-Perles lemma for lattices ⋮ Coarse decision making and overfitting ⋮ Random polytopes and the wet part for arbitrary probability distributions ⋮ Learning bounds via sample width for classifiers on finite metric spaces ⋮ Interpreting nowhere dense graph classes as a classical notion of model theory ⋮ Regular partitions of gentle graphs ⋮ Learning with mitigating random consistency from the accuracy measure ⋮ Some new maximum VC classes ⋮ Learning privately with labeled and unlabeled examples ⋮ Approximate range searching in higher dimension ⋮ Construction of confidence absorbing sets using statistical methods ⋮ On uniform concentration bounds for bi-clustering by using the Vapnik-Chervonenkis theory ⋮ Bounds on the sample complexity for private learning and private data release ⋮ Forbidding complete hypergraphs as traces ⋮ Aspects of discrete mathematics and probability in the theory of machine learning ⋮ On the complexity of constrained VC-classes ⋮ Sequential complexities and uniform martingale laws of large numbers ⋮ A note on minimum distance estimation of copula densities ⋮ Small size quantum automata recognizing some regular languages ⋮ On forbidden submatrices ⋮ An e-E-insensitive support vector regression machine ⋮ Empirical minimization ⋮ Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization ⋮ An algorithmic theory of learning: Robust concepts and random projection ⋮ A novel multi-view learning developed from single-view patterns ⋮ Research on probabilistic methods for control system design ⋮ Randomized algorithms for the synthesis of cautious adaptive controllers ⋮ Ramsey numbers of Berge-hypergraphs and related structures ⋮ Boosted ARTMAP: modifications to fuzzy ARTMAP motivated by boosting theory ⋮ Randomized algorithms for robust controller synthesis using statistical learning theory: a tutorial overview ⋮ The optimal PAC bound for intersection-closed concept classes ⋮ The complexity of exact learning of acyclic conditional preference networks from swap examples ⋮ MREKLM: a fast multiple empirical kernel learning machine ⋮ VC-dimension and Erdős-Pósa property ⋮ Finitely distinguishable erasing pattern languages ⋮ Stochastic separation theorems ⋮ Agnostic active learning ⋮ Learning via variably scaled kernels ⋮ The VC-dimension of axis-parallel boxes on the torus ⋮ Minimum distance histograms with universal performance guarantees ⋮ A new lower bound on Hadwiger-Debrunner numbers in the plane ⋮ Machine learning for credit scoring: improving logistic regression with non-linear decision-tree effects ⋮ Multi-symbol forbidden configurations ⋮ Unlabeled compression schemes exceeding the VC-dimension ⋮ On density of subgraphs of halved cubes ⋮ Bounded \(VC\)-dimension implies the Schur-Erdős conjecture ⋮ VC dimension and a union theorem for set systems ⋮ On \(n\)-dependence ⋮ The teaching size: computable teachers and learners for universal languages ⋮ Interpretable machine learning: fundamental principles and 10 grand challenges ⋮ Exact multi-covering problems with geometric sets ⋮ Uniformly supported approximate equilibria in families of games ⋮ Discrete minimax estimation with trees ⋮ Uniform rates of the Glivenko-Cantelli convergence and their use in approximating Bayesian inferences ⋮ Rademacher complexity for Markov chains: applications to kernel smoothing and Metropolis-Hastings ⋮ Moment estimates in the first Borel-Cantelli lemma with applications to mean deviation frequencies ⋮ Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model ⋮ Disjoint representability of sets and their complements ⋮ Optimal \(L_{1}\) bandwidth selection for variable kernel density estimates ⋮ A central limit theorem for two-sample U-processes ⋮ Integer cells in convex sets ⋮ Bounding the trace function of a hypergraph with applications ⋮ The enumerability of P collapses P to NC ⋮ Random forest estimation of conditional distribution functions and conditional quantiles ⋮ Primal and dual combinatorial dimensions ⋮ Some Characteristics of the Conditional Set-Indexed Empirical Process Involving Functional Ergodic Data ⋮ NOTES ON THE STABLE REGULARITY LEMMA ⋮ Ramsey properties of algebraic graphs and hypergraphs ⋮ A note on Phillips (1991): ``A constrained maximum likelihood approach to estimating switching regressions ⋮ How Many Directions Determine a Shape and other Sufficiency Results for Two Topological Transforms ⋮ On the Number of Distinct Rows of a Matrix with Bounded Subdeterminants ⋮ Almost sure classification of densities ⋮ Ample Completions of Oriented Matroids and Complexes of Uniform Oriented Matroids ⋮ Centerpoints: A Link Between Optimization and Convex Geometry ⋮ On the geometry of polytopes generated by heavy-tailed random vectors ⋮ Estimation of Entropy and Mutual Information ⋮ On multivariate variable-kernel density estimates for time series ⋮ Optimal rates of convergence for the piecewlse polynomial estimator with the index chosen by the fpe selection rule ⋮ Unique Covering Problems with Geometric Sets ⋮ Continuous and random Vapnik-Chervonenkis classes ⋮ Ten More Years of Error Rate Research ⋮ Improving Generalization Capabilities of Dynamic Neural Networks ⋮ An Asymptotic Statistical Theory of Polynomial Kernel Methods ⋮ The VC-dimension of K-vertex D-polytopes ⋮ Journey to the Center of the Point Set ⋮ The VC dimension of metric balls under Fréchet and Hausdorff distances ⋮ PAC learning in non-linear FIR models ⋮ Approximate Aggregation for Tracking Quantiles in Wireless Sensor Networks ⋮ ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INSTERSECTING A STRAIGHT LINE ⋮ Indexing for summary queries ⋮ On the VC-Dimension of Binary Codes ⋮ Geometric algorithms for the minimum cost assignment problem ⋮ Introducing the closure structure and the GDPM algorithm for mining and understanding a tabular dataset ⋮ Convolutions of sets with bounded VC-dimension are uniformly continuous ⋮ Edge Multiplicity and Other Trace Functions ⋮ Unnamed Item ⋮ Learning reliably and with one-sided error ⋮ Unnamed Item ⋮ A theoretical framework for deep transfer learning ⋮ One-Sided Epsilon-Approximants ⋮ Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems ⋮ Teaching and Compressing for Low VC-Dimension ⋮ Network Essence: PageRank Completion and Centrality-Conforming Markov Chains ⋮ Unnamed Item ⋮ A Hilbert Space Embedding for Distributions ⋮ SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ Analysis to Neyman-Pearson classification with convex loss function ⋮ On the Classification Capability of Sign-Constrained Perceptrons ⋮ Facilitating high‐dimensional transparent classification via empirical Bayes variable selection ⋮ Generalization in Interactive Networks: The Benefits of Inhibitory Competition and Hebbian Learning ⋮ Large-Scale Machine Learning with Stochastic Gradient Descent ⋮ A note on L₁consistent estimation ⋮ Algebraic Properties of ModuloqComplete ℓ-Wide Families ⋮ Definably amenable NIP groups ⋮ VC-Dimension and Shortest Path Algorithms ⋮ Unnamed Item ⋮ Some Combinatorial Applications of Gröbner Bases ⋮ Family Complexity and VC-Dimension ⋮ Tight lower bounds for the size of epsilon-nets ⋮ Unnamed Item ⋮ On the Capabilities of Higher-Order Neurons: A Radial Basis Function Approach ⋮ Learning by Kernel Polarization ⋮ Unnamed Item ⋮ Random Embedding Machines for Pattern Recognition ⋮ Statistical Learning Theory: A Pack-based Strategy for Uncertain Feasibility and Optimization Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Vapnik-Chervonenkis density in some theories without the independence property, I ⋮ Spanning trees with low crossing number ⋮ ON THE CONNECTION BETWEEN THE COMPLEXITY AND CREDIBILITY OF INFERRED MODELS ⋮ Feature augmentation for the inversion of the Fourier transform with limited data ⋮ VARIATIONS SUR UN THÈME DE ALDAMA ET SHELAH ⋮ Theory of Classification: a Survey of Some Recent Advances ⋮ Limit theorems for empirical processes ⋮ The Exact VC Dimension of the WiSARD n-Tuple Classifier ⋮ A permutation approach to validation* ⋮ On the Optimality of Sample-Based Estimates of the Expectation of the Empirical Minimizer ⋮ Traces of hypergraphs ⋮ Valid Generalisation from Approximate Interpolation ⋮ On the VC-dimension and boolean functions with long runs ⋮ The uniform convergence of the nadaraya‐watson regression function estimate ⋮ The Communication Complexity of Distributed epsilon-Approximations ⋮ On Version Space Compression ⋮ Exponential multivalued forbidden configurations ⋮ Hierarchical Design of Fast Minimum Disagreement Algorithms ⋮ Learning with a Drifting Target Concept ⋮ Subsampling in Smoothed Range Spaces ⋮ Information Preserving Dimensionality Reduction ⋮ Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications ⋮ Generically stable and smooth measures in NIP theories ⋮ Bounds on the Sample Complexity for Private Learning and Private Data Release ⋮ Spaces of algebraic measure trees and triangulations of the circle ⋮ Unnamed Item ⋮ The the uniform mean-square ergodic theorem for wide sense stationary processes ⋮ Neural networks and some applications to finance ⋮ THICKET DENSITY ⋮ Quantitative structure of stable sets in arbitrary finite groups ⋮ Playing Billiards in Version Space ⋮ Generalization of the kolmogorov-smirnov goodness-of-fit test, usinggroup invariance ⋮ Local Rademacher complexities ⋮ Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs ⋮ An information-geometric approach to a theory of pragmatic structuring ⋮ Maxima of partial sums indexed by geometrical structures ⋮ Generalization error of combined classifiers. ⋮ A linear lower bound on the unbounded error probabilistic communication complexity. ⋮ Expected time analysis for Delaunay point location ⋮ Multicoloured extremal problems ⋮ On data classification by iterative linear partitioning ⋮ Some connections between learning and optimization ⋮ Random sampling and approximation of MAX-CSPs ⋮ Tight upper bounds for the discrepancy of half-spaces ⋮ A counterexample concerning uniform ergodic theorems for a class of functions ⋮ Classification by polynomial surfaces ⋮ On specifying Boolean functions by labelled examples ⋮ Large width nearest prototype classification on general distance spaces ⋮ Forbidden configurations: Induction and linear algebra ⋮ A generalization of Sauer's lemma ⋮ Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers ⋮ Learning from a population of hypotheses ⋮ Defect Sauer results ⋮ Almost optimal set covers in finite VC-dimension ⋮ Improved upper bounds for probabilities of uniform deviations ⋮ The asymptotic tail behaviours of projection pursuit - type Kolmogorov statistics ⋮ A prediction of precipitation data based on support vector machine and particle swarm optimization (PSO-SVM) algorithms ⋮ Independence number and the complexity of families of sets ⋮ Matrixized learning machine with modified pairwise constraints ⋮ Quasi-Monte-Carlo methods and the dispersion of point sequences ⋮ A theory of formal synthesis via inductive learning ⋮ Point sets on the sphere \(\mathbb{S}^{2}\) with small spherical cap discrepancy ⋮ Uniform approximation of Vapnik-Chervonenkis classes ⋮ dp-rank and forbidden configurations ⋮ Analysis of convergence performance of neural networks ranking algorithm ⋮ Robust regression using biased objectives ⋮ Learning figures with the Hausdorff metric by fractals -- towards computable binary classification ⋮ High-probability minimax probability machines ⋮ Ham-sandwich cuts for abstract order types ⋮ Shape matching under rigid motion ⋮ Hierarchical design of fast minimum disagreement algorithms ⋮ Bounds on the minimax rate for estimating a prior over a VC class from independent learning tasks ⋮ Penalized empirical risk minimization over Besov spaces ⋮ Empirical measures for incomplete data with applications ⋮ Approximation with neural networks activated by ramp sigmoids ⋮ On simplifying dot maps. ⋮ Relative deviation learning bounds and generalization with unbounded loss functions ⋮ Accuracy of techniques for the logical analysis of data ⋮ Necessary and sufficient conditions for weak convergence of smoothed empirical processes. ⋮ An inequality for uniform deviations of sample averages from their means ⋮ A note on weak convergence of general halfspace depth trimmed means ⋮ A uniform \(L^1\) law of large numbers for functions of i.i.d. random variables that are translated by a consistent estimator ⋮ On the VC-dimension of unique round-trip shortest path systems ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Selecting iterated modified histograms ⋮ \(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration ⋮ Fast approximation of betweenness centrality through sampling ⋮ Domination in tournaments ⋮ Fast sampling of parameterised Gaussian random fields ⋮ High-dimensional asymptotics of prediction: ridge regression and classification ⋮ Large-width bounds for learning half-spaces on distance spaces ⋮ Optimization approaches to supervised classification ⋮ On Bernstein type inequalities for stochastic integrals of multivariate point processes ⋮ Estimation from nonlinear observations via convex programming with application to bilinear regression ⋮ Algorithms for strategyproof classification ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ Surrogate losses in passive and active learning ⋮ Speculate-correct error bounds for \(k\)-nearest neighbor classifiers ⋮ On data depth and distribution-free discriminant analysis using separating surfaces ⋮ Uncertain convex programs: randomized solutions and confidence levels ⋮ Separation by convex pseudo-circles ⋮ Model selection in utility-maximizing binary prediction ⋮ Forbidden subposet problems for traces of set families ⋮ Testing piecewise functions ⋮ Active-learning a convex body in low dimensions ⋮ On Hamiltonian Berge cycles in [3-uniform hypergraphs] ⋮ Sharpness estimation of combinatorial generalization ability bounds for threshold decision rules ⋮ A selective overview of deep learning ⋮ Multivariate extensions of isotonic regression and total variation denoising via entire monotonicity and Hardy-Krause variation ⋮ Robust covariance and scatter matrix estimation under Huber's contamination model ⋮ Packing and covering balls in graphs excluding a minor ⋮ Boosting the margin: a new explanation for the effectiveness of voting methods ⋮ Practical issues in temporal difference learning ⋮ Consistency of data-driven histogram methods for density estimation and classification ⋮ Histogram regression estimation using data-dependent partitions ⋮ Almost sure \(L_ 1\)-norm convergence for data-based histogram density estimates ⋮ New applications of random sampling in computational geometry ⋮ Limit theorems in a nonseparable function space ⋮ A general lower bound on the number of examples needed for learning ⋮ Quasi-optimal range searching in spaces of finite VC-dimension ⋮ Density and dimension ⋮ A better approximation for balls ⋮ Inequalities for uniform deviations of averages from expectations with applications to nonparametric regression ⋮ General lower bounds on the query complexity within the exact learning model ⋮ The Vapnik-Chervonenkis dimension of a random graph ⋮ On prediction of individual sequences ⋮ Structural properties and convergence results for contours of sample statistical depth functions. ⋮ On computing the diameter of a point set in high dimensional Euclidean space. ⋮ PAC learning with nasty noise. ⋮ Apple tasting. ⋮ Statistical learning control of uncertain systems: theory and algorithms. ⋮ Which problems have strongly exponential complexity? ⋮ Generalization and learning error for nonlinear perceptron. ⋮ Rates of uniform convergence of empirical means with mixing processes