scikit-learn / scikit-learn/scikit-learn
BUG unpenalized Ridge does not give minimum norm solution
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 67.3k
- Forks
- 27.4k
- Avg merge
- 1d 15h
- Merged PRs (30d)
- 58
Description
Describe the bug
As noted in #22910, Ridge(alpha=0, fit_intercept=True) does not give the minimal norm solution for wide data, i.e. n_features > n_samples.
Note that we nowhere guarantee that we provide the minimum norm solution.
Edit: Same seems to hold for LinearRegression, see #26164.
Probable Cause
For wide X, the least squares problem reads a bit different: $\mathrm{min} ||w||_2$ subject to $Xw = y$ with solution $w = X'(XX')^{-1} y$, see e.g. http://ee263.stanford.edu/lectures/min-norm.pdf.
With explicit intercept $w_0$, this reads $w = X'(XX' + 1 1')^{-1} y$, where 1 is a column vector of ones. $w_0 = 1'(XX' + 1 1')^{-1} y$.
This is incompatible with our mean centering approach.
Example
import numpy as np
from numpy.testing import assert_allclose
from scipy import linalg
from sklearn.datasets import make_low_rank_matrix
from sklearn.linear_model import Ridge
n_samples, n_features = 4, 12 # wide data
k = min(n_samples, n_features)
rng = np.random.RandomState(42)
X = make_low_rank_matrix(
n_samples=n_samples, n_features=n_features, effective_rank=k
)
X[:, -1] = 1 # last columns acts as intercept
U, s, Vt = linalg.svd(X)
assert np.all(s) > 1e-3 # to be sure X is not singular
U1, U2 = U[:, :k], U[:, k:]
Vt1, _ = Vt[:k, :], Vt[k:, :]
y = rng.uniform(low=-10, high=10, size=n_samples)
# w = X'(XX')^-1 y = V s^-1 U' y
coef_ols = Vt1.T @ np.diag(1 / s) @ U1.T @ y
model = Ridge(alpha=0, fit_intercept=True)
X = X[:, :-1] # remove intercept
intercept = coef_ols[-1]
coef = coef_ols[:-1]
model.fit(X, y)
# Check that we have found a solution => residuals = 0
assert_allclose(model.predict(X), y)
# Check that `coef`, `intercept` also provide a valid solution
assert_allclose(X @ coef + intercept, y)
# Ridge does not give the minimum norm solution. (This should be equal.)
np.linalg.norm(np.r_[model.intercept_, model.coef_]) > np.linalg.norm(
np.r_[intercept, coef]
)
This last statement should be be False. It proves that Ridge does not give the miminum norm solution.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reproducing the provided wide-data example with Ridge(alpha=0, fit_intercept=True), then inspect the Ridge fitting path for how centering and the unpenalized case are handled. Compare the resulting coefficients and intercept with the minimum-norm solution described in the issue; done means the behavior is resolved or its intended limitation is clearly established, with LinearRegression considered as noted in #26164.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- numpy, python
- Domain
- machine-learning
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100