1
$\begingroup$

For a class of functions $\mathcal{F}$ and a pair $f,g\in\mathcal{F}$ with $f\leq g$, the interval $[f,g]=\{h:f(x)\leq h(x)\leq g(x),\forall x\in\mathbb{R}^d\}$ is called a bracket for $\mathcal{F}$. If $d$ is a metric on $\mathcal{F}$, then de bracketing number $N_{[]}(\varepsilon,\mathcal{F},d)$ is the minimal number of brackets $[f,g]$ needed to cover $\mathcal{F}$ such that $d(f,g)\leq\varepsilon$.

Now if $\mathcal{F}$ is the collection of all (indicators of) half-spaces over $\mathbb{R}^d$, i.e., all sets of the form $$ H(u,v)=\{y\in\mathbb{R}^d:v^\top(y-u)\geq 0\} $$ where $u,v\in\mathbb{R}^d$.

Question: Does this class (the half-spaces) satisfy the integral condition $$ \int_0^1\sqrt{\log N_{[]}(\varepsilon,\mathcal{F},d)} \, d\varepsilon<\infty $$ where $d(x,y)=\|x-y\|_p$ denotes the $L^p$-norm (for simplicity, $p$ can be taken 1 or 2)? Here, the underlying probability measure can be assumed to be Lebesgue absolutely continuous. Note also that this integral is nothing but the Dudley entropy integral where we changed $N$ to $N_{[]}$.

Here are some known facts that might help to answer the question:

It is well known that the collection $\mathcal{F}$ is bracketing compact, meaning that $N_{[]}(\varepsilon,\mathcal{F},d)<\infty$ for all $\varepsilon>0$. Furthermore, the collectoin $\mathcal{F}$ is totally bounded, with envelope $F$ satisfying $|F|\leq 1$. Additionally, the class $\mathcal{F}$ is a VC-class of dimension $d+2$ and the entropy number $N$ satisfies $$ N(\varepsilon,\mathcal{F},\|\cdot\|_{r})\leq K(d+2)(4e)^{d+2}\left(\frac{1}{\varepsilon}\right)^{r(d+2)}, $$ see theorem 2.6.4 in the book weak convergence and empirical processes. Additionally, it is known that $N(\varepsilon,\mathcal{F},\|\cdot\|_{L^r})\leq N_{[]}(2\varepsilon,\mathcal{F},\|\cdot\|_{L^r})$ for $r\geq 1$, yet I do not know whether one can bound $N_{[]}$ in terms of $N$ (or the VC dimension) if $\mathcal{F}$ satisfies various properties. A notable exception is when we consider the uniform norm, i.e., $\|\cdot\|_\infty$, from which we obtain the equality $$ N(\varepsilon,\mathcal{F},\|\cdot\|_{\infty})=N_{[]}(2\varepsilon,\mathcal{F},\|\cdot\|_{\infty}), $$ see page 132 in the above book for a proof.

I also asked this question on math.stackexchange, yet I figured perhaps it is better suited to be asked on math overflow.

Any help is welcome!

Improve this question
$\endgroup$
3
  • $\begingroup$ I am confused how $\mathcal{F}$ is bracketing compact. For $f,g \in mathcal{F}$, in order to have $f\leq g$ everywhere, we need both of them to be in the exactly same direction, and then the bracket $[f,g]$ covers only (some) subspaces in that direction. So finite number number of brackets covers only finite number of directions. What am I missing? $\endgroup$ Commented Sep 28, 2024 at 11:39
  • $\begingroup$ @JarosławBłasiok, given that $Q$ is a probability measure, we can simply take a compact $A\subset\mathbb{R}^d$ such that $Q(\mathbb{R}^d\setminus A)\leq\delta$ and then apply brackets. I am not sure precisely how these brackets will come to play, but I am fairly sure that the bracketing compactness of $\mathcal{F}$ under $Q$ remains valid. $\endgroup$ Commented Oct 1, 2024 at 13:18
  • $\begingroup$ I still don't understand how is $\mathcal{F}$ supposed to be bracketing-compact under $Q$, according to definitions in the OP. Let's even take it for granted that whenever $Q$ is compactly supported, and we change the partial order on $\mathcal{F}$ to $f\leq g$ iff $\Pr_{x \sim Q}(f(x) \leq g(x)) = 1$, then $\mathcal{F}$ is bracketing compact (also changing the notion of $[f,g]$ accordingly). I don't see how would that imply that $\mathcal{F}$ is bracketing compact with definitions from OP. Why would intersecting with a compact $A$ help? What to do with remaining $\delta$ mass? $\endgroup$ Commented Oct 1, 2024 at 14:48

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.