Which norm is best for regression?
Recently I was introducing least squares regression to my students. This came up in the context of surrogate modeling for optimization. Given a set of data points \(\{(\alpha_i, y_i)\}_{i=1}^N\), which are generated using the true function \(y(\alpha)\), we want to find a surrogate function \(\hat{y}(\alpha)\) that can approximate the true function well.
They agreed that the only way to measure how close \(\hat{y}(\alpha)\) is to \(y(\alpha)\) is to use some kind of norm. So the question is, which norm should we use?
Most common options are:
- \(L^1\) norm: \(\|y - \hat{y}\|_1 = \sum_{i=1}^N |y_i - \hat{y}_i|\)
- \(L^2\) norm: \(\|y - \hat{y}\|_2 = \sqrt{\sum_{i=1}^N (y_i - \hat{y}_i)^2}\)
- \(L^\infty\) norm: \(\|y - \hat{y}\|_\infty = \max_{1 \leq i \leq N} |y_i - \hat{y}_i|\)
I gave the obvious answer that \(L^2\) norm is the most commonly used as the resulting optimisation problem is smooth and easier to solve. In fact, if we are attempting linear regression, then the resulting optimisation problem is convex and has a closed form solution.
Least squares regression appears prominently in statistics, control, system identification, machine learning, orbit determination, and Kalman filtering. These are only the areas of my interest. There must be many more.
\(L_1\) and \(L_\infty\) norms on the other hand, lead to non-smooth optimisation problems. However, \(L_1\) norm is more robust to outliers. So if we have a lot of outliers in our data, then \(L_1\) norm might be a better choice. \(L_\infty\) norm is useful when we want to minimize the maximum error. This is often the case in engineering applications where we want to ensure that the worst case error is below a certain threshold.
Still the basic question remains, that apart from computational convenience, is there any other reason to prefer \(L^2\) norm over \(L^1\) or \(L^\infty\) norms?