M.: Efficient feature group sequencing for anytime linear prediction. arXiv:1409.5495

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 struc-ture 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 ap-proach 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[7], an anytime prediction performance metric, while providing rigorous performance guarantees.