Title: GRADIENT-FREE NEURAL NETWORK TRAINING BY MULTI-CONVEX ALTERNATING OPTIMIZATION

Abstract: In recent years, stochastic gradient descent (SGD) and its variants have been the dominant optimization methods for training deep neural networks. However, SGD suffers from limitations such as the lack of theoretical guarantees, vanishing gradients, excessive sensitivity to input, and difficulties solving highly non-smooth constraints and functions. To overcome these drawbacks, alternating minimizationbased methods for deep neural network optimization have attracted fast-increasing attention recently. As an emerging and open domain, however, several new challenges need to be addressed, including 1) Convergence depending on the choice of hyperparameters, and 2) Lack of unified theoretical frameworks with general conditions. We, therefore, propose a novel Deep Learning Alternating Minimization (DLAM) algorithm to deal with these two challenges. Our innovative inequality-constrained formulation infinitely approximates the original problem with non-convex equality constraints, enabling our proof of global convergence of the DLAM algorithm under mild, practical conditions, regardless of the choice of hyperparameters and wide range of various activation functions. Experiments on benchmark datasets demonstrate the effectiveness of DLAM.

1. INTRODUCTION:

Stochastic gradient descent (SGD) and its variants have become popular optimization methods for training deep neural networks. These methods split a dataset into multiple batches and then optimize them sequentially by gradient descent in each epoch. SGD has two main advantages: not only is it simple to implement, but it can also be applied in online settings where new coming training data are used to train models. However, while many researchers have provided solid theoretical guarantees on the convergence of SGD (Kingma & Ba (2014) ; Reddi et al. (2018) ; Sutskever et al. (2013) ), the assumptions of their proofs cannot be applied to problems involving deep neural networks, which are highly nonsmooth and nonconvex. Aside from the lack of theoretical guarantees, several additional drawbacks restrict the applications of SGD. It suffers from the gradient vanishing problem, meaning that the error signal diminishes as the gradient is backpropagated, which prevents the neural networks from utilizing further training (Taylor et al. (2016) ), and the gradient of the activation function is highly sensitive to the input (i.e. poor conditioning), so a small change in the input can lead to a dramatic change in the gradient.

To tackle these intrinsic drawbacks of gradient descent optimization methods, alternating minimization methods have started to attract attention as a potential way to solve deep learning problems. Here, the loss function of a deep neural network is reformulated as a nested function associated with multiple linear and nonlinear transformations across multi-layers. This nested structure is then decomposed into a series of linear and nonlinear equality constraints by introducing auxiliary variables and penalty hyperparameters. The linear and nonlinear equality constraints generate multiple subproblems, which can be minimized alternately. Some recent alternating minimization methods have focused on applying the Alternating Direction Method of Multipliers (ADMM) (Taylor et al. (2016) ; Wang et al. (2019) ) and Block Coordinate Descent (BCD) (Jinshan Zeng (2018)), with empirical evaluations demonstrating good scalability in terms of the number of layers and high accuracy on the test sets, especially for neural networks that are very deep, thanks to parallelism (Taylor et al. (2016) ; Wang et al. (2019) ). For more information, please refer to Section H in the supplementary materials. These methods also avoid gradient vanishing problems and allow for non-differentiable activation functions such as binarized neural networks (Courbariaux et al. (2015) ), as well as allowing for complex nonsmooth regularization and the constraints that are increasingly important for deep neural architectures that are required to satisfy practical requirements such as interpretability, energy-efficiency, and cost awareness Carreira-Perpinan & Wang (2014) . The weight vector in the l-th layer. b l

The intercept in the l-th layer. z l

The temporary variable of the linear mapping in the l-th layer. h l (z l )

The nonlinear activation function in the l-th layer. a l

The output of the l-th layer. x

The input matrix of the neural network. y

The predefined label vector. R(z l , y)

The risk function in the l-th layer.

Ω l (W l )

The regularization term in the l-th layer. ε l

The tolerance of the nonlinear mapping in the l-th layer. 2019)). Therefore, there lacks a unified theoretical framework which covers wide range of commonly used losses and activation functions.

