Deep Network Classification by Scattering and Homotopy Dictionary Learning
Authors: John Zarka
Louis Thiry
Tomas Angles
Stephane Mallat
Venue:  (2020)
Keywords: dictionary learning
scattering transform
sparse coding
imagenet

Abstract: We introduce a sparse scattering deep convolutional neural network, which provides a simple model to analyze properties of deep representation learning for classification. Learning a single dictionary matrix with a classifier yields a higher classification accuracy than AlexNet over the ImageNet 2012 dataset. The network first applies a scattering transform that linearizes variabilities due to geometric transformations such as translations and small deformations.
A sparse $\ell^1$ dictionary coding reduces intra-class variability while preserving class separation through projections over unions of linear spaces. It is implemented in a deep convolutional network with a homotopy algorithm having an exponential convergence. A convergence proof is given in a general framework that includes ALISTA. Classification results are analyzed on ImageNet.

Published as a conference paper at ICLR 2020
DEEP NETWORK CLASSIFICATION BY SCATTERING AND HOMOTOPY DICTIONARY LEARNING
John Zarka, Louis Thiry, Tomás Angles Département d'informatique de I'ENS, ENS, CNRS, PSL University, Paris, France (john. zarka, louis thh ry, tomas ang les) @ens. fr
Stéphane Mallat
Collège de France, Paris, France Flatiron Institute. New York, USA
ABSTRACT
We introduce a sparse scattering deep convolutional neural network, which pro- vides simple model to analyze properties of deep representation learning for classification. Learning a single dictionary matrix with a classifier yields a higher classification accuracy than AlexNet over the ImageNet 2012 dataset. The net- work first applies a scattering transform that linearizes variabilities due to ge- ometric transformations such as translations and small deformations. sparse el dictionary coding reduces intra-class variability while preserving class sepa- ration through projections over unions of linear spaces. implemented in a deep convolutional network with homotopy algorithm having an exponential convergence. convergence proof given general framework that includes ALISTA. Classification results analyzed on ImageNet.
INTRODUCTION
Deep convolutional networks have spectacular applications to classification and regression (LeCun al. 2015), but they are black boxes that are hard to analyze mathematically because of their architecture complexity. Scattering transforms are simplified convolutional neural networks with wavelet filters which are not learned (Bruna & Mallat 2013). They provide state-of-the-art clas- sification results among predefined or unsupervised representations, and are nearly as efficient as learned deep networks relatively simple image datasets, such as digits in MNIST, textures (Brunal & Mallat (013) or small CIFAR images (Oyallon & Mallat 2014 Mallat 2016). However, over complex datasets such as ImageNet, the classification accuracy of learned deep convolutional net- work is much higher than scattering transform or any other predefined representation (Oyallon) al, 2019). fundamental issue is understand the source of this improvement. This paper addresses this question by showing that one can reduce the learning to single dictionary matrix, which is used to compute a positive sparse gz code.
Scattering S
Linear L
Sparse coding in D
Classifier
Figure A sparse scattering network is composed of scattering transform S followed by an optional linear operator L that reduces its dimensionality. A sparse code approximation of scattering coefficients is computed in a dictionary D. The dictionary and the classifier are jointly learned by minimizing the classification loss with stochastic gradient descent.
The resulting algorithm is implemented with simplified convolutional neural network architecture illustrated in Figure 1 The classifier input is positive Ll sparse code of scattering coefficients cal- culated in dictionary D. The matrix is learned together with the classifier by minimizing a clas- sification loss over training set. We show that learning / improves the performance of scattering

---

