Andreas Maurer in the paper "A vector-contraction inequality for Rademacher complexities" extended the contraction inequality for Rademacher averages to Lipschitz functions with vector-valued domains; He did it replacing the Rademacher variables in the bounding expression by arbitrary idd symmetric and sub-gaussian var…
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.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Rademacher contraction”
The contraction inequality for Rademacher averages is extended to Lipschitz functions with vector-valued domains, and it is also shown that in the bounding expression the Rademacher variables can be replaced by arbitrary iid symmetric and sub-gaussian variables. Example applications are given for multi-category learnin…
Improved generalization bounds for CNNs using Rademacher complexity.
problem Establishing non-vacuous generalization bounds for deep learning models.
method Rademacher complexity framework with novel contraction lemmas for high-dimensional mappings.
result Enhanced generalization bounds for a broader class of activation functions.
We show that the Rademacher complexity of any -valued function class composed with an -Lipschitz function is bounded by the maximum Rademacher complexity of the restriction of the function class along each coordinate, times a factor of .
The study provides a generalization bound for a family of implicit networks.
problem Theoretical understanding of implicit networks' generalization is limited.
method A generalization bound is derived for a family of implicit networks using a covering number argument for Rademacher complexity.
result A theoretical generalization bound is established for implicit networks.
The paper provides a theoretical justification for using stable SSM blocks in deep sequential models.
problem Developing generalization bounds for deep sequential models with varying sequence lengths.
method Using Rademacher contraction and stability constraints, the paper derives a PAC bound that is independent of sequence length.
result The derived PAC bound decreases as the stability of SSM blocks increases, providing theoretical justification for their use.
Majorizing measures control sequential complexities for online learning.
problem Extending classical empirical processes theory to sequential cases.
method Generic chaining, majorizing measures, fractional covering numbers.
result Sharp control of worst-case sequential Rademacher complexity.
The paper analyzes learning rates for non-irreducible Markov chains.
problem Real-world data often violates i.i.d. assumptions.
method Examines iterated random functions and contractive functions.
result Derives data-distribution dependent learning rates.
The resilience of low-degree Rademacher chaos is studied, providing probabilistic lower bounds.
problem Understanding how much a Rademacher chaos can withstand adversarial sign-flips without significant probability changes.
method Probabilistic lower-bound guarantees for the resilience of Rademacher chaos of arbitrary degree.
result Probabilistic lower-bound guarantees for the resilience of Rademacher chaos of arbitrary degree, especially meaningful for constant degree.
A formula for Rademacher symbols in triangle groups is provided.
problem No specific problem stated; focuses on a mathematical formula.
method Presentation of an explicit formula for Rademacher symbols.
result Generalizes Ghys' proof of modular knot linking numbers.
We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in terms of transductive Rademacher complexity, together with a novel bounding technique for Rademacher…
The paper bounds the complexity of GCNs using Rademacher complexity.
problem Understanding the sample complexity of GCNs.
method Derived tight upper and lower bounds of Rademacher complexity for GCN models.
result The derived bounds depend on the largest eigenvalue of the graph filter and the degree distribution.
Analyzes the complexity of linear hypothesis sets using Rademacher complexity.
problem Understanding the complexity of linear hypothesis sets for various norms.
method Tight analysis of empirical Rademacher complexity for linear hypothesis classes with bounded weights.
result Improved bounds on Rademacher complexity for linear hypothesis sets, matching or improving existing results.
The paper analyzes risk bounds and Rademacher complexity in batch RL.
problem Estimating/minimizing Bellman error with general value function approximation.
method Characterizes generalization performance using Rademacher complexities of function classes.
result Risk bounds and Rademacher complexities provide insights into batch RL.
Tensorized Rademacher projections outperform Gaussian projections in reducing tensor dimensions.
problem Reducing the dimension of high-dimensional tensors for machine learning.
method Tensorized Rademacher random projections using Tensor Train decomposition.
result Tensorized Rademacher projections can replace Gaussian projections in tensor compression.
We show how to control the generalization error of time series models wherein past values of the outcome are used to predict future values. The results are based on a generalization of standard i.i.d. concentration inequalities to dependent data without the mixing assumptions common in the time series setting. Our proo…
The paper analyzes adversarial robustness for linear models and neural networks using Rademacher complexity.
problem Understanding adversarial robustness of linear models and neural networks.
method The paper uses Rademacher complexity to provide upper and lower bounds for adversarial robustness of linear hypotheses and neural networks.
result The paper provides bounds on adversarial Rademacher complexity for linear hypotheses and neural networks, offering a finer analysis of input dimensionality.
The developments of Rademacher complexity and PAC-Bayesian theory have been largely independent. One exception is the PAC-Bayes theorem of Kakade, Sridharan, and Tewari (2008), which is established via Rademacher complexity theory by viewing Gibbs classifiers as linear operators. The goal of this paper is to extend thi…
Improved bounds for Monte Carlo Rademacher Averages using self-bounding functions.
problem Proving sharper concentration bounds for MCERA.
method Deriving new bounds through self-bounding functions and concentration of measure.
result Novel bounds depend on data-dependent quantities, improving over standard methods.
Paper improves performance guarantees for Rademacher projections.
problem Improving statistical guarantees for Rademacher random projections.
method Algebraic framework for proving Schur-concavity properties.
result Novel Schur-concavity property of Rademacher projections with improved performance.
New findings show Rademacher complexities are not crucial for learning complexities.
problem Understanding the sample complexity of learning with squared loss in convex classes.
method Novel learning procedure combining mean estimation and Talagrand's generic chaining method.
result Sample complexity is determined by the limiting Gaussian process, not Rademacher complexities.
Great successes of deep neural networks have been witnessed in various real applications. Many algorithmic and implementation techniques have been developed, however, theoretical understanding of many aspects of deep neural networks is far from clear. A particular interesting issue is the usefulness of dropout, which w…
For a finite function class we describe the large sample limit of the sequential Rademacher complexity in terms of the viscosity solution of a -heat equation. In the language of Peng's sublinear expectation theory, the same quantity equals to the expected value of the largest order statistics of a multidimensional $…
Rademacher complexity and spin glasses: A link between the replica and statistical theories of learningcond-mat.dis-nn
Statistical learning theory provides bounds of the generalization gap, using in particular the Vapnik-Chervonenkis dimension and the Rademacher complexity. An alternative approach, mainly studied in the statistical physics literature, is the study of generalization in simple synthetic-data models. Here we discuss the c…
Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii [arXiv:0708.0083]
Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii [arXiv:0708.0083]
Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii [arXiv:0708.0083]
Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii [arXiv:0708.0083]
Discussion of "2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization" by V. Koltchinskii [arXiv:0708.0083]
This paper provides a general result on controlling local Rademacher complexities, which captures in an elegant form to relate the complexities with constraint on the expected norm to the corresponding ones with constraint on the empirical norm. This result is convenient to apply in real applications and could yield re…
Logistic regression gets a new, simpler uniform bound.
problem Finding a uniform bound for logistic regression's empirical risk.
method PAC-Bayes approach with second-order expansion and Rademacher-complexity bounds.
result Provides a dimension-free uniform concentration bound.
Transductive learning considers situations when a learner observes labelled training points and unlabelled test points with the final goal of giving correct answers for the test points. This paper introduces a new complexity measure for transductive learning called Permutational Rademacher Complexity (PRC) and …
We present a study of generalization for data-dependent hypothesis sets. We give a general learning guarantee for data-dependent hypothesis sets based on a notion of transductive Rademacher complexity. Our main result is a generalization bound for data-dependent hypothesis sets expressed in terms of a notion of hypothe…
Many machine learning models are vulnerable to adversarial attacks; for example, adding adversarial perturbations that are imperceptible to humans can often make machine learning models produce wrong predictions with high confidence. Moreover, although we may obtain robust models on the training dataset via adversarial…
Quantum reservoirs risk bounds are analyzed using Rademacher complexity.
problem Bounding generalization errors of quantum reservoirs.
method Using Rademacher complexity, specific bounds are derived for quantum reservoir classes.
result Risk bounds converge with increasing training samples and qubits.
The paper introduces gapped scale-sensitive dimensions to improve learning rate bounds.
problem Improving lower bounds on rates of convergence in statistical and online learning.
method Introducing and analyzing gapped scale-sensitive dimensions for function classes.
result Gapped dimensions lead to stronger lower bounds on offset Rademacher averages.
New bounds for non-convex estimators without Bernstein condition.
problem Sharp excess risk bounds for non-convex and improper estimators.
method Exponential-tail local Rademacher complexity risk bounds with offset condition.
result Sharp bounds for non-convex and improper estimators without Bernstein condition.
This paper shows that scientific discovery can be efficiently learned via compositional function trees, reducing the sample complexity.
problem Statistical and computational intractability of scientific discovery via symbolic regression.
method PAC learning approach focusing on compositional function trees built from a finite vocabulary of smooth operators.
result The Rademacher complexity and excess risk are controlled by depth and Lipschitz constants of the base operators, leading to finite-union bounds and high-probability risk bounds.
Estimates neural network errors for classification problems.
problem Binary and multi-class classification problems.
method Rademacher complexity estimates and direct approximation theorems.
result A priori error estimates for regularized loss functionals.
In many applications (in particular information systems, such as pattern recognition, machine learning, cheminformatics, bioinformatics to name but a few) the assessment of uncertainty is essential - i.e., the estimation of the underlying probability distribution function. More often than not, the form of this function…
Windings of prime geodesicsmath.NT
New method calculates winding of geodesics on surfaces.
problem Understanding the distribution of geodesics on surfaces.
method Introducing a new construction of winding numbers for geodesics on cusped hyperbolic orbifolds.
result Winding numbers can be expressed by Rademacher symbols for various arithmetic families of surfaces.
Neural ODEs simplified using Chen-Fliess series for Rademacher complexity analysis.
problem Analyzing the complexity of neural ODE models.
method Using Chen-Fliess series to frame neural ODEs as infinite-width nets, where weights are signature of control input and features are Lie derivatives.
result Derived compact expressions for the Rademacher complexity of ODE models.
The paper proves Rademacher's theorem for Heisenberg groups.
problem Proving Rademacher's theorem for Heisenberg groups.
method New definition of intrinsic Lipschitz graphs, extension and approximation theorems, use of Heisenberg currents and Rumin's complex.
result Rademacher's theorem for intrinsic Lipschitz graphs in Heisenberg groups.
LocalDrop uses local Rademacher complexity for neural network regularization.
problem Overfitting in deep neural networks.
method Developed a new regularization function based on local Rademacher complexity.
result Demonstrated effectiveness of LocalDrop through extensive experiments.
We express the number of lattice points inside certain simplices via Dedekind-Rademacher sums. As an application, we prove a conjecture of Kronheimer and Mrowka in the special case of Brieskorn spheres (with at most 4 singular fibers). This conjecture relates the Euler characteristic of the Seiberg-Witten-Floer homolog…
New bounds explain modern machine learning algorithms' generalization.
problem Explaining generalization behavior of modern machine learning algorithms.
method Proposes a new complexity measure based on empirical Rademacher complexity of an algorithm- and data-dependent hypothesis class.
result Obtains novel bounds with finite fractal dimension, simplifies proofs, and recovers known results.
Regularization of Deep Neural Networks (DNNs) for the sake of improving their generalization capability is important and challenging. The development in this line benefits theoretical foundation of DNNs and promotes their usability in different areas of artificial intelligence. In this paper, we investigate the role of…
We present a novel notion of complexity that interpolates between and generalizes some classic existing complexity notions in learning theory: for estimators like empirical risk minimization (ERM) with arbitrary bounded losses, it is upper bounded in terms of data-independent Rademacher complexity; for generalized Baye…