Theoretical Interpretation of Learned Step Size in Deep-Unfolded Gradient Descent

2020·Arxiv

Abstract

Abstract

Deep unfolding is a promising deep-learning technique in which an iterative algorithm is unrolled to a deep network architecture with trainable parameters. In the case of gradient descent algorithms, as a result of the training process, one often observes the acceleration of the convergence speed with learned non-constant step size parameters whose behavior is not intuitive nor interpretable from conventional theory. In this paper, we provide a theoretical interpretation of the learned step size of deep-unfolded gradient descent (DUGD). We first prove that the training process of DUGD reduces not only the mean squared error loss but also the spectral radius related to the convergence rate. Next, we show that minimizing the upper bound of the spectral radius naturally leads to the Chebyshev step which is a sequence of the step size based on Chebyshev polynomials. The numerical experiments confirm that the Chebyshev steps qualitatively reproduce the learned step size parameters in DUGD, which provides a plausible interpretation of the learned parameters. Additionally, we show that the Chebyshev steps achieve the lower bound of the convergence rate for the first-order method in a specific limit without learning parameters or momentum terms.

I. INTRODUCTION

Deep unfolding [10], [12] is a promising deep learning approach whose architecture is based on existing iterative algorithms with tuning parameters such as step sizes in gradient descent (GD). The recursive structure of the algorithm is unrolled to a deep network and some parameters are embedded into the network. These parameters can be trained using standard deep learning techniques such as back propagation and stochastic GD if all the processes in the algorithm are differentiable. One notable advantage of deep unfolding is the acceleration of the convergence speed that results from tuning parameters compared with the original algorithm. Embedding proper trainable parameters also offers a flexible network structure to the algorithm that is applicable, for example, to inverse problems with/without prior information [26]. Since deep unfolding has been applied to iterative algorithms for compressed sensing [3], [15], [17], [35], [41], [42], a number of deep unfolding-based algorithms have been proposed in various fields, such as image recovery [16], [18], [22], [25], [34], [44] and wireless communications [11], [27], [33], [36], [37], [43]. Recently, theoretical aspects of deep unfolding have also been investigated [5], [21], [23].

Fig. 1. MSE performance (upper) and learned step size parameters (lower) of DUGD (circles) and GD with a constant step size (cross marks) when (n, m) = (300, 600). The details of the experimental conditions are in Appendix A.

To demonstrate deep unfolding, we consider a simple least mean square (LMS) problem written as

where is the measurement vector with the noise vector n and measurement matrix . Although the solution of (1) is explicitly given by ) using the Hermitian transpose matrix , GD is often used to reduce the computational complexity. The recursive formula for GD is given by

where is an initial vector and is a step size parameter. It is well known that the step size parameter controls the convergence speed of GD. The optimal value of is given by the largest and smallest eigenvalues of in the LMS problem, and it is found heuristically in general.

Alternatively, we define deep-unfolded GD (DUGD) by

where is a trainable step size parameter that depends on the iteration index t. The parameters can be trained using training data by minimizing the loss function such as the mean squared error (MSE) between the estimate after T iterations and . Figure 1 shows the empirical results of the MSE performance (upper) and learned parameters (lower) of DUGD and the original GD with the optimal constant step size when (m, n)=(300, 600) (see Appendix A for details). We found that the learned parameter sequence had a zig-zag shape, which accelerates the convergence speed compared with a naive GD with a constant step size. These learned parameters are not intuitive or interpretable from conventional theory. This type of nontrivial learned step size parameters is observed not only for DUGD but also other deep-unfolded algorithms that contain a nonlinear projection step [15], [21]. Regarding an iterative soft thresholding algorithm for compressed sensing, it has been proved that large step sizes accelerate its convergence speed but searching appropriate step sizes is computationally difficult in practice [1].

In this paper, the goal is to provide a plausible interpretation of the learned parameters of DUGD and show that the parameters can accelerate the convergence speed of GD.

The contributions of this paper are as follows:

• We show that minimizing the MSE loss in DUGD reduces the spectral radius related to the convergence rate of GD. This suggests that appropriately learned step size parameters can improve the convergence rate.

• By minimizing the upper bound of the spectral radius, we derive Chebyshev steps that are a step size sequence based on Chebyshev polynomials. Numerical experiments confirm that the Chebyshev steps qualitatively reproduce the learned step size parameters in DUGD.

• We perform convergence analysis of GD with the Chebyshev steps, which shows that the Chebyshev steps improve the convergence speed. Additionally, the convergence rate approaches the lower bound of first-order methods in a specific case, even though it does not require a momentum term. The numerical results support the analysis, and we demonstrate an application to ridge regression.

