On the relation between solution of random least squares and expected least squares with constraints

Question

Let $v\in \mathbb{R}^d$ be a random vector such that $\mathbb{E}v = y$, and $X$ be a given $\mathbb{R}^{d\times d}$ real fixed matrix. We assume that the following optimization problem has a unique solution $w^\star$: $$\min_{w\in \mathcal{C}}f(w):=\sum_{i=1}^d |y_i-(Xw)_i|^2$$ where $\mathcal{C}$ might be a convex or a nonconvex subset of $\mathbb{R}^d$.

Now, let us consider $\hat{w}$ be the (probably unique) solution to the following optimization problem: $$\min_{w\in \mathcal{C}}\hat{f}(w)=\sum_{i=1}^d |v_i-(Xw)_i|^2.$$ Clearly, if $\mathcal{C}=\mathbb{R}^d$, and $X$ is invertible, we have $\mathbb{E}\hat{w}=w^\star$. However,

What happens when $\mathcal{C}$ is a proper subset of $\mathbb{R}^d$? Specifically, is there any concentration result available of the following form? $$\mathbb{P}\bigg(\left\|\hat{w}-w^\star\right\|>t\bigg)<?,\ t>0.$$

The question really is how does the set $\mathcal{C}$ affects the solution $\hat{w}$. Any pointers to the literature is much appreciated. Thanks in advance.

Answer 1

$\newcommand\C{\mathcal C}$If $\C$ is convex, then the projection onto the convex set $X\C$ is uniquely defined and, moreover, $1$-Lipschitz, so that $\|X\hat w-Xw^\ast\|\le\|v-Ev\|$ and hence $\|\hat w-w^\ast\|\le\|X^{-1}\|\|v-Ev\|$. So, for instance, $$P(\|\hat w-w^\ast\|\ge t)\le\|X^{-1}\|^2\frac{E\|v-Ev\|^2}{t^2}$$ for real $t>0$.

If $\C$ is not convex, then the projection onto the convex set $X\C$ is in general not uniquely defined and is discontinuous, so that in that case no concentration result is possible.