Online sparse linear regression has new limits on prediction errors
New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression
Machine Learning
Summary
Online sparse linear regression means predicting outcomes when only a few features can be seen each time. The authors looked at how hard this problem really is by proving a lowest possible prediction error that any algorithm can achieve, and they also made algorithms that perform better than before without relying on extra assumptions. Their work shows how the difficulty of prediction depends on core problem factors. This helps understand the fundamental challenge of making predictions when data access is limited.
What this means in practice
- •For machine learning engineers: Design prediction models that efficiently handle limited feature access while knowing provable performance limits.
- •For data platform architects: Set realistic expectations for feature acquisition strategies in systems where observing all data points is costly or impossible.
A theory result. No direct application yet.
Authors
Xiaofeng Cao, Junfan Li, Langzhang Liang, Mingwei Xu, Xiao Zhang
Abstract
We study online sparse linear regression (OSLR) where any algorithm is restricted to accessing only $b$ out of $d$ attributes per instance for prediction and $b_0\geq 0$ additional attributes after prediction, which was proved to be NP-hard. Previous work focused on designing computationally efficient algorithms under regularity assumptions, but did not characterize its information theoretic complexity. In this work, we give the first lower bound on the minimax regret of OSLR and design algorithms with better upper bounds without regularity assumptions. We characterize how minimax regret scales with problem-dependent parameters, capturing the information theoretic complexity of OSLR.