Published as a conference paper at ICLR 2020
representation considerably and is sufficient to reach a higher accuracy than AlexNet (Krizhevsky al., 2012) over ImageNet 2012. This cascade of well understood mathematical operators provides simplified mathematical model to analyze optimization and classification performances of deep neural networks.
Dictionary learning for classification introduced in Mairal et al. (2009) and implemented with deep convolutional neural network architectures by several authors (Sulam et al. 2018 Mahdizade- haghdam al. 2019; (Sun al.) 2018). To reach good classification accuracies, these networks cascade several dictionary learning blocks. As result, there is no indication that these operators compute optimal sparse e codes. These architectures are thus difficult analyze mathematically and involve heavy calculations. They have only been applied to small image classification problems such as MNIST or CIFAR, as opposed to ImageNet. Our architecture reaches high classification performance on ImageNet with only one dictionary D. because it is applied to scattering coefficients as opposed to raw images. Intra-class variabilities due to geometric image transformations such as translations small deformations are linearized by scattering transform (Bruna & Mallat, 2013 which avoids unnecessary learning.
Learning dictionary in deep neural network requires to implement sparse e code. We show that homotopy iterative thresholding algorithms lead to more efficient sparse coding implementations with fewer layers. We prove their exponential convergence in general framework that includes the ALISTA (Liu et al. 2019) algorithm. The main contributions of the paper are summarized below:
A sparse scattering network architecture. illustrated in Figure 1, where the classification is performed over a sparse code computed with a single learned dictionary scattering coefficients. It outperforms AlexNet over ImageNet 2012.
A new dictionary learning algorithm with homotopy sparse coding, optimized by gradient descent in a deep convolutional network. If the dictionary is sufficiently incoherent, the homotopy sparse coding error is proved to convergence exponentially.
We explain the implementation and mathematical properties of each element the sparse scattering network. Saction@bbiifft reviews multiscale scattering transforms. Section B introduues homotopy dictionary learning for classification, with a proof exponential convergence under appropriate assumptions. Section 4 analyzes image classification results of sparse scattering networks on Ima- geNet 2012.
2 SCATTERING TRANSFORM
A scattering transform is cascade of wavelet transforms and ReLU modulus non-linearities. It can interpreted as deep convolutional network with predefined wavelet filters (Mallat 2016)) For images, wavelet filters are calculated from a mother complex wavelet ú whose average is zero. is rotated by r-o. dilated by 2 and its phase is shifted by a:
( 2- 22j (2 (2- rr_ and Vi Real(e ia
v5..)
We choose a Morlet wavelet as in Bruna & Mallat (2013) to produce sparse set of non-negligible wavelet coefficients. A ReLU written p(a) = max a, 0).
Scattering coefficients of order m are computed by averaging rectified wavelet coefficients with a subsampling stride of 2':
Sx(u, h. a) p(x v3,0,a) (2'2 with & = (j. 0)
where du is Gaussian dilated by 2 (Bruna & Mallat 2013). The averaging by d, eliminates the variations of p(æ * vij.0.a) at scales smaller than 2". This information is recovered by computing their variations at all scales 2 2d, with second wavelet transform. Scattering coefficients of order two are:
Sz(u, k K a,,a) pl(x v3300,) * w )x (2)(2 with k,K' (1,0),(''00'
2

---

Published as a conference paper at ICLR 2020
To reduce the dimension of scattering vectors, we define phase invariant second order scattering coefficients with a complex modulus instead of a phase sensitive ReLU:
Sx(u, k. k/) = || 33,01 Myyool (2 u) for j' >j
The scattering representation includes order 1 coefficients and order 2 phase invariant coefficients. In this paper, we choose = and hence scales S j S J, angles 0 and phases a on 10, 2m Scattering coefficients are computed with the software package Kymatio (Andreux et al. They preserve the image information, and z can be recovered from Sz (Oyallon et al, For computational efficiency, the dimension of scattering vectors can be reduced by factor 6 with a linear operator I. that preserves the ability to recover a close approximation of x from L.S.. The dimension reduction operator L of Figure may be orthogonal projection over the principal directions of a PCA calculated on the training set, or it can be optimized by gradient descent together with the other network parameters.
2018
2019
The scattering transform is Lipschitz continuous to translations and deformations (Mallat 2012 Intra-class variabilities due to translations smaller than 2 and small deformations are linearized. Good classification accuracies are obtained with linear classifier over scattering coefficients in image datasets where translations and deformations dominate intra-class variabilities. This is the case for digits in MNIST or texture images (Bruna & Mallat 2013). However, it does not take into account variabilities of pattern structures and clutter which dominate complex image datasets. To remove this clutter while preserving class separation requires some form of supervised learning. The sparse scattering network of Figure computes a sparse code scattering representation 3 LSx in learned dictionary D of scattering features, which minimizes the classification loss. For this purpose, the next section introduces homotopy dictionary learning algorithm, implemented a small convolutional network.
HOMOTOPY DICTIONARY LEARNING FOR CLASSIFICATION
Task-driven dictionary learning for classification with sparse coding was proposed in Mairal et al. (201)). We introduce small convolutional network architecture implement a sparse t code and learn the dictionary with a homotopy continuation on thresholds. The next section reviews dictionary learning for classification. Homotopy sparse coding algorithms studied in Section 3.2
3.1 SPARSE CODING AND DICTIONARY LEARNING
Unless specified, all norms Euclidean norms. A sparse code approximates vector 3 with linear combination of a minimum number of columns Dm of a dictionary matrix D, which are normalized || 1. It is vector a of minimum support with bounded approximation error |Da 81 < a. Such sparse codes have been used to optimize signal compression (Mallat & Zhang 1993) and remove noise, solve inverse problems in compressed sensing (Candes al. 2006), and for classification (Mairal et al.) (01I). In this case, the dictionary learning optimizes the matrix D in order minimize the classification loss. The resulting columns D' can be interpreted as classification features selected by the sparse code a To enforce this interpretation, we impose that sparse code coefficients are positive, a 0.
Positive sparse coding Minimizing the support of a code amounts to minimizing its g "norm", which is not convex. This non-convex optimization is convexified by replacing the ed norm by an el norm. Since a 2 we have ||a]| = E (m). The minimization of ||a|/ with |Da -1l < a solved by minimizing a convex Lagrangian with a multiplier X, which depends on a:
a = argmin |D - 31 + X, ||a|]1
(I)
a20
One can prove (Donoho & Elad 2006) that a (m) has the same support as the minimum support sparse code a (m) along m if the support size and the dictionary coherence satisfy:
(DD) < 1/2 where ((D) max DD Dmm
(2)
mmrmm
3

---

Published as a conference paper at ICLR 2020
The sparse approximation Da' ! is non-linear filtering which preserves the components of 3 which are "coherent" in the dictionary D. represented by few large amplitude coefficients. It eliminates the "noise" corresponding to incoherent components of 3 whose correlations with all dictionary vectors Dm are typically below X,, which can be interpreted as a threshold.
Supervised dictionary learning with deep neural network Dictionary learning for classifica- tion amounts to optimizing the matrix D and the threshold X. to minimize the classification loss on a training set [Z b. This is a much more difficult non-convex optimization problem than the convex sparse coding problem (I). The sparse code a of each scattering representation 3 = LSw depends upon D and A, It is used as an input to classifier parametrized by θ. The classification loss Σ; Loss( D, ; θ 36, y:) thus depends upon the dictionary 1) and X. (through a and on the classification parameters θ. The dictionary D is learned by minimizing the classification loss. This task-driven dictionary learning strategy was introduced in Mairal et al. (2011).
An implementation of the task-driven dictionary learning strategy with deep neural networks has been proposed in (Papyan et al. 2017: Sulam al., 2018; Mahdizadehaghdam iet al.) 2018). The deep network is designed to approximate the sparse code by unrolling a fixed number N of iterations of an iterative soft thresholding algorithm. The network takes 3 as input and is parametrized by the dictionary D and the Lagrange multiplier X. as shown in Figure 2 The classification loss is then minimized with stochastic gradient descent on the classifier parameters and on D and X The number of layers in the network is equal to the number N of iterations used to approximate the sparse code. During training, the forward pass approximates the sparse code with respect to the current dictionary, and the backward pass updates the dictionary through a stochastic gradient descent step.
al. 2019 Sun
For computational efficiency the main issue is to approximate a' with as few layers possible and hence find an iterative algorithm which converges quickly. Next section shows that this can be done with homotopy algorithms, that can have exponential convergence.
3.2 HOMOTOPY ITERATED SOFT THRESHOLDING ALGORITHMS
Sparse E codes are efficiently computed with iterative proximal gradient algorithms (Combettes & Pesquet 201T). For a positive sparse code, these algorithms iteratively apply a linear operator and rectifier which acts network. We show that homotopy algorithms can converge exponentially and thus lead to precise calculations with fewer layers.
positive thresholding. They can thus be implemented in deep neural
Iterated Positive Soft Thresholding with ReLU Proximal gradient algorithms compute sparse e codes with a gradient step on the regression term || D=1 12 followed by proximal projection which enforces the sparse penalization (Combettes & Pesquet 2011. For positive sparse code, the proximal projection defined by:
prox (B) argmin 1 laa- 3312 + 1/1a-1112 a20
||a||
2
Since |a]|| Σn (mm) for (mm) 2 O, we verify that (8) = p(3 - A) where p(a) max(a, 0) is a rectifier, with a bias X. The rectifier acts positive soft thresholding. where is the threshold. Without the positivity condition a 2 0, the proximal operator in (3) is soft thresholding which preserves the sign.
An Iterated Soft Thresholding Algorithm (ISTA) Daubechies et al. 2004) computes an ld sparse code a by alternating a gradient step on |r - = and proximal projection. For positive codes, it is initialized with og = 0, and:
Øn+1 p(a, + cD Dan) edx) with e DD'DD12.
(4)
where || 21 is the spectral norm. The first iteration computes a non-sparse code a1 = p(eD's 3 eλu)) which is progressively sparsified by iterated thresholdings. The convergence is slow: la, a = OO l). Fast Iterated Soft Thresholding Agorithm (FISTA) (Beck & Teboulle, 2009 accelerates the error decay to Onn-2), but it remains slow.
4

---

Published as a conference paper at ICLR 2020
W
R1 P
AN P a
X+
-1
1
Id W D
P
Id W D
generalized ISTC network computes positive el sparse code in a dictionary D by using auxiliary matrix W. Each layer applies Id W together with ReLU and a bias An to compute Ohp from 0n 1 in 66. The original ISTC algorithm corresponds to W D.
Figure 2:
Each iteration of ISTA and FISTA is computed with linear operators and thresholding and can be implemented with one layer (Papyan et al. 2017). The slow convergence these algorithms requires to use large number N of layers to compute accurate sparse lt code. We show that the number layers can be reduced considerably with homotopy algorithms.
Homotopy continuation Homotopy continuation algorithms introduced in Osborne et al. 2000), minimize the e Lagrangian (I) by progressively decreasing the Lagrange multiplier. This optimiza- tion path is opposite to ISTA and FISTA since it begins with very sparse initial solution whose spar- sity is progressively reduced, similarly to matching pursuit algorithms (Davis et al., 1997] Donoho & Tsaig 2008). Homotopy algorithms are particularly efficient if the final Lagrange multiplier X, large and thus produces very sparse optimal solution. We shall see that it is the case for classifi- cation.
Homotopy proximal gradient descents (Xiao & Zhang 2013) implemented with exponentially decreasing sequence of Lagrange multipliers An for n S N. Jiao, Jin and Lu (Jiao et al. 2017) 7) have introduced an Iterative Soft Thresholding Continuation (ISTC) algorithm with fixed number of iterations per threshold. To compute a positive sparse code, we replace the soft thresholding by ReLU proximal projector, with one iteration per threshold, over n S N iterations:
O₂ = p D'(3 Dan-1) An) with An Amuax (Amax
-n/N
X
By adapting the proof of (Jiao et al. eral framework that if N sufficiently large and Amax 2 [D* then o, converges exponentially to the optimal positive sparse code.
2017) to positive codes, the next theorem proves in more gen-
LISTA algorithm (Gregor & LeCun 2010) and more recent version ALISTA (Liu et al. 2019) accelerate the convergence of proximal algorithms by introducing an auxiliary matrix W which is adapted to the statistics the input and to the properties of the dictionary. Such an auxiliary matrix may also improve classification accuracy. We study its influence by replacing D' by arbitrary matrix W (5). Each column Wm of W normalized by |Wt, Dmn 1. A generalized ISTC is defined for any dictionary D and any auxiliary W by:
Amax X
-n/N
On p(a W Don- Xn) with An Amax
If W = D then we recover the original ISTC algorithm 5 Jiao et al. 2017). Figure 2 illus- trates a neural network implementation of this generalized ISTC algorithm over N layers, with side connections. Let us introduce the mutual coherence of W and D
max mFm
W Dm
The following theorem gives sufficient condition on this mutual coherence and on the thresholds so that an, converges exponentially to the optimal sparse code. ALISTA (Liu et al.) 2019) is particular case of generalized ISTC where W is optimized in order to minimize the mutual coherence jú. In Section we shall optimize W jointly with D without any analytic mutual coherence minimization like in ALISTA.
Theorem 3.1 Let o be the e sparse code of B with error || - Da S If its support satisfies
8 < 1/2
5

