Abstract
We investigate an online regression problem where the learner makes sequential predictions while observing only limited information on features. We propose a general framework combining bandit theory with online learning and develop efficient specialized algorithms for linear projections that significantly outperform existing sparse regression baselines.
Introduction
In standard online regression, a learner receives a full set of features, makes a prediction, and then observes the true label to improve its model. However, in many real-world scenarios—such as medical diagnostics or industrial quality control—observing every feature is often too expensive, slow, or physically impossible.
Previous work primarily focused on Online Sparse Linear Regression (OSLR), where the learner selects a few specific features to observe. This paper identifies a major gap: OSLR cannot handle cases where we observe combinations or projections of features, such as Radon transforms in CT scans. The authors propose a more general setting where the learner chooses an "observation function" from a predefined set to obtain a compressed glimpse of the data.
Methods
The proposed approach operates in two stages:
- The General Case (Algorithm 1): For any finite set of observation functions, the authors combine Multi-Armed Bandit (MAB) algorithms with standard Online Learning. The MAB component selects the "view" (observation function), while the Online Learning component optimizes the prediction model for that specific view. The algorithm balances exploration and exploitation by operating in blocks of time.
- The Linear Case (Algorithms 2 & 3): When observations are linear projections, the set of possible "views" can be infinite. To address this, the authors utilize the Dual Averaging method. They construct unbiased gradient estimators to update the model without seeing the full feature vector. For cases requiring a subset of projections, they incorporate Orthogonal Matching Pursuit (OMP) to approximate the best features from limited information.
Experimental Results
The researchers evaluated their algorithms using synthetic data and the real-world CT-Slice Dataset from the UCI Machine Learning Repository, which contains 384 features extracted from 53,500 CT images.
Performance on Synthetic Data
In synthetic tests, the proposed algorithms achieved significantly lower regret than the state-of-the-art baseline (KKLP).
Real-World Application: CT-Slice Dataset
On the CT dataset, the goal is to predict the relative position of the image on the axial axis. The proposed algorithms demonstrated superior scalability and accuracy.
Key Findings: * Theoretical Guarantees: The general algorithm achieves sublinear regret, ensuring average performance converges to the best fixed strategy over time. * Computational Speed: On the CT dataset, the proposed algorithms processed the data in approximately 6.6 seconds, whereas the baseline algorithm failed to finish within a 3-hour cutoff.
Discussion and Future Work
By framing the problem through "observation functions," the authors demonstrate that sparse regression is a specific instance of a broader class of partial-information problems. This generalization is crucial because it allows the application of these techniques to diverse fields like medical imaging, where data is often collected as projections rather than raw features.
Choosing what to observe is fundamentally a bandit problem, requiring a balance between "exploring" different data views to find the most informative ones and "exploiting" the best-known views to minimize prediction error. The "aha moment" for the linear case is the realization that a full feature vector isn't necessary for model updates; carefully weighted partial information can create a noisy but unbiased version of the full gradient, enabling efficient learning.
While effective, the general algorithm's efficiency depends on a relatively small set of observation functions. Furthermore, the most efficient linear algorithms (2 and 3) rely on linearity. Extending these gradient-estimation techniques to non-linear models, such as deep neural networks, remains an open challenge for future research. Additionally, some sparse recovery guarantees depend on the "Restricted Isometry Property," which may not always hold in messy real-world data.
Summary updated