Related works: GD is a fundamental algorithm in continuous optimization [7]. GD was originally proposed by Cauchy [4] and is known as the steepest descent algorithm. The convergence rate of GD with a line search method that includes Cauchy’s method is analyzed by Forsythe [8]. The acceleration of the convergence speed is a crucial issue in the literature. A well-known technique is the use of a momentum term. This originated from the heavy ball method [30], which is simply called the momentum method [32] in the machine learning community. Chebyshev semi-iterative method [9] and Nesterov’s accelerated GD [28] are other algorithms that use a momentum term. For convex quadratic problems, it has been proved that these algorithms with momentum terms are optimal because their convergence rates are proportional to the lower bound of first-order methods [20], [28]. In this paper, we consider GD with a step size sequence and without momentum

terms, which matches the recursive relation of DUGD.

II. DEEP-UNFOLDED GRADIENT DESCENT

In this paper, we consider the minimization of a convex quadratic function where is the Hermitian positive definite matrix and is its solution. Note that this minimization problem corresponds to the LMS problem (1) under a proper transformation.

The corresponding GD algorithm with the step size sequence is given by

where is the identity matrix of order n and is an arbitrary point in .

In DUGD, we first fix the total number of iterations and train the step size parameters . Training these parameters is typically executed by minimizing the MSE loss function between the output of DUGD and the true solution . Additionally, to ensure the convergence of DUGD, we assume that DUGD uses a learned parameter sequence repeatedly for t > T. Specifically, in the tth iteration, we assume that , where (mod T). In this case, the output after every T steps is written as

for any k = 0, 1, 2, . . . . Note that is a function of step size parameters .

Our motivation is to show that a proper step size parameter sequence accelerates the convergence speed of GD. In this setup, an asymptotic convergence speed with respect to the error between an estimate and the optimal solution can be measured using the spectral radius of a matrix . Let be the eigenvalues of the matrix . Then, the spectral radius of Q is defined as

For GD defined by (5), it converges to the optimal solution if holds. Additionally, because the error between and the optimal solution is bounded using , the spectral radius indicates the asymptotic convergence rate of the algorithm.

III. THEORETICAL ANALYSIS

In this section, we show the following three facts: (i) minimizing the MSE loss in DUGD also reduces the spectral radius , (ii) the step size parameter sequence defined by the explicit form minimizes the upper bound of the spectral radius , and (iii) its convergence rate is smaller than a naive GD with a constant step size and asymptotically approaches the lower bound of the first order method. These facts suggest that DUGD possibly accelerates the convergence speed by tuning step sizes properly.

A. Spectral radius and loss minimization

The training process of deep unfolding consists of minimizing a loss function. We show that minimizing a typical MSE loss also reduces the spectral radius .

Before describing this claim, we first show the relation of to the eigenvalues of A. Recall that the Hermitian positive definite matrix A has n positive eigenvalues including degeneracy. Hereafter, we assume that to avoid a trivial case.

Lemma III.1. Let be an eigenvalue sequence of A satisfying . Then, we have

Proof. This is directly derived from (4) and the following fact: for a polynomial p(x) with complex coefficients, if is an eigenvalue of A associated with the eigenvector x, then is an eigenvalue of the matrix p(A) associated with the eigenvector x [14, p. 4-11, 39].

Using this lemma, we have the following theorem.

Theorem III.2. Let be a random variable over an isotropic probability density function satisfying . Then, for any , there exists a positive constant C satisfying

The details of the proof are in Appendix B. This theorem claims that minimizing the MSE loss function in DUGD reduces the corresponding spectral radius of , which implies that appropriately learned step size parameters can accelerate the convergence speed of DUGD.

B. Chebyshev step

In this subsection, our aim is to determine a step size sequence that reduces the spectral radius to understand the nontrivial step size sequence of DUGD. When , minimizing with respect to is a non-convex problem in general. We alternatively introduce a step size parameter sequence that bounds the spectral radius from above.

We first recall a well-known result when T = 1, that is, a constant step size case [2, Section 1.3].

Proposition III.3. Let and be the minimum and maximum eigenvalues of A, respectively. When T = 1, the step size parameter that minimizes is given by

In the general case in which , we focus on the step size sequence that minimizes the upper bound of the spectral radius . The upper bound is given by

Note that this upper bound is commonly analyzed [24, Section 3.4].

Next, we introduce a step size parameter sequence called Chebyshev steps which minimizes the above upper bound.

Theorem III.4. Let and be the minimum and maximum eigenvalues of A, respectively. For a given , we define Chebyshev steps of length T as

Then, the Chebyshev steps is a sequence that minimizes the upper bound of spectral radius of .

Note that the Chebyshev step is identical to the optimal constant step size in Proposition III.3 when T = 1.

We describe a sketch of the proof. The complete version is available in Appendix C. The function with the Chebyshev steps is represented by a Chebyshev polynomial of order T. Using the minimax property that is a monic polynomial that minimizes the -norm in the Banach space [24, Col. 3.4B], we can prove that the Chebyshev steps minimize .

