Title: Supervised learning with incomplete data via sparse

Abstract: This paper addresses the problem of training a classifier on a dataset with missing features and its application to a complete or incomplete test dataset. A supervised learning method is developed to train a general classifier, such as a logistic regression or a deep neural network, using only a limited number of observed entries (features), assuming sparse representations of data vectors on an unknown dictionary. The pattern of missing entries is independent of the sample and can be random or structured. The proposed method simultaneously learns the classifier, the dictionary and the corresponding sparse representations of each input data sample. A theoretical analysis is also provided comparing this method with the standard imputation approach, which consists on performing data completion followed by training the classifier based on their reconstructions. The limitations of this last "sequential" approach are identified, and a description of how the proposed new "simultaneous" method can overcome the problem of indiscernible observations is provided. Additionally, it is shown that, if it is possible to train a classifier on incomplete observations so that its reconstructions are well separated by a hyperplane, then the same classifier also correctly separates the original (unobserved) data samples. Extensive simulation results are presented on synthetic and well-known reference datasets that demonstrate the effectiveness of the proposed method compared to traditional data imputation methods.

1. Introduction:

In many machine learning applications sometimes the measurements are noisy or affected by artifacts, resulting in incomplete data samples. Examples of this situation include: self-driving vehicle or robot where objects in the view field can be partially occluded; recommendation systems built from the information gathered by different users where not all the users have fully completed their forms; or medical datasets where typically not all tests can be performed on all patients.

A classical approach of supervised learning with missing entries is to apply entry imputation as a preprocessing step, followed by standard training based on these reconstructions (Little & Rubin, 2014) . For example, some techniques compute missing entries using statistical methods, such as the "mean", "regression" and "multiple" imputation methods (Little & Rubin, 2014) . Other completion methods are based on machine learning ideas by estimating missing entries through K-nearest neighbor (Batista & Monard, 2002) , Self Organization Maps (SOM) (Fessant & Midenet, 2002) , multilayer or recurrent neural networks (Yoon & Lee, 1999; Bengio & Gingras, 1995) , tensor completion algorithms (Solé-Casals et al., 2018) and others (García-Laencina et al., 2009) . In (Huang et al., 2018) , a technique for completing the matrix of features was proposed by imposing low-rankness and incorporating the label information into the completion process. A different approach is to avoid direct imputation of lost inputs and rely on a probabilistic model of input data, learning model parameters through the Expectation Maximization (EM) algorithm and building a Bayesian classification (Ghahramani & Jordan, 1993; Little & Rubin, 2014) . However, the latter "model-based" approach has the disadvantage that it requires a good probabilistic data model, which is usually not available, especially for real-world applications such as those involving natural images.

On the other hand, during the last few years in the signal processing community, there has been a rapid development of the Compressed Sensing (CS) theory and sparse coding algorithms that exploit the redundancy of natural signals (Candes et al., 2006; Donoho, 2006; Eldar & Kutyniok, 2012; Gregor & LeCun, 2010) . A particular case of CS is the signal completion problem, i.e. the reconstruction of signals from incomplete measurements. Several algorithms for matrix and tensor (multidimensional signals) completion have been recently proposed relying on different low-dimensional manifold models that are fit to the available entries, allowing for an extrapolation of the unobserved entries. This category of models ranges from sparse representation of vectors (Aharon et al., 2006; Fadili et al., 2008) and tensors (Caiafa & Cichocki, 2012) to low-rank matrix (Candes & Tao, 2010) and tensor decompositions (Liu et al., 2012; Yuan et al., 2018) . The success of sparse representations in many signal processing applications motivated researchers to use dictionary learning techniques for data classification (Mairal et al., 2008) , either using class-specific dictionaries (Ramirez et al., 2010; Sprechmann & Sapiro, 2010) , or using a single one for all classes (Tosic & Frossard, 2011) .

In this paper, the goal is to develop a method for training a classifier using incomplete data samples with their labels and to identify the conditions under which such a classifier performs as good as the ideal classifier, i.e. the one that could be obtained from complete observations. We propose to use the sparse representation model for data vectors, and analyze the limitations of the sequential approach, i.e. imputation followed by training (section 2). In section 3 we introduce the simultaneous classification and coding approach, which consists of incorporating a sparse data representation model into a cost function optimized for training the classifier and, at the same time, finding the best sparse representation of the observed data. We provide theoretical conditions under which we can guarantee that the obtained classifier is as good as the ideal classifier. In section 4, a computational method is presented to train a classifier on incomplete data; in section 5, extensive experimental results are presented using synthetic and well known benchmark datasets illustrating the effectiveness of our proposed algorithms; and finally, in section 6, the main conclusions are outlined.

