A Theoretical and Practical Framework for Regression and Classification from Truncated Samples

Andrew Ilyas, Emmanouil Zampetakis, Constantinos DaskalakisAISTATS 2020 · OpenReview

Abstract: Machine learning and statistics are invaluable for extracting insights from data. A key assumption of most methods, however, is that they have access to independent samples from the distribution of interest. In many real-world scenarios, data is truncated: samples are missing because their outcomes fell outside a specific observation window. This paper introduces a general framework that uses Stochastic Gradient Descent (SGD) to recover true model parameters from this biased data, providing the first efficient theoretical guarantees for truncated logistic and probit regression.

The Challenge of Truncated Data

Most machine learning algorithms rely on the "i.i.d. assumption," assuming training data is a representative, independent sample of the real world. However, data is often truncated—filtered based on the value of the dependent variable. Unlike "censoring," where the existence of a missing sample is known, truncation is "silent"; the researcher doesn't know the missing samples ever existed.

The effect of truncation on regression. Standard models (dashed line) become biased when samples below a threshold (red line) are removed, failing to recover the true relationship (dotted line).

Standard techniques like Ordinary Least Squares (OLS) or maximum likelihood estimation produce significantly biased results in these scenarios. For instance, if a study on IQ and income only includes participants below a certain poverty line, a standard model might incorrectly conclude that IQ has little impact on earnings because the high-IQ, high-income individuals are missing.

A General Framework for Truncated Learning

The authors propose a framework for learning from truncated data by maximizing the population log-likelihood of the truncated samples.

  1. Modified Likelihood: They derive a log-likelihood function that explicitly accounts for the filtering mechanism (the rule deciding which samples are kept).
  2. Optimization via SGD: The gradient of this likelihood function can be estimated by taking expectations over the model's noise distribution, enabling the use of standard Stochastic Gradient Descent (SGD).
  3. Theoretical Guarantees:
  4. For Probit Regression (Gaussian noise), the objective is shown to be strongly convex, ensuring SGD finds the global optimum.
  5. For Logistic Regression, the objective is strictly locally quasi-concave (SLQC). This is a major theoretical contribution, explaining why specialized SGD can still converge to the correct solution despite non-concavity.

Experimental Validation and Deep Learning Success

The framework was tested across synthetic data, the UCI Million Song Dataset, and CIFAR-10. In synthetic environments, the algorithm recovered true parameters with near-perfect cosine similarity, even under severe truncation. On the Million Song Dataset, the truncation-aware model maintained high test accuracy as training data became increasingly biased.

Performance on image rotation prediction (CIFAR-10). Truncated regression (red) maintains lower MSE and higher accuracy compared to standard regression (blue) as noise and truncation severity increase.

A key finding is the framework's compatibility with deep learning. In the CIFAR-10 rotation task, a ResNet-50 integrated with the truncation-aware loss maintained low Mean Squared Error (MSE) and high accuracy even when the training set only contained half of the possible rotation angles. This suggests the framework is broadly applicable beyond the linear models for which the theory was originally developed.

Limitations and Future Directions

The current framework assumes the "observation window" (the filtering function) is known. In many real-world cases, the exact boundaries of missing data might be unknown. Additionally, the method requires choosing a noise distribution; performance may degrade if the real-world noise differs significantly from the assumed distribution. Future research could focus on learning the truncation window itself or estimating unknown noise variance.

Summary updated

Abstract

Machine learning and statistics are invaluable for extracting insights from data. A key assumption of most methods, however, is that they have access to independent samples from the distribution of...
BibTeX
@inproceedings{ilyas2020theoretical,
  author = {Andrew Ilyas and Emmanouil Zampetakis and Constantinos Daskalakis},
  title = {{A Theoretical and Practical Framework for Regression and Classification from Truncated Samples}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=-QttjhMl1Qp},
}

Loading related content...

Figure