Fast rates for empirical risk minimization over c\`adl\`ag functions with bounded sectional variation norm

Understand

Empirical risk minimization over classes functions that are bounded for some version of the variation norm has a long history, starting with Total Variation Denoising (Rudin et al., 1992), and has been considered by several recent articles, in particular Fang et al., 2019 and van der Laan, 2015.

• In this article, we consider empirical risk minimization over the class $\mathcal{F}_d$ of c\`adl\`ag functions over $[0,1]^d$ with bounded sectional variation norm (also called Hardy-Krause variation).
• We show how a certain representation of functions in $\mathcal{F}_d$ allows to bound the bracketing entropy of sieves of $\mathcal{F}_d$, and therefore derive rates of convergence in nonparametric function estimation.
• Specifically, for sieves whose growth is controlled by some rate $a_n$, we show that the empirical risk minimizer has rate of convergence $O_P(n^{-1/3} (\log n)^{2(d-1)/3} a_n)$.