In order to simultaneously address these technical problems, we propose a new formulation of the deep neural network problem, along with a novel Deep Learning Alternating Minimization (DLAM) algorithm. The proposed framework is highly generic and sufficiently flexible to be utilized in common fully-connected deep neural network models, as well as being easily extendable to other models such as convolutional neural networks (Krizhevsky et al. (2012) ) and recurrent neural networks (Mikolov et al. (2010) ). Specifically, we, for the first time, transform the original deep neural network optimization problem into an inequality-constrained problem that can be infinitely approximate to the original one. Applying this innovation to an inequality-constraint based transformation ensures the convexity of all subproblems, and hence easily ensures global minima, the inequality-constraint prevents the output of a nonlinear function from changing much and reduces sensitivity to the input. The operation of matrix inversion is avoided by the quadratic approximation technique and a backtracking algorithm. Moreover, while existing methods require typically strict and complex conditions, such as Kurdyka-ojasiewicz (KL) properties (Lau et al. (2018) ) to prove convergence, our proposed method requires simple and mild conditions to guarantee convergence and covers most of the commonly-used loss functions and activation functions, and the choice of hyperparameters has no effect on the convergence of our DLAM algorithm theoretically. Our contributions include: Experiments on two benchmark datasets show that the new algorithm performs well compared with SGD or its variants and ADMM. The rest of paper is organized as follows. In Section 2, we present the problem formulation and the new DLAM algorithm. In Section 3, we introduce the main convergence results for the DLAM algorithm. Section 4 reports the results of the extensive experiments conducted to validate the convergence and effectiveness of the new DLAM. Section 5 concludes by summarizing the research.

2. THE DLAM ALGORITHM:

In this section, we present our novel DLAM algorithm. Section 2.1 provides the new algorithm's formulation and Section 2.2 shows how the DLAM algorithm solve all the subproblems.

2.1. INEQUALITY APPROXIMATION FOR DEEP LEARNING:

The important notations used in this paper are listed in Table 1 . A typical fully-connected deep neural network consists of L layers, each of which are defined by a linear mapping and a nonlinear activation function. A linear mapping is composed of a weight vector W l ∈ R n l ×n l-1 , where n l is the number of neurons on the l-th layer and an intercept b l ∈ R n l ; a nonlinear mapping is defined by an activation function h l (•). Given an input a l-1 ∈ R n l-1 from the (l -1)-th layer, the l-th layer outputs a l = h l (W l a l-1 + b l ). By introducing an auxiliary variable z l as the temporary result of the linear mapping, the deep neural network problem is formulated mathematically as follows:

Problem 1:

min a l ,W l ,b l ,z l R(z L ; y) + L l=1 Ω l (W l ) s.t. z l = W l a l-1 +b l (l = 1,• • •,L), a l = h l (z l )(l = 1, • • • , L-1)

where a 0 = x ∈ R d is the input of the deep neural network, d is the number of feature dimensions, and y is a predefined label vector. R(z L ; y) ≥ 0 is the risk function for the L-th layer, which is convex and proper, and Ω l (W l ) ≥ 0 is a regularization term on the l-th layer, which is also convex and proper. The equality constraint a l = h l (z l ) is the most challenging to handle here, because common activation functions such as tanh and smooth sigmoid are nonlinear. This makes them nonconvex constraints and hence it is difficult to obtain a global minimum when updating z l (Taylor et al. (2016) ).

To deal with this challenge, we innovatively transform the original nonconvex constraints into convex inequality constraints, which can be infinitely approximate to Problem 1. To do this, we introduce a tolerance ε l > 0 and reformulate Problem 1 to reach the following form:

min W l ,b l ,z l ,a l R(z L ; y)+ L l=1 Ω l (W l )+ L-1 l=1 I(h l (z l )-ε l ≤ a l ≤ h l (z l )+ε l ) s.t.z l = W l a l-1 + b l (l = 1,• • •,L) I(h l (z l ) -ε l ≤ a l ≤ h l (z l ) + ε l ) is an indicator function such that the value is 0 if h l (z l ) -ε l ≤ a l ≤ h l (z l ) + ε l and ∞ otherwise.

For the linear constraint z l = W l a l-1 +b l , this can be transformed into a penalty term in the objective function to minimize the difference between z l and W l a l-1 +b l .

