Instance-dependent uniform tail bounds for empirical processes

arXiv2209.10053MaRDI QIDQ6508045FDOQ6508045

Authors: Sohail Bahmani 

Abstract: We formulate a uniform tail bound for empirical processes indexed by a class of functions, in terms of the individual deviations of the functions rather than the worst-case deviation in the considered class. The tail bound is established by introducing an initial "deflation" step to the standard generic chaining argument. The resulting tail bound has a main complexity component, a variant of Talagrand's $gamma$ functional for the deflated function class, as well as an instance-dependent deviation term, measured by an appropriately scaled version of a suitable norm. Both of these terms are expressed using certain coefficients formulated based on the relevant cumulant generating functions. We also provide more explicit approximations for the mentioned coefficients, when the function class lies in a given (exponential type) Orlicz space.

This page was built for publication: Instance-dependent uniform tail bounds for empirical processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6508045)