---

Published as a conference paper at ICLR 2020
then thresholding iterations O6) with
[W - 1lo
An = Amax 7 A.
(8)
1- 1-2rjus
define an Ory whose support included in the support of a if < < (2jis) ||W* 8l The error then decreases exponentially:
and Xmax
||a - la S Amax 7
The proof is in Appendix A of the supplementary material. It adapts the convergence proof of Jiao et al. (2017) to arbitrary auxiliary matrices W and positive sparse codes. we set W to minimize the mutual coherence then this theorem extends the ALISTA exponential convergence result the noisy case. It proves exponential convergence by specifying thresholds for a non-zero approximation error a.
However, one should not get too impressed by this exponential convergence rate because the condi- tion sp < 1/2 only applies to very sparse codes in highly incoherent dictionaries. Given a dictionary D, it is usually not possible to find W which satisfies this hypothesis. However, this sufficient condi- tion is based convergence. Next section studies learned dictionaries for classification on ImageNet and shows that when W D, the ISTC algorithm converges exponentially although su(D) 1/2. When W is learned independently from D, with no mutual coherence condition, we shall see that the algorithm may not converge.
brutal upper bound calculation in the proof. It is not necessary to get an exponential
IMAGE CLASSIFICATION
The goal of this work is to construct a deep neural network model which is sufficiently simple to be analyzed mathematically, while reaching the accuracy of more complex deep convolutional networks on large classification problems. This is why we concentrate on ImageNet as opposed to MNIST or CIFAR. Next section shows that single L' sparse code in a learned dictionary improves considerably the classification performance of a scattering representation, and outperforms AlexNet on TetgeNet We analyze the influence of different architecture components. Section 4.2 compares the convergence of homotopy iterated thresholdings with ISTA and FISTA.
4.1 IMAGE CLASSIFICATION ON IMAGENET
ImageNet 2012 (Russakovsky et al. 2015) is challenging color image dataset of 1.2 million train- ing images and 50,000 validation images, divided into 1000 classes. Prior to convolutional networks, SIFT representations combined with Fisher vector encoding reached Top 5 classification accuracy of 74.3% with multiple model averaging (Sánchez& & Perronnin 2011). In their PyTorch implemen- tation, the Top accuracy of AlexNet and ResNet-152 is 79.1% % and 94.1 1% respectively?
The scattering transform Sr at a scale 2 = 16 of an ImageNet color image is a spatial array of 14 14 of 1539 channels. If apply Sar the same MLP classifier in AlexNet, with 2 hidden layers of size 4096, ReLU and dropout rate of 0.3, the Top 5 accuracy is 65.3%. We shall use the same AlexNet type MLP classifier in all other experiments, or a linear classifier when specified. If we first apply to Sx 3-layer SLE network of 1x1 convolutions with Rel.U and then the same MLP then the accuracy is improved by 14% and it reaches AlexNet performance (Oyallon et al. 2017). However, there is no mathematical understanding of the operations performed by these three layers, and the origin the improvements, which partly motivates this work.
The sparse scattering architecture is described in Figure 3 A 3 3 convolutional operator L is applicd on a standardized scattering transform to reduce the number of scattering channels from 1539 to 256. It includes 3.5 10 learned parameters. The ISTC network illustrated in Figure 2 has N = 12 layers with ReLU and no batch normalization. A smaller network with = has nearly the same classification accuracy but the ISTC sparse coding does not converge well, as explained in Section 4.2 Increasing N to 14 or 16 has little impact on accuracy and on the code precision.
is "Code to reproduce httprmmmiiiiiiiiiiaattttttttttto http://iiiaaaaeaapaeeettaaaaaaa
AAccurcciss from http://///poooooooooo//////eeeee
html

---

Published as a conference paper at ICLR 2020
Scuttering
Linear
ISTC e sparse coding
α
Classifier
transform
LSX
X
Sx
y
Da
Figure 3: Two variants of the image classification architecture: one where the input for the classifier is the sparse code a, and the other where the reconstruction Da is the input for the classifier.
The sparse code is first calculated with a convolutional dictionary D having 2048 vectors. Dictionary columns Dm have a spatial support of size and thus do overlap when translated. It preserves a small dictionary coherence so that the iterative thresholding algorithm converges ex- ponentially. This ISTC network takes as input an array LSx of size 14 x 14 256 which has been normalized and outputs code a of size 14 x 14 x 2048 or a reconstruction Da. of size 14 x 256. The total number of learned parameters in D is about 10 The output a or Da of the ISTC network is transformed by batch normalization, and 5 x average pooling and then provided as input to the MLP classifier. The representation is computed with 4 10 parameters in and D, which is above the 2.5 10 parameters of AlexNet. Our goal here is not reduce the number of parameters but to structure the network into well defined mathematical operators.
Table 1: Top and Top 5 accuracy on ImageNet with same MLP classifier applied to differ- ent representations: Fisher Vectors (Perronnin & Larlus] 2015), AlexNet (Krizhevsky et al. 2012). Scattering with SLE (Oyallon et al. 2019). Scattering alone, Scattering with ISTC for W which outputs at, , or which outputs Dat, or which outputs a² with unconstrained W.
Fisher Vectors
AlexNet
Scat.
Scat.
Scat. ISTC
Seat.+ ISTC
Scat. ISTC
+ SLE
alone
a W = D
Da W = D 56.9
a W + D
Top1
55.6
56.5
57.0
42.0
59.2
62.8
Top5
78.4
79.1
79.6
65.3
8T.0
79.3
83.7
we set D the ISTC network, the supervised learning jointly optimizes L, the dictionary D with the Lagrange multiplier X. and the MLP classifier parameters. It is done with stochastic gradient descent during 160 epochs using an initial learning rate of 0.01 with a decay of 0.1 at epochs 60 and 120. With sparse code in input of the MLP, has Top accuracy of 81.0%, which outperforms AlexNet.
If also jointly optimize W minimize the classification loss, then the accuracy improves to 83.7%. However, next section shows that in this case, the ISTC network does not compute a sparse El code and therefore not mathematically understood. In the following we thus impose that W D.
The dimension reduction operator L has a marginal effect in terms of performance. If we eliminate it or if we replace it by an unsupervised PCA dimension reduction, the performance drops by less than 2%, whereas the accuracy drops by almost 16% if we eliminate the sparse coding. The number of learned parameters to compute at then drops from 4 10 to 5 103 The considerable improve- ment brought by the sparse code further amplified if the MI.P classifier replaced by much smaller linear classifier. A linear classifier (26.1%, 44.7%). With a ISTC sparse code with W D in a learned dictionary the accuracy jumps to (51.6%, 73. 7%) and hence improves by nearly 30%.
scattering vector has (Top 1, Top 5) accuracy of
The optimization learns a relatively large factor X. which yields a large approximation error |LSx Da ||/[| se 0.5, and very sparse code a' with about 4% non-zero coefficients. The sparse approximation Da thus eliminates nearly half of the energy LS(x)) which can in- terpreted as non-informative "clutter" removal. The sparse approximation Do of LSS has small

---

Published as a conference paper at ICLR 2020
17
0.5
FISTA
RSTA
ISTA
15
IST
5TC
0.45
13
11
0.40
0.7-
0.35
0.5
25
Figure 4: Value of [(a.)) Dl,,,, B|1 + X |aal| versus the number of iterations for ISTC with W = D, ISTA and FISTA on the left, and for ISTC with W + D, ISTA and FISTA on the right.
dimension 14 x 14 x 256 similar to AlexNet last convolutional layer output. If the MLP classifier applied to 1 as opposed a then the accuracy drops by less than 2% and it remains slightly above AlexNet. Replacing LSx by Da thus improves the accuracy by 14%. The sparse coding projection eliminates "noise", which seems mostly correspond intra-class variabilities while carrying little discriminative information between classes. Since Da is sparse combination of dictionary columns Dm each D., can be interpreted as "discriminative features" in the space of scattering coefficients. They optimized to preserve discriminative directions between classes.
4.2 CONVERGENCE OF HOMOTOPY ALGORITHMS
To guarantee that the network can be analyzed mathematically, we verify numerically that the ho- motopy ISTC algorithm computes an accurate approximation of the optimal e sparse code in (1. with small number of iterations.
When W = D, Theorem 3.1 guarantees an exponential convergence by imposing strong incoher- ence condition 8 ((D) < <//2. In our classification setting, (D( 60 so the theorem hypothesis is clearly not satisfied. However, this incoherence condition is not necessary. It is derived from relatively crude upper bound the proof of Appendix A.T Figure 4 left shows numerically that the ISTC algorithm for W D minimizes the Lagrangian C(a)
Da B||2 + X ||a/] over 2 O, with an exponential convergence which is faster than ISTA and FISTA. This is tested with dictionary learned by minimizing the classification loss ImageNet.
we jointly optimize W and to minimize the classification loss then the ImageNet classification accuracy improves from 81.0% to 83.7%, However, Figure right shows that the generalized ISTC network outputs sparse code which does not minimize the Lagrangian at all. Indeed, the learned matrix W does have minimum joint coherence with the dictionary D, as in ALISTA (Liu al.) 2019). The joint coherence then becomes very large with să s 300, which prevents the convergence. Computing W by minimizing the joint coherence would require too many computations.
To further compare the convergence speed of ISTC for W = D versus ISTA and FISTA, we compute the relative mean square eтror MSE(2, y) || y /||= between the optimal sparse code a and the sparse code output of 12 iterations of each of these three algorithms. The MSE is 0.23 for FISTA and 0.45 for ISTA but only 0.02 for ISTC. In this case, after 12 iterations, ISTC reduces the error by factor 10 compared to ISTA and FISTA.
CONCLUSION
This work shows that learning a single dictionary is sufficient to improve the performance a predefined scattering representation beyond the accuracy of AlexNet ImageNet. The resulting deep convolutional network a scattering transform followed by a positive é' sparse code, which well defined mathematical operators. Dictionary vectors capture discriminative directions in
8

---

Published as a conference paper at ICLR 2020
the scattering space. The dictionary approximations act non-linear projector which removes non-informative intra-class variations.
The dictionary learning is implemented with ISTC network with ReLUs. We prove exponential convergence in a general framework that includes ALISTA. A sparse scattering network reduces the convolutional network learning single dictionary learning problem. It opens the possibil- ity to study the network properties by analyzing the resulting dictionary. also offers a simpler mathematical framework analyze optimization issues.
ACKNOWLEDGMENTS
This work was supported by the ERC InvariantClass 320959, grants from Région Ile-de-France and the PRAIRIE 3IA Institute the French ANR-19-P3IA 19-P31A-0000 program. We thank the Scientific Computing Core at the Flatiron Institute for the of their computing resources. We would like to thank Eugene Belilovsky for helpful discussions and comments.
REFERENCES
M. Andreux, T. Angles, G. Exarchakis, R. Leonarduzzi, G. Rochette, L. Thiry, J. Zarka. S. Mallat, Andén, Belilovsky, Bruna, V. Lostanlen, M. Hirn, Oyallon, Zhang, C. E. Cella, and M. Eickenberg. Kymatio: Scattering transforms in python. CoRR, 2018. URL http:
//axxiv.org/abe. http://ab//11.1111 11214
A. Beck and M. Teboulle. A fast iterative thrnesodint algorithm for linear inverse prob- lems. SIAM J. Imaging Sciences, 2(1):183-2000 2009.
J. Bruna and S. Mallat. Invariant scattering convolution networks. IEEE Trans. Pattern Anal. Mach. Intell., 35(8):1872-188) 2013.
E.J. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52 (2):4995500 509, 2006.
P.L. Combettes and JC. Pesquet. Proximal splitting methods in signal processing. In Fixed-Poine Algorithms for Inverse Problems in Science and Engineering. Springer, New York, 2011.
1. Daubechies, M. Defrise, and C. De Mol. An iterative thresholding algorithm for linear inverse problems with sparsity constraint. Communications on Pure and Applied Mathematics, 57(11): 1413-1457, 2004.
G. Davis, S. Mallat, and M. Avellaneda. Adaptive greedy approximations. Constr. Approx., 13(1): 57-98, 1997.
D.L. Donoho and M. Elad. On the stability of the basis pursuit in the presence of noise. Signal Processing, 86(3):511-533 2006.
-norm D.L. Donoho and Y. Tsaig. Fast solution -nomm minimization problems when the solution may be sparse. IEEE Trans. Information Theory, (4(11))4789 2008.
K. Gregor and Y. LeCun. Learning fast approximations of sparse coding. In ICML, pp. 399-406. 2010.
Y. Jiao, B. Jin, and X. Lu. Iterative soft/hard thresholding with homotopy continuation for sparse recovery. IEEE Signal Processing Letters, (4(6):7447788 June 2017.
A. Krizhevsky, I. Sutskever, and G. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems 25, pp. 1097-1105. Curran Associates, Inc., 2012.
Y. LeCun, Y. Bengio, and G.E. Hinton. Deep learning. Nature, 521 2015.
J. Liu, X. Chen, Z. Wang, and W. Yin. ALISTA: Analytic weights are as good as learned weights in LISTA. In International Conference Learning Representations, 2019.

---

Published as a conference paper at ICLR 2020
S. Mahdizadehaghhdm,, A. Panahi, H. Krim, and L. Dai. Deep dictionary learning: A parametric network approach. IEEE Transactions on Image Processing, 28(10))4790-4822 Oct 2019.
J. Mairal, J. Ponce, G. Sapiro, A. Zisserman, and F. Bach. Supervised dictionary learning, In Advances in neural information processing systems, pp. 1033-1040, 2009.
Mairal, F. Bach, and J. Ponce. Task-driven dictionary learning. IEEE transactions on pattern analysis and machine intelligence, 34(4):791-804, 2011.
S. Mallat. Group invariant scattering. Comm. Pure Appl. Math., 65(10);1331-1339) 2012.
S. Mallat. Understanding deep convolutional networks. Phil. Trans. of Royal Sociery A, 374(2065), 2016.
S. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries. Trans. Sig. Proc., 41 (12):3397-33) 3415, Dec 1993.
M.R. Osborne, B. Presnell, and B.A. Turlach. new approach to variable selection in least squares problems. IMA journal of numerical analysis, 20(3):389, 2000.
E. Oyallon and S. Mallat. Deep roto-translation scattering for object classification. 2015 IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pp. 2865-2873. 2014.
E. Oyallon, E. Belilovsky, and S. Zagoruyko. Scaling the scattering transform: Deep hybrid net- works. In Proceedings of the IEEE international conference on computer vision, pp. 5618-5627, 2017.
E. Oyallon, S. Zagoruyko, G. Huang, N. Komodakis, S. Lacoste-Julien, M. Blaschko, and E. Belilovsky. Scattering networks for hybrid representation learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(9))2208-223) Sep. 2019.
V. Papyan, Y. Romano, and M. Elad. Convolutional neural networks analyzed via convolutional sparse coding. Journal of Machine Learning Research, 18:83:1-83:52 2017.
F. Perronnin and D. Larlus. Fisher vectors meet neural networks: A hybrid classification architec- ture. 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3743- 3752, 2015.
2015.
O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma. Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal Computer Vision (ICV), 115(3))211-255) 252, 2015.
J. Sulam, V. Papyan, Y. Romano, and M. Elad. Multilayer convolutional sparse modeling: Pursuit and dictionary learning. IEEE Transactions on Signal Processing, 66(15):49004404, 2018
X. Sun, N. M. Nasrabadi, and T. D. Tran. Supervised deep sparse coding networks. In 2018 25th IEFE International Conference on Image Processing (ICIP), pp. 346-350, 2018.
Sánchez and Perronnin. High-dimensional signature compression for large-scale image classi- fication. In CVPR, pp. 1672. IEEE Computer Society, 2011.
L. Xiao and T. Zhang. A pww.imal-gradiieeeee homotopy method for the sparse least-square problem. SIAM Journl on Optimization, 1022):01121991 May 2013.
10

