What’s a good imputation to predict with missing values?
Authors: Marine Le Morvan
Julie Josse
Erwan Scornet
Gael Varoquaux
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: missing values
neural networks
Bayes optimality
consistency

Abstract: How to learn a good predictor on data with missing values? Most efforts focus on first imputing as well as possible and second learning on the completed data to predict the outcome. Yet, this widespread practice has no theoretical grounding. Here we show that for almost all imputation functions, an impute-then-regress procedure with a powerful learner is Bayes optimal. This result holds for all missing-values mechanisms, in contrast with the classic statistical results that require missing-at-random settings to use imputation in probabilistic modeling. Moreover, it implies that perfect conditional imputation is not needed for good prediction asymptotically. In fact, we show that on perfectly imputed data the best regression function will generally be discontinuous, which makes it hard to learn. Crafting instead the imputation so as to leave the regression function unchanged simply shifts the problem to learning discontinuous imputations. Rather, we suggest that it is easier to learn imputation and regression jointly. We propose such a procedure, adapting NeuMiss, a neural network capturing the conditional links across observed and unobserved variables whatever the missing-value pattern. Our experiments confirm that joint imputation and regression through NeuMiss is better than various two step procedures in a finite-sample regime.  

What's a good imputation to predict with missing values?
Marine Le Morvan 12
Julie Josse*
Erwan Scornet
Gaël Varoquaux'
Université Pacis-Saclay, Inria, CEA, Palaiseau, 91120, France
Université Paris-Saclay, CNRS/IN2P3, IICLab, 91405 Orsay, France CMAP, UMR7641, Ecole Polytechnique, IP Paris, 91128 Palaiseau, France Inria Sophia-Antipoliis Montpellier, France
(marine. le le-morran, julie. josse, gael. varoquaux)@inria eww..ssorrattpoolyyeedmig..ee edu
Abstract
How to learn a good predictor on data with missing values? Most efforts focus first imputing well possible and second learning the completed data predict the outcome. Yet, this widespread practice has no theoretical grounding. Here show that for almost all imputation functions, an impute-then then-regress procedure with a powerful learner is Bayes optimal. This result holds for all missing-values mechanisms, in contrast with the classic statistical results that require missing-at-random settings to use imputation in probabilistic modeling. Moreover, implies that perfect conditional imputation is not needed for good prediction asymptotically. In fact, we show that on perfectly imputed data the best regression function will generally be discontinuous, which makes it hard to learn. Crafting instead the imputation so as to leave the regression function unchanged simply shifts the problem learning discontinuous imputations. Rather, we suggest that it is easier to learn imputation and regression jointly. We propose such procedure, adapting NeuMiss, a neural network capturing the conditional links across observed and unobserved variables whatever the missing-value pattern. Experiments confirm that joint imputation and regression through NeuMiss is better than various two step procedures in our experiments with finite number of samples.
Introduction
Data with missing values are ubiquitous in many applications, as in health or business: some observations come with missing features. There is rich statistical literature imputation well as inference with missing values [Rubin] 1976 Little and Rubin 1987, 2002, 2019]. Most of the theory and practices build upon the Missing At Random (MAR) assumption that allows maximize the likelihood of observed data while ignoring the missing-valen valuus mechanism, for instance using expectation maximization [Dempster al. 1977]. On the contrary, Missing Not At Random settings, where missingness depends on the unobserved values, may not be identifiable and require dedicated methods with model of the missing-valus mechanism.
Learning predictive models with missing values poses distinct challenges compared to inference tasks [ooss et al.) 2019.. Indeed, when the input an arbitrary subset of variables in dimension there are 2d potential missing data patterns and as many sub-models to learn. Consequently, even simple data-generating mechanisms lead to complex decision rules [Le Morvan et al., 2020b). To date, there are few supervised-learmi models natively suited for partially-observed data. A notable
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

