Bracketing number for monotone functions $f:\mathbb{R} \to [0,1]$.

518 Views Asked by At

I have been trying to understand a bound on the log of the bracketing number for monotone functions with range in $[0,1]$. My book claims that constructing the brackets as piecewise constant functions on a regular grid will bring about a bound of order $1/\epsilon \log(1/\epsilon)$ but I do not see how one can arrive at this. If someone has an idea, could I please enlist their help?

The $\epsilon$-bracketing number is defined as the minimum number of brackets of size at most $\epsilon$ needed to cover a given set of functions. A set of functions $\mathcal{F}$ is covered by $\epsilon$-brackets $[l_j, u_j], j=1, \ldots, N$ if $\mathcal{F} \subset \cup_j [l_j, u_j]$ and $u_j(x)-l_j(x) < \epsilon$. This minimum number of brackets is closely related to entropy, which is defined as the logarithm of that number and is crucial in the theory of empirical processes.