# Sparse Bayesian Learning via Stepwise Regression

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 61 references that are in the map.
- First posted on arXiv 11 Jun 2021.

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

- [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016)
- [JuMP: A Modeling Language for Mathematical Optimization](https://mlsanity.com/paper/1508.01982/) (2015)
- [Maximal Sparsity with Deep Networks?](https://mlsanity.com/paper/1605.01636/) (2016)
- [Forward-Backward Selection with Early Dropping](https://mlsanity.com/paper/1705.10770/) (2017)
- [A General Framework for Fast Stagewise Algorithms](https://mlsanity.com/paper/1408.5801/) (2014)
- [Forward - Backward Greedy Algorithms for Atomic Norm Regularization](https://mlsanity.com/paper/1404.5692/) (2014)
- [From Bayesian Sparsity to Gated Recurrent Nets](https://mlsanity.com/paper/1706.02815/) (2017)
- [On Matching Pursuit and Coordinate Descent](https://mlsanity.com/paper/1803.09539/) (2018)
- [Blended Matching Pursuit](https://mlsanity.com/paper/1904.12335/) (2019)
- [On the Optimality of Backward Regression: Sparse Recovery and Subset Selection](https://mlsanity.com/paper/2106.03235/) (2021)

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

- [Scalable First-Order Bayesian Optimization via Structured Automatic Differentiation](https://mlsanity.com/paper/2206.08366/) (2022)
- [Robust Gaussian Processes via Relevance Pursuit](https://mlsanity.com/paper/2410.24222/) (2024)
- [Efficient Network Automatic Relevance Determination](https://mlsanity.com/paper/2506.12352/) (2025)
- [Novel Pivoted Cholesky Decompositions for Efficient Gaussian Process Inference](https://mlsanity.com/paper/2507.20678/) (2025)
- [General Pruning Criteria for Fast SBL](https://mlsanity.com/paper/2509.21572/) (2025)
- [Joint Model and Data Sparsification via the Marginal Likelihood](https://mlsanity.com/paper/2605.29908/) (2026)

## Abstract (arXiv)

Sparse Bayesian Learning (SBL) is a powerful framework for attaining sparsity in probabilistic models. Herein, we propose a coordinate ascent algorithm for SBL termed Relevance Matching Pursuit (RMP) and show that, as its noise variance parameter goes to zero, RMP exhibits a surprising connection to Stepwise Regression. Further, we derive novel guarantees for Stepwise Regression algorithms, which also shed light on RMP. Our guarantees for Forward Regression improve on deterministic and probabilistic results for Orthogonal Matching Pursuit with noise. Our analysis of Backward Regression on determined systems culminates in a bound on the residual of the optimal solution to the subset selection problem that, if satisfied, guarantees the optimality of the result. To our knowledge, this bound is the first that can be computed in polynomial time and depends chiefly on the smallest singular value of the matrix. We report numerical experiments using a variety of feature selection algorithms. Notably, RMP and its limiting variant are both efficient and maintain strong performance with correlated features.