1.1. Preliminary definitions and problem formulation:

We assume a supervised learning scenario with vector samples and their labels {x i , y i }, i = 1, 2, . . . I, x i ∈ R N and y i ∈ {0, 1, . . . , C -1} (C classes), so that we only have access to subsets of entries in each data vector along with their labels, which is denoted by

{x i , y i }, xi ∈ R M with M < N .

The success of CS theory is based on the fact that sparse coding of natural signals is nearly ubiquitous. It is found, for example, in the way that neurons encode sensory information (Olshausen & Field, 1996; 1997; Lee et al., 2007) . We define the set of all K-sparse vectors Σ L K = {s ∈ R L such that s 0 ≤ K} (containing at most K non-zero entries) and assume that data vectors x i admit K-sparse representations over an unknown dictionary D ∈ R N ×L (L ≥ N ), i.e. x i = Ds i , with s i ∈ Σ L K . The columns d i ∈ R N of a dictionary are called "atoms" because we can express any data vector as a combination of at most K atoms.

Without losing generality, to simplify the mathematical treatment, we shuffle the entries of the full vector x i to have the observed values placed in the upper M positions, so that we can write:

x i = xi z i , with z i ∈ R (N -M ) .

(1) However, our results are valid for any pattern of missing entries for each data vector. Accordingly, we define D i ∈ R N ×L as the shuffled version of D, such that it stacks in the top M rows those corresponding to the observed entries:

D i = Di E i , with Di ∈ R M ×L and E i ∈ R (N -M )×L .

(2) Some important uniqueness properties of sparse vector reconstructions are characterized by the Restricted Isometry Property (RIP) of a matrix, which is defined as follows: a matrix A ∈ R N ×L satisfies the RIP of order K if there exists

δ K ∈ [0, 1) such that (1-δ K ) s 2 2 ≤ As 2 2 ≤ (1+δ K ) s 2 2

, holds for all s ∈ Σ L K . RIP was introduced in the context of CS by Candes and Tao (Candès & Tao, 2005) and characterizes matrices which are nearly orthonormal when operating on sparse vectors.

Let us assume that a perfect classifier p Θ (y | x) in a two classes scenario (y i ∈ {0, 1}), e.g. a logistic regression or deep neural network, can be trained on the complete dataset {x i , y i }, such that 0.5 < p Θ (y i = 1 | x i ) ≤ 1.0 and 0 ≤ p Θ (y i = 0 | x i ) ≤ 0.5, ∀i = 1, 2, . . . , I, where Θ is the set of trained parameters. We want to develop a method to estimate the classifier parameters Θ using only the incomplete data {x i , y i } and to identify the conditions under which such classifier is compatible with the ideal classifier. In the following section we will show that, when data imputation based on sparsity followed by training is used, some limitations are clearly identified.

2. The problem of training after data imputation:

First, we will provide some intuition about the limitation of the sparsity-based imputation or "sequential" approach through a toy example. We consider the classification of hand-written digit images belonging to two classes: the numbers "3" and "8". We will assume that they admit 2-sparse representations over a dictionary and only the right halves of these digits are observed. Let us consider two example vectors x i and x j belonging to classes "3" and "8", respectively, as shown in Figure 1 (a-d ). Here, we are clearly faced with the indiscernible observations problem because our observations of two vectors from different classes are identical (x i = xj ). It is obvious that at least two possible 2-sparse representations for the observed data exist, let's say xi = Di s i = Di s i , with s i = s i . Since the solution is not unique, we are not able to correctly reconstruct the original data vectors based only on the observations and the sparsity assumption.

If the K-sparse representation of the observations xi are unique, then x i can be perfectly reconstructed from the incomplete observations and the classifier can be successfully trained using these reconstructions, but unfortunately this is not the case most of the times. In the particular case where the dictionary D is known in advance, there are some conditions on the sampling patterns based on properties of matrices such as coherence, spark or RIP that can guarantee a correct reconstruction (Eldar & Kutyniok, 2012) . However, these conditions are difficult to meet in practice. Moreover, in the more general case where the dictionary D is unknown and needs to be learned from data, it is even more difficult to obtain reconstructions of partially observed data vectors that are well separated. For example, even in the case where complete data vectors are well separated, it could happen that their reconstructions become difficult to separate, leading to suboptimal classifiers.