The formulation is shown as follows:

Problem 2: min W l ,b l ,z l ,a l F (W, b, z, a) = R(z L ; y)+ L l=1 Ω l (W l ) + L l=1 φ(a l-1 ,W l ,b l ,z l )+ L-1 l=1 I(h l (z l )-ε l ≤ a l ≤ h l (z l )+ε l ) The penalty term is defined as φ(a l-1 , W l , b l , z l ) = (ρ/2) z l -W l a l-1 -b l 2 2 , where ρ > 0 a penalty parameter. W = {W l } L l=1 , b = {b l } L l=1 , z = {z l } L l=1 ,a = {a l } L-1 l=1 .

The reason for introducing ε l is that it allows us to project the nonlinear constraint to a convex ε l -ball, thus transforming the nonconvex Problem 1 into the multi-convex Problem 2, which is much easier to solve. Here, a multi-convex problem means this problem is convex with regard to one variable while fixing others. For example, Problem 2 is convex with regard to z when W, b, and a are fixed. As ρ → ∞ and ε l → 0, Problem 2 approaches Problem 1.

2.2. ALTERNATING OPTIMIZATION:

We present DLAM algorithm developed to solve Problem 2, shown in Algorithm 1. Lines 4, 5, 7, and 10 update W l , b l ,z l and a l , respectively, and the four relevant subproblems are discussed as below:

1. Update W l The variables W l (l = 1, • • • , L) are updated as follows:

EQUATION

Because W l and a l-1 are coupled in φ(•), solving W l requires an inversion operation of a k+1 l-1 , which is computationally expensive. Motivated by deep learning Alternating Direction Method of Multipliers (dlADMM) (Wang et al. (2019) ), we define P k+1 l (W l ; θ k+1 l ) as a quadratic approximation of φ at W k l , which is mathematically reformulated as follows (Beck & Teboulle (2009) ):

P k+1 l (W l ;θ k+1 l ) = φ(a k+1 l-1 ,W k l ,z k l ,b k l )+ < ∇ W k l φ,W l -W k l > + θ k+1 l • (W l -W k l ) •2

1 /2 where θ k+1 l > 0 is a parameter vector, • denotes Hadamard product (the elementwise product), and a •b denotes a to the Hadamard power of b and

• 1 is the 1 norm. < •, • > is a Frobenius inner product.∇ W k l φ = ρ(W k l a k+1 l-1 + b k l -z k l )(a k+1 l-1 ) T (l = 1, • • • , L) is the gradient of φ with regard to W l at W k l . Obviously, P k+1 l (W k l ; θ k+1 l ) = φ(a k+1 l-1 , W k l , b k l , z k l ).

Rather than minimizing the Algorithm 1 DLAM Algorithm for Solving Problem 2

Require: y, a0 = x. Ensure:

a l , W l , b l , z l (l = 1, • • • , L).

1: Initialize ρ, k = 0. 2: repeat 3: for l = 1 to L do 4:

Update W k+1 l using Algorithm 2.

5::

Update b k+1 l in equation 3.

6::

if l = L then 7:

Update z k+1 l in equation 5.

8::

else 9:

Update z k+1 l in equation 4.

10::

Update a k+1 l using Algorithm 3.

11:

end if 12: end for 13: k ← k + 1. 14: until convergence. 15: Output a l , W l , b l , z l .

original subproblem in equation 1, we instead minimize the following: 

W k+1 l ← arg min W l P k+1 l (W l ; θ k+1 l ) + Ω l (W l ) (2) For Ω l (W l ),

2.. Update b l:

The variables b l (l = 1, • • • , L) are updated as follows:

b k+1 l ← arg min b l φ(a k+1 l-1 , W k+1 l , b l , z k l ).

Similarly to updating W l , we define U k+1 l (b l ; L b ) as a quadratic approximation of φ at b k l , which is formulated mathematically as follows (Beck & Teboulle (2009) ):

U k+1 l (b l ; L b ) = φ(a k+1 l-1 , W k+1 l , b k l , z k l ) + (∇ b k l φ) T (b l -b k l ) + (L b /2) b l -b k l 2 2 . where L b ≥ ρ is a parameter and ∇ b k l φ = ρ(b k l + W k+1 l a k+1 l-1 -z k l ).

