arXiv research

Improved bounds for Monte Carlo Rademacher Averages using self-bounding functions.

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…

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…

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…

MCRapper efficiently computes patterns in data using Monte-Carlo Rademacher Averages.

The paper introduces gapped scale-sensitive dimensions to improve learning rate bounds.

Recently, metric learning and similarity learning have attracted a large amount of interest. Many models and optimisation algorithms have been proposed. However, there is relatively little work on the generalization analysis of such methods. In this paper, we derive novel generalization bounds of metric and similarity …

The method to derive uniform bounds with Gaussian and Rademacher complexities is extended to the case where the sample average is replaced by a nonlinear statistic. Tight bounds are obtained for U-statistics, smoothened L-statistics and error functionals of l2-regularized algorithms.

In this paper, we introduce a new concept of stability for cross-validation, called the $\left( β, \varpi \right)$-stability, and use it as a new perspective to build the general theory for cross-validation. The $\left( β, \varpi \right)$-stability mathematically connects the generalization ability and the stability of…

ACL improves robustness with unlabeled data, and we analyze its generalization using Rademacher complexity.

The paper provides bounds for regression schemes using nonstationary training samples.

We derive a closed formula for the Heegaard Floer correction terms of lens spaces in terms of the classical Dedekind sum and its generalization, the Dedekind-Rademacher sum. Our proof relies on a reciprocity formula for the correction terms established by Ozsvath and Szabo. A consequence of our result is that the Casso…

The paper studies risk-sensitive learning schemes and provides learning bounds for empirical OCE minimizers.

The resilience of low-degree Rademacher chaos is studied, providing probabilistic lower bounds.

A formula for Rademacher symbols in triangle groups is provided.

Improved generalization bounds for CNNs using Rademacher complexity.

We show that the Rademacher complexity of any $\mathbb{R}^{K}$-valued function class composed with an $\ell_{\infty}$-Lipschitz function is bounded by the maximum Rademacher complexity of the restriction of the function class along each coordinate, times a factor of $\tilde{O}(\sqrt{K})$.

The paper bounds the complexity of GCNs using Rademacher complexity.

Analyzes the complexity of linear hypothesis sets using Rademacher complexity.

The paper analyzes risk bounds and Rademacher complexity in batch RL.

Tensorized Rademacher projections outperform Gaussian projections in reducing tensor dimensions.

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.

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…

Paper improves performance guarantees for Rademacher projections.

The study analyzes robustness of estimators in linear models with adversarial errors.

New findings show Rademacher complexities are not crucial for learning 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 $G$-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 $…

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…

Paper establishes generalization bounds for RNNs and improves existing results.

Logistic regression gets a new, simpler uniform bound.

Transductive learning considers situations when a learner observes $m$ labelled training points and $u$ 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.

New bounds for non-convex estimators without Bernstein condition.

Estimates neural network errors for classification problems.

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…

New method calculates winding of geodesics on surfaces.

Neural ODEs simplified using Chen-Fliess series for Rademacher complexity analysis.

The paper proves Rademacher's theorem for Heisenberg groups.