The reciprocal of the Chebyshev steps corresponds to Chebyshev points, that is, the zeros of the shifted Chebyshev polynomial of order T defined on . Figure 3 shows the Chebyshev points and Chebyshev steps when , and . A Chebyshev point is defined as a point that is projected onto an axis from a point of degree on a semi-circle (see right part of Figure 3). The Chebyshev points are located symmetrically with respect to the center of the circle corresponding to . The Chebyshev steps are given by , which is shown in the left part of Figure 3. We found that the Chebyshev steps are widely located compared with the optimal constant step size .

C. Convergence analysis

For convergence analysis, we show that GD with the Chebyshev steps converges to the optimal solution. Let be the matrix with the Chebyshev steps of length T.

Proposition III.5. For any k = 0, 1, 2, . . . and , we have

Fig. 2. Chebyshev points (right; blue) and corresponding Cheby- shev steps (left; orange) when

Proof. Let be an operator norm of A. Because is a normal matrix, holds. Using (5), (10), and , we have

The main claim in this subsection is that the Chebyshev steps of length accelerate the convergence speed with respect to a spectral radius.

Theorem III.6. Let be the matrix with the Cheby- shev steps of length . We also define with the optimal constant step size, that is, . Then, we have

The proof of this theorem is divided into two parts. First, using (10) and the definition of the Chebyshev steps, we show that the spectral radius is bounded by

where is the condition number of the matrix A. Second, we prove that . Further details are in Appendix D.

The convergence rate of GD is defined as R := . From (15), the convergence rate of GD with the Chebyshev steps (CHGD) of length T is bounded by

(16) which is lower than the convergence rate of GD with the optimal constant step size . The rate

Fig. 3. Comparison of convergence rates as functions of condition number

approaches the well-known lower bound of first order methods from above, which is given by

This bound is strict because some GD algorithms, such as the momentum method and Nesterov acceleration, can achieve this rate in the strongly convex case. In Figure 3, we show the convergence rates of GD and CHGD as functions of . For CHGD, some upper bounds of the convergence rates with different T are plotted. We confirmed that CHGD with 2 has a smaller convergence rate than GD with the optimal constant step size and the rate of CHGD approaches the lower bound (16) quickly as T increases. All rates and the lower bound converge to 1 in the large-limit.

To summarize, we focus on the fact that the training process of DUGD reduces the spectral radius and introduce learning-free Chebyshev steps that minimize its upper bound and improve the convergence rate.

IV. NUMERICAL COMPARISON OF DUGD

In this section, we examine DUGD following the setup in Sec II. The main goal is to examine whether Chebyshev steps explain the nontrivial learned step size parameters in DUGD. Additionally, we also analyze the convergence property of DUGD and CHGD numerically.

A. Experimental conditions

We describe the details of the numerical experiments. DUGD was implemented using PyTorch 1.3 [29]. Each training datum was given by a pair of the random initial point and optimal solution . The random initial point was generated as the i.i.d. Gaussian random vector with unit mean and unit variance. The matrix A is generated by with the random Gaussian matrix whose elements were i.i.d. Gaussian random variables with zero mean and variance 1/n. Then, the eigenvalue distribution of A followed the Marchenko-Pastur distribution as

Fig. 4. Comparison of the MSE loss bound in Theorem III.2 and spectral radius in DUGD when (n, m) = (300, 1200).

with m/n fixed to a constant. The maximum and minimum eigenvalues approach and , respectively. The matrix A was fixed throughout the training process.

The training process was executed using incremental training in which we gradually increased the number of layers (iterations T) by initializing the value of the parameter () to a learned value in the former training process (generation) [15], [25]. Incremental training can improve the performance of DUGD compared with conventional one-shot training in which all layers are trained at once. At the beginning of the training process, all initial values of were set to 0.3 unless otherwise noted. For each generation, the parameters were optimized to minimize the MSE loss function between the output of DUGD and the optimal solution using 500 mini batches of size 200. We used Adam optimizer [19] with the learning rate 0.002.

B. Spectral radius and MSE loss

We numerically verified the relation between the MSE loss in DUGD and the corresponding spectral radius in Theorem III.2 up to T = 15. Figure 4 shows an example of the comparison when (n, m) = (300, 1200). To estimate the average MSE loss , we used the empirical MSE loss after the Tth generation. The constant C on the r.h.s. of (8) was evaluated numerically (see Appendix B). We confirmed that the spectral radius was upper bounded by (8) with the MSE loss .

C. Learned step sizes

Next, we examined the learned step size parameter sequence in DUGD. Figure 5 shows examples of sequences of length T = 6 and 15 when (n, m) = (300, 1200). To compare parameters directly, they were rearranged in descending order, although the learned parameters indeed had a zig-zag shape. The black symbols represent the Chebyshev steps with asymptotic maximal and minimal eigenvalues and when m/n = 4. Other symbols indicate the learned step

