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

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)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.

$$\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.
• @SamratMukhopadhyay : Concerning non-convex sets, it was said, in somewhat other words, that small differences between $v$ and $Ev$ may lead to large differences between $\hat w$ and $w^*$. So, for general non-convex sets, you cannot get a concentration result. Commented Jun 24, 2022 at 18:05