Ordered Weighted L1 Regularized Regression with Strongly Correlated Covariates: Theoretical Aspects

Mario Figueiredo, Robert Nowak
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:930-938, 2016.

Abstract

This paper studies the ordered weighted L1 (OWL) family of regularizers for sparse linear regression with strongly correlated covariates. We prove sufficient conditions for clustering correlated covariates, extending and qualitatively strengthening previous results for a particular member of the OWL family: OSCAR (octagonal shrinkage and clustering algorithm for regression). We derive error bounds for OWL with correlated Gaussian covariates: for cases in which clusters of covariates are strongly (even perfectly) correlated, but covariates in different clusters are uncorrelated, we show that if the true p-dimensional signal involves only s clusters, then O(s \log p) samples suffice to accurately estimate it, regardless of the number of coefficients within the clusters. Since the estimation of s-sparse signals with completely independent covariates also requires O(s \log p) measurements, this shows that by using OWL regularization, we pay no price (in the number of measurements) for the presence of strongly correlated covariates.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-figueiredo16, title = {Ordered Weighted L1 Regularized Regression with Strongly Correlated Covariates: Theoretical Aspects}, author = {Figueiredo, Mario and Nowak, Robert}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {930--938}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/figueiredo16.pdf}, url = {https://proceedings.mlr.press/v51/figueiredo16.html}, abstract = {This paper studies the ordered weighted L1 (OWL) family of regularizers for sparse linear regression with strongly correlated covariates. We prove sufficient conditions for clustering correlated covariates, extending and qualitatively strengthening previous results for a particular member of the OWL family: OSCAR (octagonal shrinkage and clustering algorithm for regression). We derive error bounds for OWL with correlated Gaussian covariates: for cases in which clusters of covariates are strongly (even perfectly) correlated, but covariates in different clusters are uncorrelated, we show that if the true p-dimensional signal involves only s clusters, then O(s \log p) samples suffice to accurately estimate it, regardless of the number of coefficients within the clusters. Since the estimation of s-sparse signals with completely independent covariates also requires O(s \log p) measurements, this shows that by using OWL regularization, we pay no price (in the number of measurements) for the presence of strongly correlated covariates.} }
Endnote
%0 Conference Paper %T Ordered Weighted L1 Regularized Regression with Strongly Correlated Covariates: Theoretical Aspects %A Mario Figueiredo %A Robert Nowak %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-figueiredo16 %I PMLR %P 930--938 %U https://proceedings.mlr.press/v51/figueiredo16.html %V 51 %X This paper studies the ordered weighted L1 (OWL) family of regularizers for sparse linear regression with strongly correlated covariates. We prove sufficient conditions for clustering correlated covariates, extending and qualitatively strengthening previous results for a particular member of the OWL family: OSCAR (octagonal shrinkage and clustering algorithm for regression). We derive error bounds for OWL with correlated Gaussian covariates: for cases in which clusters of covariates are strongly (even perfectly) correlated, but covariates in different clusters are uncorrelated, we show that if the true p-dimensional signal involves only s clusters, then O(s \log p) samples suffice to accurately estimate it, regardless of the number of coefficients within the clusters. Since the estimation of s-sparse signals with completely independent covariates also requires O(s \log p) measurements, this shows that by using OWL regularization, we pay no price (in the number of measurements) for the presence of strongly correlated covariates.
RIS
TY - CPAPER TI - Ordered Weighted L1 Regularized Regression with Strongly Correlated Covariates: Theoretical Aspects AU - Mario Figueiredo AU - Robert Nowak BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-figueiredo16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 930 EP - 938 L1 - http://proceedings.mlr.press/v51/figueiredo16.pdf UR - https://proceedings.mlr.press/v51/figueiredo16.html AB - This paper studies the ordered weighted L1 (OWL) family of regularizers for sparse linear regression with strongly correlated covariates. We prove sufficient conditions for clustering correlated covariates, extending and qualitatively strengthening previous results for a particular member of the OWL family: OSCAR (octagonal shrinkage and clustering algorithm for regression). We derive error bounds for OWL with correlated Gaussian covariates: for cases in which clusters of covariates are strongly (even perfectly) correlated, but covariates in different clusters are uncorrelated, we show that if the true p-dimensional signal involves only s clusters, then O(s \log p) samples suffice to accurately estimate it, regardless of the number of coefficients within the clusters. Since the estimation of s-sparse signals with completely independent covariates also requires O(s \log p) measurements, this shows that by using OWL regularization, we pay no price (in the number of measurements) for the presence of strongly correlated covariates. ER -
APA
Figueiredo, M. & Nowak, R.. (2016). Ordered Weighted L1 Regularized Regression with Strongly Correlated Covariates: Theoretical Aspects. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:930-938 Available from https://proceedings.mlr.press/v51/figueiredo16.html.

Related Material