In this paper, motivated by the limitation of the sequential approach, we propose to incorporate the class information of incomplete samples in order to learn simultaneously their sparsest representations and the classifier, such that the classification error of the reconstructions is minimized.

In the previous section, we showed that sparsity-based imputation methods using only the information on available entries are prone to fail because the non-uniqueness of solutions can make the training of a good classifier an impossible task. It is interesting to note that we could solve this problem by incorporating from the beginning the information of the class to which the incomplete data vectors belong to. Let us consider the toy example of previous section, for which we assumed the classes are linearly separable and each data vector admits a K-sparse representation over a dictionary D ∈ R N ×L . A two-dimensional simplified visualization for this example is provided in Figure 1 (e). When we apply a sparsity-based reconstruction algorithm on observations xi , and xj such that xi = xj and, assuming for now that dictionary D is known, we search for the K-sparse representation that is compatible with the measurements, i.e. we find s ∈ Σ L K such that xi = D i s. In this case, there are at least two equally acceptable solutions s i and s j corresponding to vectors x i and x j , respectively. If we were to make the wrong decision of assigning s j to x i and s i to x j , then the resulting set of reconstructed vectors would not be linearly separable, which is illustrated in Figure 1 (f), therefore it would be impossible to find a linear classifier. The key observation here is that, in order to assign the proper sparse representation we could also look at the label information y i and y j , and make the solution unique by discarding any K-sparse representation resulting in not separable vector reconstructions. This suggests that we would need to train the classifier and find the proper representation not only as sparse as possible but also providing the best separation of classes. In other words, we should simultaneously learn the optimal classifier and find sparse representation of observations. Next, we theoretically analyze the case of using a logistic regression classifier and demonstrate that, if we are able to train a classifier on incomplete observations such that their sparse representations are well separated by a hyperplane, then the same classifier correctly separates the original (unobserved) data vectors.

3.1. Theoretical guarantees in the logistic regression case:

Let us consider the case of a logistic regression classifier (Hastie et al., 2009) where the set of parameters Θ = {w, b} are a vector w ∈ R N and a scalar (bias) b ∈ R, and a perfect classifier exists if there is a hyperplane that separates both classes, i.e., for each data vector x i : f (x i ) = w T x i +b > 0 when y i = 1 and f (x i ) ≤ 0 if y i = 0. We investigate the conditions under which a perfect classifier can be trained using incomplete data samples and their labels. By using the same shuffling as in equation ( 1), we can write the partition of the shuffled coefficients w i ∈ R N as follows:

w i = wi u i , where u i ∈ R (N -M ) . (3)

Since the classifier is based on the feature f

(x i ) = w T i x i + b = wT i xi + u T i z i + b, the vector u i ∈ R (N -M

) contains the weights associated with unobserved entries z i . The following definition introduces a way to measure the amount of discriminative information associated with missing entries.

Definition 3.1. Discriminative Missing Information (DMI) µ i : Given a classifier {w, b} and a partition of observed/missing entries in sample vector x i such that the shuffled vector of coefficients w i can be partitioned as in eq. ( 3), we define the DMI for sample x i as:

µ i = u i 1 = N -M m=1 |u i (m)|.

Intuitively, if the DMI is small enough, the classification will not strongly depend on the unobserved entries z i and then a classifier could be trained from incomplete data samples. The following theorem establishes precise conditions under which the existence of a classifier obtained from incomplete data can be guaranteed and thus, a perfect classifier can be successfully trained. The proof can be found in Appendix A Theorem 3.2. Given a dataset {x i , y i }, i = 1, 2, . . . , I with normalized data vectors ( x i ≤ 1) admitting a K-sparse representation over a dictionary D ∈ R N ×L with unit-norm columns and satisfying the RIP of order K with constant δ K , and suppose that, we have obtained an alternative dictionary D ∈ R N ×L also satisfying the RIP of order K with constant δ K such that, for the incomplete observation xi ∈ R M , the K-sparse representation solution is non-unique, i.e. ∃s i , 

s i ∈ Σ L K such that xi = Di s i = D i s i ,

