# Slowly Varying Regression under Sparsity

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 41 references that are in the map.
- First posted on arXiv 22 Feb 2021.

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

- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms](https://mlsanity.com/paper/1803.01454/) (2018)
- [JuMP: A Modeling Language for Mathematical Optimization](https://mlsanity.com/paper/1508.01982/) (2015)
- [Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization](https://mlsanity.com/paper/2004.06152/) (2020)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [Sparse Regression: Scalable algorithms and empirical performance](https://mlsanity.com/paper/1902.06547/) (2019)
- [A unified approach to mixed-integer optimization problems with logical constraints](https://mlsanity.com/paper/1907.02109/) (2019)
- [Ideal formulations for constrained convex optimization problems with indicator variables](https://mlsanity.com/paper/2007.00107/) (2020)
- [On change point detection using the fused lasso method](https://mlsanity.com/paper/1401.5408/) (2014)
- [MIP-BOOST: Efficient and Effective L0 Feature Selection for Linear Regression](https://mlsanity.com/paper/1808.02526/) (2018)

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

- [A Splicing Approach to Best Subset of Groups Selection](https://mlsanity.com/paper/2104.12576/) (2021)
- [Correlating Time Series with Interpretable Convolutional Kernels](https://mlsanity.com/paper/2409.01362/) (2024)
- [Improving Stability in Decision Tree Models](https://mlsanity.com/paper/2305.17299/) (2023)
- [Towards Stable Machine Learning Model Retraining via Slowly Varying Sequences](https://mlsanity.com/paper/2403.19871/) (2024)
- [Interpretable Time Series Autoregression for Periodicity Quantification](https://mlsanity.com/paper/2506.22895/) (2025)
- [BackboneLearn: A Library for Scaling Mixed-Integer Optimization-Based Machine Learning](https://mlsanity.com/paper/2311.13695/) (2023)
- [Data-Driven Discovery of Mobility Periodicity for Understanding Urban Systems](https://mlsanity.com/paper/2508.03747/) (2025)

## Abstract (arXiv)

We present the framework of slowly varying regression under sparsity, allowing sparse regression models to exhibit slow and sparse variations. The problem of parameter estimation is formulated as a mixed-integer optimization problem. We demonstrate that it can be precisely reformulated as a binary convex optimization problem through a novel relaxation technique. This relaxation involves a new equality on Moore-Penrose inverses, convexifying the non-convex objective function while matching the original objective on all feasible binary points. This enables us to efficiently solve the problem to provable optimality using a cutting plane-type algorithm. We develop a highly optimized implementation of this algorithm, substantially improving upon the asymptotic computational complexity of a straightforward implementation. Additionally, we propose a fast heuristic method that guarantees a feasible solution and, as empirically illustrated, produces high-quality warm-start solutions for the binary optimization problem. To tune the framework's hyperparameters, we suggest a practical procedure relying on binary search that, under certain assumptions, is guaranteed to recover the true model parameters. On both synthetic and real-world datasets, we demonstrate that the resulting algorithm outperforms competing formulations in comparable times across various metrics, including estimation accuracy, predictive power, and computational time. The algorithm is highly scalable, allowing us to train models with thousands of parameters. Our implementation is available open-source at https://github.com/vvdigalakis/SSVRegression.git.