Penalised/regularised regression

June 23, 2016 — September 19, 2022

functional analysis
linear algebra
model selection
signal processing
sparser than thou

Regression estimation with penalties on the model parameters. I am especially interested when the penalties are sparsifying penalties, and I have more notes to sparse regression.

Here I consider general penalties: ridge etc. At least in principle — I have no active projects using penalties without sparsifying them at the moment.

Why might I use such penalties? One reason would be that \(L_2\) penalties have simple forms for their information criteria, as shown by Konishi and Kitagawa (Konishi and Kitagawa 2008, 5.2.4).

See also matrix factorisations, optimisation, multiple testing, concentration inequalities, sparse flavoured icecream.

To discuss:

Ridge penalties, relationship with robust regression, statistical learning theory etc.

In nonparametric statistics we might estimate simultaneously what look like many, many parameters, which we constrain in some clever fashion, which usually boils down to something we can interpret as a “penalty” on the parameters.

“Penalization” has a genealogy unknown to me, but is probably the least abstruse for common, general usage.

The “regularisation” nomenclature claims descent from Tikhonov, (e.g. Tikhonov and Glasko (1965)) who wanted to solve ill-conditioned integral and differential equations, which is slightly more general.

In statistics, the term “shrinkage” is used for very nearly the same thing.

“Smoothing” seems to be common in the spline and kernel estimate communities of (Silverman 1982, 1984; Wahba 1990) et al, who usually actually want to smooth curves. When we say “smoothing” you usually mean that you can express your predictions as a “linear smoother”/hat matrix, which has certain nice properties in generalised cross validation.

“Smoothing” is not a great general term, since penalisation does not necessarily cause “smoothness” from any particular perspective — for example, some penalties cause the coefficients to become sparse and therefore, from the perspective of coefficients, it promotes non-smooth vectors. Often the thing that becomes smooth is not obvious.

Regardless, what these problems share in common is that we wish to solve an ill-conditioned inverse problem, so we tame it by adding a penalty to solutions we feel one should be reluctant to accept.

🏗 specifics

1 Connection to Bayesian priors

Famously, a penalty can have an interpretation as a Bayesian prior on the solution space. It is a fun exercise for example to “rediscover” the lasso regression as a typical linear regression but with the plus prize for the coefficients. In that case the maximum a posteriori estimate given those bays rise and the lasso solution coincide. If you want to know the full posterior you have to do a lot more work. But the connection is suggestive nonetheless.

A related and useful connection the interpretation of covariance kernels as prize producing smoothness in solutions. A very elegant introduction to these is given in Miller, Glennie, and Seaton (2020).

2 As shrinkage

TBD. James and Stein (1961). beautiful explainer video.

3 Adaptive regularization

What should we regularize to attain specific kinds of solutions?

Here’s one thing I saw recently:

Venkat Chandrasekaran, Learning Semidefinite Regularizers via Matrix Factorization

Abstract: Regularization techniques are widely employed in the solution of inverse problems in data analysis and scientific computing due to their effectiveness in addressing difficulties due to ill-posedness. In their most common manifestation, these methods take the form of penalty functions added to the objective in optimization-based approaches for solving inverse problems. The purpose of the penalty function is to induce a desired structure in the solution, and these functions are specified based on prior domain-specific expertise. We consider the problem of learning suitable regularization functions from data in settings in which prior domain knowledge is not directly available. Previous work under the title of ‘dictionary learning’ or ‘sparse coding’ may be viewed as learning a polyhedral regularizer from data. We describe generalizations of these methods to learn semidefinite regularizers by computing structured factorizations of data matrices. Our algorithmic approach for computing these factorizations combines recent techniques for rank minimization problems along with operator analogs of Sinkhorn scaling. The regularizers obtained using our framework can be employed effectively in semidefinite programming relaxations for solving inverse problems. (Joint work with Yong Sheng Soh)

4 References