EQUATION

)

with > 0 being the minimum distance of reconstructed data sample to the separating hyperplane, then the full data vector x i is also perfectly separated with this classifier, in other words: f

(x i ) = w T i x i + b > 0 (≤ 0) if y i = 1 (y i = 0).

It is interesting to note that, supposing that we have obtained a classifier from incomplete data, if we are able to evaluate condition (4) then we can figure out whether such a classifier is optimal by testing the condition of the theorem. However, It is well known that, in general, the RIP constant is difficult to compute in practice. When the dictionary is highly uncorrelated1 , i.e. if ρK < 1, then the RIP constant can be written in terms of the correlation coefficients ρ as follows:

δ K = (K -1)ρ (Eldar & Kutyniok, 2012

), and ρ is easy to compute. Our theorem provides useful insights of the problem. For example, we it suggests the following conditions are desirable: (a) very well separated reconstructed vectors (large ); (b) very sparse model (small K); (c) small norm variability of transformed K-sparse vectors through D (small δ K ), which can be interpreted as a quasi-orthonormal basis behaviour (low correlation, for example); and (d), small weights assigned to unobserved entries of x i (small DMI µ i ).

4. The proposed method:

Here, we propose to combine the training of the classifier together with the learning of a dictionary and optimal sparse representations such that reconstructed data vectors are compatible with the observed entries and, at the same time, well separated. To do that we propose to minimize the following global cost function, where we consider that x, x and m are now the original unruffled vectors and the pattern of missing features is not the same for each data sample i :

EQUATION

)

where Θ contains the classifier parameters, i.e. the vector of coefficients and bias for a logistic regression model, or the vector of weights in a deep neural network classifier architecture; D ∈ R N ×L (L ≥ N ) is a dictionary and s i ∈ R L are the representation coefficients such that the reconstructed data vectors are xi = Ds i . J 0 (Θ, xi , y i ) is a measure of the classification error for sample i. Typically, we use the crossentropy measure, i.e. J 0 (Θ, x, y i ) = -log(p yi Θ (x)), where p yi Θ (x i ) is the probability assigned by the classifier to sample x i as belonging to class y i . J 1 (D, s i ) is a measure of the error associated with the sparse representation when it is restricted to the observed entries, and is defined as follows:

J 1 (D, s i ) = M N m i * (x i -Ds i ) 2

, where * stands for the entry-wise product, m i ∈ R N is the observation mask for sample i, with m i (n) ∈ {0, 1} such that m i (n) = 1 or 0 if data entry x i (n) is available or missing, respectively. J 2 (s i ) = 1 N s i 1 is the 1 -norm whose minimization promotes the sparsity of the representation (Candès & Tao, 2005) . Finally, the hyper-parameters λ 1 and λ 2 allow to give more or less importance to the representation accuracy and its sparsity, with respect to the classification error. Intuitively, minimizing equation ( 5) favors solutions that not only have sparse representations compatible with observed entries, but also provides reconstructions that are best separated in the given classes.

To minimize the cost function in equation ( 5) we propose to alternate between the optimization over {Θ, D} and s i (i = 1, 2, . . . , I). As usual, we adopt a first order (gradient based) search of minima, where gradients of functions J 0 (•), J 1 (•) and J 2 (•) are easily derived. Note that in the case of feedforward architectures, the back-propagation technique can be used for the first term J 0 (•). It is also noted that function J 2 (•) is not differentiable at zero, so we need to avoid zero crossing in every update. In the case where the given test dataset is also incomplete we can use the dictionary learned during the training phase to find the sparsest representation for the given observations, compute the corresponding full vector reconstructions and apply the classifier to them. The algorithms are presented in Appendix B.

5. Experimental results:

