Efficient Feature Group Sequencing for Anytime Linear Prediction

Hanzhang Hu Carnegie Mellon University, Alexander Grubb, J. Andrew Bagnell, Martial Hebert
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:246-255, 2016.

Abstract

We consider \textit{anytime} linear prediction in the common machine learning setting wherefeatures are in groups that have costs. We achieve anytime or interruptible predictions by sequencing computation of feature groups andreporting results using the computed features at interruption. We extend Orthogonal Matching Pursuit (OMP) and Forward Regression (FR) to learn the sequencing greedily under this group setting with costs. We theoretically guarantee that our algorithms achieve near-optimal linear predictions at each budget when a feature group is chosen. With a novel analysis of OMP, we improve its theoretical bound to the same strength as that of FR. In addition, we develop a novel algorithm that consumes cost $4B$ to approximate the optimal performance of \textit{any} cost $B$, and prove that with cost less than $4B$, such an approximation is impossible. To our knowledge, these are the first anytime bounds at \textit{all} budgets. We experiment our algorithms on two real-world data-sets and evaluate them in terms of anytime linear prediction performance against cost-weighted Group Lasso, and alternative greedy algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-university16f, title = {Efficient Feature Group Sequencing for Anytime Linear Prediction}, author = {University, Hanzhang Hu Carnegie Mellon and Grubb, Alexander and Bagnell, J. Andrew and Hebert, Martial}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {246--255}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/university16f/university16f.pdf}, url = {https://proceedings.mlr.press/r14/university16f.html}, abstract = {We consider \textit{anytime} linear prediction in the common machine learning setting wherefeatures are in groups that have costs. We achieve anytime or interruptible predictions by sequencing computation of feature groups andreporting results using the computed features at interruption. We extend Orthogonal Matching Pursuit (OMP) and Forward Regression (FR) to learn the sequencing greedily under this group setting with costs. We theoretically guarantee that our algorithms achieve near-optimal linear predictions at each budget when a feature group is chosen. With a novel analysis of OMP, we improve its theoretical bound to the same strength as that of FR. In addition, we develop a novel algorithm that consumes cost $4B$ to approximate the optimal performance of \textit{any} cost $B$, and prove that with cost less than $4B$, such an approximation is impossible. To our knowledge, these are the first anytime bounds at \textit{all} budgets. We experiment our algorithms on two real-world data-sets and evaluate them in terms of anytime linear prediction performance against cost-weighted Group Lasso, and alternative greedy algorithms.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Efficient Feature Group Sequencing for Anytime Linear Prediction %A Hanzhang Hu Carnegie Mellon University %A Alexander Grubb %A J. Andrew Bagnell %A Martial Hebert %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-university16f %I PMLR %P 246--255 %U https://proceedings.mlr.press/r14/university16f.html %V R14 %X We consider \textit{anytime} linear prediction in the common machine learning setting wherefeatures are in groups that have costs. We achieve anytime or interruptible predictions by sequencing computation of feature groups andreporting results using the computed features at interruption. We extend Orthogonal Matching Pursuit (OMP) and Forward Regression (FR) to learn the sequencing greedily under this group setting with costs. We theoretically guarantee that our algorithms achieve near-optimal linear predictions at each budget when a feature group is chosen. With a novel analysis of OMP, we improve its theoretical bound to the same strength as that of FR. In addition, we develop a novel algorithm that consumes cost $4B$ to approximate the optimal performance of \textit{any} cost $B$, and prove that with cost less than $4B$, such an approximation is impossible. To our knowledge, these are the first anytime bounds at \textit{all} budgets. We experiment our algorithms on two real-world data-sets and evaluate them in terms of anytime linear prediction performance against cost-weighted Group Lasso, and alternative greedy algorithms. %Z Reissued by PMLR on 04 October 2026.
APA
University, H.H.C.M., Grubb, A., Bagnell, J.A. & Hebert, M.. (2016). Efficient Feature Group Sequencing for Anytime Linear Prediction. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:246-255 Available from https://proceedings.mlr.press/r14/university16f.html. Reissued by PMLR on 04 October 2026.

Related Material