Supervised learning with incomplete data via sparse representations
Authors: Cesar F. Caiafa
Ziyao Wang
Jordi Solé-Casals
Qibin Zhao
Venue:  (2020)
Keywords: Incomplete data
supervised learning
sparse representations

Abstract: This paper addresses the problem of training a classifier on incomplete data 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, assuming sparse representations of data vectors on an unknown dictionary. 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.

Under review conference paper at ICLR 2020
SUPERVISED LEARNING WITH INCOMPLETE DATA VIA SPARSE REPRESENTATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
This paper addresses the problem of training classifier dataset with missing features and its application to a complete or incomplete test dataset. A supervisod learning method is developed to train general classifier, such as 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 struc- tured. The proposed method simultaneously learns the classifier, the dictionary and the corresponding sparse representations of each input data sample. A theoretical analysis also provided comparing this method with the standard imputation approach, which consists performing data completion followed by training the classifier based on their reconstructions. The limitations of this last "sequential" approach are identified, and description of how the proposed new "simultanc- ous" method can overcome the problem of indiscernible observations is provided. Additionally, it is shown that, if it is possible to train classifier incomplete inservations 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 lcarning with missing entries to apply entry imputation as a preprocessing step, followed by standard training based on these reconstructions (Little & Rubin 2014p. For example, some techniques compute missing entries using statistical methods, such as the "mean", "regression" and "nultiple" 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 YYoon & Lee 1999 Bengio & Gingras 1995). tensor completion algorithms "So6-Casall et al. 2018) and others (García-Lacncina 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

---

