The Limits of Learning with Missing Data

Brian Bullins, Elad Hazan, Tomer KorenNeurIPS 2016 · OpenReview

Can you build a perfect machine learning model if you only ever see a fraction of the data for each individual example? According to this research, for many common machine learning tasks, the answer is a definitive "no." Even with infinite training data, if you are restricted to observing fewer than all attributes per sample, there is a fundamental "precision floor" you simply cannot cross.

The Challenge of Incomplete Data

In classical machine learning, we usually assume access to a complete feature vector for every training instance. However, in the real world—such as in medical diagnostics—collecting every possible data point for every patient is often too expensive, invasive, or time-consuming.

This paper investigates the Limited Attribute Observation (LAO) model. In this setting, a learner can only observe at most $k$ attributes out of a total of $d$ for any given example. While previous research showed that linear regression with squared loss could be solved to arbitrary precision if $k \ge 2$, it remained unclear if this was true for other loss functions or for the extreme case where $k=1$. The authors set out to find the "information-theoretic" limits: is there a point where no amount of data or computing power can make a model more accurate?

Methodology

To establish these limits, the researchers rely on mathematical proofs to define lower bounds (impossibility results) and an upper bound (a constructive algorithm).

  1. Indistinguishability Proofs: To prove a lower bound, the authors construct two different data distributions that appear identical to any algorithm that can only see $k$ attributes. Because the "optimal" solutions for these two distributions are far apart, but the algorithm cannot distinguish between them, it is guaranteed to incur a minimum level of error on at least one.
  2. Subgradient Analysis: For the absolute loss function (which is harder to analyze than squared loss because it is not "smooth"), the authors use properties of subgradients and "directional strong convexity" to show that the error grows as the dimension of the data increases.
Geometric illustration of subgradient analysis
  1. Algorithm Design: They introduce a general-purpose algorithm—a variation of Stochastic Gradient Descent—that works with missing data by using a slightly biased gradient estimator. This provides an upper bound on how much error a learner must suffer.

(Note: As a theoretical paper, this work relies on synthetic, adversarial distributions specifically designed to demonstrate the limits of learning, rather than real-world datasets.)

Key Insights and Results

The paper reveals several critical insights about the nature of learning under the LAO model:

  • The "Precision Floor": The most significant insight is that for absolute loss (L1) and hinge loss (used in Support Vector Machines), you cannot reach zero error if you see $d-1$ or fewer attributes. There is a constant $\epsilon_0$ that represents the best possible accuracy any algorithm can ever achieve.
  • Squared Loss is "Easier": The paper confirms that for squared loss, you only need to see 2 attributes per example to eventually reach perfect accuracy. If you only see 1, however, you are stuck with a precision limit.
  • The Hardness of Classification: For classification using hinge loss, the "impossibility" is even more severe. The lower bound on error scales exponentially with the dimension of the data, suggesting that learning with missing data is significantly harder for classification than for regression. The authors established the first lower bound for classification in the LAO setting, showing that arbitrary precision is impossible if $k < d$.
  • Biased Gradients Work: Usually, we want "unbiased" estimators in machine learning. The authors show that in the missing data setting, using a carefully chosen biased estimator can still yield a model that gets reasonably close to the information-theoretic limit.
  • General Algorithm Performance: The proposed algorithm achieves an expected loss of $O(1/\sqrt{d})$ away from the optimum when observing $k = d-1$ attributes. This effectively "brackets" the problem between the lower bound and this achievable upper bound.
  • Absolute Loss (Regression) Limits: For any $k \le d-1$, there is a lower bound on error of $\Omega(d^{-3/2})$. You cannot get more accurate than this, no matter how many samples you have.

Future Directions

The authors note a "polynomial gap" between their lower bounds and the performance of their proposed algorithm. While they proved that a limit exists, they haven't yet found the exact value of that limit for all scenarios. Future research directions include refining the bounds to find exactly how much precision is lost for every missing attribute, extending these proofs to other popular loss functions like logistic loss, and investigating why classification is so much harder than regression in this setting.

Summary updated

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.
BibTeX
@inproceedings{bullins2016limits,
  author = {Brian Bullins and Elad Hazan and Tomer Koren},
  title = {{The Limits of Learning with Missing Data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=H1bcNv-_-S},
}

Loading related content...

Figure