A sharp concentration inequality with applications

We present a new general concentration-of-measure inequality and illustrate its power by applications in random combinatorics. The results find direct applications in some problems of learning theory.

• Publication year

  1999

• Venue

  Random Struct. Algorithms

• Publication date

  1999-09-27

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1002/(SICI)1098-2418(200005)16:3%3C277::AID-RSA4%3E3.0.CO;2-1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Elements of Information Theory

  2005cited by this paper
• Lectures on probability theory and statistics

  2002cited by this paper
• Some applications of concentration inequalities to statistics

  2000cited by this paper
• The Nature of Statistical Learning Theory

  2000influential reference
• About the constants in Talagrand's concentration inequalities for empirical processes

  2000influential reference
• On Increasing Subsequences of I.I.D. Samples

  1999cited by this paper
• Adaptive Model Selection Using Empirical Complexities

  1998cited by this paper
• Structural Risk Minimization Over Data-Dependent Hierarchies

  1998cited by this paper
• Probabilistic methods for algorithmic discrete mathematics

  1998cited by this paper
• ESAIM. Probability and statistics

  1997cited by this paper
• Information inequalities and concentration of measure

  1997cited by this paper
• On Talagrand's deviation inequalities for product measures

  1997cited by this paper
• Isoperimetry and Gaussian analysis

  1996cited by this paper
• A new look at independence

  1996cited by this paper
• A Probabilistic Theory of Pattern Recognition

  1996cited by this paper
• Bounding $\bar{d}$-distance by informational divergence: a method to prove measure concentration

  1996cited by this paper
• Majorizing measures: the generic chaining

  1996cited by this paper
• A measure concentration inequality for contracting markov chains

  1996cited by this paper
• New concentration inequalities in product spaces

  1996cited by this paper
• Concentration of measure and isoperimetric inequalities in product spaces

  1994cited by this paper
• A Catalog of Complexity Classes

  1991cited by this paper
• On the Length of the Longest Monotone Subsequence in a Random Permutation

  1991cited by this paper
• On the independence number of random graphs

  1990cited by this paper
• Predicting (0, 1)-functions on randomly drawn points

  1988cited by this paper
• Logarithmic Sobolev inequalities and stochastic Ising models

  1987cited by this paper
• A simple proof of the blowing-up lemma

  1986cited by this paper
• Nonnegative Entropy Measures of Multivariate Symmetric Correlations

  1978cited by this paper
• Bounds on conditional probabilities with applications in multi-user communication

  1976cited by this paper
• Bounds on Conditional Probabilities with Applications in Multi-User Communication

  1976cited by this paper
• An inequality related to the isoperimetric inequality

  1949cited by this paper
• Concentration

  1894cited by this paper

• RI-Loss: A Learnable Residual-Informed Loss for Time Series Forecasting

  2025cites this paper
• Delegated Choice with Combinatorial Constraints

  2025cites this paper
• Symmetry of concentration and scaling for self-bounding functions

  2025cites this paper
• Revisit Non-parametric Two-sample Testing as a Semi-supervised Learning Problem

  2024cites this paper
• Patricia's Bad Distributions

  2024cites this paper
• On Fluctuations of Complexity Measures for the FIND Algorithm

  2024cites this paper
• On the Efficiency of ERM in Feature Learning

  2024cites this paper
• A Unified Data Representation Learning for Non-parametric Two-sample Testing

  2024cites this paper
• A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions

  2024influential citation
• Improved Approximation for Two-dimensional Vector Multiple Knapsack

  2023influential citation
• Fair Multiwinner Elections with Allocation Constraints

  2023influential citation
• An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding

  2023cites this paper
• q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations

  2023cites this paper
• Do we really need a new theory to understand over-parameterization?

  2023cites this paper
• Computational and Data Requirements for Learning Generic Properties of Simulation-Based Games

  2022cites this paper
• Prophet Inequalities via the Expected Competitive Ratio

  2022cites this paper
• Bavarian: Betweenness Centrality Approximation with Variance-aware Rademacher Averages

  2022cites this paper
• Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition

  2022cites this paper
• Concentration of the missing mass in metric spaces

  2022influential citation
• Generalization Performance of Pure Accuracy and its Application in Selective Ensemble Learning

  2022influential citation
• Modified log-Sobolev inequalities, beckner inequalities and moment estimates. involving

  2022cites this paper
• On Simple Mechanisms for Dependent Items

  2021cites this paper
• Learnability of Learning Performance and Its Application to Data Valuation

  2021cites this paper
• Bavarian: Betweenness Centrality Approximation with Variance-Aware Rademacher Averages

  2021cites this paper
• Improved Algorithms for Edit Distance and LCS: Beyond Worst Case

  2020cites this paper
• Risk upper bounds for RKHS ridge group sparse estimator in the regression model with non-Gaussian and non-bounded error

  2020influential citation
• Novel Concentration of Measure Bounds with Applications to Fairness in Machine Learning

  2020influential citation
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates

  2020cites this paper
• Sharper convergence bounds of Monte Carlo Rademacher Averages through Self-Bounding functions

  2020influential citation
• Asymptotics for Push on the Complete Graph

  2020cites this paper
• PAC-Bayes Unleashed: Generalisation Bounds with Unbounded Losses

  2020cites this paper