Under review conference paper at ICLR 2020
approach is avoid direct imputation of lost inputs and rely on a probabilistic model of input data, learning model paramcters 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 ex 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, Le. the reconstruction of signals from incomplete measurements. Several algorithms for matrix and tensor (multidimensionall 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 calegory of models ranges from sparse representation of vectors (Aharon el 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 dictionarios (Ramirez et al. 2010 Sprechmann & Sapiro (0100) or using a single one for all classcs (Tosic & Frossard] 2011p.
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 ( we introduce the simultaneous classification and coding approach, which consists of incorporating a sparse data representation model into cost function optimized for training the classifier and, at the same time, finding the best sparse representation of the observed data. We provide theorctical conditions under which we can guarantee that the obtained classifier is as good as the ideal classifier. In section $ a computational method is presented to train a classifier on incomplete data; in section 5 exlensive experimental results are presented using synthetic and well known benchmark datasets illustrating the effectiveness of our proposed algorithms; and finally, in section G the main conclusions are outlined.
1.1 PRELIMINARY DEFINITIONS AND PROBLEM FORMULATION
We assume& a supervised learning scenario with vector samples and their labels Bx,, ., I, x; E R. and yi 10. C 1) (C classes), so that we only have access subsets of entries in each data vector along with their labels, which is denoted by {x, y. X; E R M with M < N.
The success of CS theory 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 OOshansen & Field 1996 1997: Lee et al., 2007). We define the set of all K-sparse vectors Σ = {s R. such that s/ S K} (containing at most K non-zero entries) and assume that data vectors X, admit K-sparse representations over an unknown dictionary D E R NxL. (L 2 N), ie. x, Ds; with 8; E E The columns d, E R. 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; to have the observed values placed in the upper M positions, so that we can write:
x; =
x; z
with 2, E R (N-M.
(1)
2

---

Under review conference paper at ICLR 2020
However, our results are valid for any pattern of missing entries for each data vector. Accordingly, we define D; E RR*x as the shuffled version of D, such that it stacks in the top M rows those corresponding the observed entries:
D =
Dj E.
with D, E R RxL and E, E R (N)
(2)
Some important uniqueness properties of sparse vector reconstructions are characterized by the Restricted Isometry Property (RIP) of matrix, which defined as follows: matrix A R RNxL satisfies the RIP of order K if there exists dœ E 1) such that (1 - |ss| I ||As < (1+8g]]ll) holds for all E Σ RTP was introduced the context of CS by Candes and Tao (Candès Tao 2005) and characterizes matrices which are nearly orthonormal when operating sparse vectors.
Let us assume that a perfect classifier pe (y | x) in a two classes scenario (y: E {0, 1]), e.g. a logistic regression or deep neural network, can be trained on the complete dataset (x,, such that 0.5 < ( = 1 x,) I 1.0 and 0 S (3 = x.) S 0.5, Vi = =, 1,2....... where is the set of trained parameters. We want to develop method to estimate the classifier parameters Ô using only the incomplete data {K,, yi and to identify the conditions under which such classifier is compatible with the idcal classifier. In the following section we will show that, when data imputation based on sparsity followed by training 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 nunbers "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; and xj belonging to classes "3" and "8", respectively,
shown in Figure I (a-d). Here, we are clearly faced with the indiscernible observations problem because our observations of two vectors from different classes are identical (X; =,y). It is obvious that at least
two possible 2-sparse representations for the observed data exist, let's say X; = D Dis,, with si S 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 & are unique, then x, can be perfectly recon- structed 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 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 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 simultancously their sparsest representations and the classifier, such that the classification error of the reconstructions is minimized.
3

---

Under review conference paper at ICLR 2020
3 THE SIMULTANEOUS CLASSIFICATION AND CODING APPROACH
In the previous section, we showed that passd imputation methods using only the information on available entries are prone to fail because the non-uniqueness of solutions can make the training of good classifier an impossible task. It is interesting 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 NxL. A two-dimensional simplified visualization for this example is provided in Figure Te). When we apply a sparsity-based reconstruction algorithm on observations X,, and X, such that x, ==xx, Xj and, assuming for now that dictionary is known, we search for the K-sparse representation that compatible with the measurements, i.c. we find s E E such that x; = D,s. In this case, there are at least two equally acceptable solutions s; and 8j corresponding to vectors x; and X;, respectively. If we were to make the wrong decision of assigning s; to x; and s; to Xj, then the resulting set of reconstructed vectors would not be linearly separable, which is illustrated in Figure I therefore would be impossible to find a linear classifier. The key observation here is that, in order to assign the proper sparse representation information Y/ and Vj, and make the solution unique by discarding any K 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.
could also look at the label
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
R and scalar (bias) b E R. and perfect classifier exists if there is hyperplane that separates both classes, i.e., for each data vector x;: f(x,) when yi 1 and fxx) S 0 if y, O. We investigate the conditions under which perfect classifier can be trained using incomplete data samples and their labels. By using the same shuffling as in equation (L), we can write the partition of the shuffled coefficients w, E RN as follows:
x,'x+bb > 0
W; where u, E R (N-M)
W;-
(3)
Since the classifier is based on the feature (xx) wf x; + = wf'x; uf + b, the vector u, R (M) contains the weights associated with unobserved entries z, The following definition introduces a way to measure the amount of discriminative information associated with missing entries.
Definition 3.1. Discriminative Missing Information (DMI) Pe: Given a classifier (w, b) and a partition of observed/ boserved/missing entries in sample vector such that the shuffled vector of coefficients w; can be partitioned as in eq- 31 we define the DMT for somple x; as: p4 ||u:|| ΣM-M [u.(m))
Intuitively, if the DMI is small enough, the classification will not strongly depend on the unobserved entrics 2; and then a classifier could be trained from incomplete data samples. The following theorem establishes precise conditions under which the existence of classifier obtained from incomplete
4

---

Under review conference paper at ICLR 2020
dj
d2
ds
d2
(e)
(1)
222
3" class
I3
(b)
dg
d,
X;
d
3
8
5
(c)
d
d3
d.
(d)
d dr d d,
"8" class
P
P
P
B
D
Unavailable
"5" class incomplette observetions
X class incomplete observations
Figure 1: An indiscermble observation toy example: (a) 4 out L dictionary elements d; (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 d, (d) An occluded digit "3" or "8" admits more than one 2-sparse representation, for example, they be expressed the sum of occluded aloms dj and d2, dg and d.. (e) Simplified swo-dimensional represenlation samples x" [I1, E R from "3" and "g" classes that are linearly separable where incomplete observations are taken by observing only one entry. Note that x, and belong to different classes but their observations are identical. (f) A wrong reconstruction of data vectors, i.e. & # and &; + Xj can make the set of reconstructed vectors not linearly separable.
data can be guaranteed and thus, perfect classifier can be successfully trained. The proof can be found in Appendix A
Theorem 3.2. Given a dataset {x:, i i 1,2,, with normalized data vectors A|xil S 1) admilting a K-sparse represenlation over a dictionary D E RN with unil-norm columns and satisfying the RIP of order dictionary D' E R NXL also satisfying the RIP of order K with constant ôк such that, for the incomplete observation &; E RM, the K K-sparse representation solution non-unique, i.e. 3,,,s/ e Σ such that &; = D.S; = D's', where D, D' E R M are the matrices containing the observed rows of D and D', respectively; s; E R the vector of coefficients of the true data, i.e. x; DDs and sy provides a plausible reconstruction through &4 Dís, with ||,, 1. If perfect classifier {w,, b} of the reconstruction &; exists such that
with constant őK. and suppose that, we have obtained an alternative
<> 2k 8k),
(4)
with e > O being the minimum distance of reconstructed data sample to the separating hyperplane, then the full data vector x, is also perfectly separated with this classifier, in other words: fxx:) w/ x; + b 0 0) if =1 (1: 0).
is interesting to note that, supposing that we have obtained a classifier from incomplete data, if we are able to evaluate condition 4 then can figure out whether such classifier is optimal by testing the condition of the theorem. However, It well known that, in general, the RIP constant is difficult to compute in practice. When the dictionary is highly uncorrelated]] i.c. if pk < 1, then the RIP constant can be written in terms of the correlation coefficients as follows: ōk (K- 1)p (Eldar & Kutyniok 2012), and p 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 e); (b) very sparse model (small K); (c) small norm variability of transformed K-sparse vectors through D (small 6x), which can be interpreted as
"Corrllatoon coefficient is the maximum absolute correlation between any two columns in normalized dictionary.
5