Here, L b ≥ ρ is required for the convergence analysis (Beck & Teboulle (2009) ). Without loss of generality, we set L b = ρ. We can now solve the following subproblem:

EQUATION

The solution to equation 3 is:

b k+1 l ← b k l -∇ b k l φ/ρ.

3.. Update z l:

The variables z l (l = 1, • • • , L) are updated as follows:

z k+1 l ← arg min z l φ(a k+1 l-1 , W k+1 l , b k+1 l , z l )+I(h l (z l )-ε l ≤ a k l ≤ h l (z l )+ε l )(l < L) z k+1 L ← arg min z L φ(a k+1 L-1 , W k+1 L , b k+1 L , z L ) + R(z L ; y)

As when updating b l , we define V k+1 l (z l ; L z ) as a quadratic approximation of φ at z k l , which is formulated mathematically as follows:

V k+1 l (z l ;L z ) = φ(a k+1 l-1 , W k+1 l , b k+1 l , z k l )+(∇ z k l φ) T (z l -z k l )+(L z /2) z l -z k l 2 2

where L z ≥ ρ is a parameter and

∇ z k l φ = ρ(z k l -W k+1 l a k+1 l-1 -b k+1 l

). Without loss of generality, we

set L z = ρ. Obviously, V k+1 l (z k l ; ρ) = φ(a k+1 l-1 , W k+1 l , b k+1 l , z k l )

. Hence, we solve the problems:

EQUATION

2

).

where B k+1 1 and B k+1 2 represent the lower bound and the upper bound of the set {z l |h l (z l )-ε l ≤ a k l ≤ h l (z l )+ε l }. equation 5 is easy to solve using the Fast Iterative Soft Thresholding Algorithm (FISTA) (Beck & Teboulle (2009) ).

4.. Update a l:

The variables a l (l = 1, • • • , L -1) are updated as follows:

a k+1 l ← arg min a l φ(a l , W k l+1 , b k l+1 , z k l+1 ) + I(h l (z k+1 l ) -ε l ≤ a l ≤ h l (z k+1 l ) + ε l )

As when solving W k+1 l , the quadratic approximation of φ at a k l is defined as

Q k+1 l (a l ;τ k+1 l ) = φ(a k l ,W k l+1 ,b k l+1 ,z k l+1 )+(∇ a k l φ) T (a l -a k l ) + τ k+1 l • (a l -a k l ) •2

1 /2 and this allows us to solve the following problem instead:

EQUATION

where 