• Sharp uniform convergence bounds through empirical centralization

  2020cites this paper
• Modified log-Sobolev inequalities and two-level concentration

  2019cites this paper
• An analytic formulation for positive-unlabeled learning via weighted integral probability metric

  2019influential citation
• Bayesian and Frequentist: An Example

  2019influential citation
• Kernel Methods: Support Vector Machines

  2019cites this paper
• L G ] 1 J un 2 01 9 Tight Bounds on l 1 Approximation and Learning of Self-Bounding Functions

  2019cites this paper
• Some compact notations for concentration inequalities and user-friendly results

  2019cites this paper
• Complexity-Based Methods

  2019cites this paper
• Managing Information Constraints Over Networks Through the Lens of Configuration Functions

  2019cites this paper
• The “Five W” of MS and EE

  2019cites this paper
• Statistical properties of Kernel Prinicipal Component Analysis

  2019cites this paper
• Model selection and error estimation without the agonizing pain

  2018influential citation
• Improved Multi-Task Learning Based on Local Rademacher Analysis

  2017cites this paper
• Information Metrics for Predictive Modeling and Machine Learning

  2017cites this paper
• Metamodel Construction for Sensitivity Analysis

  2017influential citation
• Gaussian martingale inequality applies to random functions and maxima of empirical processes

  2017influential citation
• Quantum computing and supervised machine learning

  2017cites this paper
• Semi-supervised Learning for Affective Common-Sense Reasoning

  2017cites this paper
• Concentration of measure principle and entropy-inequalities

  2017cites this paper
• A local Vapnik-Chervonenkis complexity

  2016cites this paper
• Concentration and compression over infinite alphabets, mixing times of random walks on random graphs

  2016cites this paper
• Double roots of random polynomials with integer coefficients

  2016cites this paper
• Global Rademacher Complexity Bounds: From Slow to Fast Convergence Rates

  2016influential citation
• Network Maximal Correlation

  2016cites this paper
• Phénomènes de concentration en grande dimension, transport de mesure et inégalités fonctionnelles.

  2016cites this paper
• Opting Into Optimal Matchings ∗

  2016cites this paper
• Opting Into Optimal Matchings

  2016cites this paper
• On McDiarmid's inequality for Hamming distance

  2016influential citation
• Toward Machine Wald

  2015cites this paper
• On Dvoretzky's theorem for subspaces of L

  2015cites this paper
• Machine Wald

  2015cites this paper
• Fully Empirical and Data-Dependent Stability-Based Bounds

  2015cites this paper
• Oracle inequalities for ranking and U-processes with Lasso penalty

  2015cites this paper
• Foundations of Statistical Learning and Model Selection

  2015cites this paper
• Local Rademacher Complexity: Sharper risk bounds with and without unlabeled samples

  2015cites this paper
• Concentration inequalities for sums

  2015cites this paper
• Mathematical Foundations of Infinite-Dimensional Statistical Models

  2015cites this paper
• Fast rates for ranking with large families

  2015cites this paper
• Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions

  2015cites this paper
• Fast convergence of extended Rademacher Complexity bounds

  2015cites this paper
• A Deep Connection Between the Vapnik–Chervonenkis Entropy and the Rademacher Complexity

  2014cites this paper
• Tight Bounds on ℓ1 Approximation and Learning of Self-Bounding Functions

  2014cites this paper
• Falsifiable implies Learnable

  2014influential citation
• U-Processes and Preference Learning

  2014cites this paper
• Structure and learning of valuation functions

  2014cites this paper
• Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding Functions

  2014cites this paper
• Kernel Methods and Support Vector Machines

  2014cites this paper
• Ranking with Diverse Intents and Correlated Contents

  2013cites this paper
• Learning Coverage Functions

  2013cites this paper
• Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees

  2013influential citation
• An improved analysis of the Rademacher data-dependent bound using its self bounding property

  2013influential citation
• Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

  2013influential citation
• Some results about the Vapnik-Chervonenkis entropy and the rademacher complexity

  2013cites this paper
• Kernel Methods for Learning

  2013cites this paper
• Learning Coverage Functions and Private Release of Marginals

  2013cites this paper
• Sur la fonction de taux dans les inégalités de Talagrand pour les processus empiriques

  2012cites this paper
• Weak Transport Inequalities and Applications to Exponential and Oracle Inequalities

  2012cites this paper
• Regulating the information in spikes: a useful bias

  2012cites this paper
• Learning pseudo-Boolean k-DNF and submodular functions

  2012cites this paper
• On the Size of the Online Kernel Sparsification Dictionary

  2012cites this paper
• On the generation of representations for reinforcement learning

  2012cites this paper
• Matrix Factorization and Matrix Concentration

  2012cites this paper
• Concentration Inequalities in Locally Dependent Spaces

  2012cites this paper
• On the empirical estimation of integral probability metrics

  2012cites this paper
• Weak transport inequalities and applications to exponential inequalities and oracle inequalities

  2012cites this paper
• Sur la fonction de taux dans les inégalités de Talagrand pour les processus empiriques

  2012cites this paper
• Weak transport inequalities and applications to exponential and oracle inequalities

  2012cites this paper
• Contributions à la statistique des processus : estimation, prédiction et extrêmes

  2012cites this paper
• Information, learning and falsification

  2011cites this paper