# OKRidge: Scalable Optimal k-Sparse Ridge Regression

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 36 references that are in the map.
- First posted on arXiv 13 Apr 2023.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Ensemble-SINDy: Robust sparse model discovery in the low-data, high-noise limit, with active learning and control](https://mlsanity.com/paper/2111.10992/) (2021)
- [Sequence-to-Sequence Learning as Beam-Search Optimization](https://mlsanity.com/paper/1606.02960/) (2016)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [PySINDy: A comprehensive Python package for robust sparse system identification](https://mlsanity.com/paper/2111.08481/) (2021)
- [Sparse learning of stochastic dynamic equations](https://mlsanity.com/paper/1712.02432/) (2017)
- [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016)
- [A unified sparse optimization framework to learn parsimonious physics-informed models from data](https://mlsanity.com/paper/1906.10612/) (2019)
- [Learning Sparse Nonlinear Dynamics via Mixed-Integer Optimization](https://mlsanity.com/paper/2206.00176/) (2022)
- [Sparse Regression: Scalable algorithms and empirical performance](https://mlsanity.com/paper/1902.06547/) (2019)
- [Safe Screening Rules for ℓ0-Regression](https://mlsanity.com/paper/2004.08773/) (2020)
- [Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM](https://mlsanity.com/paper/1410.8479/) (2014)
- [The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables](https://mlsanity.com/paper/2112.04618/) (2021)

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

- [Amazing Things Come From Having Many Good Models](https://mlsanity.com/paper/2407.04846/) (2024)
- [Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert](https://mlsanity.com/paper/2308.09474/) (2023)
- [Interpretable Time Series Autoregression for Periodicity Quantification](https://mlsanity.com/paper/2506.22895/) (2025)
- [FastSurvival: Hidden Computational Blessings in Training Cox Proportional Hazards Models](https://mlsanity.com/paper/2410.19081/) (2024)
- [Efficient Cross-Validation for Sparse Linear Regression](https://mlsanity.com/paper/2306.14851/) (2023)
- [Stability Regularized Cross-Validation](https://mlsanity.com/paper/2505.06927/) (2025)
- [From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal k-Sparse GLMs](https://mlsanity.com/paper/2605.22188/) (2026)

## Abstract (arXiv)

We consider an important problem in scientific discovery, namely identifying sparse governing equations for nonlinear dynamical systems. This involves solving sparse ridge regression problems to provable optimality in order to determine which terms drive the underlying dynamics. We propose a fast algorithm, OKRidge, for sparse ridge regression, using a novel lower bound calculation involving, first, a saddle point formulation, and from there, either solving (i) a linear system or (ii) using an ADMM-based approach, where the proximal operators can be efficiently evaluated by solving another linear system and an isotonic regression problem. We also propose a method to warm-start our solver, which leverages a beam search. Experimentally, our methods attain provable optimality with run times that are orders of magnitude faster than those of the existing MIP formulations solved by the commercial solver Gurobi.