Relax-and-Sparsify Approximation Algorithms for Sparse Ridge Regression
Source: arxiv.org/abs/2611.19738
This paper studies sparse ridge regression in the low-rank, high-dimensional setting that often arises when data collection is expensive. By exploiting the low-rank structure, we develop approximation algorithms within a relax-and-sparsify framework: solve a convex relaxation and then sparsify its solution to satisfy the original sparsity constraint. Specifically, we establish a tight rank-dependent sparsity bound for the convex relaxation by decomposing its support into two parts. This decomposition in turn motivates two approximation strategies, parameter reduction and binary…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.19738
curl -X POST /api/v1/records/arxiv/2611.19738/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.19738/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'