This is exercise 2.3 from van de Geer's Empirical processes in M-estimation.
Let $\mathcal G$ be the class of unimodal functions $g : \mathbb R \rightarrow [0, 1]$. A function $f$ is unimodal if there is a value $m$ such that $f$ is increasing up until $f(m)$ and then decreasing afterwards.
I want to show that the $\delta-$bracketing entropy of $\mathcal G$ is bounded above by $A/\delta$ for some constant $A$ for all probability measures. Recall that the $\delta-$bracketing entropy is defined as the log of the smallest value $n$ for which there exist pairs of functions $\{(g_i^L, g_i^U)\}_{i=1}^n$ such that $\|g_i^U-g_i^L\|_{Q}\leq \delta$ and for each $g\in \mathcal G$ there is some $i$ such that: $g_i^L \leq g \leq g_i^U$. For this problem, $\|\cdot \|_Q$ is the $L_{2,Q}$ norm for a probability measure $Q$.
I know the following lemma:
Let $\mathcal F$ be the class of increasing functions $f: \mathbb R \rightarrow [0, 1]$. There is some constant $B$ such that for any probability measure $Q$, the $\delta-$bracketing entropy $H_B(\delta, \mathcal G, Q)$ is bounded above as: $$H_B(\delta, \mathcal F, Q) \leq B \frac{1}{\delta}$$
my attempt
I can only construct a partial solution which is for the case where $\mathcal G$ is limited to unimodal functions centered around $0$. In that case, given a $\delta-$bracketing $\mathcal H_\delta$ of $\mathcal F$, we can construct a $\delta-$bracketing of $\mathcal G$ by changing from increasing to decreasing at $x=0$. Let $refl(h) = \mathbb 1 (x \leq 0) h(x) + \mathbb 1(x>0) (1-h(x))$. Then, Defining:
$$\mathcal C^L_\delta = \{(refl(h^L), refl(h^U)) | (h^L, h^U) \in \mathcal H_\delta\}$$
which is of the same size as $\mathcal H_\delta$. This forms a bracketing of $\mathcal G$ because each $g \in \mathcal G$ is bracketed by some $h_1 \in \mathcal H_\delta$ when $x\leq 0$ (since it is equal to some $f \in \mathcal F$ in this interval) and $1-g$ is bracketed by some $h_2 \in \mathcal H_\delta$ (using the same argument). Finally, we show that each bracket is of size at most $\delta$:
$$\left ( \int_{-\infty}^\infty |refl(h^L) - refl(h^U)|^p dQ \right)^{1/p} = \left ( \int_{-\infty}^0 |h_1^L - h_1^U|^p dQ + \int_{0}^\infty |h_2^L - h_2^U|^p dQ \right)^{1/p}$$
This is bounded above by $\delta$ if the bracket defined by the functions $\mathbb 1 (x\leq 0) h_1^L + \mathbb 1 (x>0) h_2^L$ and $\mathbb 1 (x\leq 0) h_1^U + \mathbb 1 (x>0) h_2^U$ is in the original bracketing $\mathcal H_\delta$. We can ensure this by adding every function of this form to $\mathcal H_\delta$. This only squares the size of the set, adding a constant factor to the entropy. So we are done.
my questions
- Are there any issues with my proof for the limited case?
- How can I extend my proof to the more general case (which does not require the mode to be at $0$)?
- One thought I have is to split the support of $Q$ between the "$\alpha-$negligable part" and the "important part" which is the subset $S_{1-\alpha}$ of the support $S$ such that $\|\mathbb 1 (x \in S_{1-\alpha})\|_Q \geq 1-\alpha$. Since our functions are bounded, this means we can bound the contribution outside the important set uniformly over functions in the set. However, I want to show that this is the case for all probability measures, which I don't know how to handle.
EDIT: Of course I had missed that we can construct a unimodal function as the difference of two increasing functions. From Professor van de Geer:
Let $h$ be a unimodal function, with (say) a maximum at $m$. Write $h$ as the difference of two increasing functions $f$ and g$$: let $f=h$ till $m$ and from $m$ onwards let $f$ be constant equal to $h(m)$. Let $g$ be zero till $m$ and then jump to $h(m)$ and be increasing onwards, such that
$$h=f-g$$
Let $[f^L, f^U]$ be a delta bracket for $f$ and [$g^L, g^U ]$ a delta bracket for $g$. Then for $h^L:= f^L - g^U$ and $h^U := f^U - g^L$
$$h^L = f^L - g^U \le f -g \le f^U - g_L = h^U$$
and
$$h^U - h^L = f^U - f^L + g^U - g^L$$
so that $[h^L, h^U]$ is a $2-\delta$ bracket for $h$.
EDIT2: I am still interested in my question 3 above and whether my proof can be extended to the general case.