Fig. 5. Chebyshev steps (black symbols) and learned step size parameters in DUGD (others; 5 trials) in descending order when (n, m) = (300, 1200) and T = 6 (dotted) and 15 (solid).

size parameters corresponding to five trials, that is, different matrices of A and the training process with different random seeds. We found that the learned step sizes agreed with each other, which indicates the self-average property of random matrices and success of the training process. More importantly, they were close to the Chebyshev steps, particularly when was small. We found that, when T = 6, the gap between the Chebyshev steps and learned step sizes was larger than in the T = 15 case.

The zig-zag shape of the learned step size parameters is another nontrivial behavior of DUGD, although the order of the parameters does not affect the MSE performance after the Tth iteration. It is numerically suggested that the shape depends on the training process, particularly on incremental training and initial values of . In fact, we can determine a permutation of the Chebyshev steps systematically by emulating the training process. Figure 6 shows the learned step size parameters in DUGD (T = 11) with different initial values of and corresponding permuted Chebyshev steps. We found that they agreed with each other including the order of parameters. Further details are in Appendix E.

To understand the discrepancy between the Chebyshev steps and learned step sizes, we present the absolute eigenvalues of as a function of the eigenvalues of A in Figure 7. If the step size sequence of length T is given by , then the absolute eigenvalues of corresponding to the eigenvalue of A are written as . Figure 7 shows when is a learned step size parameter sequence (red) and Chebyshev steps (black) of length T = 6. To show the spectral density, symbols are located at each eigenvalue of matrix A. We found that of the learned step sizes were smaller than those of the Chebyshev steps in the high spectral-density regime and larger otherwise. This is because it reduced the MSE loss that all the eigenvalues of matrix A contributed. By contrast, it increased the maximum value of corresponding to the

Fig. 6. Zig-zag shape of the learned step size parameters (red) in DUGD and permuted Chebyshev steps (blue) with different initial values of (n, m) = (300, 1200) and T = 11.

Fig. 7. Absolute eigenvalues of using learned step size parameters (red) as a function of the eigenvalues of . Black symbols represent the corresponding absolute eigenvalues when the Chebyshev steps are used.

spectral radius . In this case, the spectral radius of DUGD was 0.074 whereas that of the Chebyshev steps was 0.029. Recalling that the spectral radius of the optimal constant step size was , DUGD accelerated the convergence speed in terms of the spectral radius whereas the Chebyshev steps further improved the convergence rate.

D. Performance analysis and convergence rate

Finally, we examined the convergence performance of DUGD and CHGD, and verified the convergence rate evaluated in Section III-C.

In the experiment, the MSE of DUGD was evaluated as a generalization error over random initial points. In DUGD, we first trained the step sizes with T = 15 and repeated them for every 15 iterations. Similarly, CHGD was executed repeatedly with the Chebyshev steps of length 15.

Figure 8 shows the MSE performance of DUGD, CHGD, and GD with the optimal constant step size when (n, m) =

Fig. 8. Comparison of the MSE performance of GD algorithms when ). Dotted lines represent the slopes of the convergence rate of CHGD (16) and GD

(300, 1200). We found that DUGD and CHGD converged faster than GD, which shows that a proper step size parameter sequence accelerated the convergence speed. Although DUGD had slightly better MSE performance than CHGD when t = 15, CHGD exhibited faster convergence as the number of iterations increased. This is because the spectral radius of CHGD was smaller than that of DUGD, as discussed in the last subsection. Figure 8 also shows the MSE calculated by (12) using the convergence rates. We found that the upper bound of the convergence rate (16) correctly predicted the convergence property of CHGD.

To summarize, we numerically verified the theoretical analyses in the last section, and found that the Chebyshev steps qualitatively reproduced a learned step size sequence in DUGD. This also indicates that deep unfolding can accelerate the GD algorithm by tuning its step size parameters.

V. APPLICATION OF CHEBYSHEV STEPS

In this section, we consider an application of CHGD instead of DUGD because CHGD requires no training process. After we compare CHGD with other accelerated GD algorithms, we demonstrate a practical application of CHGD to ridge regression.

A. Comparison with accelerated GD

We compared CHGD with two GD algorithms with a momentum term. One is the momentum method (MOM) whose recursive relation is given by

(18) where , and [30]. The other is the Chebyshev semi-iterative method (CH-semi) defined as

Fig. 9. MSE performance of CHGD (T =4, 8, 16) and other GD algorithms when

where , and [9]. These achieve the lower bound (17) of the convergence rate.

Figure 9 shows the MSE performance of CHGD (T = 4, 8, 16) and other GD algorithms. We found that CHGD improved its MSE performance as T increased. In particular, CHGD (T = 16) had reasonable performance compared with MOM and CH-semi. This indicates that CHGD is an accelerated GD algorithm without momentum terms.

