2
$\begingroup$

We were told to assume in class that the below optimization formulations are equivalent-

$$\min_w\max_{\delta:||\delta||_F\leq\epsilon}||(X+\delta)w-y||_2^2$$

$$\min_{w}||Xw-y||_2^2+\lambda||w||_2^2 $$

for appropriately chosen $\lambda$.

$X,\delta\in R^{m\times n},~w\in R^{n\times1},~y\in R^{m\times1}$

$X$ is our data matrix, while $\delta$ is the noise in it which is constrained in an $\text{L}_2$ norm sense.

Note: $||\delta||_F$ is the Frobenius norm.

This essentially states that under the robust optimization framework, the most optimal way to handle noise in your data $X$, is to use Ridge Regression. The robust optimization framework works by first maximizing the cost function for noise, and then minimizing this worst case cost.

Can someone please explain the algebra behind this? A reference paper pointing it out would also work.

$\endgroup$
2
$\begingroup$

Here are some relevant links for you:

Reference paper: this article

Also some work by Shie Mannor (and others) should be relevant: Slides, Paper for LassoPaper for SVM

$\endgroup$
  • $\begingroup$ Thanks! The paper showcases that the Robust Optimization Framework yields Lasso instead of Ridge Regression. I guess my prof's slides were wrong. $\endgroup$ – Amrit Prasad Jul 24 '18 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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