τ k+1 l > 0 is a parameter vector. ∇ a k l φ = ρ(W k l+1 ) T (W k l+1 a k l +b k l+1 -z k l+1 )(l = 1, • • • , L-1) is the gradient of φ with regard to a l at a k l . Obviously, Q k+1 l (a k l ; τ k+1 l ) = φ(a k l , W k l+1 , b k l+1 , z k l+1 ). Because Q k+1 l (a l ; τ k+1

k l , W k l+1 , z k+1 l , z k l+1 , b k l+1 , ρ, some constant η > 1. Ensure: τ k+1 l ,a k+1 l . 1: Pick up t such that β = a k l -∇ a k l φ/t and h l (z k+1 l ) -ε l ≤ β ≤ h l (z k+1 l ) + ε l . 2: while φ(β, W k l+1 , z k l+1 , b k l+1 ) > Q k+1 l (β; t) do 3: t ← tη. 4: β ← a k l -∇φ a k l /t.

5: end while 6: Output τ k+1 l ← t.

7: Output a k+1 l ← β.

3. CONVERGENCE ANALYSIS:

In this section, we present the main convergence analyses for the DLAM algorithm. Specifically, Section 3.1 introduces the assumption necessary to guarantee convergence. The main convergence properties of the new DLAM algorithm are presented in Section 3.2. Due to space limit, the discussion on the convergence conditions of the DLAM algorithm is in Section G in the supplementary materials.

3.1. ASSUMPTION:

Firstly, we make the following assumption: Assumption 1 (Quasilinearity). Activation functions h l (z l )(l = 1, • • • , n) are quasilinear functions.

The definition of Quasilinearity is given in the supplementary material. Assumption 1 is a mild condition to ensure that the nonlinear constraint a l = h l (z l ) in Problem 1 is projected in a convex set, and it allows for nonsmooth functions. Fortunately, most of the widely used nonlinear activation functions, including tanh (Zamanlooy & Mirhassani (2014) ), smooth sigmoid (Glorot & Bengio (2010) ), and the rectified linear unit (Relu) (Maas et al. ( 2013)) that are quasilinear. Notice that no assumption is needed to imposed on the risk function R(z L ; y) and the regularization term Ω l (W l ). Therefore, they can be either smooth or nonsmooth: R(z L ; y) can be a common least square loss or cross entropy loss; Ω l (W l ) can be a either 1 or 2 regularization term. They fit neatly into our framework and incorporate several important theoretical properties.

3.2. KEY CONVERGENCE PROPERTIES:

We introduce several important convergence properties possessed by the DLAM algorithm in this section. If Assumption 1 holds, then Lemmas 1-3 stated below are satisfied. These three lemmas are proven to be possessed by the DLAM algorithm, and are key for demonstrating the theoretical merits of DLAM; the proofs of them are provided in the supplementary materials. Finally, the global convergence and convergence rate of the DLAM are proved based on Lemmas 1-3 stated as follows:

Lemma 1 (Sufficient Descent). For any ρ > 0 and ε l > 0, we have

F (W k , b k , z k , a k ) -F (W k+1 , b k+1 , z k+1 , a k+1 ) ≥ L l=1 θ k+1 l • (W k+1 l -W k l ) •2 1 /2+ (ρ/2) L l=1 b k+1 l -b k l 2 2 +(ρ/2) L l=1 z k+1 l -z k l 2 2 + L-1 l=1 τ k+1 l • (a k+1 l -a k l ) •2 1 /2 (7)

Lemma 1 depicts the monotonic decrease of the objective value during iterations. The proof of Lemma 1 requires Assumption 1 and is detailed in the supplementary materials.

Lemma 2 (Convergent Sequence). (a). (W k , b k , z k , a k ) and F(W k , b k , z k , a k ) are convergent. That is, as k → ∞, (W k , b k , z k , a k ) → (W * , b * , z * , a * ) and F(W k , b k , z k , a k ) → F(W * , b * , z * , a * ). (b). (W k , b k , z k , a k ) is bounded. That is, there exist scalars M W ,M b ,M z and M a such that W k ≤ M W , b k ≤ M b , z k ≤ M z and a k ≤ M a .

Lemma 2 guarantees that the variable (W k , b k , z k , a k ) is convergent and bounded. The proof of Lemma 2 requires Lemma 1 and can be found in the supplementary materials.

Lemma 3 (Subgradient Bound). There exist C = max(ρM a , ρM

2 a + θ k+1 1 , ρM 2 a + θ k+1 2 , • • • , ρM 2 a + θ k+1 L ), some g k+1 1 ∈ ∂ W k+1 F and g k+1 2 = ∇ b k+1 F such that g k+1 1 ≤ C( W k+1 -W k + b k+1 -b k + z k+1 -z k ), g k+1 2 = ρ z k+1 -z k

Lemma 3 ensures that the subgradient of the objective function is bounded by variables. The proof of Lemma 3 requires Lemma 2 and the proof process is elaborated in the supplementary materials. We will now move on to present the global convergence of the DLAM algorithm using the following two theorems. The first theorem presents the global convergence of the DLAM algorithm.

Theorem 1 (Convergence to the Critical Point). For (W, b) in Problem 2, starting from any

(W 0 , b 0 ) , Algorithm 1 converges to a critical point (W * , b * ). That is, 0 ∈ ∂ W * F and 0 ∈ ∂ b * F . Proof. By Lemma 2, (W k , b k ) is convergent to (W * , b * ). From Lemma 3, there exist g k+1 1 ∈ ∂ W k+1 F and g k+1 2 ∈ ∂ b k+1 F such that g k+1 1 → 0 and g k+1 2 → 0 as k → ∞. we have 0 ∈ ∂ W * F and 0 ∈ ∂ b * F . In other words, (W * , b * ) is a critical point of F .

Theorem 1 shows that our proposed DLAM algorithm converges to a critical point globally no matter what ρ and ε l are chosen. This ensures that our DLAM algorithm is parameter-restriction free, so the choice of hyperparameters has no effect on its convergence. The next theorem shows that the convergence rate of DLAM is o(1/k), which is shown as follows:

Theorem 2 (Convergence Rate). For (W k , b k , z k , a k ), define c k = min 0≤i≤k ( L l=1 θ i+1 l • (W i+1 l - W i l ) •2 1 /2 +(ρ/2) L l=1 b i+1 l -b i l 2 2 +(ρ/2) L l=1 z i+1 l -z i l 2 2 + L-1 l=1 τ i+1 l • (a i+1 l -a i l ) •2 1 /2), which reflects the convergence rate of Algorithm 1, then the convergence rate of c k is o(1/k).

Proof. The proof of this theorem is in the supplementary materials.

4. EXPERIMENTS:

The DLAM algorithm is evaluated by several benchmark datasets. Effectiveness, efficiency and convergence properties of DLAM are compared with state-of-the-art methods. All experiments were conducted on 64-bit Ubuntu16.04 LTS with Intel(R) Xeon processor and GTX1080Ti GPU. and Fashion MNIST (Xiao et al. (2017) ). The MNIST dataset has ten classes of handwritten-digit images, which was firstly introduced by Lecun et al. in 1998 (LeCun et al. (1998) ). It contains 55,000 training samples and 10,000 test samples with 196 features each, which is provided by the Keras library (Chollet (2017) ). Unlike the MNIST dataset, the Fashion MNIST dataset has ten classes of assortment images on the website of Zalando, which is Europes largest online fashion platform (Xiao et al. (2017) ). The Fashion-MNIST dataset consists of 60,000 training samples and 10,000 test samples with 784 features each.

4.1.2. EXPERIMENT SETTINGS:

We set up two different architectures of multi-layer neural networks in the experiment. Two network structures contained two hidden layers with 100 and 500 hidden units each, respectively. The rectified linear unit (Relu) was used for the activation function for both network structures. The loss function was set as the deterministic cross-entropy loss. ρ was set to 10 -4 . ε was initialized as 10 and updated adaptively as follows: if R(z k L ; y) > 10ε k , ε k+1 = max(2ε k , 1); if ε k > 10R(z k L ; y), ε k+1 = min(ε k /2, 0.01), which balances between the loss function R(z L ; y) and ε. The number of iteration was set to 150. In the experiment, one iteration means one epoch.

4.1.3. COMPARISON METHODS:

Since this paper focuses on fully-connected deep neural networks, SGD and its variants and ADMM are state-of-the-art methods and hence were served as comparison methods. For SGD-based methods, the full batch dataset is used for training models. All parameters were chosen by the accuracy of the training dataset. The baselines are: 1) Stochastic Gradient Descent (SGD) (Bottou (2010) ). The SGD and its variants are the most popular deep learning optimizers, whose convergence has been studied extensively in the literature. 2) Adaptive gradient algorithm (Adagrad) (Duchi et al. (2011) ). Adagrad is an improved version of SGD: rather than fixing the learning rate during iteration, it adapts the learning rate to the hyperparameter. 3) Adaptive learning rate method (Adadelta) (Zeiler ( 2012)). As an improved version of the Adagrad, the Adadelta is proposed to overcome the sensitivity to hyperparameter selection. 4) Alternating Direction Method of Multipliers (ADMM) (Taylor et al. (2016) ). ADMM is a powerful convex optimization method because it can split an objective function into a series of subproblems, which are coordinated to get global solutions. It is scalable to large-scale datasets and supports parallel computations.

