# What is an example of a hard learning problem in the noisily realizable setting?

Suppose $$f_{\vec{w}} : \mathbb{R}^n \rightarrow \mathbb{R}$$ is a function parameterized by some parameter vector $$\vec{w}$$. Now for some true parameters $$\vec{w}^*$$, some noise function $$\xi : \mathbb{R}^n \rightarrow \mathbb{R}$$ and some data distribution $${\cal D}$$ on $$\mathbb{R}^n$$ consider the following standard learning problem in the noisily realizable model (Is that a standard terminology?),

$$\min_{\vec{w}} \mathbb{E}_{\vec{x} \sim {\cal D}} \Bigg [ \Big (\xi(\vec{x}) + f_{\vec{w}^*}(\vec{x}) - f_{\vec{w}}(\vec{x}) \Big)^2 \Bigg ]$$

• Can someone kindly share any examples known of when a regression problem as above is provably hard to solve in some sense ? Particularly when we force some niceness conditions on $$\xi$$ like it has to be say bounded or so.

• If $$\xi$$ is entirely unrestricted and if we define success as the situation when an algorithm successfully finds $$\vec{w}^*$$ by solving the above then a tricky case is if one chooses $$\xi(\vec{x}) = f_{\vec{w}_1^*}(\vec{x}) - f_{\vec{w}^*}(\vec{x})$$ for some $$\vec{w}^* \neq\vec{w}_1^*$$. Now it seems that its impossible that any algorithm can succeed. If this intuition is true then what is the cleanest mathematical way to say this?

For the first point above one might want to think of $$\xi$$ as a random random variable whereby its mapping, $$\xi : \Omega \times \mathbb{R}^n \rightarrow \mathbb{R}$$ and then have the expectation be taken over the probability space $$\Omega$$ as well.