Akaike, Hirotogu. 1973. Information Theory and an Extension of the Maximum Likelihood Principle.” In Proceeding of the Second International Symposium on Information Theory, edited by Petrovand F Caski, 199–213. Budapest: Akademiai Kiado.
Akaike, Htrotugu. 1973. Maximum Likelihood Identification of Gaussian Autoregressive Moving Average Models.” Biometrika 60 (2): 255–65.
Azizyan, Martin, Akshay Krishnamurthy, and Aarti Singh. 2015. Extreme Compressive Sampling for Covariance Estimation.” arXiv:1506.00898 [Cs, Math, Stat], June.
Bach, Francis. 2009. Model-Consistent Sparse Estimation Through the Bootstrap.” arXiv:0901.3202 [Cs, Stat].
Banerjee, Arindam, Sheng Chen, Farideh Fazayeli, and Vidyashankar Sivakumar. 2014. Estimation with Norm Regularization.” In Advances in Neural Information Processing Systems 27, edited by Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, 1556–64. Curran Associates, Inc.
Barron, Andrew R., Cong Huang, Jonathan Q. Li, and Xi Luo. 2008. MDL, Penalized Likelihood, and Statistical Risk.” In Information Theory Workshop, 2008. ITW’08. IEEE, 247–57. IEEE.
Battiti, Roberto. 1992. First-and Second-Order Methods for Learning: Between Steepest Descent and Newton’s Method.” Neural Computation 4 (2): 141–66.
Bellec, Pierre C., and Alexandre B. Tsybakov. 2016. Bounds on the Prediction Error of Penalized Least Squares Estimators with Convex Penalty.” arXiv:1609.06675 [Math, Stat], September.
Bickel, Peter J., Bo Li, Alexandre B. Tsybakov, Sara A. van de Geer, Bin Yu, Teófilo Valdés, Carlos Rivero, Jianqing Fan, and Aad van der Vaart. 2006. Regularization in Statistics.” Test 15 (2): 271–344.
Brown, Lawrence D., and Yi Lin. 2004. Statistical Properties of the Method of Regularization with Periodic Gaussian Reproducing Kernel.” The Annals of Statistics 32 (4): 1723–43.
Bühlmann, Peter, and Sara van de Geer. 2011. Additive Models and Many Smooth Univariate Functions.” In Statistics for High-Dimensional Data, 77–97. Springer Series in Statistics. Springer Berlin Heidelberg.
———. 2015. High-Dimensional Inference in Misspecified Linear Models.” arXiv:1503.06426 [Stat] 9 (1): 1449–73.
Burman, P., and D. Nolan. 1995. A General Akaike-Type Criterion for Model Selection in Robust Regression.” Biometrika 82 (4): 877–86.
Candès, Emmanuel J., and Carlos Fernandez-Granda. 2013. Super-Resolution from Noisy Data.” Journal of Fourier Analysis and Applications 19 (6): 1229–54.
Candès, Emmanuel J., and Y. Plan. 2010. Matrix Completion With Noise.” Proceedings of the IEEE 98 (6): 925–36.
Cavanaugh, Joseph E. 1997. Unifying the Derivations for the Akaike and Corrected Akaike Information Criteria.” Statistics & Probability Letters 33 (2): 201–8.
Chen, Yen-Chi, and Yu-Xiang Wang. n.d. Discussion on ‘Confidence Intervals and Hypothesis Testing for High-Dimensional Regression’.”
Chernozhukov, Victor, Christian Hansen, and Martin Spindler. 2015. Valid Post-Selection and Post-Regularization Inference: An Elementary, General Approach.” Annual Review of Economics 7 (1): 649–88.
Efron, Bradley. 2004. The Estimation of Prediction Error.” Journal of the American Statistical Association 99 (467): 619–32.
Efron, Bradley, Trevor Hastie, Iain Johnstone, and Robert Tibshirani. 2004. Least Angle Regression.” The Annals of Statistics 32 (2): 407–99.
Flynn, Cheryl J., Clifford M. Hurvich, and Jeffrey S. Simonoff. 2013. Efficiency for Regularization Parameter Selection in Penalized Likelihood Estimation of Misspecified Models.” arXiv:1302.2068 [Stat], February.
Friedman, Jerome, Trevor Hastie, and Rob Tibshirani. 2010. Regularization Paths for Generalized Linear Models via Coordinate Descent.” Journal of Statistical Software 33 (1): 1–22.
Fuglstad, Geir-Arne, Daniel Simpson, Finn Lindgren, and Håvard Rue. 2019. Constructing Priors That Penalize the Complexity of Gaussian Random Fields.” Journal of the American Statistical Association 114 (525): 445–52.
Geer, Sara van de. 2014a. Weakly Decomposable Regularization Penalties and Structured Sparsity.” Scandinavian Journal of Statistics 41 (1): 72–86.
———. 2014b. Statistical Theory for High-Dimensional Models.” arXiv:1409.8557 [Math, Stat], September.
Giryes, Raja, Guillermo Sapiro, and Alex M. Bronstein. 2014. On the Stability of Deep Networks.” arXiv:1412.5896 [Cs, Math, Stat], December.
Golub, Gene H., Michael Heath, and Grace Wahba. 1979. Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter.” Technometrics 21 (2): 215–23.
Golubev, Grigori K., and Michael Nussbaum. 1990. A Risk Bound in Sobolev Class Regression.” The Annals of Statistics 18 (2): 758–78.
Green, P. J. 1990. Bayesian Reconstructions from Emission Tomography Data Using a Modified EM Algorithm.” IEEE Transactions on Medical Imaging 9 (1): 84–93.
Green, Peter J. 1990. On Use of the EM for Penalized Likelihood Estimation.” Journal of the Royal Statistical Society. Series B (Methodological) 52 (3): 443–52.
Gu, Chong. 1993. Smoothing Spline Density Estimation: A Dimensionless Automatic Algorithm.” Journal of the American Statistical Association 88 (422): 495–504.
Gui, Jiang, and Hongzhe Li. 2005. Penalized Cox Regression Analysis in the High-Dimensional and Low-Sample Size Settings, with Applications to Microarray Gene Expression Data.” Bioinformatics 21 (13): 3001–8.
Hastie, Trevor J., and Robert J. Tibshirani. 1990. Generalized Additive Models. Vol. 43. CRC Press.
Hastie, Trevor J., Tibshirani, Rob, and Martin J. Wainwright. 2015. Statistical Learning with Sparsity: The Lasso and Generalizations. Boca Raton: Chapman and Hall/CRC.
Hawe, S., M. Kleinsteuber, and K. Diepold. 2013. Analysis Operator Learning and Its Application to Image Reconstruction.” IEEE Transactions on Image Processing 22 (6): 2138–50.
Hegde, Chinmay, Piotr Indyk, and Ludwig Schmidt. 2015. A Nearly-Linear Time Framework for Graph-Structured Sparsity.” In Proceedings of the 32nd International Conference on Machine Learning (ICML-15), 928–37.
Hoerl, Arthur E., and Robert W. Kennard. 1970. Ridge Regression: Biased Estimation for Nonorthogonal Problems.” Technometrics 12 (1): 55–67.
Huang, Jianhua Z., Naiping Liu, Mohsen Pourahmadi, and Linxu Liu. 2006. Covariance Matrix Selection and Estimation via Penalised Normal Likelihood.” Biometrika 93 (1): 85–98.
James, William, and Charles Stein. 1961. Estimation with Quadratic Loss.” In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1:361–79. University of California Press.
Janson, Lucas, William Fithian, and Trevor J. Hastie. 2015. Effective Degrees of Freedom: A Flawed Metaphor.” Biometrika 102 (2): 479–85.
Javanmard, Adel, and Andrea Montanari. 2014. Confidence Intervals and Hypothesis Testing for High-Dimensional Regression.” Journal of Machine Learning Research 15 (1): 2869–909.
Kaufman, S., and S. Rosset. 2014. When Does More Regularization Imply Fewer Degrees of Freedom? Sufficient Conditions and Counterexamples.” Biometrika 101 (4): 771–84.
Kloft, Marius, Ulrich Rückert, and Peter L. Bartlett. 2010. A Unifying View of Multiple Kernel Learning.” In Machine Learning and Knowledge Discovery in Databases, edited by José Luis Balcázar, Francesco Bonchi, Aristides Gionis, and Michèle Sebag, 66–81. Lecture Notes in Computer Science. Springer Berlin Heidelberg.
Koenker, Roger, and Ivan Mizera. 2006. Density Estimation by Total Variation Regularization.” Advances in Statistical Modeling and Inference, 613–34.
Konishi, Sadanori, and G. Kitagawa. 2008. Information Criteria and Statistical Modeling. Springer Series in Statistics. New York: Springer.
Konishi, Sadanori, and Genshiro Kitagawa. 1996. Generalised Information Criteria in Model Selection.” Biometrika 83 (4): 875–90.
Lange, K. 1990. Convergence of EM image reconstruction algorithms with Gibbs smoothing.” IEEE transactions on medical imaging 9 (4): 439–46.
Liu, Han, Kathryn Roeder, and Larry Wasserman. 2010. Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models.” In Advances in Neural Information Processing Systems 23, edited by J. D. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta, 1432–40. Curran Associates, Inc.
Meinshausen, Nicolai, and Peter Bühlmann. 2010. Stability Selection.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 72 (4): 417–73.
Meyer, Mary C. 2008. Inference Using Shape-Restricted Regression Splines.” The Annals of Applied Statistics 2 (3): 1013–33.
Miller, David L., Richard Glennie, and Andrew E. Seaton. 2020. Understanding the Stochastic Partial Differential Equation Approach to Smoothing.” Journal of Agricultural, Biological and Environmental Statistics 25 (1): 1–16.
Montanari, Andrea. 2012. Graphical Models Concepts in Compressed Sensing.” Compressed Sensing: Theory and Applications, 394–438.
Needell, D., and J. A. Tropp. 2008. CoSaMP: Iterative Signal Recovery from Incomplete and Inaccurate Samples.” arXiv:0803.2392 [Cs, Math], March.
Rahimi, Ali, and Benjamin Recht. 2009. Weighted Sums of Random Kitchen Sinks: Replacing Minimization with Randomization in Learning.” In Advances in Neural Information Processing Systems, 1313–20. Curran Associates, Inc.
Rezende, Danilo Jimenez, Shakir Mohamed, and Daan Wierstra. 2015. Stochastic Backpropagation and Approximate Inference in Deep Generative Models.” In Proceedings of ICML.
Rigollet, Philippe, and Jonathan Weed. 2018. Entropic Optimal Transport Is Maximum-Likelihood Deconvolution.” arXiv.
Shen, Xiaotong, and Hsin-Cheng Huang. 2006. Optimal Model Assessment, Selection, and Combination.” Journal of the American Statistical Association 101 (474): 554–68.
Shen, Xiaotong, Hsin-Cheng Huang, and Jimmy Ye. 2004. Adaptive Model Selection and Assessment for Exponential Family Distributions.” Technometrics 46 (3): 306–17.
Shen, Xiaotong, and Jianming Ye. 2002. Adaptive Model Selection.” Journal of the American Statistical Association 97 (457): 210–21.
Silverman, B. W. 1982. On the Estimation of a Probability Density Function by the Maximum Penalized Likelihood Method.” The Annals of Statistics 10 (3): 795–810.
———. 1984. Spline Smoothing: The Equivalent Variable Kernel Method.” The Annals of Statistics 12 (3): 898–916.
Simon, Noah, Jerome Friedman, Trevor Hastie, and Rob Tibshirani. 2011. Regularization Paths for Cox’s Proportional Hazards Model via Coordinate Descent.” Journal of Statistical Software 39 (5).
Smola, Alex J., Bernhard Schölkopf, and Klaus-Robert Müller. 1998. The Connection Between Regularization Operators and Support Vector Kernels.” Neural Networks 11 (4): 637–49.
Somekh-Baruch, Anelia, Amir Leshem, and Venkatesh Saligrama. 2016. On the Non-Existence of Unbiased Estimators in Constrained Estimation Problems.” arXiv:1609.07415 [Cs, Math, Stat], September.
Stein, Charles M. 1981. Estimation of the Mean of a Multivariate Normal Distribution.” The Annals of Statistics 9 (6): 1135–51.
Tansey, Wesley, Oluwasanmi Koyejo, Russell A. Poldrack, and James G. Scott. 2014. False Discovery Rate Smoothing.” arXiv:1411.6144 [Stat], November.
Tikhonov, A. N., and V. B. Glasko. 1965. Use of the Regularization Method in Non-Linear Problems.” USSR Computational Mathematics and Mathematical Physics 5 (3): 93–107.
Uematsu, Yoshimasa. 2015. Penalized Likelihood Estimation in High-Dimensional Time Series Models and Its Application.” arXiv:1504.06706 [Math, Stat], April.
Wahba, Grace. 1990. Spline Models for Observational Data. SIAM.
Weng, Haolei, Arian Maleki, and Le Zheng. 2018. Overcoming the Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques.” The Annals of Statistics 46 (6A): 3099–129.
Wood, S. N. 2000. Modelling and Smoothing Parameter Estimation with Multiple Quadratic Penalties.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 62 (2): 413–28.
Wood, Simon N. 2008. Fast Stable Direct Fitting and Smoothness Selection for Generalized Additive Models.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 70 (3): 495–518.
Wu, Tong Tong, and Kenneth Lange. 2008. Coordinate Descent Algorithms for Lasso Penalized Regression.” The Annals of Applied Statistics 2 (1): 224–44.
Xie, Bo, Yingyu Liang, and Le Song. 2016. Diversity Leads to Generalization in Neural Networks.” arXiv:1611.03131 [Cs, Stat], November.
Ye, Jianming. 1998. On Measuring and Correcting the Effects of Data Mining and Model Selection.” Journal of the American Statistical Association 93 (441): 120–31.
Zhang, Cun-Hui, and Stephanie S. Zhang. 2014. Confidence Intervals for Low Dimensional Parameters in High Dimensional Linear Models.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 76 (1): 217–42.
Zhang, Yiyun, Runze Li, and Chih-Ling Tsai. 2010. Regularization Parameter Selections via Generalized Information Criterion.” Journal of the American Statistical Association 105 (489): 312–23.
Zou, Hui, and Trevor Hastie. 2005. Regularization and Variable Selection via the Elastic Net.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 67 (2): 301–20.
Zou, Hui, Trevor Hastie, and Robert Tibshirani. 2007. On the ‘Degrees of Freedom’ of the Lasso.” The Annals of Statistics 35 (5): 2173–92.