Understanding approximate and unrolled dictionary learning for pattern recovery
Authors: Benoît Malézieux
Thomas Moreau
Matthieu Kowalski
Venue: ICLR 2022 Poster (2022)
Keywords: Dictionary learning
bi-level optimization
unrolling
pattern learning

Abstract: Dictionary learning consists of finding a sparse representation from noisy data and is a common way to encode data-driven prior knowledge on signals. Alternating minimization (AM) is standard for the underlying optimization, where gradient descent steps alternate with sparse coding procedures. The major drawback of this method is its prohibitive computational cost, making it unpractical on large real-world data sets. This work studies an approximate formulation of dictionary learning based on unrolling and compares it to alternating minimization to find the best trade-off between speed and precision. We analyze the asymptotic behavior and convergence rate of gradients estimates in both methods. We show that unrolling performs better on the support of the inner problem solution and during the first iterations. Finally, we apply unrolling on pattern learning in magnetoencephalography (MEG) with the help of a stochastic algorithm and compare the performance to a state-of-the-art method.

Published as a conference paper at ICLR 2022
UNDERSTANDING APPROXIMATE AND UNROLLED DICTIONARY LEARNING FOR PATTERN RECOVERY
Benoît Malézieux
Thomas Moreau
Université Paris- Srris-Sacly,, Inria, CEA
Université Paris-Saclay, Inria, CEA Palaiseau, 91 91120, France thomas www.au inria.ii......... fr
L2S, Université Paris- Maris-Scllay-ai Caraaay-------- SNNSS-CettallSupplee benoit.mne ma Lezieuxe Anria. aa.fa. fr
Matthicu Kowalski L2S, Université Saclaa-CCRssaSaSS ceaeeeeent Gif-seu-Yvette, 91190, France matthieu. www.w:kwwwwwiiiiiaa.o.. htt.:puuwoo.aaltoooooeeeeeeerrrr
ABSTRACT
Dictionary learning consists of finding sparse representation from noisy data and is a common way to encode data-driven prior knowledge on signals. Alternating minimization (AM) is standard for the underlying optimization, where gradient descent steps alternate with sparse coding procedures. The major drawback this method its prohibitive computational cost, making it unpractical large real-world data sets. This work studies an approximate formulation of dictionary learning based on unrolling and compares the best trade-off between speed and precision. We analyze the asymptotic behav- ior and convergence rate of gradients estimates in both methods. We show that unrolling performs better on the support of the inner problem solution and during the first iterations. Finally, we apply unrolling on pattern learning magnetoen- cephalography (MEG) with the help of stochastic algorithm and compare the performance to a state-of-the-an method.
alternating minimization find
INTRODUCTION
Pattern learning provides insightful information on the data in various biomedical applications. Typ- ical examples include the study of magnetoencephalograaly (MEG) recordings, where one aims to analyze the electrical activity in the brain from measurements the magnetic field around the scalp of the patient (Dupré la Tour al., 2018). One may also mention neural oscillations study in the local field potential (Cole & Voytek, 2017) or QRS complex detection in electrocardiograms (Xiang al., 2018) among others.
Dictionary learning (Olshausen & Field, 1997; Aharon et al., 2006; Mairal et al., 2009) is particu- larly efficient on pattern learning tasks, such as blood cells detection (Yellin al., 2017) and MEG signals analysis (Dupré la Tour et al., 2018). This framework assumes that the signal can be de- redundant basis of patterns also called atoms. other
composed into a sparse representation words, the goal is to recover a sparse code Z E RR*T and a dictionary D E Rm*x from noisy mea- surements Y E RmxT which are obtained as the linear transformation D DZ, corrupted with noise B E RmXT; Y = DZ B. Theoretical elements been proven in several studies (Gribonval al., 2015; Haeffele & Vidal, 2015; Agarwal al., 2016; 6;; Sun et al., 2016). Sparsity- on the usage of the lo or E regularizations. In this paper, we study Lasso-based (Tibshirani, 1996) dictionary learning where the dictionary D is learned in of constraints C by solving
identifiability and local convergence have
optimization problems related dictionary learning generally rely
min
F(Z,D) A 2
DZ x + + A
(1)
ZEREX? DEC

---

