A sharp concentration inequality with applications

Stéphane Boucheron; G�bor Lugosi; Pascal Massart

doi:10.1002/(sici)1098-2418(200005)16:3<277::aid-rsa4>3.0.co;2-1

Abstract

We derive a new general concentration-of-measure inequality. The concentration inequality applies, among others, to configuration functions as defined by Talagrand and also to combinatorial entropies such as the logarithm of the number of increasing subsequences in a random permutation and to Vapnik-Chervonenkis (VC) entropies. The results find direct applications in statistical learning theory, substantiating the possibility to use the empirical VC entropy in penalization techniques. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 277–292, 2000

Keywords

LogarithmMathematicsInequalityConcentration inequalitystructEntropy (arrow of time)Permutation (music)Measure (data warehouse)CombinatoricsDiscrete mathematicsComputer sciencePhysicsMathematical analysisThermodynamicsData mining

Affiliated Institutions

Related Publications

The Power of Convex Relaxation: Near-Optimal Matrix Completion

Emmanuel J. Candès , Terence Tao

This paper is concerned with the problem of recovering an unknown matrix from a small fraction of its entries. This is known as the matrix completion problem, and comes up in a ...

2010 IEEE Transactions on Information Theory 2104 citations

The “Fallacy” of Maximizing the Geometric Mean in Long Sequences of Investing or Gambling

Paul A. Samuelson

Because the outcomes of repeated investments or gambles involve products of variables, authorities have repeatedly been tempted to the belief that, in a long sequence, maximizat...

1971 Proceedings of the National Academy o... 231 citations

Shear Viscosity of the Binary System Aniline-Cyclohexane Near the Critical Point

Giuseppe Arcòvito , C. Faloci , M. Roberti +1 more

The shear viscosity of the system aniline-cyclohexane has been measured for a mixture at the critical concentration. Above the critical temperature the experimental points are w...

1969 Physical Review Letters 64 citations

Volume Conduction of the Spike of‘ the Motor Unit Potential Investigated with a New Type of Multielectrode

Fritz Buchthal , Christian Guld , Poul Rosenfalck

Summary. The spike of motor unit potentials was investigated in the human brachial biceps by means of a multielectrode containing twelve small leading‐off surfaces distributed o...

1957 Acta Physiologica Scandinavica 113 citations

Crystal Potential Parameters from Fermi-Surface Dimensions

O. K. Andersen

It is shown that Lee's nonunique phase-shift parameters ${\ensuremath{\eta}}_{l}(\ensuremath{\kappa})$, determined from the experimental Fermi surfaces of Cu and the alkali meta...

1971 Physical Review Letters 26 citations

Publication Info

Year: 2000
Type: article
Volume: 16
Issue: 3
Pages: 277-292
Citations: 184
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

A sharp concentration inequality with applications

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

184

OpenAlex

Cite This

APA Style

                            
                                    Stéphane Boucheron, 
                                
                                    G�bor Lugosi, 
                                
                                    Pascal Massart
                                
                            (2000). 
                            A sharp concentration inequality with applications. 
                            Random Structures and Algorithms
                            , 16
                            (3)
                            , 277-292.
                            https://doi.org/10.1002/(sici)1098-2418(200005)16:3<277::aid-rsa4>3.0.co;2-1

Identifiers

DOI: 10.1002/(sici)1098-2418(200005)16:3<277::aid-rsa4>3.0.co;2-1