We synthetically generated I = 11, 000 (10, 000 training +1, 000 test) K-sparse data vectors x i ∈ R 100 using a dictionary D ∈ R 100×200 obtained from a Gaussian distribution with normalized atoms, i.e. D(:, l) = 1, ∀l. A random hyperplane {w, b} with w ∈ R N , b ∈ R was randomly chosen dividing data vectors into two classes according to the sign of the expression w T x i + b, which defines the value of label y i . We also controlled the degree of separation between the two classes by regenerating all data vectors with distances to the hyperplane lower than a pre-specified threshold d. For each case we generated 10 realizations using different masks and input data. We applied our simultaneous method, with hyperparameters λ 1 and λ 2 tuned via cross-validation, to train a logistic regression classifier on the training dataset with randomly distributed missing entries, and compared the obtained Test Accuracy against the following standard sequential methods: Seq. Sparse: reconstructions are obtained by finding the sparsest representation compatible with the observations solving a LASSO problem; Zero Fill (ZF): missing entries are filled with zeros, which is equivalent to ignore unknown values; Mean Unsupervised (MU): missing entries are filled with the mean computed on the available values in the same position in the rest of data samples; Mean Supervised (MS): as in the previous case but the mean is computed on the samples of the same class vectors only; K-Nearest Neighbor (KNN): as in the previous case but the mean is computed on the K-Nearest Neighbors of the same class only. Since the objective here is to compare the performance of obtained classifiers, we computed the accuracy (mean ± standard error of the mean -s.e.m.) on the test dataset using all the methods for two cases of degree of separation between classes (d = 0.0, 0.2), two levels of sparsity (K = 4, 32) and missing values in the training dataset ranging from 25% to 95% as shown in Fig. 2 . Our results show that the simultaneous algorithm clearly outperforms all the sequential methods. A t-test was performed to evaluate the statistical significance of the difference between our algorithm (Simul) and MS. It is interesting to note that, when classes has some degree of separation (d = 0.2), using simple methods as computing the mean or filling with zeros, can give acceptable results but not better than our simultaneous algorithm. We also applied our algorithm to three popular computer vision datasets: MNIST (LeCun et al., 1989) and Fashion (Xiao et al., 2017) consisting of 70,000 images (60,000 train + 10,000 test) each; and CIFAR10 (Krizhevsky & Hinton, 2009) having 60,000 images (50,000 train + 10,000 test). MNIST/Fashion datasets contains 28 × 28 gray scale images while CIFAR10 dataset is built upon 32 × 32 × 3 color images of different objects. The corresponding data sample size is N = 28 × 28 = 784 for MNIST/Fashion and N = 32 × 32 × 3 = 3, 072 for CIFAR10. We considered a dictionary of size 784 × 784 (MNIST/Fashion) and 1, 024 × 1, 024 (CIFAR10) and applied our simultaneous algorithm to learn the classifier on incomplete data for these datasets using uniform random missing masks at several levels of missing entries (25%, 50% and 75%) and for 50% random partial occlusions for MNIST/Fashion. We used a logistic regression classifier (single layer neural network) and a 4-layer convolutional neural network (CNN4) for the MNIST/Fashion dataset using batch normalization (BN) in the Fashion dataset, while for CIFAR10 dataset, a residual neural network (Resnet-18, (He et al., 2016) ) was implemented. 

6. Conclusions:

We demonstrated that assuming a sparse representation model for input data vectors allows the successful learning of a general classifier on incomplete data. We analyzed the limitations of the classical imputation approach and demonstrated through experiments that our simultaneous algorithm always outperforms sequential methods for various cases such as LASSO, zero-filling, supervised/unsupervised mean and KNN based methods. Our approach is conceptually similar to the work in Ghahramani & Jordan (1993) but, instead of using a probabilistic model, we use sparse coding, which is known to fit very well for natural signals. It is also noted that in Huang & Aviyente (2006) , sparse representations of data vectors were incorporated in the optimization process for maximizing the Fisher discriminant in a context of classification. However, no theoretical guarantee was presented in that paper and our approach can be applied to any deep learning classifier architecture by simply incorporating a sparse data model, and adding two regularization terms to the objective function: one to measure the accuracy of the sparse model to explain the observations, and another to favor sparsity of the data representation, which is based on the 1 norm.

A Proof of Theorem 3.2

Proof. Let us first consider the case with y i = 1. We assume that we are able to find a perfect classifier on the reconstructed full data vector such that

EQUATION

where xi = D i s i . Now, we note that the K-sparse representation solution given the observation is non-unique, i.e. ∃s i , s i ∈ Σ L K , such that xi = Di s i = D i s i . We assume that s i is the true K-sparse vector such that the unobserved full vector is x i = D i s i and s i provides an reconstruction through D i which explains the observations but xi = x i .

Analogously to equation (1), we can find a partition of the reconstructed vector xi as follows:

EQUATION

)

