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.


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

  • $\begingroup$ The projection approach is quite interesting! Although it does not fully answer my question, this is really helpful! Thanks a lot! $\endgroup$ Commented Jun 24, 2022 at 15:38
  • $\begingroup$ @SamratMukhopadhyay : Why does it not answer your question? Your least-squares solutions are exactly what is usually called the projections -- as in the linked previous answer at math.stackexchange.com/questions/3272169/… $\endgroup$ Commented Jun 24, 2022 at 16:46
  • $\begingroup$ what I meant to say is that I think this does not answer fully the question for non-convex sets. For convex sets, this is indeed very interesting and that's why I thank you. $\endgroup$ Commented Jun 24, 2022 at 17:51
  • $\begingroup$ @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. $\endgroup$ Commented Jun 24, 2022 at 18:05
  • $\begingroup$ Thanks for your comment. $\endgroup$ Commented Jun 24, 2022 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.