# The non-overlapping statistical approximation to overlapping group lasso

arXiv: https://arxiv.org/abs/2211.09221 · HTML: https://mlsanity.com/paper/2211.09221/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 58 references that are in the map.
- First posted on arXiv 16 Nov 2022.

## Builds on (most cited first, 12 of 12)

- [Node-Based Learning of Multiple Gaussian Graphical Models](https://mlsanity.com/paper/1303.5145/) (2013)
- [Estimation of Graphical Models through Structured Norm Minimization](https://mlsanity.com/paper/1609.09010/) (2016)
- [Estimating Time-Varying Graphical Models](https://mlsanity.com/paper/1804.03811/) (2018)
- [High-dimensional Mixed Graphical Models](https://mlsanity.com/paper/1304.2810/) (2013)
- [Hierarchical Sparse Modeling: A Choice of Two Group Lasso Formulations](https://mlsanity.com/paper/1512.01631/) (2015)
- [Learning Local Dependence In Ordered Data](https://mlsanity.com/paper/1604.07451/) (2016)
- [Within Group Variable Selection through the Exclusive Lasso](https://mlsanity.com/paper/1505.07517/) (2015)
- [Sparse Group Lasso: Optimal Sample Complexity, Convergence Rate, and Statistical Inference](https://mlsanity.com/paper/1909.09851/) (2019)
- [An error bound for Lasso and Group Lasso in high dimensions](https://mlsanity.com/paper/1912.11398/) (2019)
- [Screening Rules for Overlapping Group Lasso](https://mlsanity.com/paper/1410.6880/) (2014)
- [Graph-Guided Banding of the Covariance Matrix](https://mlsanity.com/paper/1606.00451/) (2016)
- [An Efficient ADMM Algorithm for Structural Break Detection in Multivariate Time Series](https://mlsanity.com/paper/1711.08392/) (2017)

## Abstract (arXiv)

Group lasso is a commonly used regularization method in statistical learning in which parameters are eliminated from the model according to predefined groups. However, when the groups overlap, optimizing the group lasso penalized objective can be time-consuming on large-scale problems because of the non-separability induced by the overlapping groups. This bottleneck has seriously limited the application of overlapping group lasso regularization in many modern problems, such as gene pathway selection and graphical model estimation. In this paper, we propose a separable penalty as an approximation of the overlapping group lasso penalty. Thanks to the separability, the computation of regularization based on our penalty is substantially faster than that of the overlapping group lasso, especially for large-scale and high-dimensional problems. We show that the penalty is the tightest separable relaxation of the overlapping group lasso norm within the family of ℓq1/ℓq2 norms. Moreover, we show that the estimator based on the proposed separable penalty is statistically equivalent to the one based on the overlapping group lasso penalty with respect to their error bounds and the rate-optimal performance under the squared loss. We demonstrate the faster computational time and statistical equivalence of our method compared with the overlapping group lasso in simulation examples and a classification problem of cancer tumors based on gene expression and multiple gene pathways.