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.
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.
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.
New method improves deep neural networks' generalization using Local Rademacher Complexity.
problem Improving generalization of deep neural networks.
method Developed a novel regularizer based on Local Rademacher Complexity.
result Demonstrated effectiveness of the LRC-based regularizer in improving generalization.
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…
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…
New algorithms reduce online learning regret using empirical Rademacher complexity.
problem Adaptive online learning with bounded regret against any sequence.
method Developed a novel family of algorithms based on empirical Rademacher complexity and decoupling inequalities.
result Achieved adaptive regret bounds for various hypothesis classes.
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.
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 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 …
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.
Unified complexity measure for learning theory improves risk bounds.
problem Improving risk bounds in learning theory for various estimators.
method Introduces a new complexity measure interpolating between Rademacher, KL-divergence, and NML complexities.
result Bounded excess risk in terms of the new complexity measure.
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.
DOC3 learns from contradictions to improve deep one class classification.
problem Deep one class classification problems.
method Formalizes learning from contradictions for one class large-margin loss, proposes DOC3 algorithm.
result DOC3 incurs lower generalization error compared to traditional inductive learning.
We analyze the local Rademacher complexity of empirical risk minimization (ERM)-based multi-label learning algorithms, and in doing so propose a new algorithm for multi-label learning. Rather than using the trace norm to regularize the multi-label predictor, we instead minimize the tail sum of the singular values of th…
The paper generalizes offset Rademacher complexities to convex and non-convex problems.
problem Improper learning and convexity in statistical learning.
method Generalization of offset Rademacher complexities to convex and non-convex problems.
result The offset complexity provides versatile analytic tools for both convex and non-convex learning.
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…
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).
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 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.
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.
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…
Extends inequality for Rademacher complexities using p-stable variables.
problem Improving Rademacher complexity bounds using p-stable variables. method Extends contraction inequality to p-stable variables for 1<p<2. result New bounds for Rademacher complexities with p-stable variables. 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 …
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.
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.
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.
New bounds improve neural network generalization by considering data-dependent properties.
problem Exponential dependence on depth in existing bounds for neural networks.
method Augmenting functions to make their composition Lipschitz and covering the augmented functions.
result Rademacher complexity bounds scale polynomially in depth when data-dependent properties are small.
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.
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…
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.
This work proves L2-regularized ERM controls smCE without post-hoc correction.
problem Calibration of predicted probabilities in machine learning models.
method Canonical L2-regularized empirical risk minimization. result Theoretical proof that smCE is controlled by ERM without post-hoc correction.
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.
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.
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.
We propose a new approach, multi-view Laplacian support vector machines (SVMs), for semi-supervised learning under the multi-view scenario. It integrates manifold regularization and multi-view regularization into the usual formulation of SVMs and is a natural extension of SVMs from supervised learning to multi-view sem…
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.
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 introduces a new stability concept for cross-validation and derives new bounds for model stability.
problem The effect of cross-validation on model generalization and stability.
method Introducing the (β, ϖ)-stability concept and deriving new Rademacher bounds.
result The new bounds quantify the stability of cross-validated models and provide optimal number of folds.
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…
Study on generalization for data-dependent hypothesis sets.
problem Understanding generalization in hypothesis sets dependent on data.
method Learning guarantee based on transductive Rademacher complexity and hypothesis set stability.
result Generalization bound for data-dependent hypothesis sets.
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 $…
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.
The study provides theoretical guarantees for the statistical performance of optimal decision trees.
problem Theoretical limits on the statistical performance of globally optimal decision trees.
method Sharp oracle inequalities and uniform concentration framework based on Rademacher complexity.
result Derivation of minimax optimal rates for piecewise sparse heterogeneous anisotropic Besov space.
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]