B. Applications to ridge regression for real data

We demonstrate CHGD for ridge regression. Ridge regression, also known as Tikhonov regularization, is a fundamental biased estimation for ill-conditioned problems [13]. We consider a noisy linear observation with a measurement matrix . When , the LMS problem becomes ill-conditioned, which leads to numerical instability. Instead, ridge regression is often used, which is defined as

where is a regularization coefficient controlling weight of the estimate . As the parameter reduces the condition number of the matrix , a simple ridge estimator is available. However, it takes computation time to calculate a pseudo-inverse matrix. This computational cost increases if we search a proper by sweeping its value.

An alternative approach to solve (20) is to use a GD algorithm. Because it contains no inverse of the matrix, GD runs in time. The drawback of GD is its slow convergence when is relatively small. In this sense, using a GD algorithm with faster convergence is important.

To examine the convergence speed of GD in ridge regression, we performed the three algorithms: GD with the optimal constant step size, CHGD, and the momentum method (19).

Fig. 10. MSE performance of GD algorithms in ridge regression (of crime data. For CHGD, T was set to 32.

As an example, ridge regression was applied to Communities and Crime Dataset [31] in the UCI Machine Learning Repository [6]. After removing elements containing missing values, we have (n, m) = (98, 1994). The moment matrix had a huge condition number, , which indicates that the inverse problem is ill-conditioned. In the experiments, all the algorithms used the maximum and minimum values of the matrix A. Using the power method, we can estimate the maximum eigenvalue in time instead of computing eigenvalues directly in time. For the estimation of the minimum eigenvalue, the power method is also applicable to a shifted matrix .

Figure 10 shows the MSE performance between ridge estimation and estimates of the GD algorithms as a function of the iteration index t when . In CHGD, we set T = 32 and the order of the Chebyshev steps was properly permuted (see Appendix F). We found that the momentum method takes a small number of iteration steps to exhibit better MSE performance than GD, although its convergence speed was much faster for large t. Although the MSE of CHGD formed a wavy shape, the estimates at every T = 32 steps were reasonably accurate and converged quickly. We thus found that CHGD exhibited fast convergence compared with the other algorithms. CHGD requires no momentum terms and thus less computational resources, which would be advantageous for a high-dimensional problem. For example, CHGD will be useful to solve a linear equation involving a large sparse covariance matrix in Gaussian process [40].

VI. CONCLUDING REMARKS

In this paper, we studied a nontrivial learned step size sequence that appeared in DUGD. We proved that minimizing the MSE loss in DUGD reduced the spectral radius related to the convergence rate. Additionally, we introduced learning-free Chebyshev steps that minimized the the upper bound of the spectral radius. We showed that the Chebyshev steps accelerated the convergence speed compared with a naive GD, and the rate approached the strict lower bound of first-order methods in a specific limit. The numerical results supported the analyses and showed that the Chebyshev steps reproduced the learned step size sequence in DUGD, which provides a plausible interpretation of the learned parameters. Moreover, CHGD exhibited a reasonable convergence speed compared with other accelerated GD algorithms, although it did not require a momentum term.

There are several open problems. One is the extension of the analysis in this paper to convex and non-convex problems other than quadratic convex problems. Another is the application of the Chebyshev steps to other GD-based algorithms, such as stochastic GD. For example, the idea of the Chebyshev steps is successfully applicable to the fixed-point iteration [38] and Landweber algorithm [39].

ACKNOWLEDGEMENT

The authors warmly thank Mr. S. Khobahi for useful comments on the manuscript. This work was partly supported by JSPS Grant-in-Aid for Scientific Research (B) Grant Number 19H02138 (TW), JSPS Grant-in-Aid for Early-Career Scientists Grant Number 19K14613 (ST), and the Telecommunications Advancement Foundation (ST).

We describe the experimental setting for Figure 1 in the main text.

We consider the noiseless measurement , where the measurement matrix is the Gaussian random matrix whose elements are i.i.d. Gaussian random variables with zero mean and variance 1/n. We assume that (n, m) = (300, 600) and each element of follows the normal distribution. DUGD is defined by

where T is the total number of iterations (or layers) and are trainable step size parameters. The initial point is given by .

DUGD was implemented using PyTorch 1.3 [29]. Each training data were given by a pair consisting of the true solution and the corresponding measurement vector for a given H. The training process of DUGD was conducted using incremental training in which we gradually increased the number of layers (iterations T) by initializing the value of the parameters ) according to the learned values in the former training process (generation) to improve the performance of DUGD. At the beginning of the training process, all the initial values of were set to 0.3. In each generation, the parameters were optimized using Adam optimizer [19] with a learning rate of 0.002 to minimize the MSE loss function between the output of DUGD using and the true solution . As mini-batch training, 500 mini-batches of size 200 were used in each generation. The MSE was evaluated as a generalization error over random samples.