---

Under review conference paper at ICLR 2020
quasi-orthonormal basis behaviour (Jow correlation, for example); and (d), small weights assigned to unobscrved entries of x; (small DMI js)).
4 THE PROPOSED METHOD
Here, we propose 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 consider that x, & and are now the original unruffled vectors and the pattern of missing features is not the same for each data sample i:
Σ (Jo(O,&,,)) JD,,s + )2)2(s))).
where O contains the classifier parameters, i.e. the vector of coefficients and bias for logistic ic regression model, or the vector of weights in deep neural network classifier architecture; D RNL (L 2 N) is a dictionary and s; E R are the representation coefficients such that the reconstructed data vectors are & Ds,- Jo(O, &;, yb) is a measure of the classification error for sample i. Typically, we use the crossentropy mcasure, i.c. Jo(O, x, = - log(r (x)), where p (x,) is the probability assigned by the classifier to sample x; belonging to class ys- (D, s;) is a mcasure of the error associated with the sparse representation when it is restricted to the observed entries, and is defined N ||m (x, - -Ds:) where stands for the entry-wise product, m; R the observation mask for sample i, with (n) E [0.1) such that m2(n) = 1 or 0 if data entry x; (n) is available or missing, respectively. (s, = 1 |s is the 4-norm whose minimization promotes the sparsity of the representation (Candès & Tao 2005). Finally, the hyper-parane syper-perameters x and X allow to give more or less importance 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.
follows: Ji (D, s:) M
To minimize the cost function in equation we propose to alternate between the optimization over [},D] and s; (i 1.2.....JJ I). As usual, we adopt first order (gradient based) search of minima, where gradients of functions Jo(.), (.) and J2(-) are easily derived. Note that in the case of feedforward architectures, the back-propagation technique Jo(.). It is also noted that function Jz(-) 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 correspouding full vector reconstructions and apply the classifier to them. The algorithms are presented in Appendix
be used for the first term
5 EXPERIMENTAL RESULTS
We synthetically generated = 11, 000 (10, 000 training +00 000 test) K-sparse data vectors x; E R 100 using dictionary D E R 10002000 obtained from a Gaussian distribution with normalized aloms, R was randomly chosen
Le. [D( = 1, VI. random hyperplane { (w,b) b} with w E R.N, dividing data vectors into two classes according to the sign of the expression wTx + b, which defines the value of label y4. 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 For cach case we generated 10 realizations using different masks and input data. We applied simultancous method, with hyperparameters x and X tuned via cross-valin validation, to train
6

---

Under review conference paper at ICLR 2020
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 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 simultancous algorithm.
K=4, d=0.0
K=32, d=0.0
K=4, d=0.2
K=32, d=0.2
Simult.
*
*
8
1.0
Seq. Sp.
*
ZF
0.9
Test accuracy
-Q- MU
0.8
MS
KNN-10
0.7
KNN-20
0.6
KNN-50
0.5
KNN-100
0.25
0.50
0.75
0.25
0.75 Missing entries
0.50
0.25 Missing entries
0.50
0.75
0.25
0.50
0 0.75
Missing entries
Missing entries
P < 0.05
Figure 2: Experimental results syuthetic dataset using our "simultancous" " (red thick solid line) compared to various "sequential" methods. Obtained lest accuracy (mean 1 s.e.in 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).
We also applied our algorithm to three popular computer vision datasets: MNIST [eCun et al. 1989) and Fashion (Xiao et al. (017) consisting of 70,000 images (60,000 train + 10,000 test) each; and CIFAR1O (Krizhevsky & Hinton 2009) having 60,000 images (50,000 train + 10,000 test). MNIST/ /Fashiosn datasets contains 28 x 28 gray scale images while CIFAR10 dataset is built upon 32 x 32 x color images of different objects. The corresponding data sample size is N 28 x 28 = 784 for MNIST MNIST/Fashion and N = 32 x 32 x 3 = 3, 072 for CIFAR10. We considered a dictionary of size 024 (CIFAR10) and applied our simultancous 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 HIIST/Fashian Fasshoon. We used a logistic regression classifier (single layer neural network) and 4-layer convolutional neural network (CNN4) for the MNIST/Fashion dataset using batch normalization (BN) in the Fashion dataset, while for CIFAR10 dataset, residual neural network (Resnet-18, (He let al. 2016)) was implemented. Table 1 columns 3rd through 10th, show the accuracy obtained in the test step, when the model was trained on incomplete data and applicd to incomplete as well as
784 x 784 (MNIST/ /Fashion) and 1, 024
7

---

Under review conference paper at ICLR 2020
Random uniseing entries
Occlusion
Baseline
Dataset
Classifier
TeTest
Traain
Test
76/76
60/50
25/25
75/0
50/0
26/0
50/60
50/0
0/0
MNIST
Log, Reg.
90:45
93.68
91.11
91.91
95.31
94:35
99 91.305
CNN4
91.37
Fashion
CNN4 EN
83.71
86.05
86.38
86.30
87.11
87.04
81.73
82.47
500.0
CIPARTIO
Resnet I8
03.73
47.27
47.15
41.77
45.87
46.45
86,22
Table 1: Test accuracy: columns 3rd through 10th show the results with incomplete training data and cromplete/complett test data. The baseline results were obtained by training the model complete data.
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 [ and [ 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 parpee-prameters Y and d were adjusted by cross-va validation through a grid-search, as shown in Appendix C In Fig. B we present some selected examples comparing the original images in the MNIST/Fashion FFashion 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
mask (75% missing entries)
Coclusion (50% missing entrios)
recing othamee origial
/:
3
9
S
2
6
7
8
2
7
6
7
7
O
/
3
5
9
6
7
g
Figure 3: Reconstruction of MNIST test data with missing entries: original images (top), incomplete observations (widdle) and their reconstructions (botlom).
6 CONCLUSIONS
We demonstrated that assuming sparse representation model for input data vectors allows the successful learning of 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- sero-filling, supervised/ unsupervised mean and KNN based methods. Our approach is conceptually similar to the work in Ghahramani & Jordan (1993 but, instcad 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 & Aviyento (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 lj norm.
2 petppe /ttttp///gtthbb... //ggthub.ccom torch/ exxmmles// twee/ master mnnit batpes/ //gtthbb.com. auangluu/ wetpnggluppyptohhhoo citfr
8

---

Under review conference paper at ICLR 2020
REFERENCES
M Aharon, M Elad, and A Bruckstein. K-SVD: An Algorithm for Designing Overcomplete Dictio- naries for Sparse Representation. Signal Processing, IEEE Trensactions on, 54(11):4311 4322, 2006.
Gustavo E A P A Batista and Maria Carolina Monard. A Study of K-Nearest Neighbour an Imputation Method. HIS, 2002.
Yoshua Bengio and Francois Gingras. Recurrent Neural Networks for Missing or Asynchronous Data. NIPS, 1995.
Cesar F Caiafa and A Cichocki. Computing Sparse representations of multidimensional signals using Kronecker bases. Neural Computation, pp. 186 220, December 2012.
E.J. Candès and T Tao. Decoding by Linear Programming. Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 51(12):4203 4215, December 2005.
Emmanuel Candes and Terence Tao. The Power of Convex Relaxation: Near-Optimal Matrix
Completion. Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 56(5):2053 200200003000,,0
April 2010.
Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications pure and applied mathematics, 59(8):1207 2006.
D L Donoho. Compressed sensing. Institute of Electricol and Electronics Engineers. Transactions on Information Theory, 52441122991131) March 2006.
YC Eldar and Gitta Kutyniok. Compressed Sensing: Theory and Applications. New York: Cambridge Unio. Press, 20:12, 2012.
M J Fadili, J-L Starck, and F Murtagh. Inpainting and Zooming Using Sparse Representations. The Computer Journal, 52(1):64-79, February 2008.
Francoise Fessant and Sophie Midenet. Self-Organising Map for Data Imputation and Correction in Survcys. Neural Computing and Applications, 10(4):300-310, 2002.
Pedro J Garcia-Laencina, José-Tuis Bancho-Gómez, and Aníbal R Figueiras-Videe Vidal. Pattern classifica- tion with missing data: a review. Neural Computing and Applications, 19(2):263-2))) 282, September
2009.
Zoubin Ghahramani and Michael T Jordan. Supervised learning from incomplete data via EM approach. NTPS, 1993.
Karol Gregor and Yann LeCun. Learning Fast Approximations of Sparse Coding. ICML, 2010.
Trevor Hastie, Robert Tibshirani, and Jerome H Friedman. The elements of statistical learning data mining, inference, and prediction, 2nd Edition. Springer series in slalistics, 2009.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. 2016 IEEE Conference on Computer Vision and Pallern Recognition (CVPR, pp. 770 778. IEEE, 2016.
Ke Huang and Sclin Aviyente. Sparse Reprosentation for Signal Classification. NIPS, 2006.
9

---

Under review conference paper at ICLR 2020
Sheng-Jun Huang, Miao Xu, Ming-Kun Xie, Masashi Sugiyama, Gang Niu, and Songean Chen. Active Feature Acquisition with Supervised Matrix Completion. arxiv. pp. arXiv:1802.05380, February 2018.
A Krizhevsky and G Hinton. Learning multiple layers of features from tiny images. PhD thesis, Toronto University, 2009.
Yann LcCun, Bernhard E Boser, John S Denker, Donnic Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel. Handwritten Digit Recognition with Back-Propagation Network. NIPS, 1989.
Honglak Lee, Alexis Battle, Rajat Raina, and Andrew Y Ng. Efficient sparse coding algorithms. In Advances in Neural Information Processing Systems, pp. 801 808. Stanford University, Palo Alto, United States, December 2007.
Roderick J A Little and Donald B Rubin. Statistical Analysis with Missing Data. John Wiley & Sons, August 2014.
Liu, Przemyslaw Musialski, Peter Wonka, and Jieping Ye. Tensor Completion for Estimating Missing Values in Visual Data. IEEE Transactions on Pottern Analysis and Machine Intelligence, 35(1):208 220, November 2012.
Julien Mairal, Jean Ponce, Guillermo Sapiro, Andrew Zisserman, and Francis R Bach. Supervised Dictionary Learning. In Advances in Neural Information Processing Systems (NIPS), 2008.
A Olshausen and D Field. Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature, (61633)):6607 609, June 1996.
BA Olshausen and DJ Field. Sparse coding with an overcomplete basis set: A strategy employed by V1? Vision research, 37(23):3311 3325, 1997.
Ignacio Ramirez, Pablo Sprechmann, and Guillermo Sapiro. Classification and clustering via dictionary learning with structured incoherence and shared features. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pallern Recograttion, pp. University of Minnesota System, United States, IEFF, August 2010.
J Solé Cosé-Casals, C Caiafa, Q Zhao, and A Cichocki. Brain-Computer Interface with Corrupted EEG Data: Tensor Completion Approach. Cognitive Compulation, 10(6):1062 1074, July 2018.
Pablo Sprechmann and Guillermo Sapiro. Dictionary learning and sparse coding for unsupervised clustering, In ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing Proceedings, pp. 2042 2045. University of Minnesota System, United States, IEEE, November 2010.
Ivana Tosic and Pascal Frossard. Dictionary Learning. IEEE Signal Processing Magazine, 28(2): 27- 27-38, March 2011.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: a Novel Image Datasct for Bench- marking Machine Learning Algorithms. arXiv.org, pp.
August 2017.
Song Yee Yoon and Soo Young Lee. Training algorithm with incomplete data for feed-forward neural networks. Newral Processing Letters, 10(3):171-179, January 1999.
Longhao Yuan, Chao Li 0013, Danilo P Mandic, Jianting Cao, and Qibin Zhao. Tensor Ring Decomposition with Rank Minimization on Latent Space An Efficient Approach for Tensor Completion. arXiv, es. Ls 2018.
10

---

Under review conference paper at ICLR 2020
A PROOF OF THEOREM 3.2
Proof. Let us first consider the case with yi = 1. We assume that able to find perfect classifier on the reconstructed full data vector such that
- =
0,
(6)
where &, Dis;, Now, note that the K-sparse representation solution given the observation non-unique, i.e. 7s, s/ Ex, such that &; D,S, D's!. We assume that s; is the true K-sparse vector such that the unobserved full vector is x; = D,s, and s provides an alternative reconstruction through D which explains the observations but &; # x₃.
Analogously to equation
we can find a partition of the reconstructed vector &; as follows:
x z
D E
x;
where z e R and we want prove that f(x;) implies f(x)) 0, i.. the original data vector X, (unobserved) is also correctly classified by the logistic regression with parameters {w,, 6). To that end we need evaluate the following expression:
f(x,) = wf x + w &; + u 2; +
(8)
where equation 3 was used. If we add and substract uf z and arrange the terms in the previous equation, we get:
f(x:) w/ + uf 25 + b+ uf (z, -(),, zi), = f(x)) + u E.s; un E/s/.
(9)
(10)
The first term in the right-hand side of last equation is f(x,) c > 0 so if we show that |u E,s; uf E[s] < then the proof will be complete. To do so, we can write:
Eu,E, - E S Iu E.S. + uu E/s/
(11)
and
N- M
N
N- M
N
Ju E,s:
Σ (m) m=l
[, m))
Σ m=1
In (m))
Σ n=l
Em n)]ls:(n)))
(12)
Since we assumeed normalized vectors ||x;|| < 1, by applying the left-hand side of the RIP we
obtain: ||s||| I 1/(1 8x), which implies that [sx(n)] < 1/(1 5g). Now, taking into ac-
count that E,(m, n)] < 1 (columns of are unit-norm) and using the fact that s; E Σ
we obtain: |u] E,s: 5 [I-Ox] ΣM=M [u((m)]; and, similarly, can obtain that Ju E.s]] S
K
K Σ - [m)). Putting everything together into equation 11 get:
(1-6k)
N M
2K
u E.T E/ S
[,(mm) <e
(13)
8k)
where we used that ΣN-M [u,(m) <(1-xx) which completes the proof for the case y/ 1. 2k
Similarly, it is strait-forward to prove that, if yi = 0, having f(x)) < -c < 0 implics that f(x) < 0.
11

