Skip to main content

The Limits of Learning with Missing Data

Author(s): Bullins, Brian; Hazan, Elad; Koren, Tomer

To refer to this page use:
Abstract: We study regression and classification in a setting where the learning algorithm is allowed to access only a limited number of attributes per example, known as the limited attribute observation model. In this well-studied model, we provide the first lower bounds giving a limit on the precision attainable by any algorithm for several variants of regression, notably linear regression with the absolute loss and the squared loss, as well as for classification with the hinge loss. We complement these lower bounds with a general purpose algorithm that gives an upper bound on the achievable precision limit in the setting of learning with missing data.
Publication Date: 2016
Citation: Bullins, Brian, Elad Hazan, and Tomer Koren. "The Limits of Learning with Missing Data." In Advances in Neural Information Processing Systems 29 (2016).
Type of Material: Conference Article
Journal/Proceeding Title: Advances in Neural Information Processing Systems
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.