Proof. As the matrix A is a Hermitian matrix, it can be decomposed by using the unitary matrix U and diagonal matrix with eigenvalues of A. Then, we have

where is the diagonal matrix whose (i, i)-element is an eigenvalue of corresponding to the eigenvalue of A. In the last line, we use . Introducing the column vectors of U by , holds.

where is a positive constant because the probability density function of is assumed to be isotropic. Recalling that from Lemma 3.1, we have , which is identical to (8).

The proof indicates that the constant C is explicitly given by with . In the special case in which each element of is an i.i.d. random variable, C can be easily calculated. This fact is used in the numerical experiment in Section 4.2. In this case, we have because each element of follows the Gaussian distribution with unit mean and unit variance.

Before we provide the proof of Theorem 3.4, we prove the following lemma related to the minimax property of Chebyshev polynomials. The Chebyshev polynomial of degree n (n = 0, 1, . . . ) is defined as a recursive relation with and . Let C[a, b] (a < b) be the Banach space defined as -norm, i.e., .

Lemma C.1. Suppose that b > a > 0. Let be a subspace of polynomials of z on [a, b] represented by for any . We define the Chebyshev steps of length n as

and a normalized Chebyshev polynomial of degree n as

Then, the following statements hold.

(a) The function belongs to D as a result of setting ).

(b) The function is a polynomial in D that minimizes the norm .

Proof. (a) The Chebyshev polynomial of degree n has n zeros in , which are given by ) [24, Section 2.2]; that is, holds. Then, using the affine trans- formation from [a, b] to , we have

Because , we have , which indicates that the statement holds.

(b) We show that is a minimizer of among functions in D by indirect proof. Assume that there exists of at most degree n except for satisfying . As ) are the extreme points in (including both edge points) of [24, Section 2.2], are those of . Particularly, the sign of the extremal value at (or ) changes alternatively; , and so on (or , and so on when ) hold [24, Lemma 3.6]. The assumption indicates that n + 1 inequalities, , , and so on hold; that is, a polynomial of degree at most n has n zeros in [a, b].

However, because , the constant term of is equal to zero, which suggests that has at most zeros in [a, b]. This results in a contradiction of the assumption and shows that minimizes the norm in D.

It is straightforward to prove Theorem 3.4 from this lemma.

proof of Theorem 3.4. Using the notation of Lemma C.1, we notice that , and

From Lemma C.1, the Chebyshev steps of length T form a sequence that minimizes .

Proof. To simplify the notation, we use as a condition number of the matrix A. From (10) and Lemma C.1, we have

We use the properties that holds for and holds for |x| > 1, and the identity when .

By contrast, the spectral radius when the optimal constant step size is used can be calculated directly. We have

Finally, we show that holds. This is equivalent to the following relation for :

If we set , the (2t)th coefficient of (X + is given by. Additionally, its coefficients of odd orders are equal to zero. From the Vandermonde identity:

Fig. 11. Dynamics of step size parameters (n, m) = (300, 1200). Horizontal line represents the number of mini batches in incremental training. All the initial values were set to 0.3. In incremental training, the number of learning parameters increased by one for every 2000 mini batches fed to DUGD. For example, only (black) was trained during the first 2000 mini batches and (orange) were trained during the next 2000 mini batches.

(equality holds only when t = 0, T), which indicates that (30) holds.

We thus prove that when .

In this subsection, we describe how to determine a permutation of the Chebyshev steps that reproduces a zig-zag pattern of the learned step size parameters of DUGD. A key observation is the dynamics of trainable step size parameters in the training process.

Figure 11 shows the dynamics of the trainable step size parameters. During incremental training, the number of trainable parameters increases at every 2000 mini batches; that is, DUGD of T iterations (or layers) is trained from the th mini batches to the 2000Tth mini batches, which we call the Tth generation of incremental training. After the Tth generation ends, we add an initialized parameter to the learned parameters to start a new generation. As we can see in Figure 11, the trainable parameters immediately move toward a (sub)optimal point to reduce the MSE loss function, which forms a staircase shape of . Although there are T! optimal points of step sizes by permutation symmetry, it is numerically suggested that DUGD chooses an optimal point so that the “distance” (discussed later) from the former learned parameters is minimized. This seems natural because these parameters are updated by a GD-based optimizer and the convergent point depends on the initial point.

From these observations, we attempt to emulate the order of the learned step size parameters using the Chebyshev steps. We consider a training process of DUGD that minimizes the spectral radius instead of the MSE loss function.

Although it seems practically difficult, we assume that we obtain the Chebyshev steps as an approximate solution. The problem is which order of the Chebyshev steps is chosen at each generation. We thus determine an order of the Chebyshev steps that minimizes the “distance” from a given initial point to a point whose elements are permuted Chebyshev steps. As a measure of distance, we use a simple Euclidean norm because an actual distance defined by an energy landscape is difficult to calculate. The details of the algorithm are shown in Algorithm 1. To emulate incremental training, the length of the Chebyshev steps is gradually increased. As an initial point () of length are set to the optimally permuted Chebyshev steps in the last generation and is set to a given initial value. Then, an optimal permutation of the Chebyshev steps of length t + 1 is searched so that its distance from the initial point takes the minimum value. The point is used as an initial point of the next generations. As shown in Figure 6, this successfully reproduces the zig-zag shape of learned step size parameters that depends on an initial value of .

APPENDIX F ORDER OPTIMIZATION OF THE CHEBYSHEV STEPS

The order of the Chebyshev steps is important practically to ensure numerical stability. Figure 12 shows the MSE performance of CHGD with different orders of the Chebyshev steps. We found that using an ascending order led to a search point with huge values that might cause a digit loss. To avoid this instability, we need to permute the step size parameter sequence. It is noted that the performance of CHGD itself is ensured every T iterations if numerical errors are ignorant. Because the total number of permutations rapidly diverges depending on T, we focus on permutations defined by

Fig. 12. MSE performance of CHGD (T = 16) with optimal permutation (red), ascending order (orange), and descending order (blue) when (n, m) = (500, 800). They have the same MSE every T = 16 iterations.

where is an initial index. Then, the sequence is a permutation of 1} if b is odd, (mod 4), and (). We then search parameters a, b, c that minimizes the maximum temporal spectral radius of , that is,