---

Published as a conference paper at ICLR 2020
A APPENDIX
A.1 PROOF OF THEOREM 3.1
Let a be the optimal e sparse code. We denote by S(a) the support of any a. We also write (x(a) = p(a X). We are going to prove by induction on n that for any n 2 0 we have S(an) C S(a²) and lla, al I 2A, X, 2 X.
For 0,
so S(ao) = @ is indeed included in the support of a and llay-allle- = 1la" To verify the induction hypothesis for Xo Amax 2 Ae, we shall prove that ||a"|lo I 2Amax.
Let us write the error w = 3 Da For all m
a (m)) m Dm = W Wr 3
W
Σ
(mm') W Dm'
mtmm
Since the support of a is smaller than s, W Dm 1 and jí maxm [ Dm
lan(m)] S W 81 + I wl + |1a
so taking the max on gives:
11 1011-1ah jis) - | + [W'
But given the inequalities
W 31100
Amax
W I w|llo
Amax 27j(s)
(1 - 7/s))
since y 2 and (1 - jus) >
(1 - j(s)
we get
||a"1lo0 2Amax 2Au
Let us now suppose that the property is valid for n and let us prove it for n + We denote by DA the restriction of D to vectors indexed by A. We begin by showing that S(a,+1) S(a"). For any m E S(an+1), since 3 = Da + w and W Dm = we have
(m-
( Wt (3 Dan))
PAuti (a W (Ds(a))SS(..)-(m) (a on)) w))
For any m not in S(a"), let prove that an+ (m) 0. The induction hypothesis assumes that S(an) C S(a²) and I|a" an ox S 2An with A, 2 do so:
(m)) + W (Dss(a))ssS())
an (n))sa)) + w)]
s |W (D)(a")) - an)sta))) + IW w| since S(a,) C S(a") and a am(m) = 0 by assumption.
ūssla am + w|W'ol
Since assume that Aa+1 2 >o we have
W W woloo S (11-277h )
and thus
I fuslaa amloo + Wlo S Jus2An + An+ (1-2fjs)) S An+1
since An = 7dn+1.
Because of the thresholding PA_-1 it proves that an+1 (m) 0 and hence that S(a,+1) C. S(a²). Let us now evaluate ||a" - can-illoe For any (a1, 022 A), a soft thresholding satisfies
lex(an 02) on < X + [a2|

---

Published as a conference paper at ICLR 2020
|an=1(m) - (m)
x An+1 + |W (wW.(sssa (D((a))us(ca)) (a - (m)sso))us(( + IW w|
An+1 + īaslla anl + ||' w||x
An+1 + pss2An + An-1 2ypss) = 2
Taking a max over m proves the induction hypothesis.
12


Reviews:
[{"review_id": "SkgtJzcntH", "reviewer": "AnonReviewer1", "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": "The work considers a new architecture for artificial neural networks to be used in image classification tasks. The network combines several promising previous research directions into an interesting approach (to the best of my knowledge, the architecture is novel). \n\nIn the first step, the input representation (i.e., image) is processed using deep scattering spectrum. This is an operator proposed by Mallat (2012) and it is known for extracting robust features with properties such as translation invariance and Lipschitz continuity of the operator mapping. As a result, such a representation is likely to be more stable to perturbations and noise in the inputs.\nThe scattering operator of the second and higher orders tends to produce a large number of coefficients. Such a representation is, in general, sparse with many of the higher order coefficients equal to zero. To lower the dimension of the scattering representation, the architecture employs a linear projection operator. For example, one can take principal component analysis and project to a sub-space retaining most of the variation present in the data.\nThe first two blocks (scattering and linear projection) are unsupervised and, thus, kept fixed during learning. \n\nThe third block in the architecture aims at finding a sparse coding dictionary that will take into account instances and labels. It builds a dictionary using a convolutional neural network and finds sparse coding using previous work on dictionary learning (e.g., Donoho & Elad, 2006: Marial et al., 2011; Jiao et al., 2017 etc). The algorithm works by computing the sparse encoding vector (see Eq. 1) in the forward pass and updating the convolutional parameters as well as sparsity controlling hyperparameter in the backward step. To speed up the convergence, the authors rely on homotopy iterated thresholding illustrated in Figure 2.\n\nThe approach is evaluated on ImageNet and empirical results demonstrate that the removal of the sparse encoding block amounts to a significant performance degradation. The results also establish a minor improvement in the accuracy as a result of adding a linear projection matrix (i.e., principal component analysis applied to scattering coefficients). Overall, the network shows promising performance on ImageNet by doing better than AlexNet. The result is not yet 'competitive' with ResNets but it might be worth to pursue this direction of research in the future.\n\nThe work is properly structured with well organized materials from previous work. The clarity, however, could be improved in several places. In particular, the last paragraph in Section 3.1 does not explain the algorithm clearly. The confusing part is how to update the dictionary (i.e., convolutional network) parameters. One might infer from the current materials that first the problem in Eq. (1) is solved to find \\alpha and that solution is fixed. Then, for that setting of the sparse encoding vector one will train the network parameters. Section 3.2 then givens an iterative procedure in Eq. (3) and Figure 2, which suggest that in a forward pass the dictionary representation is computed using some setting of parameters and \\alpha is updated per Eq. (3). Following this, the gradient of the convolutional parameters is computed (\\alpha_{n + 1} is differentiated, which means that the gradient depends on other \\alpha iterates). I believe that this is the crux of the methodological/conceptual contribution and requires proper explanation with proper illustration of the forward-backward pass.\n\nIn Section 3.2 (homotopy iterated thresholding and ALISTA), there is a matrix W which comes ad-hoc. There should be some motivation and gentle introduction. At the moment, it is completely justified to ask why one needs this matrix and why the approach would not work without Proposition 3.1. Please add some discussion and make sure things are properly motivated and gently introduced. This will also place the theoretical contribution in the proper context and strengthen the work.\n\nJust below Figure 2, I fail to follow how the number of layers N relates to the iterative algorithm? Does it mean that you would actually have blocks per each \\alpha_n for some N indices (this again refers to previous comment on clarity)?\n\nCan you please use \\ell_1 or l_1 notation for sparse dictionary coding. The current symbol reads as 1 to the power of 1 and it is very confusing (never seen it before in the context of sparse encodings).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SkeHSjoe9H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper proposes a network architecture composed of three interpretable components followed by a simple MLP classifier. It first applies a scattering transform followed by a learned linear projection (to reduce dimensionality). A sparse representation of these coefficients is then obtained using dictionary learning. The projection, dictionary and MLP classifier are jointly trained to minimize the classification loss. Results show that the model outperforms AlexNet on the Imagenet benchmark.\n\nThe paper is well written. The main contribution of the work is to present an architecture with composed of mathematically interpretable components achieving very high empirical performance. I find that these results are very significant. \n\nThe second contribution is to propose a dictionary learning algorithm that uses ISTC and can be trained with gradient descent.  I think that it would be interesting to add an ablation showing the change in performance by changing N (the number of iterations in the ISTC net). Also, it would make sense to run FISTA or ISTA unrolls to see if the benefits of the faster convergence also affect classification performance.\n\nIt would be good to add to Table 1 the number of trainable parameters of each variant.\n\nI find it a bit confusing to refer to the setting in which W is learned as ALISTA, as to me ALISTA implies using analytical W. This is clear later in the text (and makes sense from a computational standpoint). Would be good to clarify it early in the text.\n\nFinally the paper presents a proof of exponential convergence for ALISTA in the noisy case. While this is an interesting result, it is not very closely linked to the main focus of the work. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJl5HgCpFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "\n## Summary\n\nThe paper proposes an interpretable architecture for image classification based on a scattering transform and sparse dictionary learning approach. The scattering transform acts as a pre-trained interpretable feature extractor that does not require data. A sparse dictionary on top of this representation (the scattering coefficients) is learnt to minimize the classification error. The authors cast the dictionary learning as a classical CNN learning approach and implement an efficient solution via homotopy learning (given that some assumptions are fulfilled). The scattering transform approach is not new (as the authors mention in the paper, it was published in Oyallon et al., 2019). The main novelty comes from applying a previously published dictionary learning approach (as the authors mention in the paper, it was published in Jiao et al., 2017) on top to boost the performance. As a second contribution, the authors extend the exponential convergence proof of ISTC (Jiao et al., 2017) and ALISTA (Liu et al., 2019). In the experiments, they show that the proposed architecture, despite its simplicity, outperform AlexNet in the ImageNet classification problem.\n \n## Comments\n\nThe paper is well written and the exposition is clear. The main motivation of the paper is to propose an interpretable architecture with similar performance to black box deep learning architectures. To do so, the authors put together:\n\n- A scattering transform feature extractor: Unlike I am missing something, this is exactly what was previously proposed in (Oyallon et al., 2019). \n- A dictionary learning on top: This seems to be the biggest novelty of the paper. This component allows to boost the performance of the previously proposed architecture. However, this approach has been previously explored in the literature (Mahdizadehaghdam et al. 2018), the authors just apply it on top the extracted features. The justification of the paper lies in that previous dictionary learning approaches did not scale (convergence too slow), and so the authors use a different method recently published in (Jiao et al., 2017). \n\nThis allow the authors to apply the method to bigger datasets ImageNet, and keep the performance above AlexNet. \n\nGeneralizing the convergence results of ALISTA and ISTC is a nice contribution. However, my main concern is with respect the novelty of the rest of the paper. The authors do not propose a substantially different approach, rather they apply the same approach (an scalable  dictionary learning method already published in Jiao et al., 2017) on top of some extracted features (scattering coefficients)  to a different datasets. The problem with accepting the paper is that changing the dataset/dictionary learning method/features to compare with, you get a different paper, and so, in my opinion, the impact of this publication is limited.\n \nAlso, given that the paper main point is the interpretability of the proposed method wrt to black-box deep learning methods, I think the authors should include recent references to the active field of interpretability in the deep neural network community.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "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_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: After the rebuttal period the ratings on this paper increased and it now has a strong assessment across reviewers. The AC recommends acceptance.
Decision: Accept (Poster)