Published as a conference paper at ICLR 2022
Dictionary learning can be written as bi-level optimization problem to minimize the cost function with respect to the dictionary only, as mentioned in Mairal et al. (2009),
min G(D) & F(Z D) with z" (D) arg min F(Z, DEC
(2)
ZEReXT
Computing the data representation Z (D) is often referred to the inner problem, while the global minimization is the outer problem. Classical constraint sets include the unit norm, where each atom is normalized to avoid scale-invariant issues, and normalized convolutional kernels to perform Convolutional Dictionary Learning (Grosse et al., 2007).
Classical dictionary learning methods solve this bi-convex optimization problem through Alternat- ing Minimization (AM) (Mairal et al., 2009). It consists in minimizing the cost function F over Z with fixed dictionary D and then performing projected gradient descent to optimize the dictionary with fixed Z. While AM provides simple strategy to perform dictionary learning, it can be ineffi- cient on large-scale data sets due to the need to resolve the inner problems precisely for all samples. In recent years, many studies have focused on algorithm unrolling (Tolooshams et al., 2020; Scetbon et al., 2021) 1) to overcome this issue. The core idea consists of unrolling the algorithm, which solves the inner problem, and then computing the gradient with respect to the dictionary with the help of back- poo-prropagttion through the iterates of this algorithm. Gregor & LeCun (2010) popularized this method and first proposed to unroll ISTA (Daubechies et al., 2004) a proximal gradient descent algorithm designed for the Lasso - to speed up the computation of (D) The N + 1-th layer of this network- called LISTA- is obtained as ZN+1
ST² (WLY W2Zx), with ST be- ing the wot-ttheesholdin operator. This work has led to many contributions aiming at improving this method and providing theoretical justifications in supervised (Chen et al., 2018; Liu & Chen, 2019) or unsupervised (Moreau & Bruna, 2017; Ablin et al., 2019) setting. For such unrolled algorithms, the weights W and 8 can be re-parameterized as functions of D - as illustrated in Figure A in appendix - such that the output N () matches the result of N iterations of ISTA, i.e.
W - DT and w 10=11-11 (1-1D')) where L == D||2
(3)
Then, the dictionary can be learned by minimizing the loss F(ZN(D). D) over D with back- propagation. This approach is generally referred to Deep Dictionary Learning (DDL... DDL and variants with different kinds of regularization (Tolooshams et al., 2020; 1 Lecouat et al., 2020; Scethon al., 2021), image processing based metric learning (Tang et al., 2020), and classification tasks with scattering (Zarka et al., 2019) have been proposed in the literature, among others. While these techniques have achieved good performance levels on several signal processing tasks, the reasons they speed up the learning process are still unclear.
In this work, we study unrolling based dictionary learning as an approximate bi-level opti- mization problem. What makes this work different from Bertrand et al. (2020), Ablin et al. (2020) and Tolooshams & Ba (2021) that we study the instability of non-smooth bi-level optimization and unrolled sparse coding out of the support, which is of major interest in practice with small number of layers. In Section 2, we analyze the convergence of the Jacobian computed with auto- matic differentiation and find out that its stability is guaranteed only. De facto, numerical instabilities in its estimation make unrolling inefficient after few dozen iterations. In Section 3, we empirically show that unrolling leads to better results than AM only with a small number of iterations of sparse coding, making it possible to learn a good dictionary in this setting. Then we adapt stochastic approach make this method usable on large data sets, and we apply it to pattern learning in magnetoenceehallggrahhh (MEG) in Section 4. We do so by adapting unrolling rank one convolutional dictionary learning on multivariate time series (Dupré la Tour et al., 2018). We show that there is no need to unroll more than a few dozen iterations to obtain satisfying results, leading to a significant gain of time compared to a of-te-of-the-rr algorithm.
the support of the sparse codes
BI-LEVEL OPTIMIZATION FOR APPROXIMATE DICTIONARY LEARNING
As (DD does not have closed-form expression, G cannot be computed directly. A solution is to replace the inner problem ZD( by an approximation Z (D) obtained through N iterations of a numerical optimization algorithm or its unrolled version. This reduces the problem minimizing
Gx() A F(Zx(D), D). The first question is how sub-optimal global solutions of GN
2

---

Published as a conference paper at ICLR 2022
compared to the ones of G. Proposition 2.1 shows that the global minima of GN converge as fast as the numerical approximation Zy in function value.
Proposition 2.1 Let D arg min G(D) and Dj- arg DEC Gx(D), ()), where N is the number of unrolled iterations. We denote by K K(D") a constant depending on D", and by C(N) the convergence speed of the algorithm, which approximates the inner problem solution. We have
Gx(Dw) G(D") & K(D*)C(N).
The proofs of all theoretical results are deferred to Appendix C. Proposition 2.1 implies that when Zn is computed with FISTA (Beck & Teboulle, 2009), the function value for global minima of GN converges with speed C(N) N2 towards the value of the global minima of F. Therefore, solving the inner problem approximately leads to suitable solutions for equation 2, given that the optimization procedure is efficient enough find a proper minimum of Gy. As the computational cost of z increases with N, the choice of NN results in a trade-off between the precision of the solution and the computational efficiency, which is critical for processing large data sets.
Moreover, learning the dictionary and computing the sparse codes are two different tasks. The loss Gy takes into account the dictionary and the corresponding approximation Zv (D) to evaluate the quality of the solution. However, the dictionary evaluation should reflect its ability to generate the same signals as the ground truth data and not consider an approximate sparse code that can be recomputed afterward. Therefore, we should distinguish the ability of the algorithm to recover good dictionary from its ability to learn the dictionary and the sparse codes at the same time. In the metric proposed in Moreau & Gramfort (2020) for convolutions to evaluate
this work, the quality of the dictionary. We compare the atoms using their correlation and denote as the cost matrix whose entry ý. compare the atom i of the first dictionary and j of the second. We define sign and permutation invariant metric S(C) = max 1 E [Ca(t),ll, where 6,, is the group of permutations of n]. This metric corresponds to the best linear sum assignment on the cost matrix C, and it can be computed with the Hungarian algorithm. Note that doing has several limitations and that evaluating the dictionary is still an open problem. Without loss of generality, let
T = 1 and thus E R" in the rest of this section.
Gradient estimation in dictionary learning. Approximate dictionary learning is a non-convex problem, meaning that good or poor local minima of Gr may be reached depending on the initial- ization, the optimization path, and the structure of the problem. Therefore, gradient descent on G has no guarantee to find an adequate minimizer of G. While complete theoretical analysis of these problems is arduous, we propose to study the correlation between the gradient obtained with GN and the actual gradient of G, as way to ensure that the optimization dynamics are similar. Once (D) is known, Danskin (1967, Thm 1) states that g" (D) VG(D) is equal to V2/(22 (D)), D), where Va indicates that the gradient computed relatively to the second variable in F. Even though the inner problem is non smoohh, this result holds as long the solution 2" 2*(D) is unique. In the following, we will assume that D is invertible on the support of x (D), which implics the uniqueness of x= (DD) This occurs with probability one if D is sampled from continuous distribu- tion (Tibshirani, 2013). AM and DDL differ in how they estimate the gradient of G. AM relies on the analytical formula of g" and uses an approximation nn of z", leading to the approximate gra- dient g D) = (zF(2x(D), D). We evaluate how well giy approximates g" in Proposition 2.2.
Proposition 2.2 Let D E RRxx, Then, there exists constant L, > 0 such that for every number of iterations N
ggyy 90 < Li -D)
-0-
Proposition 2.2 shows that gly converges fast the iterates of ISTA converge. DDL computes the gradient automatically through nN (D). As opposed to AM, this directly minimizes the loss Gx Automatic differentiation yields sub-gradient g (D) such that
gh ()) E V2F((N( D) J (0 (0.F(EN(D) D))
(4)
where JN Rmxn -> RD is the weak Jacobian of 2N (D) with respect to D and J denotes its adjoint. The product between J and 0 F(ZN( ((ZN(D), ()), D) is computed via automatic differentiation.
3

---

Published as a conference paper at ICLR 2022
Proposition 2.3 Let D E Rmxx. Let 5t be the support of x² (D). SN be the support of NN and
SN = Sx US. Let D) = 1 Dz ull2 be the data-fitting term in F. Let R(J.S) J (V D) & 1g) + (2,1((z, ( D) @ 1.. Then there exists a constant L2 > 0 and a sub- sequence of (F)ISTA ieeraee ZØ(N) such that for all N N:
3 1 (2 D) + J (an)) (VI((ZO(N), D) 10111, (RS(N)) s.t.:
1aIN) 0rl1 = (R(JoN,), SacNN) [ - x=1 =11++ L2
[ x²1
2
This sub-sequence N corresponds iterates on the support of
Proposition 2.3 shows that 9 may converge faster than g once the support is reached.
Ablin et al. (2020) and Tolooshams & Ba (2021) have studied the behavior of strongly convex functions, as it is the case on the support, and found similar results. This allowed Tolooshams & Ba (2021) to focus on support identification and show that automatic differentiation leads to better gradient estimation in dictionary learning on the support under minor assumptions.
However, we are also interested in characterizing the behavior outside of the support, where the gradient estimation is difficult because of the sub-differential. In practice, automatic differenti- ation uses the sign operator as a sub-gradient of II-II1- The convergence behavior of g is also driven by R[Jv,Sy and thus by the weak Jacobian computed via puck-propagation. We first com- pute a closed-form expression of the weak Jacobian of z (D) and NN (D). We then show that R(JN: Sx) < L ||
J| and we analyze the convergence of JN towards J"
Study of the Jacobian. The computation of the Jacobian can be done by differentiating through ISTA. In Theorem 2.4, we show that JN+1 depends on J.y and the past iterate 2N. and converges towards a fixed point. This formula can be used to compute the Jacobian during the forward pass, avoiding the computational cost of back-propagates
and saving memory.
Theorem 2.4 At iteration N + of ISTA, the weak Jacobian of zN+1 relatively to Di, where Dj is the 1-th row of D. is given by induction:
0(z++1)
((zx)
1
(DIE
(DIEN + (DT AN I. + DJD D
M(N))
0D: 1| 20 ①
@Di
I
aD,
0(xx) aD; will be denoted by JN. converges towards the weak Jacobian J of x" relatively Dp, whose values are
g' -:D.= (DT 2-' - In)) on the support S* z", and O elsewhere. Moreover, ((J",S") =0. O.
This result is similar to Bertrand et al. (2020) where the Jacobian of 2 is computed over À to perform prper-parameter optimization in Lasso-type models. Using R(J", (5*) 0, we can write
R(JN, 3x) < [(JN, 3w) - R(J", | < L ||N J"|l
(5)
as Vi,nf D) If the back-propagation were to output an accurate estimate JN of the weak Jacobian J" (((NN.x) would be O, and the convergence rate of g²x could be twice as fast as the one of giv To quantify this, we now analyze the convergence of JN towards J In Proposition 2.5, we compute an upper bound of J - -J || with possible usage of truncated back- propagation (Shaban et al., 2019). Truncated back-propagation of depth K corresponds to an initial estimate of the Jacobian JN-x = 0 and iterating the induction in Theorem 2.4.
Proposition 2.5 Let N be the number of iterations and K be the buck-propagation depth. We as- sume that Vn 2 N NKK, S* C Sn. Let EN = Sn, SS* let L be the largest eigenvalue of D D
and let pa be the smallest eigenvalue of s, D.,s.... Let B, = PEn - DD. D.J. D..... Ps- where
Ps is the projection on R and Dt is the pseudo-inved of D. We have
K
K-1 &
|| - J.
1 (1 1N-K)
11511+++
2
D
ΣII
PN-i )) (1 =ill+ 111+BN-Kll [||++N==ll=+l])
L
L
k=1
k= E1
4

---

Published as a conference paper at ICLR 2022
Max BP depth
||
J,
||
S" llo
full
200
50
20
10"
20 0
20
10
20
10
10.a
10
0
10"
10
10
10"
102
10*
10
102 10*
10" 10a
10
Iterations N
Iterations N
Iterations N
Iterations N
Average convergence of Jj towards J for samples from the data set, gener- ated with random Gaussian matrix. J JN converges linearly the support in both cases. However, for sample 2, full back-propagation makes the convergence unstable, and truncated back- propagation improves its behavior, described Proposition 2.5. The proportion of stable and unstable samples in this particular example is displayed in Figure 2.
Figure 1:
Proposition 2.5 reveals multiple stages in the Jacobian estimation. First, one can see that if all iterates used for the back prkpaappaaation lie on the support S*, the Jacobian estimate has quasi-linear convergence, as shown in the following corollary.
0 be the smallest eigenvalue of D D..s.. Let K S N be the back- propagation depth and let AN = F(zN, D) F(z", D) + Il - 111 Suppose that Vn [N WW-K, N,; Sn S². Then, have
Corollary 2.6 Let
- ( (1- |
4AN-K 2
|
Once the support is reached, ISTA also converges with the same linear rate (1 f). Thus the gradient estimate 9 converges almost twice as fast as gly in the best case with optimal sub- gradient - as O(K(1 () )2*). This is similar to Ablin et al. (2020, Proposition.5) and Tolooshams & Ba (2021), Second, Proposition 2.5 shows that || - may increase when the support is not well-estimated, leading to a deterioration of the gradient estimate. This is due to an accumulation of errrr materialized by the not vanish to 0 as long as SN & St. Interestingly, once the support is reached at iteration S N, the errors converge linearly towards O, and we recover the fast estimation of g with g². Therefore, Lasso-based DDL should either be used with low number of steps or truncated prcpppoppaatiion ensure stability. These results apply for all linear dictionaries, including convolutions.
in the right-hand side of the inequality, the term B || may
Numerical illustrations. We now illustrate these theoretical re- sults depending on the number N of unrolled iterations. The data are generated from a random Gaussian dictionary D of size 30 x 50, with Gaussian sparse codes z (sparsity 0.3, o² = 1), and Gaussian noise (o2 hoise = 0.1) more details in Appendix A.
30
10
Figure 1 confirms the linear convergence of J once the support reached. However, the convergence might be unstable when the number of iteration grows, leading to exploding gradient, as illus- trated in the second case. When this happens, using a small number of iterations or truncated back- pock-propagttion becomes necessary to prevent accumulating errors. is also of interest to look the pro- portion of unstable Jacobians (see Figure 2). We recover behaviors observed in the first and second case in Figure 1, 40% samples suf- fer from numerical instabilities in this example. This has negative impact on the gradient estimation outside of the support.
0
10a
103
Iterations N
Average conver- gence of JN towards Jj for 50 samples. In this example, 40% of the Jacobians are stable (red curves).
Figure
We display the convergence behavior of the gradients estimated by AM and by DDL with different Back-propagation depths (20, 50, full) for simulated data and images in Figure 3. We unroll FISTA instead of ISTA to make the convergence faster. We observed similar

---

Published as a conference paper at ICLR 2022
BP depth
AM
20
50
full
Gaussian dictionary
Noisy image
Noisy image
10
10a
Relative diff.
0.2
10
0.0
10-3
-0.2
10
10
10a
10
10a
10
10a
Iterations
Iterations N
Iterations
Figure Gradient convergence in angle for 1000 synthetic samples (left) and patches from noisy image (center). The image is normalized, decomposed into patches of dimension 10 x 10 and with additive Gaussian noise (o² = 0.1). The dictionary for which the gradients are computed is composed of 128 patches from the image. (right) Relative difference between angles from DDL and AM. Convergence is faster with DDL early iterations, and becomes unstable with too many steps.
behaviors for both algorithms in early iterations but using ISTA required too much memory reach full convergence. As we optimize using a line search algorithm, we are mainly interested in the abil- ity of the estimate to provide an adequate descent direction. Therefore, we display the convergence in angle defined the cosine similarity (g.g") Trig"g" g²) Tlgi g The angle provides good metric to assert that the gradients correlated and thus will lead to similar optimization paths. We also provide the convergence in norm in appendix. We compare gly and g with the relative difference of their angles with g", defined as (9 1- -o'' When value is positive, DDL provides the
best descent direction. Generally, when the back-propagation goes too deep, the performance of g decreases compared to glv and we observe large numerical instabilities. This behavior is coherent with the Jacobian convergence patterns studied in Proposition 2.5. Once on the support, g reaches back the performance of g/v anticipated. In the case of real image, unrolling beats AM by up to 20% in terms of gradient direction estimation when the number of iterations does not exceed 50, especially with small back- pack-propagation depth. This highlights that the principal interest of unrolled algorithms is to use them with a small number of layers i.e., a small number of iterations.
APPROXIMATE DICTIONARY LEARNING IN PRACTICE
This section introduces practical guidelines on Lasso-based approximate dictionary learning with unit norm constraint, and provide empirical justifications for its ability recover the dictionary. We also propose strategy to scale DDL with a stochastic optimization method. We provide a full description of all our experiments in Appendix A. We optimize with projected gradient descent com- bined to line search to compute high-quality steps sizes. The computations have been performed on GPU NVIDIA Tesla V100-DGXS 32GB using PyTorch (Paszke et al., 2019).'
Improvement precision. As stated before, low number of iterations allows for efficient and stable computations, but this makes the sparse code less precise. One can learn the steps sizes of (FIISTA to speed up convergence and compensate for imprecise representations, as proposed by Ablin et al. (2019) for LISTA. To avoid poor results due large degrees of freedom in unsuper- vised learning, we propose a method in two steps to refine the initialization the dictionary before relaxing the constraints the steps sizes:
1. We learn the dictionary with fixed steps sizes equal to f, where L. 2| given by convergence conditions. Lipschitz constants or upper bounds are computed at each gradient step with norms, or the FFT for convolutions, outside the scope of the network graph.
2. Then, once convergence reached, we jointly learn the step sizes and the dictionary. Both are still updated using gradient descent with line search to ensure stable optimization.
Cooee available https://g/ii com /ba www.euu//ooolooe......

---

Published as a conference paper at ICLR 2022
AM
DDL
DDL steps
Gradient steps
Loss
Rec. score
Number
10a
200
10
100
10
10-3
10
102 10
10a 10a
10
102
10a
Iterations N
Iterations N
Iterations N
Figure 4: (left) Number of gradient steps performed by the line search before convergence, (center) distance to the optimal loss, and (right) distance to the optimal dictionary recovery score depending on the number of unrolled iterations. The data are generated as in Figure We display the mean and the 10% and 90% quantiles over 50 random experiments. DDL needs less gradient steps to converge in early iterations, and unrolling obtains high recovery scores with only few dozens of iterations.
Denoising
Min. distribution
CDL minima
25
Rec. score
25
0.9
PSNR
AM
PSNR
Loss
20
steps
21
0.7
DL Oracle
100
101
102
10
18
-2
0
2
Iterations N
SNR (dB)
Normalized distance
Figure 5: We consider a normalized image degraded by Gaussian noise. (left) PSNR depending on the number of unrolled iterations for hhaiis = 0.1, i.c. PSNR 10 dB. DL-Oracle stands for full AM dictionary learning (103 iterations FISTA). There no need unroll too many iterations to obtain satisfying results. (center) PSNR and average recovery score between dictionaries depending on the SNR for 50 random initializations in CDL (right) 10 loss landscapes in 1D for hoose 0.1. DDL is robust to random initialization when there is not too much noise.
The use of LISTA-like algorithms with no ground truth generally aims at improving the speed of sparse coding when high precision is not required. When it is the case, the final sparse codes can be computed separately with FISTA (Beck & Teboulle, 2009) or coordinate descent (Wu et al., 2008) to improve the quality of the representation.
3.1 OPTIMIZATION DYNAMICS IN APPROXIMATE DICTIONARY LEARNING
In this part, we study empirical properties of approximate dictionary learning related to global opti- mization dynamics to put our results on gradient estimation in a broader context.
Unrolling v. AM. In Figure 4, we show the number of gradient steps before reaching convergence, the behavior of the loss Fy. and the recovery score defined the beginning of the section for syn- thetic data generated by a Gaussian dictionary. As a reminder, S(C) max 1 -E= (Ca where C is the correlation matrix between the columns of the true dictionary and the estimate. The number of iterations corresponds to N in the estimate ( (D). First, DDL leads to fewer gradient steps than AM in the first iterations. This suggests that automatic differentiation better estimates the directions of the gradients for small depths. However, computing the gradient requires back- propagating through the algorithm, and DDL takes 1.5 times longer to perform one gradient step than AM on average for the same number of iterations N. When looking at the loss and the recovery score, we notice that the advantage of DDL for the minimization of FN minor without learning the steps sizes, but there is increase of performance concerning the recovery score. DDL bet- ter estimates the dictionary for small depths, inferior to 50. When unrolling more iterations, AM performs as well as DDL on the approximate problem and is faster.
Approximate DL. Figure& shows that high-quality dictionaries are obtained before the conver- gence of Fx. either with AM DDL. 40 iterations are sufficient reach reasonable solution

---

Published as a conference paper at ICLR 2022
concerning the recovery score, even though the loss is still very far from the optimum. This suggests that computing optimal sparse codes at each gradient step is unnecessary to recover the dictionary. Figure 5 illustrates that by showing the PSNR of noisy image reconstruction depending the number of iterations, compared to full AM dictionary learning with 10 iterations. As for synthetic data, optimal performance is reached very fast. In this particular case, the model converges after 80 seconds with approximate DL unrolled for 20 iterations of FISTA compared to 600 seconds in the case of standard DL. Note that the speed rate highly depends on the value of X. Higher values of À tend to make FISTA converge faster, and unrolling becomes unnecessary in this case. On the contrary, unrolling is more efficient than AM for lower values of X.
Loss landscape. The ability of gradient descent to find adequate local minima strongly depends on the structure of the problem. To quantify this, we evaluate the variation of PSNR depending on the Signal to Noise Ratio (SNR) (10 1og (=² where of is the variance of the noise) for 50 random initializations in the context of convolutional dictionary learning on a task of image denoising, with 20 unrolled iterations. Figure shows that approximate CDL is robust to random initialization when the level of noise is not too high. In this case, all local minima are similar in terms of reconstruction quality. We provide a visualization of the loss landscape with the help of ideas presented in Li et al. (2018). The algorithm computes a minimum, and chose two properly rescaled vectors to create a plan from this minimum. The 3D landscape is displayed on this plan in Figure B using the Python library 2JD-Jupyter'. We also compare in Figure 5 (right) the shapes of local minima in 1D by computing the values of the loss along a line between two local minima. These visualizations confirm that dictionary learning locally behaves like a convex function with similar local minima.
3.2 STOCHASTIC DDL
Minibatch size
In order to apply DDL in realistic settings, it is tempting to adapt Stochastic Gradient Descent (SGD), commonly used for neural networks. The major advantage is that the sparse coding is not per- formed on all data at each forward pass, leading to significant time and memory savings. The issue is that the choice of gradient steps is critical to the op-
100
2000
Full batch
10000
Complete AM
1.0
Rec. score
0.8
0.6
timization process in dictionary learning, and SGD methods based on simple heuristics like rate decay difficult to tune in this context. We propose to leverage a new optimization scheme introduced in Vaswani al. (2019), which consists of performing a stochastic line search. The algorithm computes a good step size at each epoch, after which a heuristic decreases the maximal step. Figure 6 displays the recovery score function of the time for various mini- batch sizes on a problem with 10" samples. The data were generated as in Figure 1 but with larger dictionary (50 100). The algorithm achieves good performance with small mini-batches and thus limited memory usage. We also compare this method with Online dictionary learning (Mairal et al., 2009) in Figure E. It shows that our method speeds up the dictionary recovery, especially for lower values of X. This strategy can be adapted very casily for convolutional models by taking bab-windows of the full signal and performing a stochastic line search, as demonstrated in Section 4. See Tolooshams et al. (2020) for another unrolled stochastic CDL algorithm applied to medical data.
10
20 30
Time (s)
Figure 6: Recovery score vs. time for 10 random Gaussian matrices and 10 samples. Initialization with random dictionaries. In- termediate batch sizes offer good trade-off between speed and memory usage.
APPLICATION TO PATTERN LEARNING IN MEG SIGNALS
In mageeteencephalography (MEG), the measurements over the scalp consist of hundreds of simul- taneous recordings, which provide information on the neural activity during a large period. Convo- lutional dictionary learning makes it possible to learn cognitive patterns corresponding to physiolog- ical activities (Dupré la Tour et al., 2018). As the electromagnetic waves propagate through the brain at the speed of light, every sensor measures the same waveform simultaneously but not at the same
Package available at https: bttppa//githhai com/ K30- //330- jupyter.
8

---

Published as a conference paper at ICLR 2022
Spatial pattern 0
Spatial pattern 1
Figure 7: Stochastic Deep CDL on 6 minutes MEG data (204 channels, sampling rate of 150Hz). The algo- rithm uses 40 atoms, 30 un- Temporal pattern 2 rolled iterations and 100 iter- ations with batch size 20. We recover heartbeat (0), blink- ing (1) artifacts, and an au- ditory evoked response (2) among others.
Spatial pattern 2
Tem poral pattern
Temporal pattern
0.4
0.0
0.0
0.2
-0.2
0.0
-0.5
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Time (s)
Time (s)
Time (s)
Minibatch
Time window
Steps learning
Corr.
Corr. v
Mcan corr.
Time
5
20 s
True
0.85 0.02
0.84 + 0.06
0.845
110
5
20 s
False
0.88 + 0.02
0.78 + 0.06
0.83
57 s
5
10
True
0.83 = 0.01
0.82 + 0.09
0.825
56
20
10
True
0.85 + 0.01
0.75 + 0.09
0.80
163
Table 1: Stochastic Deep CDL MEG data (as in Figure 7). We compare and to 12 important atoms output by a alphacse (correlation averaged on 5 runs), depending on several hyperparame- ters, with 30 layers. 10 epochs and 10 iterations per epochs. Arescaled 0.3Amax. Amax
| y eo
The best setups achieve 80% 90% average correlation with a alphacsc in around 100 sec. com- pared around 1400 sec. Our method is also faster than convolutional K-SVD (Yellin al., 2017).
intensity. The authors propose to rely multivariate convolutional sparse coding (CSC) with rank- constraint to leverage this physical property and learn prototypical patterns. In this case, space and time patterns disjoint in each atom: D₃ ug of where gathers the spatial activations on each channel and v corresponds to the temporal pattern. This leads to the model
min 24 ET my E Mr BRER
( 2/:
+
| 1=1
(6)
1=1
where n is the number of atoms, T is the total recording time, is the kernel size, and is the number of sensors. We propose to learn and with Stochastic Deep CDL unrolled for few iterations to speed up the computations of the atoms. Figure 7 reproduces the multivariate CSC experiments of alphacsc (Dupré la Tour et al., 2018) on the dataset sample of MNE (Gramfort et al., 2013) minutes of recordings with 204 channels sampled at 150Hz with visual and audio stimuli.
The algorithm recovers the main waveforms and spatial patterns with approximate sparse codes and without performing the sparse coding on the whole data set at each gradient iteration, which leads a sigmificant gain of time. We are able to distinguish several meaningful patterns as heartbeat and blinking artifacts or auditive evoked response. As this problem is unsupervised, it is difficult to provide robust quantitative quality measurements. Therefore, we compare our patterns to 12 important patterns recovered by alpahese in terms of correlation in Table 1. Good setups achieve between 80% and 90% average correlation ten times faster.
CONCLUSION
Dictionary learning is an efficient technique learn patterns in a signal but challenging to ap- ply to large real-world problems. This work showed that approximate dictionary learning, which consists in replacing the optimal solution of the Lasso with a time-efficient approximation, offers valuable trade-off between computational cost and quality of the solution compared to complete Alternating Minimization. This method, combined with a well-suited stochastic gradient descent algorithm, scales up to large data sets, demonstrated on MEG pattern learning problem. This work provided a thcoretical study of the asymptotic behavior of unrolling in approximate dictionary learning. In particular, we showed that numerical instabilities make DDL usage inefficient when too many iterations are unrolled. However, the super-efficiency of DDL in the first iterations remains unexplained, and our first findings would benefit from theoretical support.
Package and experiments available at https: http://aaaaaccc..ece wtt.sssss.iituu.tti... thub. ic

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
The MEG data conform ethic guidelines (no individual names, collected under individual's con- sent....)
REPRODUCIBILITY STATEMENT
Code is available at full description of all our experiments Appendix A, and the proofs of our theoretical results in Appendix C.
cow/bmalleeeeeeoocoooooaee...aae lewaleziiuue /enr//urrlll 1 d1. We provide
ACKNOWLEDGMENTS
This work was supported by grants from Digiteo France.
REFERENCES
Pierre Ablin, Thomas Moreau, Mathurin Massias, and Alexandre Gramfort. Learning step sizes for unfolded sparse coding. In Advances in Neural Information Processing Systems, pp. 13100- 13110, 2019.
Pierre Ablin, Gabriel Peyré, and Thomas Moreau. Super-efficiency of automatic differentiation for functions defined as minimum. Proceedings of the 37th International Conference on Machine Learning, pp. 32-41, 2020.
Alekh Agarwal, Animashree Anandkumar, Prateek Jain, and Praneeth Netrapalli. Learning sparsely used overcomplete dictionaries via alternating minimization. SIAM Journal on Optimization, 26 (4):2775-2799, 2016.
Michal Aharon, Michael Elad, and Alfred Bruckstein. K-svd: An algorithm for designing overcom- plete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 54:4311 4322, 2006.
Amir Beck and Mare Teboulle. A fast iterative thrinkage-t algorithm for linear inverse problems. SIAM Imaging Sciences, 2:183-202, 2009.
Quentin Bertrand, Quentin Klopfenstein, Mathieu Blondel, Samuel Vaiter, Alexandre Gramfort, and Joseph Salmon. Implicit differentiation of lasso-type models for hyperparameter optimization. In International Conference Machine Learning, pp. 810-821. PMLR, 2020.
Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Theoretical linear convergence of unfolded ista and its practical weights and thresholds. Advances in Neural Information Processing Systems, 2018.
Scott R Cole and Bradley Voytek. Brain oscillations and the importance of waveform shape. Trends in cognitive sciences, 21(2):137-149, 2017.
John M. Danskin. Theory of Max-Min and Its Application to Weapons Allocation Problems. Springer Berlin Heidelberg, Berlin/Heidelberg. 1967.
Ingrid Daubechies, Michel Defrise, and Christine Mol. An iterative thresholding algorithm for linear inverse problems with sparsity constrains. Communications on Pure and Applied Mathematics, 57, 2004.
Charles-Alban Deledalle, Samuel Vaiter, Jalal Fadili, and Gabriel Peyré. Stein unbiased gradient estimator of the risk (sugar) for multiple parameter selection. SIAM Journal on Imaging Sciences, 7(4):2448-22) 24874 2014.
Tom Dupré la Tour. Thomas Moreau, Mainak Jas, and Alexandre Gramfort. Multivariate convolu- tional sparse coding for electromagnetic brain signals. Advances in Neural Information Process- ing Systems, 31:3292-3302. 2018.
10

---

Published as a conference paper at ICLR 2022
Alexandre Gramfort, Martin Luessi, Eric Larson, Denis A Engemann, Daniel Strohmeier, Christian Brodbeck, Roman Goj, Mainak Jas, Teon Brooks, Lauri Parkkonen, et al. Meg and eeg data analysis with mne-py,hon. Frontiers in neuroscience, 7:267, 2013.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. International con- ference machine learning, pp. 399-406, 2010.
Rémi Gribonval, Rodolphe Jenatton, and Francis Bach. Sparse and spurious: dictionary learning with noise and outliers. IEEE Transactions on Information Theory, 61(11):6298-66 6318,, 2015.
Roger Grosse, Rajat Raina, Helen Kwong, and Andrew Y. Ng. Shift-Invariant Sparse Coding for Audio Classification. Cortex, 8:9, 2007.
Benjamin D Haeffele and René Vidal. Global optimality in tensor factorization, deep learning, and beyond. arXiv preprint 1rXiv:1506.07544 2015.
Bruno Lecouat, Jean Ponce, and Julien Mairal. A flexible framework for designing trainable priors with adaptive smoothing and game encoding. Advances in neural information processing systems, 2020.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land- scape of neural nets. In Advances in neural information processing systems, pp. $389-6399 2018.
Jialin Liu and Xiaohan Chen. Alista: Analytic weights are as good as learned weights in lista. In International Conference on Learning Representations, 2019.
Julien Mairal, Francis Bach, J. Ponce, and Guillermo Sapiro. Online learning for matrix factorization and sparse coding, Journal of Machine Learning Research, 11, 2009.
Thomas Moreau and Joan Bruna. Understanding neural sparse coding with matrix factorization. In International Conference Learning Representation, 2017.
Thomas Moreau and Alexandre Gramfort. Dicodile: Distributed convolutional dictionary learning-
IEEE Transactions Pattern Analysis and Machine Intelligence, 2020.
Bruno A. Olshausen and David Field. Sparse coding with an incomplete basis set: A strategy employed by \protect( V1). Vision Research, 37(23):311-3325, 1997.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances neural information processing systems, pp. 8026-8037, 2019.
Meyer Scethon, Michael Elad, and Peyman Milanfar. Deep k-svd denoising. IEEE Transactions Image Processing, 0.55444-955, 2021.
Amirreza Shaban, Ching-An An Cheng, Nathan Hatch, and Byron Boots. Truncated back propagation for bilevel optimization. International Conference on Artificial Intelligence and Statistics, pp. 1723 1732. PMLR, 2019.
Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere Overview and the geometric picture. IEEE Transactions Information Theory, 63(2):853 -884, 2016.
Wen Tang, Emilie Chouzenoux, -hir-hhistttphe Pesquet, and Hamid Krim. Deep transform and metric learning network: Wedding deep dictionary learning and neural networks. arXiv preprint arXiv:2002.07889, 2020.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B, 58:267-288. 1996.
Ryan J. Tibshirani. The lasso problem and uniqueness. Electronic Journal of Statistics, 7(1): 1456 1490, 2013.
11

---

Published as a conference paper at ICLR 2022
Bahareh Tolooshams and Demba Ba. Pudle: Implicit acceleration of dictionary learning by back- propagation. arXiv preprint, 2021.
Bahareh Tolooshams, Sourav Dey, and Demba Ba. Deep residual autoencoders for expectation maximizationninspired dictionary learning. IEEE Transactions Neural Networks and Learning Systems, PP:1-15, 2020.
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates, Advances in neural information processing systems, 52:3732-3744 2019.
Tong Tong Wu, Kenneth Lange, et al. Coordinate descent algorithms for lasso penalized regression. Annals of Applied Statistics, 2(1):224-22) 244, 2008
Yande Xiang, Zhitao Lin, and Jianyi Meng. Automatic qrs complex detection using two-level con- volutional neural network. Biomedical engineering online, 17(1):1-17, 2018.
Florence Yellin, Benjamin D Haeffele, and René Vidal. Blood cell detection and counting in holo- graphic lens-free imaging by convolutional sparse dictionary learning and coding. In International Symposium Biomedical Imaging, pp. 650-653. IEEE, 2017.
John Zarka, Louis Thiry, Tomas Angles, and Stephane Mallat. Deep network classification by
scattering and homotopy dictionary learning. In International Conference on Learning Represen- tations, 2019.
A FULL DESCRIPTION OF THE EXPERIMENTS
This section provides complementary information on the experiments presented in the paper.
A.1 CONVERGENCE OF THE JACOBIANS FIGURE AND FIGURE 2
We generate a normalized random Gaussian dictionary D of dimension 30 50, and sparse codes
from a Bernoulli Gaussian distribution of sparsity 0.3 and x² = 1. The signal to process is y = Dz + b where b an additive Gaussian noise with ah = 0.1. The Jacobians are computed for random perturbation D + bD of where 6D is a Gaussian noise of scale 0.50 JN corresponds to the approximate Jacobian with N iterations of ISTA with À = 0.1. J corresponds the true Jacobian computed with sparse codes obtained after 10 iterations of ISTA with À = 0.1.
In Figure 2, the norm ||
J is computed for 50 samples.
A.2 CONVERGENCE OF THE GRADIENT ESTIMATES- FIGURE 3
Synthetic data. We generate a normalized random Gaussian dictionary D of dimension 30 50, and 1000 sparse codes z from Bernoulli Gaussian distribution of sparsity 0.3 and o² 1. The signal to process = Dz + b where an additive Gaussian noise with o² of = 0.1. The gradients are computed for a random perturbation D + bn of D where bn is Gaussian noise of scale 0.5g
Noisy image. A 128 128 black-and-white image degraded by a Gaussian noise with o2 0.1 and normalized. We processed 1000 patches of dimension 10 x 10 from the image, and we computed the gradients for dictionary composed of 128 random patches.
corresponds to the gradient for N iterations of FISTA with À = 0.1. g" corresponds to the true gradient computed with sparse code obtained after 10 iterations of FISTA.
A.3 OPTIMIZATION DYNAMICS ON SYNTHETIC DATA FIGURE
We generate normalized random Gaussian dictionary D of dimension 30 50, and sparse codes
z from a Bernoulli Gaussian distribution of sparsity 0.3 and 5² = 1. The signal to process is
y Dz b where is additive Gaussian noise with o2 0.1. The initial dictionary
noise
12

---

Published as a conference paper at ICLR 2022
is taken as random perturbation D DD of D where DD is Gaussian noise of scale 0.5o N corresponds to the number of unrolled iterations of FISTA. F is the value the loss for 103 iterations minus 10-3. 3. S* is the score obtained after 100 iterations plus 10-3 The optimization is done with X = 0.1. We compare the number of gradient steps (left), the loss values (center), and the recovery scores (right) for 50 different dictionaries. DDL with steps sizes learning is evaluated 100 iterations only due to memory and optimization time issues.
A.4 OPTIMIZATION DYNAMICS AND LOSS LANDSCAPES ON IMAGES FIGURE 5
A 128 128 black-and-white image is degraded by Gaussian noise and normalized.
Left. this experiment, o² " 0.1. We learn a dictionary composed of 128 atoms on x 10 patches with FISTA and À 0.1 in all cases. The PSNR is obtained with sparse codes output by the network. The results are compared to the truth with the Peak Signal to Noise Ratio. Dictionary learning denoising with 1000 iterations of FISTA is taken baseline.
Center: We learn 50 dictionaries from 50 random initializations in convolutional dictionary learn- ing with 50 kemnels of size 8 8 with 20 unrolled iterations of FISTA and À 0.1. The PSNR is obtained with sparse codes output by the network. We compare the average, minimal and maximal PSNR, and recovery scores with all other dictionaries to study the robustness to random initialization depending on the level of noise (SNR).
Right. In this experiment, of 0.1. We learn 2 dictionaries from 2 random initializations in convolutional dictionary learning with 50 kernels of size x 8 with 20 unrolled iterations of FISTA and À = 0.1. We display the loss values on the line between these two dictionaries. The experiment is repeated on 10 different random initializations.
A.5 STOCHASTIC DDL ON SYNTHETIC DATA FIGURE 6
We generate normalized random Gaussian dictionary D of dimension 50 100, and 10 sparse
codes = from a Bernoulli Gaussian distribution of sparsity 0.3 and o² = 1. The signal to process y Dz + where b an additive Gaussian noise with noise 0.1. The initial dictionary is taken as random gaussian dictionary. We compare stochastic and full-batch line search projected gradient descent with 30 unrolled iterations of FISTA and À 0.1, without steps sizes learning. Stochastic DDL is run for 10 epochs with maximum of 100 iterations for each epoch.
A.6 PATTERN LEARNING IN MEG FIGURE 7
Stochastic Deep CDL on 6 minutes of recordings of MEG data with 204 channels and a sampling rate of 150Hz. We remove the powerline artifacts and high-pass filter the signal to remove the drift which can impact the CSC technique. The signal also resampled computational burden. This preprocessing procedure is presented in alphacsc, and available in the code in the supplementary materials. The algorithm learns 40 atoms of I second on mini batches of 10 seconds, with 30 unrolled iterations of FISTA, Ascaled 0.3, and 10 epochs with 10 iterations per epoch. The number of mini-batches per iteration is 20, with possible overlap.
150 Hz reduce the
B EXTRA FIGURES AND EXPERIMENTAL RESULTS
LISTA Figure A. Illustration of LISTA for Dictionary Learning with initialization Z, = =0 for
N = 3. Wh = (D) W3 = (I- (D) D), where L = ||]] The result (D) output
by the network an approximation of the solution of the LASSO.
Loss landscape in 2D- Figure B. We provide a visualization of the loss landscape with the help of ideas presented in Li et al. (2018). The algorithm computes minimum, and we chose two properly rescaled vectors to create plan from this minimum. The 3D landscape is displayed on this plan in the appendix using the Python library K3D-Jupyter. This visualization and the visualization in iD confirm that (approximate) dictionary learning locally behaves like a convex function with smooth local minima.
13

---

Published as a conference paper at ICLR 2022
W
W
Wh
3
W
2N(D)
Figure A: LISTA
Figure B: Loss landscape in approximate CDL
Gradient convergence norm - Figure C. Gradient estimates convergence in norm for synthetic data (left) and patches from noisy image (right). The setup is similar to Figure 3. Both gradient estimates converge smoothly in early iterations. When the back-pre socck-ropaggtion goes too deep, the performance of IN decreases compared to gly. and observe large numerical instabilities. This behavior coherent with the Jacobian convergence patterns studied Proposition 2.5. Once on the support, gyy reaches back the performance of gkx-
Gaussian dictionary
Noisy image
10a
103
BP depth
10a
20
10
50
10
full
AM
100
101
102
103
10"
101
10a
103
Iterations N
Iterations N
Figure C: Gradient estimates convergence in norm for synthetic data (left) and patches from noisy image (right). Both gradient estimates converge smoothly in early iterations, after what DDL gradi- ent becomes unstable. The behavior returns normal once the algorithm reaches the support.
Computation time to reach 0.95 recovery score Figure D. The setup is similar to Figure 6. A random Gaussian dictionary of size 50 100 generates the data from 10a sparse codes with sparsity 0.3. The approximate sparse coding is solved with X = 0.1 and 30 unrolled iterations of FISTA. The algorithm achieves good performances with small mini-batches and thus limited memory usage. Stochastic DDL can process large amounts of data and recovers good quality dictionaries faster than full batch DDL.
Sto DDL vs. Online DL Figure et al., 2009) and Stochastic DDL need reach recovery of 0.95 with batch size of 2000. Online DL is run with 10 threads. We repeat the experiment times for different values of from
compare the time Online DL from spams (Mairal
package available http::/thotte inri ape.. fr/peop' e/mai ral /spams/
14

---

Published as a conference paper at ICLR 2022
Time to reach a score of 0.95
50
40
Timeout
Time (s)
30
20
10
100
500
2000
10000
DDL Oracle DL
Minibatch size
Figure D: Time to reach a recovery score of 0.95. Intermediate batch sizes offer a good trade-off between speed and memory usage compared to full-batch DDL.
0.1 to 1.0. The setup is similar to Figure D, and we initialize both methods randomly. Stochastic DDL is efficient for smaller values of X, due the fact that sparse coding slower in this case. For higher values of X, both methods are equivalent. Another advantage of Stochastic DDL its modularity. works on various kinds of dictionary parameterization thanks to automatic differentiation, as illustrated on 1-rank multivariate convolutional dictionary learning in Figure 7.
Time to reach score of 0.95
102
Sto. DDL
Time (s)
Online DL
10
0.2
0.4
0.6
0.8
1.0
A
Figure E: Comparison between Online DL and Stochastic DDL. Stochastic DDL is more efficient for smaller values of X, due to the fact that sparse coding is slower in this case.
C PROOFS OF THEORETICAL RESULTS
This section gives the proofs for the various theoretical results the paper.
C.I PROOF OF PROPOSITION 2.1.
Proposition 2.1 Let D arg min G(D) and D arg min Dec Gx(D), where N is the number of unrolled iterations. We denote by K (DD") a constant depending on D and by C(N) the convergence speed of the algorithm, which approximates the inner problem solution. We have
Gx(D)) G(D") K(D*)C(N)
D) where ZD arg min F(Z, D) and (D) FISTA(D,N), Let D arg mi G(D) and D arg min DEC G (D). We have
Let G(D) A
F(Z (D), D) and Gx(D) & F(ZN(D),
Gx() G(D")
GN((D)) -N (D +g' (xx G(D")
= =F(Z Dx) -F(xx(")) F(ZNN D F(Z(D"),D)
(8)
15

---

Published as a conference paper at ICLR 2022
By definition of Div
F(ZN(D%),D)) F(2x(D") D*) 0
(10)
The convergence rate of FISTA in function value for fixed dictionary D is
((D)
F(Zx(D), - D & N
(11)
Therefore
K(D*)
F(ZN - D - N
(12)
Hence
- S K(D*)
(13)
N2
C.2 PROOF OF PROPOSITION 2.2
Proposition 2.2 Let D E Rmxn. Then, there exists constant L1 0 such that for every number of iterations
|g - grll s T, (zx) 2² =D))ll
We have
F(z, D)
DDz - y11 + A |
(14)
2
V2F D) (Dz y)
(15)
DD) O and the iterates (zN (D)) NEN converge towards 2" (D). Hence, they contained in a closed ball around 20 (D). As F( D) is continuously differentiable, it is locally Lipschitz on this closed ball, and there exists a constant Li (D) depending on D such that
gg - g" || = [22 D) V2F (D), (2F(=
(16)
S (n I (D)]
(17)
C.3 PROOF OF PROPOSITION 2.3.
Proposition 2.3 Let E RMxx Let S* be the support of (D), SN be the support of zN and
5N = SN S Let f(z, = + Dz - v1l2 be the data-filting term in F. Let R(J, S) (Vi,f(zz D) o 1g) + (2,f(z', D) @ 13. Then there exists constant L2 0 and a sub- sequence of (F)ISTA iterates Zo(N) such that for all N E N:
3 DOIN) V2](ZE(N) D) J JO(N) (VIS(EO(N); D) Xa (EO(N)) s. 1O(N)
S [[] 3 ( =z'l L2 [ZO(N) =0112
This sub-sequence Zo(N) corresponds iterates on the support of
We have
(D) (D) V2f(EN D) D) JN (Vif(zn(D), D) + (xN))
(18)
We adapt equation (6) in Ablin al. (2020)
2 = + R(J,, Sw) - x²) + RR 1
(19)
where
V2,5(=", R(J,5) ('V + DD) 3 13
(20)
RD Vef(EN, D) V2f(2" D) v ,D)( =x)
(21)
RV VIS(EN, D) 20 (zN) (D)(NN) z²)
(22)
16

---

Published as a conference paper at ICLR 2022
As nN and z" on SN
V2 DzN =²) (V2, D) 2 15w (zN =2)
(23)
J (V.s((>" (NN -²") J (Vi. D)
11 S (ZN -=") 2²)
(24)
As stated in Proposition 2.2, ( D) is locally Lipschitz, and Ry is the Taylor rest of V2/(; D). Therefore, there exists a constant I.D2 such that
LD. IZN D) - (D)]? 2
AA E N, R -
(25)
We know that Vif(=*, D) + |-1, (z*). In other words, Bur \d -1,, (2*) s.t. Vif(=* D)+
u = 0. Therefore we have:
R E VIJ(ZN. D) VIS(=", Vi, (=)(((",))<(N 2²) + X0 | u (26)
Let 1.z be the Lipschitz constant of VIJ(.,), (F)ISTA outputs sequence such that there exists a sub-sequence (ZO(N))NEN which has the same support as z'. For this sub-sequence, "" E 10 (=o(N)). Therefore, there exists R such that
1. Ro(()= Vif(zo(N); D) + 1-1 (= - (2(f(z,,))<z01 - =²))
2.
I L..= ( 1
((N)
For this sub-sequence, adapt Proposition 2 from Ablin et al. (2020). Let L2 LD,> Lzz,z
we have
3 DO(N) E V2[(Z D) Jocn (Vis(= D) + A0 | = s.t.:
(27)
| - 3r $ [R(JoN), || - ==1 La
- =2" -2=11
(28)
C.4 PROOF THEOREM 2.4.
Theorem 2.4 At iteration N + of ISTA, the weak Jacobian of x relatively to Di, where Dj is the 1-th row of D, is given by induction:
1(z++1)
(((zN)
I (DIET +DT NN W + D M(zN)
0D: 1/x41 20
aD;
DD,
0(zx)
DD: will be denoted by JNN It converges towards the weak Jacobian Ji of xt relatively to Di.
whose values are
J g- -D..s.
(DJ=" In)s
on the support St of " and 0 elsewhere. Moreover, R(J", = O.
We start by recalling Lemma from Deledalle et al. (2014).
Lemma C.1 The soft-tresholding ST₃ defined by STy(2) sgn(z) @ (|2) 10) is weakly dif-
ferentiable with weak derivative dST.iiz) 1l |
dz
Woordinate-wise, ISTA corresponds to the following equality:
zx+1 = STp((I 1 D' D)zN
L DTyy) 4)
(29)
n + L
= Σ
Djc
Σ D5w0s)
(30)
j=1
17

---

Published as a conference paper at ICLR 2022
The Jacobian is computed coordinate wise with the chain rule:
O(NN+1) dDi
((NN):
1
Y7 n
1 a
Σ Djilis))
"
(=N+1))120
LODIK
L0D
j=1
j=1
(31)
Last term:
Djcts = 6u
(32)
0D
j=1
Second term:
0
o M(NN) d 0Du
iD
0Dm p=1j=1
=
Dji D
(ZN)p
(33)
p=1j=1
p=1Ø=1
2Dt
if j I and p k
0D
Dip
if j = I and i = 1 and # 1:
(34)
0hk
Dii
if j I and + k and p k
0
else
Therefore:
m
n
0D 1p
(ZN),
sp h Drcpp Dipdes 1x p=1
(35)
0ik
p=1j=1
m
2 (EN))NN) + Du(2N))llikk
Din(zn)
(36)
Pabk
= =Du(ZN) + dik ppm
Dr, (ZN)p
(37)
Hence:
0(2N+1);
((EN))
(aN4s))
I (Di(ex))+
(38)
0Dtk
2Du
HZN) Dji Dip )lvvi)
8sk
Dip(EN)p) +
0Dik
p=1-=1
This leads to the following vector formulation:
((x++1) 1 O
((ENN) - 1 (DiIT+(D) (DT øN - Im + +T
O ((NN)
0D, ))
(39)
0D,
aD:
On the support of 2", denoted by S* this quantity converges towards the fixed point:
J -D DD.s ) T + (D. =" Im)s
(40)
Elsewhere, Ji is equal 0. To prove that R(J", S*) 0, we use the expression given by equa- tion 39
J' = =1= 3 J - (V2 D.) + Vi,f(*" ()
(41)
1 1s- @ V2./(=", D.) + 1s- & Vi,l(=,, TJ
J' 1s- @ J
(42)
0 S (Vi,f(z'. D) 11.)) va,f(= D 01s-
(43)
R())
(44)
18

---

Published as a conference paper at ICLR 2022
C.5 PROOF OF PROPOSITION 2.5 AND COROLLARY 2.6
Proposition 2.5 Let N be the number of iterations and K be the proppaaonnn depth. We as- sume that vn 2 N N-K. K, S C Sn. Let EN Sn S let be the largest eigenvalue of D., D.,
and let pma be the smallest eigenvalue of :.S, - Let Bn Ps is the projection on R$ and D is the aseudo-inversee of D. We have
PE. - -D. Di.5- Ps. where
K-1 A
|| - J7ll = II (1 1=1
UN -N- |1 2
Dill
EII
MN-i
(1
(1178-
=2 2/|l+ Br - [|=
I
k0
We denote by G the matrix have with the induction in Theorem 2.4
- DD D). For EN with support SN and z* with support S we
N, = (GJ, + un N 1 SN
(45)
Si (GJi + ui)s
(46)
where u/" = (Di + (DJ nN -y)() and the other terms on SN and S are 0. We can thus decompose their difference as the sum of two terms, one on the support S and one on this complement Æ, SN S
Jr - J.N = (J) )n + +J J
Recall that we assume S C SNv Let's study the terms separately on S and E = SN \ S". These two terms can be decompose again constitute double recursion system,
(J - JÇ)s. = (J (J, Ji' - (u) N1 us)ss
(47)
s- (Ji Ji)s + Gg.. EN-i (JN-1- - J') + +uuf- - ui)s.
(48)
(JN (JN-JT Ji (NN-x)xx (x GGx (J -JN-1- GENis.Ji + (u) (ui--1) En
(49)
GFy.S-(J (J. Ji'ss- + GFN,
(J, (
ui) D.T dB Dis (D.... D..s)) -
(50)
+ (uN-- - - FN En + ((u))
We define as Es the operator which projects a vector from EN on (SN, EN) with zeros on SN. As S* U ENN = SN. we get by combining these two expressions,
JJN J()sx -GsN.S -JN-1- J(Ss + (uf-1--f) -u;)sx
(51)
+ PNS.EN ((u)) DTTEW (D.. D..s)
Taking the norm yields to the following inequality,
|| J = [[GS || 1 + || N uill
(52)
+ (u -DT D.T.N Dr,s- DD.. D..s-) D (wi)s
Denoting by Ja the smallest eigenvalue of D.Toy D.SSx then ||G = =(1 (x) and we get that
K
JoNV - Jill
<
PN-K)
|| J:
(53)
L
k=1
K-1
ui + (ui)xx Ex DT
DJT (wi)s 1)
19

---

Published as a conference paper at ICLR 2022
The back-propagation is initialized as JN over ||u will S & || =| z ||- Finally, (ui) D
K 0. Therefore || - J |
More-
D. (ui)s
can
:NEN-
be rewritten with projection matrices PEN-1 and Ps. to obtain
- D. -D ENE
D.T
D. (u])s
< Px 2 - -D,,, :EEN- D.T. Ps. ui
(54)
<
PEN-N - -D._ [ D. Ps--
|
(55)
<
BE-= -D.- D.J. Dip.-Ps-
:,EEEE i,s- Ps.
2
D ||
(56)
Let Bx-+ = =
-DT
D. Ps-
We have
=EE
K
K-1 K:
|| - Ji S II
PN-K) L
|| 1|+
2 L
||
(1 "
MN-i L
z1 +1|+ BN - [1=F1l)
k=
(57)
We now suppose that the support is reached iteration N- 8, with 8 2 K. Therefore, Vn
[N 8, s, Sn = S Let A, = F(zn, D) F(z", D) +
L
2| - 2²1l- On the support, F is a
2
u-strongly convex function and the convergence rate of (zN) is
11 24
1|2 zx s (1
(58)
L
L
Thus, we obtain
||
J
S
II (1 PN-K |,
(59)
K-1
+
2
Drll
Σ
AN-1 (1157~
=1'l + BN x
||
T,
k= =1
(1
UN- L
(60)
1=1
+
2
|
[1-
Σ
1-1
10
L
K-
2 L
~N 1 - -zill+ BN =1(())]]]
+
Dill (1 -
-=s-1
K
II(1
HNN |J
(61)
A=1
2 Drll
Σ (1
s-1
4 41 )
1-a-1-22AN
+ T
k=
K-1
2 Dill (1
(1 II
zill + BN -N-+ I[(a]]]
L
L
k=s-1
K
<
IIO (1
WN-K || I
(62)
k=1
11 + 1 4AN-s
+
+ill (1
12
K-1
2 I
Diil (1 - y Σ I ( ( - zill + BN - [[(
L
k=s-li=s-1
(63)
20

---

Published as a conference paper at ICLR 2022
Corollary 2.6 Let 0 be the smallest eigenvalue of D.. D..s.. Let K I N be the back-
propagation depth and let A F(zN, D) F(z", D) + L ll - 2- ||. Suppose that Vn [N N, Sn S* Then, we have
|5 K (1 1 - J = (1-1) 4)
1 K-1
4AN-K
|
L
I
The term 1:1 (1- (1- -k Ei -1: (1- (1- when the algorithm is initialized on the support. Otherwise, it goes to 0 as 8, K N and N + oo because Vn N 8, Pn = / 1.
||
BN [[(5]]]] vanishes
D ITERATIVE ALGORITHMS FOR SPARSE CODING RESOLUTION.
ISTA.
Algorithm to solve min; 2 1yy D21 ||
Algorithm 1STA
y. D. N
Zg = n =
Compute the Lipschitz constant of DJ D
while < N do
Un+1 2N 1
(Dzn 9)
Zn+1 - STx E (zn++1)
n 1- n++1 end while
FISTA. Algorithm to solve ming y lyy D=1 A ||
Algorithm FISTA
y. D. X, N
20 = xo = 0, n O, to =
Compute the Lipschitz constant L of D D
while n < do
Un+1 2n (D2n y)
Ea+1 - ST (un+1)
1+ 1+11+41
In+1
2
Zu+1 Fnt1 b1t1 (Ent1 F..))
n 14-+1
end while
21


Reviews:
[{"review_id": "_gdUMuZ1NYr", "reviewer": "Reviewer_njnY", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Strong points*\n\n1. The technical writing of the paper is fairly well. The derivation can be followed without too much effort.\n\n2. The paper presented an quite detailed discussion on unrolling scheme related to deep dictionary learning (DDL) which can be interested to the people working on DDL.\n\n*Weak points*\n\n1.  The applicability of the presented unrolling scheme is rather limited. It is only applicable to the problem motivated from a convex formulation of sparse coding, while a majority of the dictionary learning is using non-convex sparsity-regularization term such as -norm.\n\n2. Its advantage over existing optimization methods e.g. K-SVD, proximal alternating method, and proximal alternating linearized method (PALM) for dictionary learning, is neither justified in theoretical analysis nor in experimental evaluation.\n\n3. Experimental evaluation is limited with important missing information.\n\n*Comments and Questions*\n\n\n1. The hard part in dictionary learning is about the efficient treatment of non-convex constraints such as orthogonality or normalization. Are these treated using Lagrangian multiplier? if one want to call the proposed scheme for optimization model of dictionary learning\n\n2. In Proposition 2.2 and 2.3. The results says there exist  such that the conclusion holds true. It seems that  is the cardinality of dictionary. Is this a typo, or they are the same.\n\n3. While the proposed scheme is applicable to a specific learning scheme for MEG signal, it is not convincing enough to claim it is computationally efficient. The scale of such a problem is well handled by the traditional methods such as K-SVD, PAML.\n\n4. In general, dictionary learning is not well-defined without additional constraints on the dictionary atoms, there is no mention of such constraints in the experiments.\n\n\n", "summary_of_the_paper": "This paper present an efficient unrolling scheme for finding an approximate solution to the optimization problem arising from sparsity-based dictionary learning. Some asymptotically analysis on its gradient is presented and the method is also tested on analyzing MEG signal.", "summary_of_the_review": "Numerical scheme for solving the non-convex problem related to dictionary learning has been extensively studied. For example, proximal alternating method and proximal alternating linearized method. The hard part indeed lies in efficient and effective estimation of dictionary with non-convex constraints. The proposed unrolling scheme does not address the true bottleneck of the problem. The asymptotic analysis presented indeed are rather the application of existing available techniques. Numerical experiments on MEG signals are also too limited to show its practical advantage\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "LvjrdVSh8jI", "reviewer": "Reviewer_EyuW", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "From my point of view, this paper is well-written and the presented analysis is interesting in the context of a recently growing body of work on unrolling. It provides a rigorous theoretical investigation and justification of practically observable phenomena.\n\nI only have one minor point which can hopefully be clarified. Maybe the authors can comment on the role of $L$ in Proposition 2.2. Is it correct that $L$ is at the same time the row dimension of $D$ and a constant to estimate convergence speed?", "summary_of_the_paper": "The authors investigate the asymptotic behavior of unrolling applied to dictionary learning. The applicability of unrolling to dictionary learning results from the circumstance that dictionary learning can be reformulated in terms of bilevel optimization, where the lower-level (or inner) problem is a sparse coding problem (in the LASSO case considered here). Unrolling means to replace the argmin in the lower-level problem with the $N$-th iterate of a suitable optimization algorithm. Gradients of the upper-level loss can then be computed by means of backpropagation through algorithmic iterates. The authors study the behavior of resulting gradients depending on $N$ and draw a comparison with alternating minimization. They find that unrolling constitutes a scalable alternative to alternating minimization, where unrolling a relatively small number of iterations or using truncated backpropagation is favorable to ensure stable approximate gradients.", "summary_of_the_review": "I think that this paper should be accepted. As far as I can see, the presented results are relevant and correct. However, I did not check the proofs in the last detail.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9HkItRVcDr", "reviewer": "Reviewer_5JDj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Pros: The paper is written clearly. They study an interesting problem. Given the summary above, the stability analysis of the Jacobian and insights of limited-depth backpropagation to improve stability is new and of interest (proposition 2.5). The authors have provided comprehensive numerical results along with real applications to support their theories and claims. The visualization of loss landscape is interesting and has not previously explored for dictionary learning.\n\nCons: Given (Ablin et al., 2020, Tolooshams et al., 2020, and [1]), the novelty of the paper is incremental. Specifically, proposition 2.2 is known results from Ablin et al., 2020. Given the support and uniqueness assumption of the code, the reconstruction loss is strongly convex, and the optimization is reduced to the case in Ablin et al., 2020. Hence, proposition 2.3 follows. Stochastic CDL using unrolled networks has been previously explored in (Tolooshams et al., 2020) in the context of spike sorting and image denoising. Theoretical analysis and comparison of g1 and g2 for dictionary learning is known from [1].\n\nThe authors must clearly indicate their contributions and how their work differs from (Ablin et al., 2020, Tolooshams et al., 2020, and [1]). An additional analysis to make this work different from prior works can be providing dictionary recovery type of results similar to [2]. Overall, a better organization of the paper is recommended. See my detailed comments below. \n\n- There are some statements that are not fully supported and are not completely accurate.\n\t- For example, In \"Gradient estimation in dictionary learning\" paragraph, the authors mention that \" ... complete theoretical analysis of these problems are arduous\". It is not clear what that means. Indeed, [2] is missing where it studies gradient-based alternating minimization for dictionary learning and provides convergence guarantees.\n\t- The statement on \"... computing optimal sparse codes at each gradient step is unnecessary to recover the dictionary\" is not precise. Indeed,  one factor that is crucial is sparsity of the code.\n\t- The statement before Section 3 is not generally true. For example, the instability issue does not exist for the case of strongly convex function or a another loss function.\n\t- The statement \"we notice that there is no gain in the usage of DDL for the minimization of F_N without learning the steps sizes\" seems to be contradicting the whole idea of \"a better gradient estimation with DDL compared to AM\". Elaborations needed.\n\t- The statement \"... taking sub-windows of the full signal and performing SGD ...\" is not precise. It depends whether you define a global loss function over the whole image or local for each patch.\n\t- The authors refer to the dictionary learning problem as non-convex. However, a more accurate statement is \"bi-convex\".\n\n- How can you guarantee that invertibility of D^TD on the support stays along the whole iterations of alternating minimization?\n\n- In dictionary learning, you usually learn the dictionary for a finite set of examples. However, (1) does not reflect this and aims to learn D for only one example y.\n\n- The proof of proposition 2.2, the authors should clearly cite and highlight that Proposition 2.2 is a result from Ablin et al., 2020.\n\n- How is lambda chosen to guarantee dictionary recovery in the numerical examples given the data generation of y = Dx? Given the overcomplete dictionary, very low lambda may result in false positive in support recovery which will affect the dictionary recovery result. The value of lambda is indeed crucial at the presence of noise to avoid noise overfitting.\n\n- Experiments: \n\t- The paper has skipped a lot of experimental details in the main text and included only in the supp. Here are some that is recommended to be included in the main. How many iterations is \"full\"? At what iteration of the dictionary learning, Figure 1, 2, 3, 4 are based on (i.e., at dictionary initialization, after convergence, etc.)? Please elaborate what DL-Oracle is? How do you compute the optimal loss?\n\t- Why the dictionary error in Figure 4 (right) does not go to zero, and if their theory and analysis can explain that.\n\t- How to you define D of interest used in S(C)?\n\t- In Figure 5, do the authors train with various N values or train with the max N and look into the denoising performance given the code estimate at iteration n (i.e., Dx_n)?\n\t- What is the PSNR of the noisy image?\n\t- Intuitively, you may expect to find a trend in performance as you move from 100 batch size (which is not very low) to full batch. However, Figure 5 does not show such trend. Is there any insight for this?\n\n\n- Other comments:\n\t- In the introduction, it is missed to mentioned that n  >> m.\n\t- \"we propose to study the correlation between the gradients ...\". It is not clear how we can show dictionary recovery given such comparison.\n\t- In (6), does y entails the entire data? Is there a notion of # of examples?\n\t- The change of y-axis from Figure 4 to 5 is confusing. Recommend to use the same x-axis on Figure 5 (left) as in Figure 4.\n\t- What is the SNR for when the noise variance is 0.1?\n\t- What are the properties of the dictionary and code, in addition to lambda, that can make support selection faster?\n\t- Recommend to differentiate between L in proposition 2.2 and 2.3 which are different.\n\n- There are various typos and change of notation:\n\t- What is matrix A? there are numerous places that we see AD.\n\t- D has size of m x n but also n x L.\n\t- S is used once for the support and another time as a matric for dictionary error.\n\t- In the proof of Proposition 2.1, argmin must be over D \\in C not D in general. In addition, z must have dimension m not L.\n\n[1] B. Tolooshams and D. Ba, \"PUDLE: implicit acceleration of dictionary learning by backpropagations\", 2021.\n\n[2] N. Chatterji and P. Bartlett, \"Alternating minimization for dictionary learning: Local convergence guarantees\", 2017.\n\n\n------------\nafter discussion\n\nSee discussion on \"Revision of the paper\" comment initiated by the author's for my updated review. I hope the authors find my overall comments and the discussion useful in improving their manuscript. My main concern had been in relation to prior work and its novelty. The authors have addressed this with proper citation and additional explanation in the intro. I have updated my rating accordingly, increased the technical novelty to 3 (given the focus of the paper on the regime before support identification), however still kept the empirical novelty to 2.", "summary_of_the_paper": "The paper studies dictionary learning where assumes that data can be represented as a linear combination of a few atoms of a matrix called dictionary. Traditionally, one way to approach the problem is to set up a min-min (bi-convex) optimization problem known as lasso or basis pursuit and solve it through alternating minimization (alternate between a sparse coding step and a dictionary update). The paper compares gradient based alternating minimization which uses an analytic gradient (given the code estimate, compute the gradient) to unrolled-based dictionary learning which uses backpropagation (automatic differentiation) through an iterative algorithm estimating the code (inner problem) to compute the gradient for update of the dictionary. This paper borrows results from (Ablin et al., 2020) that had studied min-min optimization problems when the objective functions are smooth, differentiable, and strongly convex. Specifically, solving lasso iteratively through ISTA or FISTA, after support selection, with some assumption on the dictionary, the problem of this paper is reduced to the strongly convex case of (Ablin et al., 2020). Hence, the results follow. Their contribution that makes their paper different from (Ablin et al., 2020) is the study of the Jacobian and instability of the convergence prior to support selection. This very same model (dictionary learning through unrolled algorithms) have been already studied theoretically by [1] (which is missing in the citations) and empirically in the context of convolutional dictionary learning by this paper (Tolooshams et al., 2020) that they cite.", "summary_of_the_review": "The paper contains some new results compared to prior works (stability analysis of the Jacobian and limited-depth backprop). However, the papers lacks novelty given the works from Ablin et al., 2020, Tolooshams et al., 2020, and [1] (see above for details). Given the current formulation, results, and version of the paper, the paper's contributions do not distinguish itself from prior works. Hence, I do not recommend an acceptance of this paper. I hope that authors find my comments helpful and can address my concerns detailed in the review.\n\n------------\nafter discussion\n\nThe authors explained how their work with focus on instability of the Jacobian and analysis prior to support identification distinguishes itself from prior studies. Given this and the additional citations, I have increased my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1J7-XbUWWL", "reviewer": "Reviewer_S6uo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n- The topic is important and timely.\n- Unrolling optimization algorithms and coupling them via backpropagation is a natural direction being pursued in several application domains. It is nice to see some careful analysis for this specific context (dictionary learning).\n- The paper is nicely and clearly written.\n- The experiments are thorough and well conducted.\n\nCons:\n- The significance of the proposed method (and analysis), and overall relative contributions to the state of the art, is somewhat unclear.\n- Theoretical analysis of dictionary learning is a well-studied problem (with all kinds of running time and sample complexity guarantees).\nIt will be helpful to precisely position the quantitative guarantees (Theorem 2.4, Prop 2.6) in the literature whether there is any particular benefit or drawback of computing the (outer) sub-gradient over, say, AM or other techniques.\n- Backpropagation through the solution of sparse recovery has been already done before (by Bertrand et al, ICML 2020), so a clear comparison with this previous approach (and discussions of pros vs cons of backpropagation through unrolling) will be beneficial.\n- The experimental results in Figs 3/4 don't really show significant improvement over AM. It may be helpful to illustrate what lessons can be learned here. \n- Since the MEG application addresses convolutional DL, it may be helpful to address whether variations of the analysis approach is applicable to the convolutional case.\n\n---\n\nThanks for your response and for clarifying my questions regarding novelty. Bumping my score up to 6.", "summary_of_the_paper": "The authors theoretically study the performance of dictionary learning using \"unrolling\" based methods. As opposed to alternating minimization (AM) which switches back and forth between dictionary estimation and sparse recovery, the paper writes down the target dictionary as the solution to a bi-level optimization, where the \"inner\" optimization is approximated by unrolling with N steps. The main contribution is an approach (along with careful analysis) of computing the subgradient for the outer optimization, and experiments to show that this method works on synthetic and real datasets.", "summary_of_the_review": "This nicely written paper theoretically studies the dynamics of dictionary learning via unrolling + backpropagation style training. However, the authors could consider contrasting the results with the existing literature and clearly articulating how/where unrolling-style training is better or worse than the current of the art.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an unrolled algorithm to solve the l1-norm formulated dictionary learning problem, and focuses on the number of unrolling steps. It shows that it is better to limit the number of unrolling steps, and this leads to favorable performance over the alternating minimization baseline. The method can also be adapted to scale to very large datasets.

Most reviewers were positive or became positive after the rebuttals.  Reviewer njnY was still concerned about some issues, such as constraints and the choice of the l1 model over the l0 model; there also may have been confusion about unit sphere vs unit ball constraints.  However, given the recommendations of the other reviewers and my own opinion, I think the paper is a worthy contribution, and the point about not unrolling too deeply is an important one that is worth highlighting.
Decision: Accept (Poster)