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…
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,932 papers · 148 categories
Trend · papers per month
48 results for “Rademacher bounds”
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.
New bound on Rademacher complexity for vector functions.
problem Bounding Rademacher complexity for vector-valued functions.
method Bounding Rademacher complexity by coordinate-wise complexity with a factor of sqrt(K).
result Rademacher complexity is bounded by the maximum coordinate-wise complexity times sqrt(K).
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.
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.
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.
Paper extends PAC-Bayesian theory using shifted Rademacher processes.
problem Improving PAC-Bayesian bounds for fast rates.
method Using shifted Rademacher processes to match Catoni's bounds and derive new fast-rate bounds.
result New fast-rate PAC-Bayes bounds derived in terms of empirical risk surface flatness.
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.
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.
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…
Extends inequality for Rademacher complexities using -stable variables.
problem Improving Rademacher complexity bounds using -stable variables.
method Extends contraction inequality to -stable variables for .
result New bounds for Rademacher complexities with -stable variables.
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.
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.
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…
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.
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.
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…
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.
New bound explains why high-rank neural nets generalize well.
problem Understanding why high-rank neural networks generalize well.
method Using Koopman operators, group representations, and RKHSs, a new Rademacher complexity bound is derived.
result Derives a bound for a wider range of realistic models.
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.
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…
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…
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…
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 $…
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 …
This paper improves bounds on DNN generalization to adversarial examples.
problem Improving generalization of deep neural networks to adversarial data.
method Investigates Rademacher complexity and introduces a new covering number.
result Achieves upper bounds for adversarial Rademacher complexity matching standard settings.
This paper bounds errors in data-driven power grid models using Rademacher complexity.
problem Ensuring accuracy of data-driven power grid models under incomplete physical information.
method Rademacher complexity theory for error bounds and evaluation implementation.
result Generalization error bounds for branch flow linearization and external network equivalent models.
Study bounds Rademacher complexity of Fourier neural operators.
problem Bounding Rademacher complexity for Fourier neural operators.
method Investigated using specific group norms and capacity.
result Inferred that group norms determine model information.
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.
Improved bounds and algorithms for vector-valued learning using unlabeled data.
problem Vector-valued learning with improved bounds and algorithms.
method Local Rademacher complexity and Laplacian regularization.
result Significantly improved convergence rates and better performance.
New margin-based learning guarantees improve generalization bounds.
problem Improving generalization bounds for machine learning models.
method Relative deviation margin bounds using empirical margin loss and Rademacher complexity.
result Distribution-dependent generalization bounds for unbounded loss functions.
Study improves generalization bounds for equivariant networks on Markov data.
problem Challenges in integrating equivariance with Markov dependencies in neural networks.
method Applied McDiarmid's inequality and computed covering number using group theory.
result Derived upper bound on Rademacher complexity for equivariant neural networks on Markov datasets.
The paper offers generalization bounds for Transformers that ignore sequence length.
problem Developing generalization bounds for Transformers that are independent of sequence length.
method Covering number approach to upper bound Rademacher complexity of bounded linear transformations.
result Theoretical bounds for Transformer generalization are independent of sequence length.
Paper establishes a generalization bound for gradient flow using a data-dependent kernel.
problem Understanding the generalization properties of gradient-based optimization methods.
method Establishes a generalization bound for gradient flow through a data-dependent kernel called the loss path kernel (LPK).
result The LPK captures the entire training trajectory and leads to tighter generalization guarantees.
We derive an upper bound on the local Rademacher complexity of -norm multiple kernel learning, which yields a tighter excess risk bound than global approaches. Previous local approaches aimed at analyzed the case only while our analysis covers all cases , assuming the different feature …
Upper bounds for CV errors apply to lasso and other models.
problem Bounding CV errors for lasso and similar models.
method Rademacher complexity and Orlicz- norm.
result Upper bounds are tight and stable for lasso.
We develop a novel family of algorithms for the online learning setting with regret against any data sequence bounded by the empirical Rademacher complexity of that sequence. To develop a general theory of when this type of adaptive regret bound is achievable we establish a connection to the theory of decoupling inequa…
We propose Rademacher complexity bounds for multiclass classifiers trained with a two-step semi-supervised model. In the first step, the algorithm partitions the partially labeled data and then identifies dense clusters containing predominant classes using the labeled training examples such that the proportion of t…
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 …
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.
Study excess capacity in neural networks using Rademacher complexity.
problem Understanding how much capacity deep networks have beyond what's needed for classification.
method Unified Rademacher complexity bounds for function composition and convolutional layers, considering Lipschitz constants and initialization norms.
result There is substantial excess capacity per task, and capacity can be kept similar across different tasks.
From concentration inequalities for the suprema of Gaussian or Rademacher processes an inequality is derived. It is applied to sharpen existing and to derive novel bounds on the empirical Rademacher complexities of unit balls in various norms appearing in the context of structured sparsity and multitask dictionary lear…
New analysis shows PE in Transformers increases generalization gap and vulnerability.
problem Understanding the impact of PE on Transformer generalization and robustness.
method Generalization analysis and adversarial Rademacher bounds for a single-layer Transformer with trainable PE.
result PE systematically enlarges the generalization gap and makes models more vulnerable to attacks.
ACL improves robustness with unlabeled data, and we analyze its generalization using Rademacher complexity.
problem Improving robustness of deep networks against adversarial attacks using unlabeled data.
method We analyze the generalization performance of Adversarial Contrastive Learning (ACL) using Rademacher complexity.
result The average adversarial risk of the downstream tasks can be upper bounded by the adversarial unsupervised risk of the upstream task.
We consider regression with square loss and general classes of functions without the boundedness assumption. We introduce a notion of offset Rademacher complexity that provides a transparent way to study localization both in expectation and in high probability. For any (possibly non-convex) class, the excess loss of a …
SGD-trained deep nets have bounds on their generalization error.
problem Bounding generalization error for deep neural networks trained by SGD.
method Combining dynamical control of parameter norms and Rademacher complexity estimates.
result Explicit bounds depend on loss trajectory, work for various architectures.
Approximation bounds for norm constrained neural networks with applications to regression and GANscs.LG
The paper bounds neural networks' approximation error and applies it to regression and GANs.
problem Bounding the approximation error of norm-constrained neural networks.
method Proved upper and lower bounds on approximation error using Rademacher complexity.
result Obtained convergence rates for over-parameterized neural networks and optimal GAN learning rates.