4.2. EXPERIMENTAL RESULTS:

In this section, experimental results of DLAM algorithm are analyzed against comparison methods.

4.2.1. CONVERGENCE:

First, we show that our proposed DLAM algorithm converges for both the MNIST dataset and the Fashion MNIST dataset. The convergence of DLAM algorithm is shown in Figure 1 . The X axis and Y axis denote the number of iterations and the logarithm of objective value, respectively. Overall, the objective value decreased monotonically during iteration whatever network structures and datasets we choose. Specifically, the objective value dropped tremendously at the early stage and then converged smoothly towards the critical point of the problem. We also found that the objective value for the Fashion MNIST dataset decreased more quickly than that for the MNIST dataset. and the test accuracy of our proposed DLAM outperformed all baselines for the MNIST dataset, while those of our proposed DLAM algortihm performed competitively for the Fashion MNIST dataset. Specifically, the curves of our DLAM algorithm soared to 0.7 at the early stage, and then raised steadily towards to 0.8 or more. The curves of the SGD-related methods, SGD, Adadelta, and Adagrad, moved more slowly than our proposed DLAM algorithm. The curves of the ADMM also rocketed to around 0.8, but decreased slightly later on.

4.2.2. PERFORMANCE:



4.2.3. EFFICIENCY:

In this subsection, the relationship between running time per iteration of our proposed DLAM algorithm and two potential factors, namely, the value of ρ, the size of training sample was explored. The running time was calculated by the average of 150 iterations. The computational result for the MNIST dataset and Fashion MNIST dataset on the 100 × 100 neural network is shown in Table 2 . The number of training samples of the MNIST dataset ranged from 11,000 to 55,000, with an increase of 11,000 each time, whereas The number of training samples of the Fashion MNIST dataset ranged from 12,000 to 60,000, with an increase of 12,000 each time. The value of ρ ranged from 0.0001 to 1, with multiplying by 10 each time. Generally, the running time increased as the training sample and the value of ρ became larger.

