OKRidge: Scalable Optimal k-Sparse Ridge Regression
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909070460452864 |
|---|---|
| author | Liu, Jiachang Rosen, Sam Zhong, Chudi Rudin, Cynthia |
| author_facet | Liu, Jiachang Rosen, Sam Zhong, Chudi Rudin, Cynthia |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_06686 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | OKRidge: Scalable Optimal k-Sparse Ridge Regression Liu, Jiachang Rosen, Sam Zhong, Chudi Rudin, Cynthia Machine Learning 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. |
| title | OKRidge: Scalable Optimal k-Sparse Ridge Regression |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2304.06686 |