# Support recovery without incoherence: A case for nonconvex regularization

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2014.

## Built on by (most cited first, 25 of 25)

- [Structure Learning with Continuous Optimization: A Sober Look and Beyond](https://mlsanity.com/paper/2304.02146/) (2023)
- [Generalizing Nonlinear ICA Beyond Structural Sparsity](https://mlsanity.com/paper/2311.00866/) (2023)
- [Optimal estimation of Gaussian DAG models](https://mlsanity.com/paper/2201.10548/) (2022)
- [A Kernel-Expanded Stochastic Neural Network](https://mlsanity.com/paper/2201.05319/) (2022)
- [Generalized Precision Matrix for Scalable Estimation of Nonparametric Markov Networks](https://mlsanity.com/paper/2305.11379/) (2023)
- [Sparse Graph Learning Under Laplacian-Related Constraints](https://mlsanity.com/paper/2111.08161/) (2021)
- [On the instrumental variable estimation with many weak and invalid instruments](https://mlsanity.com/paper/2207.03035/) (2022)
- [Adaptive Estimation of Graphical Models under Total Positivity](https://mlsanity.com/paper/2210.15471/) (2022)
- [Robust High-Dimensional Regression with Coefficient Thresholding and its Application to Imaging Data Analysis](https://mlsanity.com/paper/2109.14856/) (2021)
- [Learning the Structure of Large Networked Systems Obeying Conservation Laws](https://mlsanity.com/paper/2206.07083/) (2022)
- [Learning Multi-Attribute Differential Graphs with Non-Convex Penalties](https://mlsanity.com/paper/2505.09748/) (2025)
- [Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers](https://mlsanity.com/paper/2109.12713/) (2021)
- [Best Subset Selection with Efficient Primal-Dual Algorithm](https://mlsanity.com/paper/2207.02058/) (2022)
- [On High dimensional Poisson models with measurement error: hypothesis testing for nonlinear nonconvex optimization](https://mlsanity.com/paper/2301.00139/) (2022)
- [The Adaptive τ-Lasso: Robustness and Oracle Properties](https://mlsanity.com/paper/2304.09310/) (2023)
- [Dynamic Incremental Optimization for Best Subset Selection](https://mlsanity.com/paper/2402.02322/) (2024)
- [Learning Networks from Wide-Sense Stationary Stochastic Processes](https://mlsanity.com/paper/2412.03768/) (2024)
- [Multi-Attribute Graph Estimation with Sparse-Group Non-Convex Penalties](https://mlsanity.com/paper/2505.11984/) (2025)
- [Uncertainty Quantification for Large-Scale Deep Networks via Post-StoNet Modeling](https://mlsanity.com/paper/2508.01217/) (2025)
- [Sparse minimum Redundancy Maximum Relevance for feature selection](https://mlsanity.com/paper/2508.18901/) (2025)
- [Learning Conditional Independence Differential Graphs From Time-Dependent Data](https://mlsanity.com/paper/2512.06960/) (2025)
- [On Conditional Independence Graph Learning From Multi-Attribute Gaussian Dependent Time Series](https://mlsanity.com/paper/2512.07557/) (2025)
- [Nonconvex Latent Optimally Partitioned Block-Sparse Recovery via Log-Sum and Minimax Concave Penalties](https://mlsanity.com/paper/2603.01304/) (2026)
- [Sublinearly Structured Deep Neural Networks Achieve Feature Learning Consistency for Compositional Functions](https://mlsanity.com/paper/2606.23477/) (2026)
- [Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization](https://mlsanity.com/paper/2607.10618/) (2026)

## Abstract (arXiv)

We demonstrate that the primal-dual witness proof method may be used to establish variable selection consistency and ℓ_∞-bounds for sparse regression problems, even when the loss function and/or regularizer are nonconvex. Using this method, we derive two theorems concerning support recovery and ℓ_∞-guarantees for the regression estimator in a general setting. Our results provide rigorous theoretical justification for the use of nonconvex regularization: For certain nonconvex regularizers with vanishing derivative away from the origin, support recovery consistency may be guaranteed without requiring the typical incoherence conditions present in ℓ1-based methods. We then derive several corollaries that illustrate the wide applicability of our method to analyzing composite objective functions involving losses such as least squares, nonconvex modified least squares for errors-in variables linear regression, the negative log likelihood for generalized linear models, and the graphical Lasso. We conclude with empirical studies to corroborate our theoretical predictions.