---

Under review conference paper at ICLR 2020
B ALGORITHMS
Here, the pseudocode of the algorithms discussed in the paper are presented. In Algorithm I the simultaneous classification and coding method is described. It consists in the iteralive 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 8;, compute the full data vector estimations and, finally, apply the classifier.
The standard sparsity-based imputation method is presented Algorithm (sequential approach), which consists of learning first the optimal D and sparse coefficients 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 reconstrueted input data vectors & Ds;.
Algorithm 1 Simultancous classification and coding (training on incomplete data)
Require: Incomplete data vectors and their labels {&, Mr), 1,2,.....4 number of iterations Nater and update rate a
a, and A2,
Ensure: Classifier parameters è and sparse representation of full data vectors & Ds,, Vi 1: Initialize O, D, Vi randomly do
for Fix 8., update and D: 2d J6 D= - - 8J
4: e θ
D
MD
5: Normalize columns of matrix
6: Fix ④ and D, update s;, Vi:
A. = as.
if s;())ss((j) A.()) then
A.(j) = s;(i); avoid zero crossing 10: end if
11: Si A., Vi
12: end for
13:
return D,D.s. Ds,, Vi
Algorithm 2
Testing on incomplete data
Require: Incomplete data vectors {x,], i= 1,2...., classifier parameters θ dictionary D, hyper- parameters Å and λς, number of iterations Nater and update rate
Ensure: Class assigned to each vector ya and sparse representation of full data vectors Ds., Vi
Sparse coding stage: for fixed dictionary find sparse representations observations x;
2: Initialize St, Vi randomly
3: for < Niter do
A. - X 0J1 + A2 0J2], Vi
08,
5: if (s) Adt) ( then
A.l)) (;);;; avoid crossing
end if
8: 8: = Si AA. Vi
9: end for
10: &, Ds,, vi; Compute reconstructions of unobserved vector data
11: Classification stage: apply classifier reconstructions x;
12: 81 = =ar max, (pg())
13: return O yi, 8i, &;, Vi
12