where z i ∈ R (N -M ) , and we want to prove that f (x i ) > implies f (x i ) > 0, i.e. the original data vector x i (unobserved) is also correctly classified by the logistic regression with parameters {w i , b}.

To that end we need to evaluate the following expression:

EQUATION

)

where equation ( 3) was used. If we add and substract u T i z i and arrange the terms in the previous equation, we get:

EQUATION

EQUATION

)

The first term in the right-hand side of last equation is f (x i ) > > 0 so if we show that |u T i E i s iu T i E i s i | < , then the proof will be complete. To do so, we can write:

EQUATION

and

EQUATION

)

Since we assumed normalized vectors x i ≤ 1, by applying the left-hand side of the RIP we obtain:

s i ≤ 1/(1 -δ K ), which implies that |s i (n)| ≤ 1/(1 -δ K )

. Now, taking into account that |E i (m, n)| ≤ 1 (columns of D are unit-norm) and using the fact that s i ∈ Σ L K we obtain:

|u T i E i s i | ≤ K (1-δ K ) N -M m=1 |u i (m)|; and, similarly, we can obtain that |u T i E i s i | ≤ K (1-δ K ) N -M m=1 |u i (m)|.

Putting everything together into equation ( 11) we get:

EQUATION

)

where we used that

N -M m=1 |u i (m)| < (1-δ K ) 2K

, which completes the proof for the case y i = 1. Similarly, it is strait-forward to prove that, if y i = 0, having f (x i ) < -< 0 implies that f (x i ) < 0.

B Algorithms:

Here, the pseudocode of the algorithms discussed in the paper are presented. In Algorithm 1, the simultaneous classification and coding method is described. It consists in the iterative alternation between the update of the classifier's parameters together with the dictionary, and the update of the sparse coefficients for the representation of data observations. Once the classifier is trained, we are able to apply it to incomplete test data by using Algorithm 2, where for fixed Θ and D, we need to find the corresponding sparse coefficients s i , compute the full data vector estimations and, finally, apply the classifier.

The standard sparsity-based imputation method is presented in Algorithm 3 (sequential approach), which consists of learning first the optimal D and sparse coefficients s i compatible with the incomplete observations (dictionary learning and coding phase), followed by the training phase, where the classifier is tuned in order to minimize the classification error of the reconstructed input data vectors xi = Ds i . 

C Additional experimental results:



C.1 Comparison to sequential methods on benchmark datasets:

In Table 2 , we compare our simultaneous algorithm (Simul) with the following standard sequential methods: Zero Fill -ZF, Mean Supervised -MS, KNN-10, KNN-20, KNN-50 and KNN-100. We computed the Test Accuracy on incomplete data using random masks for MNIST and CIFAR10 datasets. It is noted that the bests result using standard sequential method were obtained with KNN-10 or KNN-20. However, the simultaneous algorithm outperforms KNN in all the cases increasing the performance by approximately 10.% for MNIST and CIFAR10, when the percentage of random missing features is 75%.

C.2 Hyperparameter tunning:

In Table 3 and Figure 4 we present the results of the grid search for hyper-parameter tuning on MNIST and CIFAR10 datasets. We fit our model to the training dataset for a range of values of parameters λ 1 and λ 2 and apply it to the test data set. Figure 4 shows the accuracy obtained for the test dataset with different classifiers and levels of missing entries. We chose the hyper-parameters values such that the test accuracy is maximum, as shown in Table 3 .

C.3 Additional visual results:

To visually evaluate our results, additional selected examples of original (complete) images of the test dataset in MNIST and Fashion, together with their given incomplete observations and obtained reconstructions, are shown in Figure 5 

25% 50% 75%:

MNIST -Log. Reg. Random mask (75% missing entries) Occlusion (50% missing entries) 

MNIST -CNN4 CIFAR10 -Resnet18:



:

Correlation coefficient is the maximum absolute correlation between any two columns in a normalized dictionary.

https://github.com/pytorch/examples/tree/master/mnist

https://github.com/kuangliu/pytorch-cifar

Figures and Tables:

