Why is linear regression not a stable algorithm? In the paper Stability and Generalization the author defines the stability of a learning algorithm, which intuitively means that changing one sample in the sample set does not affect the outcome much.
In page 18 the author discusses the stability bound for Regularized Least Squares Regression . When $\lambda \to 0$,however, the bound is uninformative. Since the case $\lambda = 0$ corresponds to linear regression, this result suggests that the linear regression algorithm is not stable.
This result seems easy to prove. However, does this mean that we cannot derive a generalization stability bound for linear regression(similar to that in P18, example3)?
Note.Here I’m refer to the definition of uniform stability, you can find the definition on p504, def6 in the paper. A self-contained definition:we say an algorithm $A$ is uniformly $\beta$-stable if there exist a constant $\beta$ such that if $S$ and $S’$ are two samples that differ at exactly one point, then for any possible example $z=(x,y)$,$|L(h_S(x),y)-L(h_{S’}(x),y)|\leq \beta$,here $h_S$ denotes the output of algorithm $A$ when receiving sample $S$ and $L$ some loss function used to measure the closeness of the predicted label and the true label.
Note also that I’m not asking whether such $\beta$ exists for linear regression, but whether it is possible for us to obtain a generalization bound for it.In the paper such bounds are given for some regularized regression using the stability concept.
 A: Linear regression is a general term to describe a linear model that predicting continuous response variable. Depending on the loss function and regularization, the model can be sensitive or not sensitive to outliers.
L2 loss is more sensitive to outliers and L1 is less sensitive. Other than L2 or L1 loss there are also other loss functions can be used.
There are metrics and diagnostics in regression analysis to check the impact for outliers for input data. Such as Cook's distance.
Finally, the author definition of "Stability" is not commonly used (at least I am not familiar with). When I first read the question title I was thinking about Numerical Stability.
A: If you mean by linear regression, the solution to $\frac{1}{n} \sum_{i=1}^n (y_i-w^\top x_i)^2$ then note that in general there might be multiple solutions, so solution to this problem is not well-defined. A special case (where the solution is well-defined) is when you assume that for all datasets and size $n$, $\sum_{i=1}^n x_ix^T \succ \lambda_0 I$. In this case, you can use the uniform stability bound with $\lambda=\lambda_0$ and get a generalization bound.
When this condition is not met, then one algorithm is: regularize and solve the regularized problem (note that its solution is necessarily unique, so it is well-defined). Herein, we pay a cost of $\lambda$ in error (in the unregularized objective) due to regularization (check). We can convert it into a generalization bound using the unform stability bound of $\frac{1}{\lambda n}$ yeilding a bound of $O\left(\frac{1}{\sqrt{n}}\right)$, which is optimal in general.
Another method is to do one pass stochastic gradient descent (SGD) on the "unregularized" objective. It can be shown (with or without uniform stability based analysis) that its generalization bound is $O\left(\frac{1}{\sqrt{n}}\right)$
