Proper loss function for this robust regression problem

Question

For classification problems, we may use cross entropy as our loss function, while for regression problems, we may choose mean square error.

However, here I'd like to find a proper loss function for my regression problem with many outliers. Since these outerliers may greatly affect mean square error, MSE is not proper for this problem.

I did some search and found the huber loss, but it seems outerliers still affect the final loss, though alleviated.

I'd like to find some loss function, with give target $\hat{y}$, and estimated $y$, the loss may be calculated like the follows

$$ Loss(y, \hat y) = \begin{cases} \frac{1}{\theta}|y-\hat y| & (|y-\hat y| \le \theta )\\ 1& (|y-\hat y| > \theta) \end{cases} $$

Here $\theta$ is a known parameter. For example we may plot the loss as follows (with $\theta = 0.6$).

expected loss function

And do the optimization like

$$ \min \sum_{i=1}^N Loss(f(x_i), \hat y_i) $$

Here $f$ may be some certain model, for example linear model or some more complex nonlinear models (like the nn etc)

However, when directly using this loss, there are several problems

1. First, it'not convex, but this may not be a big problem, since some local optimum (if is's close to the global optimum if possible) may still be ok.
2. Second, a large area of its gradient is zero, which means, it's easily to "get stuck", and cannot optimize any more.

So I'm looking for some approximate loss, which looks like the expected one I posted, but can be optimized easier.

Thank you for any suggestions.

Answer 1

While this is not officially an answer, I would like to point out that robust estimation in polynomial time is in general a very difficult problem. Indeed, even for the simplest task of estimating a Normal mean, its robust version requires very complicated techniques. See, for example, https://arxiv.org/pdf/1702.07709.pdf and there references therein.

I would also like to comment that if you want an absolutely outlier insensitive loss (e.g., $L(\theta,\hat\theta)\equiv C$ for all $\theta,\hat\theta$ that are far away), then such loss functions are destined to be highly non-convex. The high-level story is that you can't hope to achieve robust recovery by such simple methods of alternating loss functions: there's no free lunch here. You must delve into the particular structure of your question and derive alternative frameworks.