We propose a regularized linear learning algorithm to sequence groups of features, where each group incurs test-time cost or computation. Specifically, we develop a simple extension to Orthogonal Matching Pursuit (OMP) that respects the structure of groups of features with variable costs, and we prove that it achieves near-optimal anytime linear prediction at each budget threshold where a new group is selected. Our algorithm and analysis extends to generalized linear models with multi-dimensional responses. We demonstrate the scalability of the resulting approach on large real-world data-sets with many feature groups associated with test-time computational costs. Our method improves over Group Lasso and Group OMP in the anytime performance of linear predictions, measured in timeliness, an anytime prediction performance metric, while providing rigorous performance guarantees.

本文主要讨论机器学习中任意时间的线性预测问题，并提出了一种基于成本分组的算法来实现。通过理论分析，我们保证了该算法在任何成本预算下都能取得接近最优的线性预测性能。同时，我们也提出了一种可将成本 $B$ 的线性预测问题近似到 $4B$ 的算法，并证明该算法在成本小于 $4B$ 时是不可能的。

任意线性预测的高效特征组排序