(34) Algorithm 2 shows the pseudocode of the searching algorithm. Figure 12 shows the MSE performance of CHGD (T = 16) with and without permutation when n = 500 and m = 800. The MSE is evaluated using 200 samples. In this case, the asymptotic value of the condition number was and the optimal parameters are given by (a, b, c) = (1, 9, 7). In CHGD without permutation, the step sizes was given by (24) in a descending or ascending manner. Particularly, GD with ascending Chebyshev steps had a relatively large MSE. The numerical results show that CHGD with optimal permutation decreased the MSE effectively. An example of (a, b, c) for different , and is given in Table I. We found that the optimal choice of (a, b, c) depended on and . In Section 5.2, the Chebyshev steps were permuted according to (a, b, c) = (1, 11, 10).

TABLE I SEARCHED PERMUTATION PARAMETERS HEBYSHEV STEPS WHEN

REFERENCES

[1] P. Ablin, T. Moreau, M. Massias, and A. Gramfort. Learning step sizes for unfolded sparse coding. In Advances in Neural Information Processing Systems 32, pages 13100–13110. Curran Associates, Inc., 2019.

[2] D. P. Bertsekas. Nonlinear Programming. Athena Scientific, 1995.

[3] M. Borgerding, P. Schniter, and S. Rangan. Amp-inspired deep networks for sparse linear inverse problems. IEEE Transactions on Signal Processing, 65(16):4293–4308, 2017.

[4] A. Cauchy. Méthode générale pour la résolution des systemes d’équations simultanées. Comp. Rend. Sci. Paris, 25(1847):536–538, 1847.

[5] X. Chen, J. Liu, Z. Wang, and W. Yin. Theoretical linear convergence of unfolded ISTA and its practical weights and thresholds. In Advances in Neural Information Processing Systems, pages 9061–9071, 2018.

[6] D. Dua and C. Graff. UCI machine learning repository, 2017.

[7] R. Fletcher. Practical methods of optimization. John Wiley & Sons, 2013.

[8] G. E. Forsythe. On the asymptotic directions of thes-dimensional optimum gradient method. Numerische Mathematik, 11(1):57–76, 1968.

[9] G. H. Golub and M. D. Kent. Estimates of Eigenvalues for Iterative Methods. Mathematics of Computation, 53(188):619, 1989.

[10] K. Gregor and Y. LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pages 399–406. Omnipress, 2010.

[11] H. He, C.-K. Wen, S. Jin, and G. Y. Li. A model-driven deep learning network for mimo detection. In 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 584–588. IEEE, 2018.

[12] J. R. Hershey, J. L. Roux, and F. Weninger. Deep unfolding: Model-based inspiration of novel deep architectures. arXiv preprint arXiv:1409.2574, 2014.

[13] A. E. Hoerl and R. W. Kennard. Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1):55–67, 1970.

[14] L. Hogben. Handbook of linear algebra. Chapman and Hall/CRC, 2013.

[15] D. Ito, S. Takabe, and T. Wadayama. Trainable ISTA for sparse signal recovery. IEEE Transactions on Signal Processing, 67(12):3113–3125, 2019.

