Least Square vs Shrinkage approach of fitting models What is the difference between the Least Square and Shrinkage approach of fitting models in the context of model selection?
In https://www.youtube.com/watch?v=QlyROnAjnEk the author at [0:28] instance of the video says - "Subset selection uses least-squares fit and shrinkage methods as Lasso uses shrinkage approach to fit the model". What is the difference?
 A: Assume you have $y\in \mathbf{R^n}$ and $X\in \mathbf{R^{n\times p}}$, $n>p$. The best subset selection solves the following minimization problem
$\qquad \qquad \qquad \min_{\beta \in \mathbf{R^p}} \|y-X\beta\|^2_n  \quad \text{subject to} \quad\|\beta\|_0 \leq k\qquad (1)$
where $\|u\|^2_n = \langle u,u \rangle $/n   and  $\|\beta\|_0$ counts the total number of non-zero coefficients. You solve it by running all possible regressions with all combinations of different covariates (in total $2^p$) and rank solutions using some criterion (e.g. Akaike information criterion, AIC, or bayesian information criterion, BIC). Unfortunately, when $p>n$, the problem is non-convex and it is very difficult to solve it - or at least to solve exactly - in polynomial time. Put differently, it will take ages to compute all possible solutions.
LASSO is a convex relaxation of non-convex best subset selection problem in eq. (1) and is heavily used in many high-dimensional applications. It solves (in Lagrangian form)
$\qquad \qquad \qquad \qquad \qquad \min_{\beta \in \mathbf{R^p}} \|y-X\beta\|^2_n + \lambda\|\beta\|_1 \qquad (2)$
where $\lambda>0$ is a penalty term that regulates the strength of the shrinkage, and $\|.\|_1$ is the $\ell_1$ norm. It turns out that for large enough $\lambda$ we get sparse solutions to the problem, i.e. some $\beta$ entries are zero and therefore we perform variable selection. Note that since (2) is convex we can solve it and there are very fast ways to do it. (1) and (2) are different problems, although in practice they work similarly (depends on your data). You may check Tibshirani, Friedman, Hastie and others books, e.g. Elements of Statistical Learning, for more discussions and examples.
Some references of the main papers:
LASSO (also mention differences between (1) and (2):
Tibshirani, R. (2011). Regression shrinkage and selection via the lasso: a retrospective. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 73(3), 273-282.
Fast algorithm for LASSO:
Friedman, J., Hastie, T., Höfling, H., & Tibshirani, R. (2007). Pathwise coordinate optimization. Annals of Applied Statistics, 1(2), 302-332.
Comparison between (1) and (2):
Hastie, T., Tibshirani, R., & Tibshirani, R. J. (2017). Extended comparisons of best subset selection, forward stepwise selection, and the lasso. arXiv preprint arXiv:1707.08692.
