The Limits of Learning with Missing Data
Authors: Brian Bullins, Elad Hazan, Tomer Koren
NeurIPS 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. In this paper we show, for the first time, that in fact this problem cannot be solved in general. Our main result shows that even for regression with the absolute loss function, for any k d 1, there is an information-theoretic lower bound on the error attainable by any algorithm. |
| Researcher Affiliation | Collaboration | Brian Bullins Elad Hazan Princeton University Princeton, NJ {bbullins,ehazan}@cs.princeton.edu Tomer Koren Google Brain Mountain View, CA tkoren@google.com |
| Pseudocode | Yes | We provide the pseudo-code in Algorithm 1. Algorithm 1 General algorithm for regression/classification with missing attributes |
| Open Source Code | No | No, the paper does not provide any concrete access information for its source code. |
| Open Datasets | No | No, the paper does not provide concrete access information for a publicly available dataset. The paper discusses distributions but not specific datasets for empirical training. |
| Dataset Splits | No | No, the paper does not provide specific dataset split information. |
| Hardware Specification | No | No, the paper does not provide specific hardware details. |
| Software Dependencies | No | No, the paper does not provide specific ancillary software details. |
| Experiment Setup | No | No, the paper does not contain specific experimental setup details. |