Figure 1: An indiscernible observation toy example: (a) 4 out L dictionary elements di (atoms). (b) Digit "3" and "8" can be represented by combining only two atoms in the dictionary (2-sparse representations). (c) Atoms with their left-halves occluded di. (d) An occluded digit "3" or "8" admits more than one 2-sparse representation, for example, they can be expressed as the sum of occluded atoms d1 and d2, or d3 and d4. (e) Simplified two-dimensional representation of samples x T = [x1, x2] ∈ R 2 from "3" and "8" classes that are linearly separable where incomplete observations are taken by observing only one entry. Note that xi and xj belong to different classes but their observations are identical. (f) A wrong reconstruction of data vectors, i.e. xi = xi and xj = xj can make the set of reconstructed vectors not linearly separable.

where Di , D i ∈ R M ×L are the matrices containing the observed rows of D and D , respectively; s i ∈ R L is the vector of coefficients of the true data, i.e. x i = D i s i and s i provides a plausible reconstruction through xi = D i s i with xi ≤ 1. If a perfect classifier {w i , b} of the reconstruction xi exists such that

Figure2: Experimental results on synthetic dataset using our "simultaneous" (red thick solid line) compared to various "sequential" methods. Obtained test accuracy (mean ± s.e.m computed over 10 realizations) as a function of the percentage of missing entries for separation of classes d = 0.0, 0.2 and levels of sparsity K = 4, 32. Statistical significance for the Simul-MS difference is shown (p < 0.05).

to complete test data. The right-most column shows the baseline results obtained by training the model on complete training dataset using the implementations found in 2 and 3 . We implemented our algorithm in Pytorch 1.0.0 and ran the experiments on a single GPU. Note that for the logistic regression classifier, we obtained better results when training with incomplete data rather than using complete data. Also, it is highlighted that training on incomplete data, with 50% or less random missing entries, provides the same test accuracy as training on complete data for MNIST dataset. The hyper-parameters λ 1 and λ 2 were adjusted by cross-validation through a grid-search, as shown in Appendix C. In Fig.3we present some selected examples comparing the original images in the MNIST/Fashion test dataset, their observations using random masks and partial occlusions, and reconstructions computed using their sparse representation over a dictionary learned from the incomplete training data. Additional visual examples are provided in Appendix C.

Figure 3: Reconstruction of MNIST/Fashion test data with missing entries: original images (top), incomplete observations (middle) and their reconstructions (bottom).

Simultaneous classification and coding (training on incomplete data) Require: Incomplete data vectors and their labels {xi, yi}, i = 1, 2, . . . , I, hyper-parameters α, λ1 and λ2, number of iterations Niter and update rate σ Ensure: Classifier parameters Θ and sparse representation of full data vectors xi = Dsi, ∀i 1: Initialize Θ, D, si, ∀i randomly 2: for n ≤ N do 3: Fix si, update Θ and D: = si + ∆i, ∀i 12: end for 13: return Θ, D, si, xi = Dsi, ∀i Algorithm 2 : Testing on incomplete data Require: Incomplete data vectors {xi}, i = 1, 2, . . . , I, classifier parameters Θ, dictionary D, hyperparameters λ1 and λ2, number of iterations Niter and update rate σ Ensure: Class assigned to each vector yi and sparse representation of full data vectors xi = Dsi, ∀i 1: Sparse coding stage: for fixed dictionary D find sparse representations of observations xi 2: Initialize si, ∀i randomly 3: for n ≤ Niter do 4: ∆i = -σ λ1 ∂J 1 ∂s i + λ2 ∂J 2 ∂s i , ∀i 5: if si(j)[si(j) + ∆i(j)] < 0 then 6: ∆i(j) = -si(j); avoid zero crossing 7: end if 8: si = si -σ∆i, ∀i 9: end for 10: xi = Dsi, ∀i; Compute reconstructions of unobserved vector data xi 11: Classification stage: apply classifier to reconstructions xi 12: yi = arg max y (p y Θ (x)) 13: return Θ, yi, si, xi, ∀i Algorithm 3 : Sequential approach (imputation method) Require: Incomplete data vectors and their labels {xi, yi}, i = 1, 2, . . . , I, hyper-parameters α, λ1 and λ2, number of iterations Niter and update rate σ Ensure: Classifier parameters Θ and sparse representation of full data vectors xi = Dsi, ∀i 1: Initialize D, si, ∀i randomly 2: Dictionary learning and coding stage: update D and si 3: for n ≤ N do 4: D = D -σ ∂J 1

Figure4: Testing accuracy in the grid search for hyper-parameter tuning: λ1 and λ2 were chosen through crossvalidation by maximizing the testing accuracy in all datasets with different levels of missing entries: 25%, 50% and 75%.

