Instance-dependent uniform tail bounds for empirical processes

  • 2022-09-22 15:53:11
  • Sohail Bahmani
  • 0


We formulate a uniform tail bound for empirical processes indexed by a classof functions, in terms of the individual deviations of the functions ratherthan the worst-case deviation in the considered class. The tail bound isestablished by introducing an initial "deflation" step to the standard genericchaining argument. The resulting tail bound has a main complexity component, avariant of Talagrand's $\gamma$ functional for the deflated function class, aswell as an instance-dependent deviation term, measured by an appropriatelyscaled version of a suitable norm. Both of these terms are expressed usingcertain coefficients formulated based on the relevant cumulant generatingfunctions. We also provide more explicit approximations for the mentionedcoefficients, when the function class lies in a given (exponential type) Orliczspace.


Quick Read (beta)

loading the full paper ...