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 penalties have simple forms for their information criteria, as shown by Konishi and Kitagawa (KoKi08 5.2.4).

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

To discuss:

Ridge penalties, relationship with robust regression 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, (eg TiGl65 etc) who wanted to solve ill-conditioned integral and differential equations, so it's somewhat more general. “Smoothing” seems to be common in the spline and kernel estimate communities of Wahba (Wahb90) and Silverman (Silv82) et al, who usually actually want to smooth curves. When you 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” – for example, some penalties cause the coefficients to become sparse and therefore, from the perspective of coefficients, it promotes non-smooth vectors.

In every case, you wish to solve an ill-conditioned inverse problem, so you tame it by adding a penalty to solutions you feel one should be reluctant to accept.

TODO: specifics

## 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)

## Refs

- BuNo95: P. Burman, D. Nolan (1995) A general Akaike-type criterion for model selection in robust regression.
*Biometrika*, 82(4), 877–886. DOI - HeIS15: Chinmay Hegde, Piotr Indyk, Ludwig Schmidt (2015) A nearly-linear time framework for graph-structured sparsity. In Proceedings of the 32nd International Conference on Machine Learning (ICML-15) (pp. 928–937).
- GoNu90: Grigori K. Golubev, Michael Nussbaum (1990) A Risk Bound in Sobolev Class Regression.
*The Annals of Statistics*, 18(2), 758–778. DOI - KlRB10: Marius Kloft, Ulrich Rückert, Peter L. Bartlett (2010) A Unifying View of Multiple Kernel Learning. In Machine Learning and Knowledge Discovery in Databases (pp. 66–81). Springer Berlin Heidelberg DOI
- ShYe02: Xiaotong Shen, Jianming Ye (2002) Adaptive Model Selection.
*Journal of the American Statistical Association*, 97(457), 210–221. DOI - ShHY04: Xiaotong Shen, Hsin-Cheng Huang, Jimmy Ye (2004) Adaptive Model Selection and Assessment for Exponential Family Distributions.
*Technometrics*, 46(3), 306–317. DOI - BüGe11: Peter Bühlmann, Sara van de Geer (2011) Additive models and many smooth univariate functions. In Statistics for High-Dimensional Data (pp. 77–97). Springer Berlin Heidelberg DOI
- HaKD13: S. Hawe, M. Kleinsteuber, K. Diepold (2013) Analysis operator learning and its application to image reconstruction.
*IEEE Transactions on Image Processing*, 22(6), 2138–2150. DOI - Gree90: P. J. Green (1990) Bayesian reconstructions from emission tomography data using a modified EM algorithm.
*IEEE Transactions on Medical Imaging*, 9(1), 84–93. DOI - BeTs16: Pierre C. Bellec, Alexandre B. Tsybakov (2016) Bounds on the prediction error of penalized least squares estimators with convex penalty.
*ArXiv:1609.06675 [Math, Stat]*. - JaMo14: Adel Javanmard, Andrea Montanari (2014) Confidence Intervals and Hypothesis Testing for High-dimensional Regression.
*Journal of Machine Learning Research*, 15(1), 2869–2909. - ZhZh14: Cun-Hui Zhang, 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–242. DOI - Lang90: K. Lange (1990) Convergence of EM image reconstruction algorithms with Gibbs smoothing.
*IEEE Transactions on Medical Imaging*, 9(4), 439–446. DOI - WuLa08: Tong Tong Wu, Kenneth Lange (2008) Coordinate descent algorithms for lasso penalized regression.
*The Annals of Applied Statistics*, 2(1), 224–244. DOI - NeTr08: D. Needell, J. A. Tropp (2008) CoSaMP: Iterative signal recovery from incomplete and inaccurate samples.
*ArXiv:0803.2392 [Cs, Math]*. - HLPL06: Jianhua Z. Huang, Naiping Liu, Mohsen Pourahmadi, Linxu Liu (2006) Covariance matrix selection and estimation via penalised normal likelihood.
*Biometrika*, 93(1), 85–98. DOI - KoMi06: Roger Koenker, Ivan Mizera (2006) Density estimation by total variation regularization.
*Advances in Statistical Modeling and Inference*, 613–634. - ChWa00: Yen-Chi Chen, Yu-Xiang Wang (n.d.) Discussion on ‘Confidence Intervals and Hypothesis Testing for High-Dimensional Regression.’
- XiLS16: Bo Xie, Yingyu Liang, Le Song (2016) Diversity Leads to Generalization in Neural Networks.
*ArXiv:1611.03131 [Cs, Stat]*. - JaFH15: Lucas Janson, William Fithian, Trevor J. Hastie (2015) Effective degrees of freedom: a flawed metaphor.
*Biometrika*, 102(2), 479–485. DOI - FlHS13: Cheryl J. Flynn, Clifford M. Hurvich, Jeffrey S. Simonoff (2013) Efficiency for Regularization Parameter Selection in Penalized Likelihood Estimation of Misspecified Models.
*ArXiv:1302.2068 [Stat]*. - Stei81: Charles M. Stein (1981) Estimation of the Mean of a Multivariate Normal Distribution.
*The Annals of Statistics*, 9(6), 1135–1151. DOI - BCFS14: Arindam Banerjee, Sheng Chen, Farideh Fazayeli, Vidyashankar Sivakumar (2014) Estimation with Norm Regularization. In Advances in Neural Information Processing Systems 27 (pp. 1556–1564). Curran Associates, Inc.
- AzKS15: Martin Azizyan, Akshay Krishnamurthy, Aarti Singh (2015) Extreme Compressive Sampling for Covariance Estimation.
*ArXiv:1506.00898 [Cs, Math, Stat]*. - TKPS14: Wesley Tansey, Oluwasanmi Koyejo, Russell A. Poldrack, James G. Scott (2014) False discovery rate smoothing.
*ArXiv:1411.6144 [Stat]*. - Wood08: Simon N. Wood (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. DOI - Batt92: Roberto Battiti (1992) First-and second-order methods for learning: between steepest descent and Newton’s method.
*Neural Computation*, 4(2), 141–166. DOI - KoKi96: Sadanori Konishi, Genshiro Kitagawa (1996) Generalised information criteria in model selection.
*Biometrika*, 83(4), 875–890. DOI - HaTi90: Trevor J. Hastie, Robert J. Tibshirani (1990)
*Generalized additive models*(Vol. 43). CRC Press - GoHW79: Gene H. Golub, Michael Heath, Grace Wahba (1979) Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter.
*Technometrics*, 21(2), 215–223. DOI - Mont12: Andrea Montanari (2012) Graphical models concepts in compressed sensing.
*Compressed Sensing: Theory and Applications*, 394–438. - BüGe15: Peter Bühlmann, Sara van de Geer (2015) High-dimensional inference in misspecified linear models.
*ArXiv:1503.06426 [Stat]*, 9(1), 1449–1473. DOI - Meye08: Mary C. Meyer (2008) Inference using shape-restricted regression splines.
*The Annals of Applied Statistics*, 2(3), 1013–1033. DOI - KoKi08: Sadanori Konishi, G. Kitagawa (2008)
*Information criteria and statistical modeling*. New York: Springer - Akai73: Hirotogu Akaike (1973) Information Theory and an Extension of the Maximum Likelihood Principle. In Proceeding of the Second International Symposium on Information Theory (pp. 199–213). Budapest: Akademiai Kiado
- EHJT04: Bradley Efron, Trevor Hastie, Iain Johnstone, Robert Tibshirani (2004) Least angle regression.
*The Annals of Statistics*, 32(2), 407–499. DOI - CaPl10: Emmanuel J. Candès, Y. Plan (2010) Matrix Completion With Noise.
*Proceedings of the IEEE*, 98(6), 925–936. DOI - Akai73: Htrotugu Akaike (1973) Maximum likelihood identification of Gaussian autoregressive moving average models.
*Biometrika*, 60(2), 255–265. DOI - BHLL08: Andrew R. Barron, Cong Huang, Jonathan Q. Li, Xi Luo (2008) MDL, penalized likelihood, and statistical risk. In Information Theory Workshop, 2008. ITW’08. IEEE (pp. 247–257). IEEE DOI
- Bach09: Francis Bach (2009) Model-Consistent Sparse Estimation through the Bootstrap
- Wood00: S. N. Wood (2000) Modelling and smoothing parameter estimation with multiple quadratic penalties.
*Journal of the Royal Statistical Society: Series B (Statistical Methodology)*, 62(2), 413–428. DOI - Ye98: Jianming Ye (1998) On Measuring and Correcting the Effects of Data Mining and Model Selection.
*Journal of the American Statistical Association*, 93(441), 120–131. DOI - ZoHT07: Hui Zou, Trevor Hastie, Robert Tibshirani (2007) On the “degrees of freedom” of the lasso.
*The Annals of Statistics*, 35(5), 2173–2192. DOI - Silv82: B. W. Silverman (1982) On the Estimation of a Probability Density Function by the Maximum Penalized Likelihood Method.
*The Annals of Statistics*, 10(3), 795–810. DOI - SoLS16: Anelia Somekh-Baruch, Amir Leshem, Venkatesh Saligrama (2016) On the Non-Existence of Unbiased Estimators in Constrained Estimation Problems.
*ArXiv:1609.07415 [Cs, Math, Stat]*. - GiSB14: Raja Giryes, Guillermo Sapiro, Alex M. Bronstein (2014) On the Stability of Deep Networks.
*ArXiv:1412.5896 [Cs, Math, Stat]*. - Gree90: Peter J. Green (1990) On Use of the EM for Penalized Likelihood Estimation.
*Journal of the Royal Statistical Society. Series B (Methodological)*, 52(3), 443–452. - ShHu06: Xiaotong Shen, Hsin-Cheng Huang (2006) Optimal Model Assessment, Selection, and Combination.
*Journal of the American Statistical Association*, 101(474), 554–568. DOI - WeMZ18: Haolei Weng, Arian Maleki, Le Zheng (2018) Overcoming the limitations of phase transition by higher order analysis of regularization techniques.
*The Annals of Statistics*, 46(6A), 3099–3129. DOI - GuLi05: Jiang Gui, 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–3008. DOI - Uema15: Yoshimasa Uematsu (2015) Penalized Likelihood Estimation in High-Dimensional Time Series Models and its Application.
*ArXiv:1504.06706 [Math, Stat]*. - ZoHa05: Hui Zou, Trevor Hastie (2005) Regularization and variable selection via the elastic net.
*Journal of the Royal Statistical Society: Series B (Statistical Methodology)*, 67(2), 301–320. DOI - BLTG06: Peter J. Bickel, Bo Li, Alexandre B. Tsybakov, Sara A. van de Geer, Bin Yu, Teófilo Valdés, … Aad van der Vaart (2006) Regularization in statistics.
*Test*, 15(2), 271–344. DOI - ZhLT10: Yiyun Zhang, Runze Li, Chih-Ling Tsai (2010) Regularization Parameter Selections via Generalized Information Criterion.
*Journal of the American Statistical Association*, 105(489), 312–323. DOI - SFHT11: Noah Simon, Jerome Friedman, Trevor Hastie, Rob Tibshirani (2011) Regularization Paths for Cox’s Proportional Hazards Model via Coordinate Descent.
*Journal of Statistical Software*, 39(5). - FrHT10: Jerome Friedman, Trevor Hastie, Rob Tibshirani (2010) Regularization Paths for Generalized Linear Models via Coordinate Descent.
*Journal of Statistical Software*, 33(1), 1–22. DOI - HoKe70: Arthur E. Hoerl, Robert W. Kennard (1970) Ridge Regression: Biased Estimation for Nonorthogonal Problems.
*Technometrics*, 12(1), 55–67. DOI - Gu93: Chong Gu (1993) Smoothing Spline Density Estimation: A Dimensionless Automatic Algorithm.
*Journal of the American Statistical Association*, 88(422), 495–504. DOI - Wahb90: Grace Wahba (1990)
*Spline Models for Observational Data*. SIAM - Silv84: B. W. Silverman (1984) Spline Smoothing: The Equivalent Variable Kernel Method.
*The Annals of Statistics*, 12(3), 898–916. DOI - LiRW10: Han Liu, Kathryn Roeder, Larry Wasserman (2010) Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models. In Advances in Neural Information Processing Systems 23 (pp. 1432–1440). Curran Associates, Inc.
- MeBü10: Nicolai Meinshausen, Peter Bühlmann (2010) Stability selection.
*Journal of the Royal Statistical Society: Series B (Statistical Methodology)*, 72(4), 417–473. DOI - HaTW15: Trevor J. Hastie, Tibshirani, Rob, Martin J. Wainwright (2015)
*Statistical Learning with Sparsity: The Lasso and Generalizations*. Boca Raton: Chapman and Hall/CRC - BrLi04: Lawrence D. Brown, Yi Lin (2004) Statistical properties of the method of regularization with periodic Gaussian reproducing kernel.
*The Annals of Statistics*, 32(4), 1723–1743. DOI - Geer14a: Sara van de Geer (2014a) Statistical Theory for High-Dimensional Models.
*ArXiv:1409.8557 [Math, Stat]*. - ReMW15: Danilo Jimenez Rezende, Shakir Mohamed, Daan Wierstra (2015) Stochastic Backpropagation and Approximate Inference in Deep Generative Models. In Proceedings of ICML.
- CaFe13: Emmanuel J. Candès, Carlos Fernandez-Granda (2013) Super-Resolution from Noisy Data.
*Journal of Fourier Analysis and Applications*, 19(6), 1229–1254. DOI - SmSM98: Alex J. Smola, Bernhard Schölkopf, Klaus-Robert Müller (1998) The connection between regularization operators and support vector kernels.
*Neural Networks*, 11(4), 637–649. DOI - Efro04: Bradley Efron (2004) The Estimation of Prediction Error.
*Journal of the American Statistical Association*, 99(467), 619–632. DOI - Cava97: Joseph E. Cavanaugh (1997) Unifying the derivations for the Akaike and corrected Akaike information criteria.
*Statistics & Probability Letters*, 33(2), 201–208. DOI - TiGl65: A. N. Tikhonov, V. B. Glasko (1965) Use of the regularization method in non-linear problems.
*USSR Computational Mathematics and Mathematical Physics*, 5(3), 93–107. DOI - ChHS15: Victor Chernozhukov, Christian Hansen, Martin Spindler (2015) Valid Post-Selection and Post-Regularization Inference: An Elementary, General Approach.
*Annual Review of Economics*, 7(1), 649–688. DOI - Geer14b: Sara van de Geer (2014b) Weakly decomposable regularization penalties and structured sparsity.
*Scandinavian Journal of Statistics*, 41(1), 72–86. DOI - RaRe09: Ali Rahimi, Benjamin Recht (2009) Weighted Sums of Random Kitchen Sinks: Replacing minimization with randomization in learning. In Advances in neural information processing systems (pp. 1313–1320). Curran Associates, Inc.
- KaRo14: S. Kaufman, S. Rosset (2014) When does more regularization imply fewer degrees of freedom? Sufficient conditions and counterexamples.
*Biometrika*, 101(4), 771–784. DOI