Figure 5: Reconstructions of incomplete test MNIST dataset vectors by applying our simultaneous classification and coding algorithm using the CNN4 architecture.

Table1, columns 3 rd through 10 th , show the accuracy obtained in the test step, when the model was trained on incomplete data and applied to incomplete as well as Test accuracy: columns 3 rd through 10 th show the results with incomplete training data and incomplete/complete test data. The baseline results were obtained by training the model on complete data.

Table content: <table><tr><td/><td/><td/><td colspan="3">Random missing entries</td><td colspan="2">Occlusion</td><td>Baseline</td></tr><tr><td>Dataset</td><td>Classifier</td><td/><td/><td colspan="2">%Train / %Test</td><td colspan="3">%Train / %Test %Train / %Test</td></tr><tr><td/><td/><td colspan="5">75/75 50/50 25/25 75/0 50/0 25/0 50/50</td><td>50/0</td><td>0/0</td></tr><tr><td>MNIST</td><td>Log. Reg. CNN4</td><td>90.45 94.62</td><td>93.68 98.34</td><td>94.14 98.94</td><td>91.94 93.44 94.43 98.14 98.94 98.95</td><td>-88.55</td><td>-91.37</td><td>91.95 98.95</td></tr><tr><td>Fashion</td><td>CNN4+BN</td><td>83.71</td><td>86.09</td><td>86.38</td><td>86.39 87.11 87.04</td><td>81.73</td><td>82.47</td><td>90.76</td></tr><tr><td>CIFAR10</td><td>Resnet18</td><td>43.73</td><td>47.27</td><td>47.15</td><td>44.07 45.87 46.45</td><td>-</td><td>-</td><td>86.22</td></tr></table>

Test Accuracy obtained on MNIST and CIFAR10 dataset using standard sequential methods and compared to our simultaneous algorithm.

Table content: <table><tr><td>and Figure 6</td></tr></table>

Hyper-parameter tuning: crossvalidated hyperparameters λ1 and λ2 obtained for MNIST and CIFAR10 datasets with the classifiers used in our experiments.

Table content: <table/>

Peer review (iclr2020):
1. Summary The authors propose a scheme for simultaneous dictionary learning and classification based on sparse representation of the data within the learned dictionary. Their goal is achieved via optimization of a three-part training cost function that explicitly models the accuracy and sparsity of the sparse model, simultaneously with usual classification error minimization. An alternating optimization algorithm is used, alternating between sparse representations and other parameters. The problem they want to address with this scheme is training over incomplete/partial feature vectors. A clean theoretical statement is provided that provides conditions under which a classifier trained via partial feature vectors would do no better in terms of accuracy, had it been trained on complete feature vectors. The authors claim this condition can be checked after training, although this ability is not validated/illustrated numerically. 2. Decision and Arguments Weak Accept a) Very nice mathematical result and justification. The proof is clear. However, why wasn’t the result used in the numerical section? You claim that the condition (4) can be evaluated to test optimality: how do your trained dictionaries compare to say another dictionary learning scheme? After all, this doesn’t seem to inform your actual learning scheme and is not used to evaluate your results. It would be nice to see a numerical validation/illustration of this result. Also is delta_K really that easy to compute? b) The numerical results are good—but lack error bars and comparators. I don’t understand why you considered so many comparators on synthetic data and none on more ‘realistic’ benchmark data. c) Also I don*t feel very satisfied doing image examples, it would be more interesting to work on difficult (eg medical) classification problems with large feature vectors 4. Additional Feedback a) Very well and clearly written with intuitive examples and clean math. My only suggestion is to clarify in the abstract that there are missing *features*-- when I first read *incomplete data* I think of entire data samples that are missing from the training set. That makes no sense, but it became clear when I got to section 2. b) Please use markers and dashes etc. with *every* line in your plots. It is hard (or impossible for many) to compare as is with such tiny thin lines. 5. Questions a) Could you comment on statistical significance of your results? For synthetic data it should be easy to perform the experiments on a number of mask realizations and include error bars. b) Why no comparators on benchmark datasets? c) The proof of Thm 3.2 is nice—but how reasonable is the assumption that you have two dictionaries each with the exact same RIP constant delta_K? Can that property be enforced (even approximately) during training? Or is it trivial that, given one such dictionary, there exists a second one? d) See 2.a