Need help understanding how these assumptions imply? 
I am trying to understand the assumption proof of Theorem 3 in the paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke.

Theorem 3. Let $\mathcal{F}$ be a class of functions from $\mathbb{R}^{d} \rightarrow \mathbb{R}$ and let $\left(x_{i}, y_{i}\right)_{i=1}^{n}$ be i.i.d. input-output pairs in $\mathbb{R}^{d} \times[-1,1]$. Fix $\epsilon, \delta \in(0,1)$. Assume that:

*

*The function class can be written as $\mathcal{F}=\left\{f_{\boldsymbol{w}}, \boldsymbol{w} \in \mathcal{W}\right\}$ with $\mathcal{W} \subset \mathbb{R}^{p}$, $\operatorname{diam}(\mathcal{W}) \leq W$ and for any $\boldsymbol{w}_{1}, \boldsymbol{w}_{2} \in \mathcal{W}$,
$$
\left\|f_{\boldsymbol{w}_{1}}-f_{\boldsymbol{w}_{2}}\right\|_{\infty} \leq J\left\|\boldsymbol{w}_{1}-\boldsymbol{w}_{2}\right\|
$$

*The distribution $\mu$ of the covariates $x_{i}$ can be written as $\mu=\sum_{\ell=1}^{k} \alpha_{\ell} \mu_{\ell}$, where each $\mu_{\ell}$ satisfies c-isoperimetry, $\alpha_{\ell} \geq 0, \sum_{\ell=1}^{k} \alpha_{\ell}=1$, and $k$ is such that $9^{4} k \log (8 k / \delta) \leq n \epsilon^{2}$.

*The expected conditional variance of the output is strictly positive, denoted $\sigma^{2}:=\mathbb{E}^{\mu}[\operatorname{Var}[y \mid x]]>0$.


Then, with probability at least $1-\delta$ with respect to the sampling of the data, one has simultaneously for all $f \in \mathcal{F}$ :
$$
\frac{1}{n} \sum_{i=1}^{n}\left(f\left(x_{i}\right)-y_{i}\right)^{2} \leq \sigma^{2}-\epsilon \Rightarrow \operatorname{Lip}(f) \geq \frac{\epsilon}{2^{9} \sqrt{c}} \sqrt{\frac{n d}{p \log \left(60 W J \epsilon^{-1}\right)+\log (4 / \delta)}} .
$$
I want to clearly understand these 3 assumptions,

*

*typically they want to mean the max component of the absolute value of the subtraction is atleast J times $l2$ norm of the subtraction of those two $w$ vectors.

*Have not understood the intuition at all

*noise should be positive , but what does "expected conditional variance of the output" mean , I am unable to figure it out.

Can anyone explain it naively in a lucid manner why these assumptions they have taken and what is the significance of it?
 A: *

*Condition 1 tells you that the map $\boldsymbol w\mapsto f_{\boldsymbol w}$ is Lipschitz continuous. In other words, if two parameters $\boldsymbol w_1$ and $\boldsymbol w_2$ are close to each other, the associated functions $f_{\boldsymbol w_1}$ and $f_{\boldsymbol w_2 }$ are uniformly close to each other by the same amount, up to a multiplicative constant $J$.

*Condition 2 is essentially a more formal version of Condition 2 of Theorem 1 in the same paper. Basically the authors want the distribution $\mu$ to satisfy $c$-isoperimetry (Definition 1.1 in the paper), but instead of simply requiring $\mu$ to have that property, which might be too restrictive for certain applications, they require the more general condition that $\mu$ is a mixture of $k$ $c$-isoperimetric distributions (notice that if $k=1$, that is equivalent to requiring $\mu$ to be $c$-isoperimetric). The condition on the value of $k$ being not too large is purely technical and is there to ensure that the desired bounds will hold.

*The last condition says that the random variable $y\mid x$ is not constant at given $x$, or in other words that $y\mid x$ is "still random" for given $x$. Indeed, by non-negativity of the conditional variance, it is clear that
$$\mathbb{E}^{\mu}[\operatorname{Var}[y \mid x]]=0\iff\operatorname{Var}[y \mid x] = 0 \iff y\mid x = \text{cst}$$
Hence, when condition 3 holds, the random variable $y\mid x$ is not constant. This is a very common assumption in the regression setting and is commonly stated as
$$y\mid x = f(x) + \varepsilon $$
Where $f$ is some deterministic function and $\varepsilon$ a random variable which we commonly call "noise".