---

Under review conference paper at ICLR 2020
Algorithm 3 Sequential approach (imputation method)
Require: Incomplete data vectors and their labels (&, y:), i 1, hyper-parameters a, A and d2, number of iterations Niter and update rate
Ensure: Classifier parameters and sparse representation of full data vectors Ds,, Vi
1: Initialize D,s,, randomly
2: Dictionary learning and coding stage: update D and 8;
3: for < N do
4: D = D 0/
Normalize columns matrix D
A. = -a A1 8s
aJ + A2 0J2
Ss; 1 Vi
7: (:) A.() 0 then
8:
A.( = (i); avoid zero crossing
9: end if
10:
A., Vi
11: end for
12: &; = -D,, vi; Compute reconstructions of unobserved vector data X,
13: Training stage: update θ
14: for n < N do
15: =
Update O:
16: end for
17: return &,D,s.& = Ds,, Vi
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, Mcan 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 CIFARI0 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 random missing features 75%.
C.2 HYPERPARAMETER TUNNING
In Table 3 and Figure 4 present the results of the grid search for syper-parameter tuning MNIST and CIFAR10 datasels. We fit our model to the training dataset for a range of values of parameters Àι and A2 and apply 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, 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 and Figure
13

---

Under review conference paper at ICLR 2020
MNIST (CNN4)
Missing
ZF
MS
KNNIO
KNN20
KNN50
KNN100
Simul
75%
84.14
83.69
88.10
87.68
86.77
86.11
98.14
50%
89.65
88.40
91.22
90.94
90.72
90.68
98.94
CIFARIO (Resnet18)
Missing
ZF
MS
KNN10
KNN20
KNN50
KNN100
Simul.
75%
18.7
21.98
33.10
34.78
29.56
30.55
44.07
50%
41.35
17.79
31.54
36.94
31.16
30.78
45.87
Table 2: Test Accuracy obtained on MNIST and CIFAR10 dataset using standard sequential methods and compared to our simultancous algorithm.
Random missing entries
Occlusion
Dataset
Classifier
75%
50%
25%
50%
X2
A
Aa
A
X2
Log. Reg.
0.32
1.28
0.64
1.28
0.64
1.28
MNIST
CNN4
1.28
1.28
2.56
1.28
5.12
1.28
10.24
10.24
CIFAR1O
Resnet18
0.024
0.008
0.032
0.004
0.032
0.01
Table Hyper-parameter tuning: crossvalidated hyperparameters d and d2 obtained for MNIST and CIFAR10 datasets with the classifiers used in our experiments.
14

---

Under review conference paper at ICLR 2020
25%
50%
75%
0.9448
15
MNIST Log. Reg.
10
0.910C
05
0.900C
log
-08900
0.870C
0.0000
0.9894
MNIST CNN4
0.9759
(og(A2)
0.9200
0.6000
0.4000
0.4715
CIFAR10 Resnet18
-30
-33
0 0.4000
log (22)
45
0
-50
0 2000
0.0800
log(An) (X))
log (11)
(og(
Figure 4: Testing accuracy in the grid search for hyper-parameter tuning: a1 and x2 were chosen through crossvalidation by maximizing the testing accuracy in all datasets with different levels of missing entries: 25%, 50% and 75%.
15

---

Under review conference paper at ICLR 2020
Random mask (75% missing entries) original
Occlusion (50% missing entries) original
observed reconst.
observed reconst.
1
1
2
2
2
2
2
3
3
3
3
3
1
4
165
4
5837
5
5
5
5
6
7
7
7
7
8
8
8
8
9
9
9
7
9
Figure 5: Reconstructions of incomplete test MNIST dataset vectors by applying our simultaneous classification and coding algorithm using the CNN4 architecture.
16

---

Under review conference paper at ICLR 2020
Random mask (75% missing entries) original observed reconst.
Occlusion
(53% missing entries)
original observed reconst.
Figure 6: Reconstructions of incomplete test Fashion datasel vectors by applying our simultancous classification and coding algorithm using the CNN4 architecture with Batch Normalization (BN).
17


Reviews:
[{"review_id": "rylmQK7y9S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This manuscript studies supervised learning with incomplete observation of the features, assuming a low-rank structure in the full set of features. The work tackles the problem with a global cost function that optimizes the classifier on observations reconstructed with a dictionary penalized jointly for sparse coding. Importantly, the dictionary is optimized both for the supervised-learning task (the classifier) and the sparse coding. The manuscript contributes a theoretical argument showing with sparse-recovery arguments that if the data can be decomposed sparsely, the incomplete feature prediction problem can perform as well as the complete one. Finally, it performs a empirical study on simulated data as well as computer-vision problems with random missing pixels as well as occlusions, and using for the classifier logistic regression as well as classic neural network architectures.\n\nThe work is interesting, but I have several big-picture comments on the framing of the work. The first one is that framing the problem as a missing values one, referring to the classic missing-values literature, does not seem right to me. Indeed, in the missing-values literature, different features are observed on different samples, which leads to a set of problems and corresponding solutions. The contribution here is a different one. My second big picture comment is that it seems that this is very much related to the classic work \"supervised dictionary learning\" by Mairal et al. The framing of the Mairal paper is that of a representation-learning architecture: the cost function is there to impose an inductive bias. Added to a linear model, it contributes representation learning, and hence can bring some of the appealing properties of deep architectures. This is very much what the experimental study reveals, where the contributed architecture with latent factors outpeforms the linear model on fully observed data. With these two comments, I would like to know better how the work positions itself to supervised dictionary learning: the paper is cited (albeit with an incorrect citation), but the positioning is not explicit.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gAnrEtdr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Summary\nThe 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.\n\nThe 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.\n\n2. Decision and Arguments\nWeak Accept\na) 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?\nb) 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.\nc) 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\n\n4. Additional Feedback\na) 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.\nb) 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.\n\n5. Questions\na) 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.\nb) Why no comparators on benchmark datasets?\nc) 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? \nd) See 2.a\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "BJlRQqNS5B", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method for simultaneously imputing data and training a classifier. Here are my detailed comments:\n\n1. The proposed method is a simple combination of dictionary learning and classification. As can be seen from (5), J_1 and J_2 are the loss function for dictionary learning, and J_0 is the empirical risk for classification (J_0). I did not see much novelty here.\n\n2. There exists a capacity mismatch between data imputation and classifier. The paper claims that the method is proposed for training deep neural networks. However, deep neural networks are capable of modeling very complex distributions (e.g., images), and the dictionary learning only considers a very simple bilinear factorization, which is not of the same modeling capability as neural networks. \n\n3. The experimental evaluations are very weak. Table 1 even does not provide any meaningful baseline methods, e.g., the so-called \"sequential method\".\n\n4. Theorem 3.2 requires the dictionary to be RIP, which is a very strong assumption and unlikely to hold in practice, especially when considering D is actually trained by minimizing (5). The proof of Theorem 3.2 is very elementary, ad-hoc, and does not provide any insight to the problem.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This was a difficult paper to decide, given the strong disagreement between reviewer assessments.  After the discussion it became clear that the paper tackles some well studied issues while neglecting to cite some relevant works.  The significance and novelty of the contribution was directly challenged, yet I could not see a convincing case presented to mitigate these criticisms.  The paper needs to do a better job of placing the work in the context of the existing literature, and establishing the significance and novelty of its main contributions.
Decision: Reject