  The presence of missing values makes supervised learning much more
challenging. Indeed, previous work has shown that even when the response is a
linear function of the complete data, the optimal predictor is a complex
function of the observed entries and the missingness indicator. As a result,
the computational or sample complexities of consistent approaches depend on the
number of missing patterns, which can be exponential in the number of
dimensions. In this work, we derive the analytical form of the optimal
predictor under a linearity assumption and various missing data mechanisms
including Missing at Random (MAR) and self-masking (Missing Not At Random).
Based on a Neumann-series approximation of the optimal predictor, we propose a
new principled architecture, named NeuMiss networks. Their originality and
strength come from the use of a new type of non-linearity: the multiplication
by the missingness indicator. We provide an upper bound on the Bayes risk of
NeuMiss networks, and show that they have good predictive accuracy with both a
number of parameters and a computational complexity independent of the number
of missing data patterns. As a result they scale well to problems with many
features, and remain statistically efficient for medium-sized samples.
Moreover, we show that, contrary to procedures using EM or imputation, they are
robust to the missing data mechanism, including difficult MNAR settings such as
self-masking.