5. CONCLUSION:

Even though stochastic gradient descent (SGD) is a popular method to train deep neural networks, alternating minimization methods have attracted increasing attention from a great deal of researchers recently as they have several advantages including solid theoretical guarantees and avoiding gradient vanishing problems. In this paper, we propose a novel formulation of the original deep neural network problem and a novel Deep Learning Alternating Minimization (DLAM) algorithm. Specifically, the nonlinear constraint is projected into a convex set so that all subproblems are solvable. At the same time, the quadratic approximation technique and the backtracking algorithm are applied to boost up scalability. Furthermore, several mild assumptions are established to prove the global convergence of our DLAM algorithm. Experiments on real-world datasets demonstrate the convergence, effectiveness, and efficiency of our DLAM algorithm.

:



Figures and Tables:

common regularization terms like 1 or 2 regularizations lead to closed-form solutions. As for the choice of θ k+1 l , the backtracking algorithm is shown in Algorithm 2. Specifically, for a given θ k+1 l , we minimize equation 2 to obtain W k+1 l until the condition in Line 3 is satisfied. The time complexity of Algorithm 2 is O(d 2 ), where d is the dimension of the neurons or features. Algorithm 2 Backtracking Algorithm to update W k+1 l Require: a k+1 l-1 , W k l , b k l , z k l , ρ, some constant γ > 1. Ensure:

is a quadratic function with respect to a l , the solution can be obtained by a Now the main focus is how to choose τ k+1 l . Similar to Algorithm 2, the backtracking algorithm for finding a suitable τ k+1 l is shown in Algorithm 3. The time complexity of Algorithm 3 is O(d 2 ), where d is the dimension of neurons or features. Algorithm 3 Backtracking Algorithm to update a k+1 l Require: a

, two benchmark datasets were used for comparison:MNIST (LeCun et al. (1998))

Figure 1: Convergence curves of DLAM algorithm on MNIST and Fashion MNIST datasets for two neural network structures: DLAM algorithm converged.

Figure 2 and Figure 3 show the curves of the training accuracy and test accuracy of our proposed DLAM algorithm and baselines, respectively. Overall, both the training accuracy

Notations Used in This Paper

Table content: <table><tr><td>Notations</td><td>Descriptions</td></tr><tr><td>L</td><td>Number of layers.</td></tr><tr><td>W l</td><td/></tr></table>