exception is found with tree- rree-based models [Twala et al., 2008 Chen and Guestrin 2016 widely used in data-science practice.
The most common practice however remains by far to use off-the-shelf methods first for imputation of missing values and second for supervised-leand -earnind on the resulting completed data. Such procedure may benefit from progress in missing-value value imputation with machine learning [van Buuren 2018 Yoon et al. 2018 Mattei and Frellsen 2019]. However, there a lack of learning theory to support such Impute-then- Regress procedures: Under what conditions are they Bayes consistent? Which aspects of the imputation are important?
There is empirical realization that the choice of imputation matters for predictive performance. The NADIA R package [Borowski and Fic] can select an imputation method to minimize a prediction on test set. Auto-ML is used to optimize full pipelines, including imputation [eg Jarrett et al. 2021] Ipsen et al. [2200] optimize a constant imputation for supervised learning. However, the imputation is only weakly guided by the target in these approaches, it is set either from family of black-box methods using gradient-fre free model selection, or from trivial imputation functions. In addition, there is lack of insight what drives good imputation for prediction.
We contribute systematic analysis of Impute-the-Regres procedures in general setting: non-linear response function and any missingness mechanism (no MAR assumptions). We show that:
Impute-then- Regress procedures are Bayes optimal for all missing data mechanisms and for almost all imputation functions, whatever the number of variables that may missing. This very general result gives theoretical grounding to such widespread procedures.
the oracle imputation by the conditional expectation and oracle regression function on the complete data. We show that chaining these oracles is not Bayes optimal in general and quantify its excess risk. We show that both cases, choosing an oracle for one step, imputation or regression, imposes discontinuities on the other step, thus making it harder to learn.
We study "natural" choices of imputation and regression functions:
As these results suggest that imputation and regression should be adapted to one another, contribute a method that jointly optimizes imputation and regression, using NeuMiss networks [Le Morvan al. 2020al differentiable imputation procedure.
We compare empirically number of Impute-then thpute-then-Regress procedures simulated non- non-linear regression tasks. Joint optimization of both steps provides the best performance.
2 Problem setting
Notations We consider dataset of i.i.d. realizations of the random variable (X, Rd (0, 13. x IR where X are the complete covariates, M missingness indicator, and Y a response of interest. For each realization (xc, m. y), m, = 1 indicates that x, is missing, and m,- = 0 that it is observed. We denote by missmm) C [1,d] dl] the indices corresponding to the missing covariates (and similarly obs(mn) the observed indices), so that Foba(m) corresponds to the entries actually observed.
We define the incomplete covariate vector X E (IR U (NA))* as X, = X, if Mj = and X, = NA otherwise, where NA represents a missing value.
Assumptions We assume that X admits density Ie and that, for all j E [1, d]l, each compo- nent Xú has finite expectation and variance, that is E [x2] < co. Moreover, we assume that the response Y is generated according to:
Y f*XX)++ +. with E. [c|X (M) M] = and E [Y
<
(1)
where fr Rd + F is function of the complete input data X, E R is a random noise vari- able.
2.1 Supervised learning with missing values
Optimization problem In practice, in the presence of missing values, we do not have access to the complete data (X, M. Y) but only the subset of it that is observed, i.c. (Xobs(M)- M, Y). Thus instead of learning a mapping from Rd to R. we need to learn a mapping from (R U (NA))* to R, where the set of observed covariates can be any subset of [1, d]]. It is this unusual input space, partly discrete, that makes supervised learning with missing values challenging and different from classical

---

supervised learning problems. Formally, the optimization problem we wish to solve is:
R(f) : E xx f(
min (:()
(2)
Bayes predictor
The function which minimizes 2 called the Bayes predictor, is given by:
(x) = E [o| M
EE [f (x))
(3)
As X is function of Xobs and M, will sometimes slightly abuse notations and write (X)
f (Xoos M). The risk of the Bayes predictor is called the Bayes risk, which we denote R*. It is the lowest achievable risk for given supervised learning problem.
Definition (Bayes optimality). A Bayes function f achieves the Bayes rate, i.e, R()) = R function
As can be seen from 3 the Bayes predictor is function of M, discrete random variable that can take one of 24 values since M E [0, The function f can thus be viewed as 2d different functions, one for each possible subset of variables. This view raises questions that are central to this paper: How should we parametrize functions on such input domains? And which function families should we consider to approximate f*? These questions have been studied in the case where f is assumed to be a linear function, and X follows Gaussian distribution. Indeed, under these assumptions, Le Morvan et al. 2020bba al have derived analytical expressions for the Bayes predictor and deduced appropriate parametric estimators. However, aside from specific cases, it is impossible to derive an analytical expression for the Bayes predictor, and novel arguments are needed to understand which classes of functions should be considered in general.
3 Asymptotic analysis of Impute-then-regres procedures
3.1 Impetesthen-regreess procedures
Let (mis(m)) (resp. (obs(m)) () be the number of missing entries (resp. observed) for any missing data pattern m.. For each m E {0, 13dd, we define an imputation function (((m) IR [globe(m]] + [mm)s(m)) which outputs values for the missing entries based on the observed ones. We denote by of!" Rlohs(m)) + R the component function of (f(m) that imputes the j-th component in X if is missing. Classical choices of imputation functions include constant functions linear functions. Finally, we introduce the family of functions JFl that transform an incomplete vector into a complete one, precisely:
Xj (Xooo())))))
if Mj =
F
④ (RU (RU (NA))" + Rd Vj [1,d] 2x
(4)
if M, =1
Let us define F'C in the exact same way but for imputation functions ((m) E C for all m E {0, 1]d. Here study impute-then-regres, procedures, which define two-step procedures where the data is first imputed using a function /b E F', and then a regression is performed on the imputed data. Such procedure is quite natural to deal with arbitrary subsets of inputs variables. It embeds the data into Rd to reduce the problem to a classical one. In practice, impute-then-regred widely used. However, the choice of function class is far mostly ad-hoc and raises multiple questions: How close to the Bayes rate can functions obtained via such procedures be? Should we prefer some choices of imputation functions over others? What happens when the missing data mechanism is missing not at random? In this section, we will give answers to these questions.
procedures
Below, we write obs (resp. mis) instead of obs (resp. mi)( to lighten notations.
3.2 Impute-then-regres procedures are Bayes optimal
R(fm) = R Definition (Universal consistency). An estimator fn Bayes consistent if lim,, It is said to be universally consistent if the previous statement holds for all distributions of Y).
The following theorem shows that Impute-then-regres, all imputation functions. In other words, it means that a universal learner trained on imputed data provides optimal performances asymptotically for almost all imputation functions, Let us now define,
procedures are Bayes optimal for almost
(r go xx(())
for all imputation functions & E Fl, the function 9 E argmin
E
g
3

---

Theorem 3.1 (Bayes consistency of Impute-ther sealte-the--rgggeee regress procedures). Assume the data is generated according to T Then, for almost all imputation function & E F the function g Bayes optimal. In other words, for almost all imputation functions & Fos a universally consistent algorithm trained on the imputed data (X) is Bayes consistent.
Appendix gives the proof. Theorem 3.1 states a very general result: Impute-then-regress procedures are Bayes consistent for all missing data mechanisms, almost all imputation functions, regardless of the distribution of (X, Y) and the number of missing covariates. Since Theorem 3.1 holds for almost all imputation functions, it implies that good imputations are not required obtain good predictive performances, at least asymptotically. Note that here, the notion of almost all is to be understood in its topological sense, and not its measure theory sense. Moreover, this theorem does not make any assumption on the missing data mechanism, and is therefore valid for Missing Not At Random (MNAR) data. This contrasts with most methods for inference and imputation with missing values, valid only for MAR data. Finally, the theorem remains valid for any configuration of variables that may contain missing values, including the case in which all variables may contain missing values. Bayes consistency of Empute-the-Regred
procedures has already been studied, but in much more restricted settings. Josse et al. [2019] proved that such procedures are Bayes consistent under the MAR assumption, for constant imputations functions and for only one potentially missing variable. Bertsimas al.] 202T] refined this result to almost surely continuous imputation functions. While
these two prior works build very similar proofs, use here very different arguments summarized in the next paragraph.
The first key idea of the proof is that, after imputation, all data points with a given missing data pattern m are mapped to a manifold M(m) of dimension [obs(m)). For example 3D, data points mapped to RR when completely observed, to 2D manifolds when they have one value missing, to ID manifolds when they have two values missing, and to one point when all values are missing (see Fi Thus, Impute-thert Reeness procedures first map data points various manifolds depending on their missing data patterns and then apply a prediction function defined on the whole space including manifolds. The second key idea of the proof is to ensure that the original missing data patterns of imputed points can almost surely be identified. For this, the proof requires that all manifolds of the same dimension pairwise transverse. This assumption is sufficient, though not necessary, to ensure that the intersection of two manifolds of dimension [obs(m)] cannot itself be of dimension (ob)(m)) Transversality is weak assumption. In fact, Thom's transversality theorem, (which we rely on in our proof) says that it is a generic property: it holds for "typical examples", i.e almost all imputation functions will lead to transverse manifolds. To clarify this concept, we provide a particular case in 2D where ID manifolds are not transverse in Appendix A.4
The proof is constructive and exhibits function 94. which achieves the Bayes rate for a given set of imputation functions. For each manifold ((m)), ordered from smallest dimension to largest, require that 9 on (m)) equals the Bayes predictor for missing data pattern m except on points for which d has already been defined, i.e, the points where (m() intersects with the manifolds ranked before it. Thus, we obtain a function g that does not depend on m, and which for each manifold, equals the Bayes predictor except subsets of measure zero under the assumption that manifolds of the same dimension are pairwise transverse. Refer to appendix A.3 for more details.
Figure I: Example Imputation manifolds in three dimensions - 3-dimensional Gaussian data after imputation. Data points are colored according to their missing data pattern prior to imputation. Red, brown and purple (resp. orange, blue, and green) cor- respond to missing data patterns with two (resp. one) missing value(s). Completely observed points are not represented to ease the visualization of manifolds.
t1
X2

---

While this theorem is very general result, it does not say what the optimal function associated to given imputation looks like. In fact, depending on the imputation function may be non-continuous. vary widely, and require a very large number of samples to be approximated.
Note on Impute-then-classify procedures- Theorem 3.1 applies to regression problems. However, can easily be shown that a similar result holds in binary classification settings. Indeed, in a binary classification setting, the Bayes predictor predicts class I if P(Y = 1|X) > 0.5 and -1 otherwise. Thus, suffices to consider that the function of interest (xX is the posterior probability P(Y = 1(x). Then the same arguments as those used to prove Theorem 3.1 can be used to show that Impute-then then-elass----s-yy procedures are Bayes optimal for almost all imputation functions.
4 Imputation versus regression: choosing one may break the other
Theorem gives theoretical grounding Impute-tten--regees procedures. As it holds for almost any imputation functiinn, one could very well choose simple and cheap imputations such as imputing by constant. However, the difficulty of the ensuing learning problem will depend the choice of imputation function. Indeed, the function 9 that achieves the Bayes rate depends on the imputation function +. In general, it may not be continuous smooth. Thus g be more less difficult to approximate by machine learning algorithms depending on the chosen imputation function.
Le Morvan et al. 2020b showed that even if Y is linear function of X, imputing by a constant leads to a complicated Bayes predictor: piecewise affine but with 24 regions. This result highlights how imputations neglecting the structure of covariates can result in additional complexity for the regression function ga. Rather, another common practice is to impute by the conditional expectation: it minimizes the mean squared error between the imputed matrix and the complete one and is the target of most imputation methods, One hope may be that if f has desirable properties, such as smoothness, conditional imputation will lead to function 9 which inherits from these properties.
In this section we first show that replacing missing values by their conditional expectation in the oracle regression function f* gives small but non-zero risk. Characterizing the optimal function on the conditionalll-imputed data, we find that it suffers from discontinuities and thus forms a difficult estimation problem. Rather, we study whether the imputation can be corrected for f* to form the Bayes predictor on partially-observed data.
4.1 Applying f* on conditional imputations: chaining oracles isn't without risks.
The conditional imputation function ΦC1, :(R U (NAH)* - Rdd is defined as follows:
X [X M] if M, =
if M,
Vj E [1, of = E
Note that CJ E Fl. To lighten notations, we will write == imputed data.
-CC((T to denote the conditionally
Lemma 4.1 (First order approximation), Assume that the data is generated according to ( More- over assume that (i) 1 E C²(S,RR RR) where S C. R&d the support of the data, and that (ūi) there exists positive semidefnite matrices H Pt and H PJ such that for all X in S. H $ H(X) & H+ with H(X the Hessian of 8 at X. Then for all X in S and for all missing data patterns:
1
tr (H (imismmis Emiisjobs S (x - tr (imis/oe,sm))))
(5)
where Emislobe,M is the covariance matrix of the distribution of Xmis given Xabs and M.
Appendix A.6 gives the proof. The assumption that H & H(X) & H for any X means that the minimum and maximum curvatures of f" in any direction are uniformly bounded over the entire space. Lemma shows that applying f* to the conditionally imputed (CI) data is a good approximation of the Bayes predictor when there is no direction which both the curvature of I and the conditional variance of the missing data given the observed one are high. Intuitively, if a low quality imputation compensated by a flat function, or conversely, if a fast varying function is compensated by a high quality imputation, then f applied to the CI data approximates well the Bayes predictor.
5

---

Proposition 4.1 (NNon-YConsises (Consistecyy of chaining oracles). The function f o &CT is Bayes optimal if and only if the function f* and the imputed data X satisfy:
VM s.I. P(M) >
(X) M] - (Xx1) almost everywhere.
(6)
Besides, under the assumptions of Lemma 4.1 the excess risk of chaining oracles compared to the Bayes risk R is upper-bounded by:
1 S EM max trr (H miiie.mis Emis lobs, 15) tr
H meie. Emis jobs, Mf ) (7)
R(f o
Appendix A.7 gives the proof. Condition 6 for Bayes optimality is clearly stringent. Indeed, if one variable is missing, condition 6 says that the expectation of the regression function should be equal to the regression function applied at the expected entry. Although such functions difficult to characterize precisely, is clear that condition (6) is difficult to fulfill for generic regression functions (linear functions are among the few examples that do satisfy it). Therefore, for most functions f*, f &C' is not Bayes optimal. Proposition 4.1 also gives an upper bound for the excess risk of the predictor f* C1) compared the Bayes rate, showing here again that if there is no direction in which both the curvature and the variance of the missing data given the observed one are high, the excess risk is small.
The special case of linear regression: When I is a linear function, the curvature is 0. hence eq. implies excess risk. This is also visible from the expression of the Bayes predictor B where the expectation on unobserved data can be pushed inside f* as it is linear. The Bayes predictor can thus be exactly written f* applied conditionally-mmpun
data.
4.2 Regressing on conditional imputations, a good idea?
Proposition 4.2 (Regression function discontinuities). Suppose that f o ΦCT is not Bayes optimal, and that the probability of observing all variables strictly positive, i.e., for all x, P(M = (0,....0), X r) 0. Then there is no continuous function g such that g &01 is Bayes optimal.
In other words, when conditional imputation is used, the optimal regression function experiences discontinuities unless is f". The proof is given in appendix A.8 From a finite-sample learning standpoint, discontinuous functions are in general harder to learn: in the general case, non-parametric regression requires more samples to achieve given error on functions without specific regularities as opposed to functions with form of smoothness [see e.g., Györfi al. 2006 chap 3]. Hence, while regression on conditional imputation may be consistent Theorem 3.1) it can require an inordinate number of samples.
4.3 Fasten your seat belt: corrected imputations may experience discontinuities.
Another possible route is to find corrected imputations which we define as imputation functions & such that, if f is used as regression function, the peuute--the--egress procedure f* o Φ is Bayes optimal. Intuitively, given a fixed regression function f*, the question is: can we "correct" an imputation function and thus the manifold that it describes so that f restricted to this manifold is equal to the Bayes predictor? Assuming f is continuous, the intermediate value theorem gives a first answer to this question by ensuring the existence of imputations functions satisfying
f T (Xots((M) M) E (X)) Xobs M].
For the same reasons as above, determining that such imputations not only exist but continuous is important from a practical perspective. Indeed, assuming f" is continuous, the Bayes predictor with missing values could then be tackled as the composition of two continuous functions, with an Impute-then-Ree
strategy. Intuitively in 2D, the existence of a continuous corrected imputation can be seen as the existence of continuous path in the 2D plane whose value by f* equals the Bayes predictor. Figure 2 (left) gives a simple example in 2D for which continuous corrected imputation exists. Here if one chooses the imputation function of X2 given X, as the black function denoted as & Pcorrected, then its composition by the green paraboloid f" gives the Bayes Predictor depicted on the right black. By contrast, if one imputes by the conditional expectation, then composition with I" gives the red curve which is different from the Bayes Predictor. Note that the manifolds in Figure l were obtained using (continuous) corrected imputations functions for the same setting as Figure (left) but with 3-dimensional data. However, as illustrated in Figure (right), continuous corrected

---

Bowl
Wave
[[XX)
Y
Y
t corrected
X2
Figure 2: Left: corrected imputation The regression function is f"(21, x2) 3 27 x.. When 22 is missing, chaining perfect conditional imputation with the regression function (f* o T0 gives a biased predictor, shown in red, the unexplained variance in 22 turned into bias. However, using as an imputation ((x1)) p² + (1 p²) corrects this bias, with p the correlation between #1 and 22. Right: no continuous corrected imputation exists. The function is defined as (*1 X22) + 22 3.2 No continuous corrected imputation is possible because the Bayes predictor the partially-observed data [1] is monotonous, while the regression function f is not.
imputations do not always exist. Indeed, on this example the Bayes predictor is non non- con-decreasing but there no continuous path the 2D plane on which f* is non-decreasing and maps at some point to both the 'purple' and yelloo values' (proof in Appendix A.9 It is thus of interest to clarify when continuous corrected imputations exist. Proposition 4.3 establishes such conditions.
Proposition 4.3 (Existence of continuous corrected imputations). Assume that f is uniformly continuous, twice continuously differentiable and that, for all missing patterns m and all Tobs- the support of X Xobs Tobs; M = is connected. Additionally, assume that for all missing patterns m, and all (Tobs; Im the gradient of f with respect to the missing coordinates is nonzero:
Dmmie f (Nober mmis) + O.
(8)
Then, for all m, theres exist continuous imputation functions (fm)) (gobss(m) - Rimis(m)) such that I @ is Bayes optimal.
Appendix gives proof based on a global implicit function theorem. Assumption g is restrictive: it is for instance not met for example in Figure (lef),, which still admits continuous corrected imputations. This highlights the fact that continuous corrected imputations also exist under weaker
conditions, but it is difficult to conclude on "how often" it is the case.
Jointly optimizing an impute-n-regress procedure: NeuMiss+MLJ.
The above suggests that it is beneficial to adapt the regression function to the imputation procedure and vice versa. Hence, we introduce a method for the joint optimization of these two steps by chaining NeuMiss network with MLP (multi-layer perceptron).
NeuMiss Le Morvan et al. 2020a is a neural-network architecture originally designed to approximate the Bayes predictor for linear models with missing values. It contains a Neumann block that has the particularity of using element-wise multiplications by the missingness indicator as non-linearities. Here we reuse this block to play the role of an imputation layer. This choice is motivated by two key reasons. First, the Neumann block a theoretically grounded layer for missing values: can approximate the conditional expectation of the missing values given the observed ones with an error that decays exponentially fast with its depth. As explained in Prop. 4.1, this property is desirable in some cases. Second, it is differentiable block, which allows it to be chained with MLP and learned jointly with the regression function. The resulting architecture can thus be seen as an Impute-ther -heute-the--ae Regg-ss architecture, but that be jointly optimized.
We performed one minor improvement on NeuMiss architecture compared the original paper. Though the theory behind NeuMiss points to using shared weights in the Neumann block as well as residual connections going from the input to each hidden layer the Neumann block, Le Morvan al. 2020al used neither. We found empirically that shared weights in the Neumann block well
7

---

as residual connections improved performance. Therefore, we used both in all our experiments. For clarity, the (non-linear) NeuMiss architecture described in detail in Appendix B.1
6 Empirical study of impute-n-regress procedures
6.1 Experimental setup
Data generation The data X [x are generated according a multivariate Gaussian distribu- tion (n, 2) where the mean is drawn from standard Gaussian and the covariance is generated as Σ = BBT + D. E Ixdx is a matrix with entries drawn from a standard normal Gaussian distribution, and D is diagonal matrix with small entries that ensures that the covariance matrix is full rank. We study two correlation settings called high and low corresponding respectively to with 50.
4= (0.3 d) and q int d). The experiments
Choice of l" The response Y is generated according to = (X) + with three choices of I" named bowl, wave, and break depicted in Figure 3 (exact expression in appendix B.2 is vector of ones normalized such that the quantity 2 = 13 + 3g follows a Gaussian distribution centered on with variance 1. Note that hou!! J wave and fbrak were designed so that the desired variations occur over the support of the data. The noise is chosen so as to have a signal-to-nois ratio of 10.
1r x 841
bowl
rie x A3)
wave
break
Figure 3: Bowl, wave and break functions used for f* in the empirical study.
-1
B X 8o
# x Bo
8 X Bo
Missing values 50% of the entries of X were deleted according to one of two missing data mechanisms: Missing Completely At Random (MCAR) or Gaussian self-masking [GSM, see Lc Missing Not At Random (MNAR) mechanism, where the probability that a variable j is missing depends on Xj via Gaussian function.
Morvan et al. 2020a|. Gaussian self-masking
Baseline methods benchmarked For each level of correlation (low or high), for each function f* (bowl, wave or break), and each missing data mechanism (MCAR or GSM), we compare a number of methods. First, for reference, compute various oracle predictors:
Bayes predictor: This is the function that achieves the lowest achievable risk. In general cases, expression cannot be derived analytically. However, we show that can be derived for ridge functions, i.e. functions of the form x + g(8 x), for some choices of g including polynomials, the Gaussian edf and piecewise constant functions. We thus built fiow! füove and fbreak as combination of these base functions which allows us to compute their corresponding Bayes predictors. Appendix B.2 gives their expressions.
Chained oracles: f o CCI consists in imputing by the conditional expectation and then applying f*. The analytical expression of 4C can be derived analytically for both MCAR and GSM, and we thus use this analytical expression to impute the missing values.
Oracle + MIP: The data is imputed using the analytical expression of the conditional expectation, and then a MLP is fitted to the completed data.
These three predictors all use ground truth information (parameters μ., D of the data distribution, expression of f or of the missing data mechanism) which are unavailable in practice. They are mainly useful as reference points. We then compare the NeurMiss+MLP architecture and a number of classic Impute- Impute-then-Ree then-Regres. methods as well as gradient boosted regression trees:
Mean + MLP The data is imputed by the mean, and a multilayer perceptron (MLP) is fitted to the completed data.
MICE MLP The data is imputed using Scikit-learn's Pedregosa et al. 2012 BSD licensed] conditional imputer Iterative Imputer that adapts the popular Multivariate Imputation by Chained Equations [MICE, van Buuren 2018 to be able to impute test set. multilayer perceptron (MLP) is then fitted to the completed data.
8

---

Gradient boosted regression trees (Scikit-learn' Hisrrraa with default parameters). This predictor readily supports missing values: during training, missing values on the decision variable for a given split are sent to the left or right child depending on which provides the largest gain. This is know as the Missing Incorporated Attribute strategy (aaaa et al. 2008].
GBRT:
Finally, we also run Mean + mask MLP as well as MICE + mask + MLP in which the mask concatenated to the imputed data before fitting MLP. Concatenating the mask is widespread pratice to account for MNAR data.
All MLPs are implemented with PyTorch [Paszke et al.) 2019
validation is used to choose
MLPs' depth (1, 2 or 5), width (Id, 5d or 10d), initial learning rate (ranging from 5.10-4 to 10-3 and weight decay (ranging from 10-6 10-3). Adam used with an adaptive learning rate: the learning rate is divided by 5 each time 10 consecutive epochs fail to decrease the training loss by at least le-4. Early stopping is triggered when the validation score does not improve by least le-4 for 12 consecutive epochs. The batch size is set to 100, and ReLUs are used as activation functions. Finally for NeuMiss the depth set 20. Note that since the weights of NeuMiss are shared, increasing its depth does not increase its number of parameters. For gradient boosted regression trees, several hyperparameters are chosen using the validation set including the maximum number of leaves for each tree (from 50 to 600), the maximum number of iterations for the boosting process (from 100 to 300), as well as the minimum number of samples per leaf (from to 50).
The experiments training sets of size 100000 and validation and test sets of size 10000. The code for all experiments is available at bitts:///gthar thub. com woommaarinelM. Impute/ then Regress
6.2 Experimental results
The results are presented Figure as well as in Figure g (Appendix
B.3
Chaining oracles fails when both curvature high and correlation is low. The chained oracle has performance close that of the Bayes predictor in all cases except when the functions are applied to low correlation data. This observation illustrates well Proposition 4.1 Intuitively, the Bayes predictor for each missing data pattern is a smoothed version of ʃ*, and all the more smoothed that there is uncertainty around the likely values of the missing data. In the
break
Bowl
Wave
high correlation: easy
low correlation: hard
high correlation: easy low correlation: hard
MCAR
Chaining oracles
Oracle impute + MLP
NeuMiss + MLP
MICE + MLP
MICE & mask + MLP
mean impute + MLP
mean impute mask MLP
Gradient-boosted trees
MNAR
Chaining oracles
Oracle impute + MLP
NeuMiss + MLP
MICE + MLP
MICE & mask + MLP
mean impute + MLP
mean impute & mask + MLP
Gradient-boosted trees
Drop in R2 compared to Bayes predictor
Figure 4: Performances (R2 score on test set) compared to that of the Bayes predictor across 10 repeated experiments.

---

low correlation setting, the uncertainty is such that f is not a good proxy anymore for the Bayes predictor.
Regressing on oracle conditional imputation provide excellent performances. Contrary to the chained oracles, Oracle + MLP is close to the Bayes rate in all cases. This result should be put into perspective with Proposition 4.2, which states that there is continuous regression function g such that g @C is Bayes optimal unless it is f*. Indeed, as the MLP can only learn continuous functions, it shows that there continuous functions g such that g Φcr even though it is not Bayes optimal, performs very well.
Adding the mask is critical in MNAR settings with mean and MICE imputations In MNAR settings, missingness carries information that can be useful for prediction. However, both the mean and iterative conditional imputation output an imputed dataset in which the missingness information is more difficult to retrieve. For this reason, it is common practice to concatenate the mask with the imputed data to expose the missingness information under self- masking (MNAR), adding the mask to the mean or iteratively imputed data markedly improves performances. Note that NeuMiss does not require adding the mask as an input since the missingness information is already incorporated via the non-linearities.
the predictor. Our experiments show that
NeuMiss+MMP performs best among Impute-then- Regress predictors. In all settings, Neu- Miss performs best. GBRT performs poorly here possibly because they not well adapted to approximate smooth functions. Finally, note that when the difficulty of the problem increases, for example with lower correlation, then (i) the performance of the Bayes predictor decreases and (ii) the differences in performance among methods is reduced, as in the lower right panel.
7 Conclusion
Impute-then teree-hhe-rreee rehness procedures assemble standard statistical routines to build predictors suited for data with missing values. However, we have shown that seeking the best prediction of the outcome leads to different tradeoffs compared to inferential purposes. Given powerful learner, almost all imputations lead asymptotically to the optimal prediction, whatever the missingness mechanism. A good choice of imputation can however reduce the complexity of the function to learn. Though conditional expectation can lead to discontinuous optimal regression functions, our experiments show that it still leads to easier learning problems compared to simpler imputations. In order to adapt the imputation to the regression function, we proposed to jointly learn these two steps by chaining trainable imputation via the NeuMiss networks and classical MLP. An empirical study of non-linear regression shows that outperforms papute-then-regreee procedures built on standard imputation methods as well as gradient- boosted trees with incorporated handling of missing values. In further work, would be useful theoretically characterize the learning behaviors of Impute-ther seatte-then-Reeee Regg-ss methods in finite sample regimes.
Acknowledgments and Disclosure of Funding
MLM, JJ, and GV acknowledge funding via DataIA MissingBigData. MIM and GV acknowledge funding via ANR-17-CE22 Learnl. JJ acknowledges funding via ANR-16-IDEX-0006
DirtyData and GV acknowledges funding via ANR-20-CHIA-00
References
AV Arutyunov and SE Zhukovskiy. Application of methods of ordinary differential equations to global inverse function theorems. Differential Equations, 55(4):437 448, 2019.
Dimitris Bertsimas, Arthur Delarue, and Jean Pauphilet. Prediction with Missing Data, 2021.
Christopher M. Bishop. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verte Verlag, Berlin, Heidelberg, 2006. ISBN 0387310738.
Jan Borowski and Piotr Fic. NADIA package. https://craa.r-pojjcc.ooor NADIA/index. html Accessed: 2021-05-26.
packages/
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd aem sigkdd international conference on knowledge discovery and data mining, pages 785-794, 2016.
10

---

Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39:1, 1977.
G B Folland. Advanced Calculus. Featured Titles for Advanced Calculus Series. Prentice Hall, 2002. ISBN 97801 30652652.
Martin Golubitsky. Stable mappings and their singularities. Graduate texts mathematics. Springer- Verlag, 1973. ISBN 0-387-90072-1.
Victor W. Guillemin and Alan Pollack. Differential topology. Prentice-Hall Englewood Cliffs, N.J, 1974. ISBN 0132126052.
László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. A distribution-free theory of nonparametric regression. Springer Science & Business Media, 2006.
Niels Ipsen, Pierre-Alexandre Mattei, and Jes Frellsen. How to deal with missing data supervised deep learning? In ICML Workshop on the Art of Learning with Missing Values (Artemiss), 2020.
Daniel Jarrett, Jinsung Yoon, Ioana Bica, Zhaozhi Qian, Ari Ercole, and Mihaela van der Schaar. Clairvoyance: pipeline toolkit for medical time series. In International Conference on Learning Representations, 2021.
Julie Josse, Nicolas Prost, Erwan Scornet, and Gaël Varoquaux. On the consistency of supervised learning with missing values. arXiv preprint arXiv:1902.06931/ 2019.
Marine Le Morvan. Julie Josse, Thomas Moreau, Erwan Scornet, and Gaël Varoquaux. NeuMiss networks: differentiable programming for supervised learning with missing values. Advances in Neural Information Processing Systems, 33, 2020a.
Marine Le Morvan, Nicolas Prost, Julie Josse, Erwan Scornet, and Gael Varoquaux, Linear predictor on linearl-ggeerrtte data with missing values: non consistency and solutions. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 3165-3174. PMLR, 2020b.
Roderick JA Little and Donald B Rubin. Statistical analysis with missing data. John Wiley & Sons, 1987, 2002, 2019.
Pierre-Alexandre Mattei and Jes Frellsen. MIWAE: Deep generative modelling and imputation of incomplete data sets. In Kamalika Chaudhuri and Ruslan Salakhutdinov. editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 4413-4423, PMLR, 09-15 Jun 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32: 8026-8037, 2019.
Fabian Pedregosa, Gaël Varoquaux. Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg. Jake Vanderplas, Alexandre Passos, David Cournapeau, Matthicu Brucher, Matthieu Perrot, and Edouard Duchesnay, Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, 12(oct): 2825-2830, 2012.
Donald B Rubin. Inference and missing data. Biometrika, 63(3):581 1976.
B. E. T. H. Twala, M. C. Jones, and D. J. Hand, Good methods for coping with missing data in decision trees. Pattern Recogn. Lett., 29:950-956, 2008. ISSN 0167-8655.
Stef van Buuren. Flexible Imputation of Missing Data, Second Edition. 2018.
Jinsung Yoon, James Jordon, and Mihaela Schaar. Gain: Missing data imputation using generative adversarial nets, In International Conference on Machine Learning, page 5689, PMLR, 2018.
11


Reviews:
[{"review_id": "zXH8810_e1U", "reviewer": "Reviewer_1UHV", "summary": "The authors look at the impute and regress framework and provide arguments as to Bayes optimality of the process for missing data mechanisms and imputation functions. It gives a general theoretical framework for the impute and regress procedures. Unlike the missing at random setups, they look at more general missing value mechanisms. They also argue that the imputation and regression processes should be properly aligned with each other and also provide a method for optimizing the two processes jointly.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and provides a well-structured overview of the results. They provide a framework that gives a theoretical background for the impute-then-regress process and they look at a more general setup that does not require any structured missing data mechanisms such as MAR and etc. The authors show that for almost all infinitely differentiable, smooth impute functions, there is an impute-then-regress process that is Bayes optimal. They provide a constructive argument to that effect. The paper also looks at the case of using conditional expectations for the imputation and how this could result in regression functions with discontinuity. The authors also provide a chaining of NeuMiss and multi-layer perceptron to compute the impute-then-regress process. All the claims are clearly stated and properly presented and the math seems to hold as well.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do state that the choice of imputation function impacts the regression step and how the continuity and smoothness are not guaranteed making it hard to approximate. However, as stated in the previous section, they look at this case with the imputation being conditional expectation and also show the existence of continuous imputation functions that lead to Bayes optimality.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "y7CeuFxwYq4", "reviewer": "Reviewer_wpgv", "summary": "The paper first seeks to study the theoretical properties of impute-then-regress procedures -- which are widely used. They show that most any imputations admit Bayes consistent estimators; however, that estimation may be difficult in certain settings. They show that conditional imputation is not necessarily an optimal strategy, supply bounds on the associated risk, and discuss when it can be expected to perform reasonably well. In particular, conditional imputation under some conditions requires learning a discontinuous regression function for optimal performance. Given all this, they examine the conditions under which imputations exist such that impute-then-regress procedures are optimal. Lastly, they propose a procedure for joint optimization of an imputation and a regression scheme that is empirically shown to 1. outperform common impute-then-regression procedures as well as gradient boosting which naturally can accommodate missingness and 2. perform similarly to oracle estimators in certain settings. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**: I was not familiar with general work on the validity of impute-then-regress schemes, though this submission seems to clearly move beyond the restrictive settings considered in past papers. In general, there is not much related work cited on this concrete task (not that I am sure more exists). The actual method proposed to take advantage of the demonstrated theory -- NeuMiss+MLP -- is not very innovative, though it is not meant to be; the point is simply that joint optimization of how to impute and how to regress is superior. The proof technique of Theorem 3.1. seems to be original, though I did not examine it carefully. \n\n**Quality**: Claims are backed up by theoretical results, the proofs of which I did not examine closely. There is empirical support for the overall argument of the paper. Thought it is not the focus, it might have been good to touch upon the limitations of NeuMiss. I would also have liked to see a discontinuous $f^*$, though I understand that the Bayes predictor might be harder to compute.\n\n**Clarity**: I thought the paper read very well. A few typos to address before CR, but I like the overall structure. \n\n**Significance**:  I don't think the prevalence of \"first impute, then regress\" as a strategy for handling missing data can be understated and for this reason I find the work very compelling. It is possible that in the future the standard shifts towards a joint treatment of the two tasks and this paper provides evidence for why that would be beneficial. It would have been useful to comment on joint schemes beyond the one proposed here. For example, do researchers that don't want to rely on an uninterpretable method for regression have any hope of adopting / adapting the approach here? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "fqy9CIF2UXb", "reviewer": "Reviewer_Jo6j", "summary": "In handling missing data, a standard approach is to simply impute and then run a prediction model that requires fully-revealed data. However, this standard \"impute-then-regress\" approach is largely a hack without theoretical grounding. This paper provides theory to justify this standard approach, with a surprising finding that it turns out that for almost all imputation functions, impute-then-regress with a sufficiently powerful learner is Bayes optimal. Moreover, the paper theoretically justifies why imputation and regression should be done jointly rather than separately as doing so separately can require learning discontinuous functions that are harder to learn. Numerical experiments corroborate the theoretical findings.", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper is very well-written and I find it to constitute a major advance in our understanding of the standard impute-then-regress approach (which shows up in a massive number of applied papers throughout scientific literature but lacks theoretical grounding). The theoretical findings (summarized in my summary above) are surprising and informative of the direction researchers should shift toward in handling missing data.\n\nStrengths:\n- extremely well-motivated paper\n- compelling theoretical and experimental results\n- detailed numerical experiments\n\nWeaknesses:\n- especially as the claim of Theorem 3.1 is surprising regarding the \"almost all\" imputation methods, perhaps it would be instructive providing an example problem setup and imputation method that does not lead to Bayes optimality and relating such an example to what is done in practice (perhaps such an example is contrived and basically all practical imputation methods really do fall under the coverage of Theorem 3.1)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have provided a sufficient answer (see checklist 1(c)).", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "7Mn1dy2-Qg", "reviewer": "Reviewer_YYbQ", "summary": "This paper proposes to jointly optimize imputation and regression to learn from data with missing values, backed by theoretical analysis of impute-then-regress procedures. In particular, the authors show that the impute-then-regress procedure is asymptotically Bayes optimal for almost all (smooth) imputation functions, regardless of the missing data mechanism (including MNAR). However, apart from restrictive special cases, learning the regression function for conditional imputation to obtain a Bayes optimal function is hard due to discontinuities; similar with correcting the imputation for a given oracle function. The authors thus propose to jointly optimize impute-then-regress procedures, in particular chaining a NeuMiss architecture with an MLP. The proposed approach is empirically evaluated on synthetic data with various combinations of imputation and regression methods.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers an important problem of learning with missing data, under a general setting with little assumptions on the oracle function or the missingness mechanism, and thus can be relevant in many practical scenarios.\n\nIt is also well-written overall. One suggestion for clarity is to formally define “almost all” in Theorem 3.1 sooner.\n\nThis work contains interesting and novel theoretical results. In particular, I was surprised that impute-then-regress is Bayes optimal even under MNAR for almost all imputation functions, including a simple constant function. I believe Proposition 4.1 is also an important result, because many existing works on imputation implicitly or explicitly target to learn the conditional imputation and oracle labeling function. \n\nHowever, I was less convinced by the conclusion to jointly optimize imputation and regression. According to the authors, for a fixed imputation function, the Bayes optimal regression function may not be continuous, and vice versa. It was not clear how joint optimization addresses this, and whether the joint learning could be confused. The specific choice of NeuMiss was also not very well motivated.\n\nAlternatively, if the goal is not to learn the “best” imputation and “best” regression functions but rather to chain two architectures to optimize predictive performance, how does it compare to simply optimizing one architecture that takes as input the given observations concatenated with missingness information? \n\nAnother recommendation is to also evaluate on real-world benchmark dataset to compare against state-of-the-art learning from missing data.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies prediction in the presence of missing values. A common approach to solving this problem is "impute-then-regress", independently imputing missing values and predicting using the imputed data. The authors show that this strategy is almost always Bayes optimal w.r.t. risk, but that a poor imputation may lead to learning a complex prediction function. Several strategies are evaluated and compared empirically on synthetic data. 

All reviewers recognised the value of this work and pointed out its strong motivation and clarity in exposition. 
Decision: Accept (Spotlight)