Online and Batch Learning Algorithms for Data with Missing Features

Afshin Rostamizadeh, Alekh Agarwal, Peter Bartlett
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:701-713, 2011.

Abstract

We introduce new online and batch algorithms that are robust to data with missing features, a situation that arises in many practical applications. In the online setup, we allow for the comparison hypothesis to change as a function of the subset of features that is observed on any given round, extending the standard setting where the comparison hypothesis is fixed throughout. In the batch setup, we present a convex relation of a non-convex problem to jointly estimate an imputation function, used to fill in the values of missing features, along with the classification hypothesis. We prove regret bounds in the online setting and Rademacher complexity bounds for the batch i.i.d. setting. The algorithms are tested on several UCI datasets, showing superior performance over baselines.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-rostamizadeh11a, title = {Online and Batch Learning Algorithms for Data with Missing Features}, author = {Rostamizadeh, Afshin and Agarwal, Alekh and Bartlett, Peter}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {701--713}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/rostamizadeh11a/rostamizadeh11a.pdf}, url = {https://proceedings.mlr.press/r9/rostamizadeh11a.html}, abstract = {We introduce new online and batch algorithms that are robust to data with missing features, a situation that arises in many practical applications. In the online setup, we allow for the comparison hypothesis to change as a function of the subset of features that is observed on any given round, extending the standard setting where the comparison hypothesis is fixed throughout. In the batch setup, we present a convex relation of a non-convex problem to jointly estimate an imputation function, used to fill in the values of missing features, along with the classification hypothesis. We prove regret bounds in the online setting and Rademacher complexity bounds for the batch i.i.d. setting. The algorithms are tested on several UCI datasets, showing superior performance over baselines.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Online and Batch Learning Algorithms for Data with Missing Features %A Afshin Rostamizadeh %A Alekh Agarwal %A Peter Bartlett %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-rostamizadeh11a %I PMLR %P 701--713 %U https://proceedings.mlr.press/r9/rostamizadeh11a.html %V R9 %X We introduce new online and batch algorithms that are robust to data with missing features, a situation that arises in many practical applications. In the online setup, we allow for the comparison hypothesis to change as a function of the subset of features that is observed on any given round, extending the standard setting where the comparison hypothesis is fixed throughout. In the batch setup, we present a convex relation of a non-convex problem to jointly estimate an imputation function, used to fill in the values of missing features, along with the classification hypothesis. We prove regret bounds in the online setting and Rademacher complexity bounds for the batch i.i.d. setting. The algorithms are tested on several UCI datasets, showing superior performance over baselines. %Z Reissued by PMLR on 04 October 2026.
APA
Rostamizadeh, A., Agarwal, A. & Bartlett, P.. (2011). Online and Batch Learning Algorithms for Data with Missing Features. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:701-713 Available from https://proceedings.mlr.press/r9/rostamizadeh11a.html. Reissued by PMLR on 04 October 2026.

Related Material