# Taming Nonconvexity in Kernel Feature Selection -- Favorable Properties of the Laplace Kernel

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 51 references that are in the map.
- First posted on arXiv 17 Jun 2021.

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

- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [Interpretable machine learning: definitions, methods, and applications](https://mlsanity.com/paper/1901.04592/) (2019)
- [Panning for Gold: Model-X Knockoffs for High-dimensional Controlled Variable Selection](https://mlsanity.com/paper/1610.02351/) (2016)
- [Feature Selection: A Data Perspective](https://mlsanity.com/paper/1601.07996/) (2016)
- [A Self-Penalizing Objective Function for Scalable Interaction Detection](https://mlsanity.com/paper/2011.12215/) (2020)

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

- [On the Self-Penalization Phenomenon in Feature Selection](https://mlsanity.com/paper/2110.05852/) (2021)
- [A Compositional Kernel Model for Feature Learning](https://mlsanity.com/paper/2509.14158/) (2025)
- [RFFNet: Large-Scale Interpretable Kernel Methods via Random Fourier Features](https://mlsanity.com/paper/2211.06410/) (2022)

## Abstract (arXiv)

Kernel-based feature selection is an important tool in nonparametric statistics. Despite many practical applications of kernel-based feature selection, there is little statistical theory available to support the method. A core challenge is the objective function of the optimization problems used to define kernel-based feature selection are nonconvex. The literature has only studied the statistical properties of the global optima, which is a mismatch, given that the gradient-based algorithms available for nonconvex optimization are only able to guarantee convergence to local minima. Studying the full landscape associated with kernel-based methods, we show that feature selection objectives using the Laplace kernel (and other ℓ1 kernels) come with statistical guarantees that other kernels, including the ubiquitous Gaussian kernel (or other ℓ2 kernels) do not possess. Based on a sharp characterization of the gradient of the objective function, we show that ℓ1 kernels eliminate unfavorable stationary points that appear when using an ℓ2 kernel. Armed with this insight, we establish statistical guarantees for ℓ1 kernel-based feature selection which do not require reaching the global minima. In particular, we establish model-selection consistency of ℓ1-kernel-based feature selection in recovering main effects and hierarchical interactions in the nonparametric setting with n ~ log p samples.