Classification with Low Rank and Missing Data

Abstract

We consider classification and regression tasks where we have missing data and assume that the (clean) data resides in a low rank subspace. Finding a hidden subspace is known to be computationally hard. Nevertheless, using a non-proper formulation we give an efficient agnostic algorithm that classifies as good as the best linear classifier coupled with the best low-dimensional subspace in which the data resides. A direct implication is that our algorithm can linearly (and non-linearly through kernels) classify provably as well as the best classifier that has access to the full data.

References in corpus (3)

• Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
• Near-Optimal Algorithms for Online Matrix Prediction
• Linear Regression with Limited Observation

Cited by in corpus (9)

• Handling Missing Data with Graph Representation Learning
• Processing of missing data by neural networks
• Semi-supervised Deep Generative Modelling of Incomplete Multi-Modality Emotional Data
• Why Not to Use Zero Imputation? Correcting Sparsity Bias in Training Neural Networks
• MisConv: Convolutional Neural Networks for Missing Data
• Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
• On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes
• Cloned Identity Detection in Social-Sensor Clouds based on Incomplete Profiles
• Learning from Incomplete Features by Simultaneous Training of Neural Networks and Sparse Coding