# Linear Regression - Data Subset with Lowest Mean-Squared Error?

Short version: given a linear regression dataset and an integer $$K$$, what data subset of size $$K$$ results in linear parameters with the lowest mean squared error on the entire dataset?

Long version: Suppose I have a supervised dataset $$D_n := \{x_n, y_n\}_{n=1}^N$$ and I want to perform ordinary linear regression by minimizing

$$L_{OLS, N}(w) = ||Y_N - X_N w||_2^2$$

where $$Y_N$$ is the matrix formed by stacking $$y_n$$ as row vectors and $$X_N$$ is the matrix formed by stacking $$x_n$$ as row vectors. I use the subscript $$N$$ to remind us that we used all the data to compute the parameter estimates. Alternatively, I might want to perform ridge linear regression by minimizing

$$L_{Ridge, N}(w) = ||Y_N - X_N w||_2^2 + c ||w||_2^2$$

We know that the parameters that minimize the above losses are given by

$$w_{OLS, N} = (X_N^T X_N)^{-1} X_N^T Y_N$$

$$w_{Ridge, N} = (X_N^T X_N + c I)^{-1} X_N^T Y_N$$

What I'm curious to know is: if we're forced to choose a subset of only $$K < N$$ data $$D_K := \{(x_k, y_k)\}_{k=1}^K \subset D_N$$ and we fit parameters

$$w_{OLS, K} = (X_K^T X_K)^{-1} X_K^T Y_K$$

$$w_{Ridge, K} = (X_K^T X_K + c I)^{-1} X_K^T Y_K$$

what subset of $$K$$ data results in parameters $$w_{OLS, K}$$ and $$w_{Ridge, K}$$ such that $$L_{OLS, N}(w)$$ and $$L_{Ridge, N}(w)$$ (respectively) are minimized?

the squared error of the full data set are: $$SSE=\varepsilon'\varepsilon$$where $$\varepsilon=Y-X\hat\beta_K$$ and $$\hat\beta_K=(X_K'X_K)^{-1}X'_KY_K$$
You want to minimize SSE wrt a subset K. Unfortunately the only way to do it is through trying all combinations of K-subsets. It's $$\frac{N!}{K!(N-K)!}$$, which is a lot of work to say the least.
• One place to watch out when you try this is if two observations have the same $x$-values but different $y$-values.
• No, not true. You'll get zero errors on those $K$ points, but I want to know about the errors on the full dataset. Nov 18, 2021 at 21:38