Study on Vapnik-Chervonenkis dimension of product intervals in R^d.
problem Combinatorial complexity of product intervals in R^d.
method Vapnik-Chervonenkis geometry approach.
result Vapnik-Chervonenkis dimension of balls in ℓ∞^d equals (3d+1)/2.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,291 papers · 148 categories
Trend · papers per month
48 results for “Vapnik-Chervonenkis Dimension”
The Vapnik-Chervonenkis (VC) dimension of a collection of subsets of a set is an important combinatorial concept in settings such as discrete geometry and machine learning. In this paper we prove that the VC dimension of the family of -dimensional cubes in is .
New method estimates Vapnik-Chervonenkis Dimension for linear functions.
problem Estimating Vapnik-Chervonenkis Dimension for linear models.
method Approximates VCD using cross-validated error and bounds on true risk.
result Model selection using estimated VCD performs well compared to other methods.
For any family of measurable sets in a probability space, we show that either (i) the family has infinite Vapnik-Chervonenkis (VC) dimension or (ii) for every epsilon > 0 there is a finite partition pi such the pi-boundary of each set has measure at most epsilon. Immediate corollaries include the fact that a family wit…
The paper provides risk bounds for learning many response functions using linear regression.
problem Learning many response functions from a single dataset.
method Ordinary least squares regression in a high-dimensional feature space.
result Convergence guarantees on worst-case excess prediction risk for infinite response functions with finite VC dimension.
Optimal sample complexity for contrastive learning of distances.
problem Minimum labeled tuples needed for high accuracy in learning distances.
method Analyzes sample complexity in various distance settings, proving tight bounds.
result Almost optimal bound on sample complexity for learning distances.
Vapnik-Chervonenkis (VC) dimension is a fundamental measure of the generalization capacity of learning algorithms. However, apart from a few special cases, it is hard or impossible to calculate analytically. Vapnik et al. [10] proposed a technique for estimating the VC dimension empirically. While their approach behave…
This research sets limits on how complex multi-class learning problems can be.
problem Understanding the complexity of multi-class classification problems.
method Established upper bounds on Natarajan dimensions for specific function classes.
result Upper bounds on Natarajan dimensions for multi-class decision trees, random forests, and neural networks.
Linear classifiers in product space forms improve scRNA-seq data classification.
problem Linear classification in products of Euclidean, spherical, and hyperbolic spaces.
method Novel formulations of linear classifiers on Riemannian manifolds, proving expressive power, and formalizing perceptron and SVM classifiers.
result Linear classifiers in product space forms have the same expressive power as in Euclidean space of the same dimension.
Deep Heaviside networks are limited but can be improved with connections or linear neurons.
problem Limited expressivity of deep Heaviside networks.
method Including skip connections or linear activation neurons improves expressivity.
result Lower and upper bounds for VC dimensions and approximation rates are derived.
Study on VC dimension of GCNNs with input resolution effects.
problem Understanding the generalization capabilities of GCNNs.
method Derived upper and lower bounds for VC dimension, analyzed factors affecting it.
result Extended previous results on VC dimension of GCNNs, providing insights into input resolution dependence.
Bounds on VC dimension for 1NN classifiers with fixed prototype sets.
problem No theoretical results for VC dimension of 1NN classifiers with fixed size prototype sets.
method Collected and used relevant theoretical results to provide explicit lower and upper bounds.
result Explicit lower and upper bounds for VC dimension of 1NN classifiers with fixed prototype set size.
The recently proposed Minimal Complexity Machine (MCM) finds a hyperplane classifier by minimizing an exact bound on the Vapnik-Chervonenkis (VC) dimension. The VC dimension measures the capacity of a learning machine, and a smaller VC dimension leads to improved generalization. On many benchmark datasets, the MCM gene…
The paper provides bounds on relational learning errors using VC-dimension.
problem Bounding errors in relational learning models.
method VC-dimension based bounds for relational data.
result Proved a bound on the error of relational models.
The paper provides bounds for regression schemes using nonstationary training samples.
problem Developing confidence intervals for nonparametric regression with nonstationary data.
method The approach involves Rademacher and Vapnik-Chervonenkis theories to analyze the cost and optimality of regression schemes.
result The paper establishes nonasymptotic bounds for regression schemes and optimality in -distance.
Study tests whether trade-off functions are above or below benchmarks using finite samples.
problem Testing trade-off functions between unknown distributions.
method Identifies a condition for nontrivial testing, constructs a test with error guarantees, and inverts the test for confidence bands.
result Finite-sample testing is possible under specific structural assumptions about rejection regions.
This paper analyzes the limits of neural networks under adversarial attacks.
problem Understanding how neural networks perform under adversarial noise.
method Defined the adversarial VC-dimension and combined it with the VC-dimension of halfspace classifiers.
result Concluded the adversarial VC-dimension of neural networks with sign activation functions.
New neural network class reduces VC dimension, leading to better generalization.
problem VC theory struggles with explaining small generalization errors in overparametrized neural networks.
method Developed hyperplane arrangement neural networks (HANNs) and used sample compression analysis.
result HANNs can have significantly smaller VC dimension than the number of weights, yet remain highly expressive.
Introduces greedy feature selection for classifier-dependent feature ranking.
problem Feature selection for classification tasks.
method Greedy feature selection, identifying the most important feature at each step based on the selected classifier.
result Theoretical and numerical benefits of greedy feature selection.
Deep ReLU networks generalize well with few parameters.
problem Generalization of overparametrized deep neural networks.
method Explicit bounds on test error independent of overparametrization and VC dimension.
result Generalization error is independent of network architecture and overparametrization.
Improves conformal prediction by combining multiple score functions and optimizing weights.
problem Limitations of single-score conformal predictors in multi-class classification.
method Combines multiple score functions and optimizes weights to minimize prediction set size.
result Consistently outperforms single-score conformal predictors while maintaining valid coverage.
The paper analyzes reducing model complexity for better generalization.
problem Improving model generalization with reduced complexity networks.
method Upper bound on Vapnik-Chervonenkis dimension, pruning, quantization, and a novel loss function.
result Quantization and the proposed loss function lead to sparser models with comparable accuracy.
WL meet VCcs.LG
The paper connects GNNs to VC dimension theory to study their generalization performance.
problem Understanding GNNs' ability to make meaningful predictions beyond the training set.
method Using Vapnik-Chervonenkis (VC) dimension theory in two settings: no upper bound on graph order and known upper bound.
result Tight connections between GNNs' bitlength, number of colors, and VC dimension in different settings.
New algorithm for non-Markovian optimal stopping problems using Brownian motion.
problem Optimal stopping time problems for non-Markovian state processes.
method Longstaff-Schwartz-type algorithm based on statistical learning theory.
result Error estimates for approximation architecture spaces with finite Vapnik-Chervonenkis dimension.
Paper extends nonparametric regression bounds for dependent -mixing samples.
problem Analyzing error in nonparametric regression with dependent data.
method Extends uniform deviation inequalities from independent to dependent -mixing samples.
result Derives generalization bounds for nonparametric regression with dependent data.
We investigate the use of Deep Neural Networks for the classification of image datasets where texture features are important for generating class-conditional discriminative representations. To this end, we first derive the size of the feature space for some standard textural features extracted from the input dataset an…
New Sauer inequality improves multiclass hypothesis class bounds.
problem Bounding the size of multiclass hypothesis classes.
method Polynomial method and combinatorial parameters (DS, list-DS dimensions).
result Sharp Sauer inequality with optimal polynomial dependence on list size and alphabet size.
The paper extends PAC-learning to handle evasion adversaries, finding limits on what can be learned.
problem Evasion attacks on machine learning models during testing.
method Extending PAC-learning framework to include evasion adversaries, defining corrupted hypothesis classes, and deriving adversarial VC-dimension.
result The adversarial VC-dimension can be larger or smaller than the standard VC-dimension, offering new insights.
New bounds show agnostic multiclass learning depends on two dimensions: Natarajan and Daniely-Shalev-Shwartz.
problem Understanding sample complexity in multiclass classification with agnostic learning.
method Developed a novel online procedure based on a self-adaptive multiplicative-weights algorithm.
result Agnostic sample complexity bounds are in the form of DS^(1.5)/ε + Nat/ε^2, nearly tight up to a √DS factor.
Statistical Regeneration Guarantees of the Wasserstein Autoencoder with Latent Space Consistencystat.ML
This paper provides statistical guarantees for WAE's latent space regeneration.
problem Lack of statistical analysis for Autoencoders, especially WAE.
method Utilizes Vapnik Chervonenkis (VC) theory and Optimal Transport of measures under the Wasserstein metric.
result WAE achieves the target distribution in the latent space and regenerates the input distribution.
The paper tackles extrapolation in extreme regions of regression problems.
problem Extrapolation on the tails of covariates in continuous regression problems.
method Statistical regression on a subsample of furthest observations, focusing on their angular components, using multivariate regular variation theory.
result Quantifies predictive performance on tail regions in terms of excess risk, presenting it as a finite sample risk bound with a bias-variance decomposition.
New algorithm reduces sample complexity for multi-distribution learning.
problem Achieving data-efficient multi-distribution learning with robustness and fairness.
method Proposes a novel algorithm with sample complexity (d+k)/varepsilon^2 for Vapnik-Chervonenkis (VC) dimension d, matching lower bounds.
result Algorithm matches best-known lower bound and resolves open problems in COLT 2023.
An Approach to One-Bit Compressed Sensing Based on Probably Approximately Correct Learning Theorystat.ML
Paper tackles one-bit compressed sensing using PAC learning theory.
problem One-bit compressed sensing problem.
method Formulated as PAC learning problem, uses VC-dimension and PAC learning theory.
result Consistent algorithm can recover -sparse vectors with measurements.
Chemical networks outperform spiking neural networks in classification tasks.
problem Learning tasks with spiking neural networks require hidden layers, which are computationally expensive.
method Used deterministic mass-action kinetics to prove chemical reaction networks without hidden layers can solve tasks previously solved by spiking neural networks.
result A chemical reaction network without hidden layers outperforms a spiking neural network with hidden layers in a handwritten digit classification task.
Paper combines RL with policy regularization for inventory policies.
problem Optimizing inventory policies using RL and dynamic programming.
method Hybrid approach combining RL with policy regularization.
result Generalization guarantees for inventory policies using VC theory.
Rademacher complexity and spin glasses: A link between the replica and statistical theories of learningcond-mat.dis-nn
Statistical learning theory connects to spin glass models via Rademacher complexity and replica theory.
problem Bounding generalization gap in statistical learning theory.
method Linking Rademacher complexity in statistical learning to synthetic models in statistical physics.
result Rademacher complexity is closely related to ground state energy in spin glass models.
Deep networks can efficiently approximate functions on curved manifolds.
problem Approximating functions and their derivatives on complex, curved domains.
method Proved constant-depth ReLU networks can approximate functions in Sobolev spaces on manifolds.
result Deep networks with bounded weights can approximate functions in to an error of using parameters.
PEA improves PCA and k-means for non-linear data and complex clusters.
problem Non-linear dimensionality reduction and clustering challenges.
method Principal Elliptical Analysis (PEA) for efficient non-linear approximation.
result PEA outperforms k-means in complex data clustering.
This paper tackles target-dependent label complexity gap in active learning.
problem Target-dependent label complexity gap in Agnostic Active Learning.
method Introduces a novel distribution-splitting strategy based on number density to reduce label complexity and error rate.
result Provides theoretical guarantees and practical advantages for reducing label complexity and error rate.
Effect of Various Regularizers on Model Complexities of Neural Networks in Presence of Input Noisecs.LG
The paper analyzes how different regularizers affect neural network complexity under input noise.
problem Understanding the impact of input noise on neural network complexity and regularization.
method Analysis of various regularization schemes (L2, DARC1, Jacobian, Spectral normalization) on neural network complexity under Gaussian input noise.
result Spectral normalization achieves the highest test set accuracies for both shallow and deep architectures.
We present an information-theoretic framework for bounding the number of labeled samples needed to train a classifier in a parametric Bayesian setting. We derive bounds on the average distance between the learned classifier and the true maximum a posteriori classifier, which are well-established surrogates for th…
Derives VC bounds for deep neural networks using radius-margin approach.
problem Understanding the capacity of deep neural networks.
method Applies radius-margin bounds from SVM to deep feed-forward architectures.
result Derives new VC bounds different from earlier ones.
Paper shows SVM can achieve super fast convergence rates.
problem Understanding fast convergence rates for SVM.
method Presented a simple mechanism to obtain fast convergence rates for SVM.
result SVM can exhibit exponential convergence rates without hard Tsybakov margin condition.
New findings show compressed representations are exponentially easier to learn.
problem Understanding the generalization power of neural networks.
method Studied the entropy of input variables as a simplicity assumption and proved a bound on sample complexity.
result Compressed representations are exponentially easier to learn, providing new insights into neural network generalization.
The paper studies empirical processes from nearest neighbors in regression.
problem Estimating conditional cumulative distribution functions and local linear regression.
method Uniform central limit theorem and non-asymptotic bound under local bracketing entropy and uniform entropy numbers.
result Gaussian limit of empirical process with simple covariance.
The paper provides consistency results for KDE on manifolds with irregular kernels.
problem Analyzing density estimation on manifolds with complex kernels.
method Strong uniform consistency with rates for KDE on Riemannian manifolds with Riemann integrable kernels.
result Strong uniform consistency with rates for KDE on manifolds.
Model selection is difficult to analyse yet theoretically and empirically important, especially for high-dimensional data analysis. Recently the least absolute shrinkage and selection operator (Lasso) has been applied in the statistical and econometric literature. Consis- tency of Lasso has been established under vario…
Study financial contagion in networks using low-rank approximations and graphons.
problem Modeling distress contagion in heterogeneous financial networks.
method Rank-K factorization, nonautonomous ODE, transport representation, graphon limits.
result Established well-posedness and stability for contagion models in various settings.