[16] K. H. Jin, M. T. McCann, E. Froustey, and M. Unser. Deep convolutional neural network for inverse problems in imaging. IEEE Transactions on Image Processing, 26(9):4509–4522, 2017.

[17] U. S. Kamilov and H. Mansour. Learning optimal nonlinearities for iterative thresholding algorithms. IEEE Signal Processing Letters, 23(5):747–751, 2016.

[18] M. Kellman, E. Bostan, N. Repina, and L. Waller. Physics-based learned design: Optimized coded-illumination for quantitative phase imaging. IEEE Transactions on Computational Imaging, 2019.

[19] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.

[20] L. Lessard, B. Recht, and A. Packard. Analysis and design of opti- mization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57–95, 2016.

[21] J. Liu, X. Chen, Z. Wang, and W. Yin. ALISTA: Analytic weights are as good as learned weights in LISTA. In International Conference on Learning Representations, 2019.

[22] M. Mardani, Q. Sun, D. Donoho, V. Papyan, H. Monajemi, S. Vasanawala, and J. Pauly. Neural proximal gradient descent for compressive imaging. In Advances in Neural Information Processing Systems, pages 9573–9583, 2018.

[23] M. Mardani, Q. Sun, V. Papyan, S. Vasanawala, J. Pauly, and D. Donoho. Degrees of freedom analysis of unrolled neural networks. arXiv preprint arXiv:1906.03742, 2019.

[24] J. C. Mason and D. C. Handscomb. Chebyshev polynomials. Chapman and Hall/CRC, 2002.

[25] C. Metzler, A. Mousavi, and R. Baraniuk. Learned d-amp: Principled neural network based compressive image recovery. In Advances in Neural Information Processing Systems, pages 1772–1783, 2017.

[26] V. Monga, Y. Li, and Y. C. Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. arXiv preprint arXiv:1912.10557, 2019.

[27] E. Nachmani, Y. Be’ery, and D. Burshtein. Learning to decode linear codes using deep learning. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 341– 346. IEEE, 2016.

[28] Y. Nesterov. Introductory lectures on convex programming volume i: Basic course. Lecture notes, 3(4):5, 1998.

[29] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, highperformance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024– 8035. Curran Associates, Inc., 2019.

[30] B. T. Polyak. Some methods of speeding up the convergence of iter- ation methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964.

[31] M. Redmond and A. Baveja. A data-driven software tool for enabling cooperative information sharing among police departments. European Journal of Operational Research, 141(3):660–678, 2002.

[32] D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning representations by back-propagating errors. Nature, 323(6088):533– 536, Oct 1986.

[33] N. Samuel, T. Diskin, and A. Wiesel. Deep mimo detection. In 2017 IEEE 18th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pages 1–5. IEEE, 2017.

[34] W. Shi, F. Jiang, S. Zhang, and D. Zhao. Deep networks for compressed image sensing. In 2017 IEEE International Conference on Multimedia and Expo (ICME), pages 877–882. IEEE, 2017.

[35] P. Sprechmann, A. M. Bronstein, and G. Sapiro. Learning efficient sparse and low rank models. IEEE transactions on pattern analysis and machine intelligence, 37(9):1821–1833, 2015.

[36] S. Takabe, M. Imanishi, T. Wadayama, R. Hayakawa, and K. Hayashi. Trainable projected gradient detector for massive overloaded mimo channels: Data-driven tuning approach. IEEE Access, 7:93326–93338, 2019.

[37] T. Wadayama and S. Takabe. Deep learning-aided trainable projected gradient decoding for LDPC codes. In IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, July 7-12, 2019, pages 2444–2448, 2019.

[38] T. Wadayama and S. Takabe. Chebyshev inertial iteration for acceler- ating fixed-point iterations. arXiv preprint arXiv:2001.03280, 2020.

[39] T. Wadayama and S. Takabe. Chebyshev inertial landweber algorithm for linear inverse problems. arXiv preprint arXiv:2001.06126, 2020.

[40] C. K. Williams and C. E. Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.

[41] S. Wu, A. Dimakis, S. Sanghavi, F. Yu, D. Holtmann-Rice, D. Storcheus, A. Rostamizadeh, and S. Kumar. Learning a compressed sensing measurement matrix via gradient unrolling. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6828–6839, Long Beach, California, USA, 09–15 Jun 2019. PMLR.

[42] B. Xin, Y. Wang, W. Gao, D. Wipf, and B. Wang. Maximal sparsity with deep networks? In Advances in Neural Information Processing Systems, pages 4340–4348, 2016.

[43] M. Yao, J. Dang, Z. Zhang, and L. Wu. SURE-TISTA: A signal recovery network for compressed sensing. In ICASSP 2019-2019 IEEE

International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3832–3836. IEEE, 2019.

[44] J. Zhang and B. Ghanem. ISTA-net: Interpretable optimization-inspired deep network for image compressive sensing. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1828–1837, 2018.