However, as an emerging domain, alternating minimization for deep model optimization suffers from a number of unsolved challenges including: 1. Convergence properties are sensitive to penalty parameters. One recent work by Wang et al. firstly proved the convergence guarantee of ADMM in the fully-connected neural network problem(Wang et al. (2019)). However, such convergence guarantee is dependent on the choice of penalty hyperparameters: the convergence can not be guaranteed any more when penalty hyperparameters are small. 2. Lack of unified theoretical frameworks with general conditions. The global convergence of ADMM on deep learning has rarely been explored(Wang et al. (2019);Zeng et al. (2019)). And existing few works are tailored for and limited to few specific loss functions and activation functions: Zeng et al. proved that the ADMM is convergent for square loss function and twice differentiable activation functions (e.g. sigmoid)

Table content: <table/>

The relation between running time per iteration (in second) and size of training samples as well as value of ρ: generally, the running time increased as the training sample and the value of ρ became larger.

Table content: <table><tr><td/><td>0.8</td><td/></tr><tr><td/><td>0.7</td><td/></tr><tr><td>Test Accuracy</td><td>0.1 0.2 0.3 0.4 0.5 0.6</td><td>SGD Adadelta Adagrad ADMM DLAM</td></tr><tr><td/><td>Iteration</td><td/></tr><tr><td colspan="3">(d) Size of 500×500 on Fashion MNIST</td></tr></table>

Peer review (iclr2020):
The motivation for this paper is as follows: Why SGD: 1. Easy 2. applied in online settings However: 1. Convergence proof has been done by others, but the assumptions of their proofs cannot be applied to problems involving deep neural networks, which are highly nonsmooth and nonconvex 2. Suffer from gradient vanish 3. sensitive to the input The paper is based on new ideas on alternative minimization method. In particular the loss function is reformulated as nested function associated with multiple linear and nonlinear transformations. This nested structure is then decomposed into a series of linear and nonlinear equality constraints by introducing auxiliary variables and penalty hyperparameters. Then multiple subproblems are generated which can be minimized alternatively. (using ADMM, BCD) However, these methods suffer from problems: 1. Convergence properties are sensitive to penalty parameters. 2. Lack of unified theoretical frameworks with general conditions. (Not fully proved the convergence. Most of the work is based on some assumptions) Main Assumption: Activation functions are quasilinear functions. pros (+): 1. Generic, easy to extend it to convolutional layers and recurrent layers. 2. Transform the Neural network optimization problem into inequality constrained problem (new point of view) 3. Ensure convexity of subproblems. (quadractic approximation of activation function). 4. Ensure global minima, and converges to the critical point (where 0 is in the set of partial differential of F(F(W,b,,z,a) is the augment loss function) with respect to W*, and set of partial differential of F with respect to b*). 5. The convergence rate is O(1/k), k is the number of iterations of updating (W,b,z,a). 6. inequality-constraint prevents the output of a nonlinear function from changing much and reduces sensitivity to the input. 7. Matrix inversion is avoided by quadratic approximation 8. No need strict and complex condition, such as KL properties to prove convergence. Instead, this algorithm needs simple and mild conditions to guarantee convergence, and cover most of the loss function and activation functions. 9. The choice of hyperparameters has no effect on convergence. 10. Much better performance on MNIST cons(-): 1. penalty parameters need to be tuned as ADMM does. 2. The regularizations is l1 and l2, otherwise, it will not be closed-form solutions. The regularization like dropout, batch-norm can not be added into this algorithm. 3. The dataset is relatively naive. Only MNIST and Fashion MNIST. It would be better to include little more sophisticate dataset like ImageNet or Cifar10. Since the computation complexity is O(d^2) where d is the dimension of the features, large scale of image like ImageNet could cause problem. (Comparison: features of MNIST: 196, features of Fashion MNIST:784, features of ImageNet: 65536). 4. The Adagrad has better performance than DLAM on 500*500 on Fashion MNIST and close performance on MNIST. As the authors suggest: DLAM performed competitively for the Fashion MNIST dataset. This can be interpreted as follows: the proposed algorithm performs well on easy datasets, however the performance is not much better than other algorithms on Fashion MNIST, which is little more challenging. What would be your comment about this criticism? Can you provide any theoretical insight? Certainly it would strengthen the paper if there were more comparisons of DLAM on more complex dataset.