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

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.

text: 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.

heading: 1 INTRODUCTION
text: 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).
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) (Zeng et al. (2019)); Wang et al. proved the convergence of ADMM for the Relu activation function (Wang et al. (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: • We propose a novel formulation for deep neural network optimization. The deeply nested acti-
vation functions are disentangled into separate functions innovatively coordinated by inequality constraints that are inherently convex. • We present a novel and efficient DLAM algorithm. A quadratic approximation technique and a
backtracking algorithm are utilized to avoid matrix inversion. Every subproblem has a closed-form solution, further boosting efficiency. • We investigate several attractive convergence properties of the DLAM algorithm under mild
conditions. The model assumptions are very mild, ensuring that most deep learning problems will satisfy our assumptions. The new DLAM algorithm is guaranteed to converge to a critical point. • We conduct experiments on benchmark datasets to validate our proposed DLAM algorithm.
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.

heading: 2 THE DLAM ALGORITHM
text: 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.

heading: 2.1 INEQUALITY APPROXIMATION FOR DEEP LEARNING
text: 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 Wl ∈ Rnl×nl−1 , where nl is the number of neurons on the l-th layer and an intercept bl ∈ Rnl ; a nonlinear mapping is defined by an activation function hl(•). Given an input al−1 ∈ Rnl−1 from the (l − 1)-th layer, the l-th layer outputs al = hl(Wlal−1 + bl). By introducing an auxiliary variable zl as the temporary result of the linear mapping, the deep neural network problem is formulated mathematically as follows:
Problem 1: minal,Wl,bl,zl R(zL; y) + ∑L
l=1 Ωl(Wl)
s.t. zl= Wlal−1+bl(l=1,· · ·,L), al=hl(zl)(l=1, · · · , L−1) where a0 = x ∈ Rd is the input of the deep neural network, d is the number of feature dimensions, and y is a predefined label vector. R(zL; y) ≥ 0 is the risk function for the L-th layer, which is convex and proper, and Ωl(Wl) ≥ 0 is a regularization term on the l-th layer, which is also convex and proper. The equality constraint al = hl(zl) 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 zl (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:
minWl,bl,zl,alR(zL; y)+ ∑L
l=1 Ωl(Wl)+ ∑L−1 l=1 I(hl(zl)−εl≤al≤hl(zl)+εl)
s.t.zl = Wlal−1 + bl(l=1,· · ·,L) I(hl(zl) − εl ≤ al ≤ hl(zl) + εl) is an indicator function such that the value is 0 if hl(zl) − εl ≤ al ≤ hl(zl) + εl and∞ otherwise. For the linear constraint zl= Wlal−1+bl, this can be transformed into a penalty term in the objective function to minimize the difference between zl and Wlal−1+bl. The formulation is shown as follows:
Problem 2: minWl,bl,zl,al F (W,b, z, a) = R(zL; y)+ ∑L
l=1 Ωl(Wl) + ∑L
l=1 φ(al−1,Wl,bl,zl)+ ∑L−1 l=1
I(hl(zl)−εl≤al≤hl(zl)+εl) The penalty term is defined as φ(al−1,Wl, bl, zl) = (ρ/2)‖zl−Wlal−1−bl‖22, where ρ > 0 a penalty parameter. W = {Wl}Ll=1, b = {bl}Ll=1, z = {zl}Ll=1,a = {al} 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.

heading: 2.2 ALTERNATING OPTIMIZATION
text: We present DLAM algorithm developed to solve Problem 2, shown in Algorithm 1. Lines 4, 5, 7, and 10 update Wl, bl,zl and al, respectively, and the four relevant subproblems are discussed as below: 1. Update Wl The variables Wl(l = 1, · · · , L) are updated as follows: W k+1l ← arg minWl φ(a k+1 l−1 ,Wl, b k l , z k l ) + Ωl(Wl) (1)
Because Wl and al−1 are coupled in φ(•), solving Wl requires an inversion operation of ak+1l−1 , which is computationally expensive. Motivated by deep learning Alternating Direction Method of Multipliers (dlADMM) (Wang et al. (2019)), we define P k+1l (Wl; θ k+1 l ) as a quadratic approximation of φ at W kl , which is mathematically reformulated as follows (Beck & Teboulle (2009)):
P k+1l (Wl;θ k+1 l )=φ(a k+1 l−1,W k l ,z k l ,b k l )+<∇Wkl φ,Wl−W k l > +‖θk+1l ◦ (Wl −W k l ) ◦2‖1/2
where θk+1l > 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.∇Wkl φ = ρ(W k l a k+1 l−1 + b k l − zkl )(a k+1 l−1 )
T (l = 1, · · · , L) is the gradient of φ with regard to Wl at W kl . 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: al,Wl, bl, zl(l = 1, · · · , L). 1: Initialize ρ, k = 0. 2: repeat 3: for l = 1 to L do 4: UpdateWk+1l using Algorithm 2. 5: Update bk+1l in equation 3. 6: if l = L then 7: Update zk+1l in equation 5. 8: else 9: Update zk+1l in equation 4. 10: Update ak+1l using Algorithm 3. 11: end if 12: end for 13: k ← k + 1. 14: until convergence. 15: Output al,Wl, bl, zl.
original subproblem in equation 1, we instead minimize the following:
W k+1l ← arg minWl P k+1 l (Wl; θ k+1 l ) + Ωl(Wl) (2)
For Ωl(Wl), common regularization terms like `1 or `2 regularizations lead to closed-form solutions. As for the choice of θk+1l , the backtracking algorithm is shown in Algorithm 2. Specifically, for a given θk+1l , 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(d2), where d is the dimension of the neurons or features.
Algorithm 2 Backtracking Algorithm to update W k+1l Require: ak+1l−1 ,W k l , b k l , z k l , ρ, some constant γ > 1. Ensure: θk+1l ,W k+1 l .
1: Initialize α. 2: update ζ in equation 2 where θk+1l = α. 3: while φ(ak+1l−1 , ζ, b k l , z k l ) > P k+1 l (ζ;α) do 4: α← αγ. 5: update ζ in equation 2 where θk+1l = α. 6: end while 7: Output θk+1l ← α. 8: OutputWk+1l ← ζ.

heading: 2. Update bl
text: The variables bl(l = 1, · · · , L) are updated as follows:
bk+1l ← arg minbl φ(a k+1 l−1 ,W k+1 l , bl, z k l ).
Similarly to updating Wl, we define Uk+1l (bl;Lb) as a quadratic approximation of φ at b k l , which is formulated mathematically as follows (Beck & Teboulle (2009)):
Uk+1l (bl;Lb) = φ(a k+1 l−1 ,W k+1 l , b k l , z k l ) + (∇bkl φ) T (bl − bkl ) + (Lb/2)‖bl − bkl ‖22.
where Lb ≥ ρ is a parameter and ∇bkl φ = ρ(b k l +W k+1 l a k+1 l−1 − zkl ). Here, Lb ≥ ρ is required for the convergence analysis (Beck & Teboulle (2009)). Without loss of generality, we set Lb = ρ. We can now solve the following subproblem:
bk+1l ← arg minbl U k+1 l (bl; ρ) (3)
The solution to equation 3 is: bk+1l ← bkl −∇bkl φ/ρ. 3. Update zl The variables zl(l = 1, · · · , L) are updated as follows:
zk+1l ← arg minzlφ(a k+1 l−1 ,W k+1 l , b k+1 l , zl)+I(hl(zl)−εl ≤ a k l ≤ hl(zl)+εl)(l <L)
zk+1L ← arg minzL φ(a k+1 L−1,W k+1 L , b k+1 L , zL) +R(zL; y)
As when updating bl, we define V k+1l (zl;Lz) as a quadratic approximation of φ at z k l , which is formulated mathematically as follows:
V k+1l (zl;Lz) =φ(a k+1 l−1 ,W k+1 l , b k+1 l , z k l )+(∇zkl φ) T (zl−zkl )+(Lz/2)‖zl−zkl ‖22 where Lz ≥ ρ is a parameter and∇zkl φ = ρ(z k l −W k+1 l a k+1 l−1 −b k+1 l ). Without loss of generality, we set Lz = ρ. Obviously, V k+1l (z k l ; ρ) = φ(a k+1 l−1 ,W k+1 l , b k+1 l , z k l ). Hence, we solve the problems:
zk+1l ← arg minzlV k+1 l (zl; ρ) +I(hl(zl)−εl ≤ a k l ≤ hl(zl)+εl)(l <L) (4)
zk+1L ← arg minzL V k+1 L (zL; ρ) +R(zL; y) (5)
As for zl(l = 1, · · · , l − 1), the solution is zk+1l ← min(max(B k+1 1 , z k l −∇φzkl /ρ), B k+1 2 ). where Bk+11 and B k+1 2 represent the lower bound and the upper bound of the set {zl|hl(zl)−εl ≤ akl ≤ hl(zl)+εl}. equation 5 is easy to solve using the Fast Iterative Soft Thresholding Algorithm (FISTA) (Beck & Teboulle (2009)). 4. Update al The variables al(l = 1, · · · , L− 1) are updated as follows:
ak+1l ← arg minal φ(al,W k l+1, b k l+1, z k l+1) + I(hl(z k+1 l )− εl ≤ al ≤ hl(z k+1 l ) + εl)
As when solving W k+1l , the quadratic approximation of φ at a k l is defined as
Qk+1l (al;τ k+1 l ) =φ(a k l,W k l+1,b k l+1,z k l+1)+(∇akl φ) T (al−akl ) + ‖τk+1l ◦ (al − a k l ) ◦2‖1/2
and this allows us to solve the following problem instead:
ak+1l ← arg minal Q k+1 l (al; τ k+1 l ) + I(hl(z k+1 l )− εl ≤ al ≤ hl(z k+1 l ) + εl) (6)
where τk+1l > 0 is a parameter vector. ∇akl φ = ρ(W k l+1) T (W kl+1a k l +b k l+1−zkl+1)(l = 1, · · · , L−1) is the gradient of φ with regard to al at akl . 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 Qk+1l (al; τ k+1 l ) is a quadratic function with respect to al, the solution can be obtained by ak+1l ← akl − ∇akl φ/τ k+1 l given a suitable τ k+1 l . Now the main focus is how to choose τ k+1 l . Similar to Algorithm 2, the backtracking algorithm for finding a suitable τk+1l is shown in Algorithm 3. The time complexity of Algorithm 3 is O(d2), where d is the dimension of neurons or features.
Algorithm 3 Backtracking Algorithm to update ak+1l Require: akl ,W k l+1, z k+1 l , z k l+1, b k l+1, ρ, some constant η > 1. Ensure: τk+1l ,a k+1 l . 1: Pick up t such that β = akl −∇ak l φ/t and hl(z k+1 l )− εl ≤ β ≤ hl(z k+1 l ) + εl. 2: while φ(β,Wkl+1, zkl+1, bkl+1) > Qk+1l (β; t) do 3: t← tη. 4: β ← akl −∇φak
l /t.
5: end while 6: Output τk+1l ← t. 7: Output ak+1l ← β.

heading: 3 CONVERGENCE ANALYSIS
text: 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.

heading: 3.1 ASSUMPTION
text: Firstly, we make the following assumption:
Assumption 1 (Quasilinearity). Activation functions hl(zl)(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 al = hl(zl) 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(zL; y) and the regularization term Ωl(Wl). Therefore, they can be either smooth or nonsmooth: R(zL; y) can be a common least square loss or cross entropy loss; Ωl(Wl) can be a either `1 or `2 regularization term. They fit neatly into our framework and incorporate several important theoretical properties.

heading: 3.2 KEY CONVERGENCE PROPERTIES
text: 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 (Wk, bk, zk, ak)− F (Wk+1, bk+1, zk+1, ak+1) ≥ ∑L
l=1 ‖θk+1l ◦ (W k+1 l −W k l ) ◦2‖1/2+
(ρ/2) ∑L
l=1 ‖bk+1l −b k l ‖22+(ρ/2) ∑L l=1 ‖zk+1l −z k l ‖22 + ∑L−1 l=1 ‖τk+1l ◦ (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). (Wk, bk, zk, ak) and F(Wk, bk, zk, ak) are convergent. That is, as k →∞, (Wk, bk, zk, ak)→ (W∗, b∗, z∗, a∗) and F(Wk, bk, zk, ak)→ F(W∗, b∗, z∗, a∗). (b). (Wk, bk, zk, ak) is bounded. That is, there exist scalars MW,Mb,Mz and Ma such that ‖Wk‖ ≤ MW, ‖bk‖ ≤Mb, ‖zk‖ ≤Mz and ‖ak‖ ≤Ma.
Lemma 2 guarantees that the variable (Wk,bk, zk, ak) 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(ρMa, ρM2a + ‖θk+11 ‖, ρM2a + ‖θk+12 ‖, · · · , ρM2a + ‖θ k+1 L ‖), some g k+1 1 ∈ ∂Wk+1F and g k+1 2 = ∇bk+1F such that
‖gk+11 ‖≤C(‖Wk+1−Wk‖+‖b k+1−bk‖+‖zk+1−zk‖), ‖gk+12 ‖=ρ‖zk+1−zk‖
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 (W0, b0) , Algorithm 1 converges to a critical point (W∗, b∗). That is, 0 ∈ ∂W∗F and 0 ∈ ∂b∗F . Proof. By Lemma 2, (Wk,bk) is convergent to (W∗,b∗). From Lemma 3, there exist gk+11 ∈ ∂Wk+1F and g k+1 2 ∈ ∂bk+1F 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 (Wk, bk, zk, ak), define ck = min0≤i≤k( ∑L l=1 ‖θ i+1 l ◦(W i+1 l − W il ) ◦2‖1/2 +(ρ/2) ∑L l=1 ‖b i+1 l −bil‖22+(ρ/2) ∑L l=1 ‖z i+1 l −zil‖22 + ∑L−1 l=1 ‖τ i+1 l ◦ (a i+1 l − ail)◦2‖1/2), which reflects the convergence rate of Algorithm 1, then the convergence rate of ck is o(1/k). Proof. The proof of this theorem is in the supplementary materials.

heading: 4 EXPERIMENTS
text: 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.

heading: 4.1 EXPERIMENT SETUP

heading: 4.1.1 DATASET
text: In this experiment, two benchmark datasets were used for comparison: MNIST (LeCun et al. (1998)) 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.

heading: 4.1.2 EXPERIMENT SETTINGS
text: 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(zkL; y) > 10ε
k, εk+1 = max(2εk, 1); if εk > 10R(zkL; y), εk+1 = min(εk/2, 0.01), which balances between the loss function R(zL; y) and ε. The number of iteration was set to 150. In the experiment, one iteration means one epoch.

heading: 4.1.3 COMPARISON METHODS
text: 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.

heading: 4.2 EXPERIMENTAL RESULTS
text: In this section, experimental results of DLAM algorithm are analyzed against comparison methods.

heading: 4.2.1 CONVERGENCE
text: 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.

heading: 4.2.2 PERFORMANCE
text: 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
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.

heading: 4.2.3 EFFICIENCY
text: 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.

heading: 5 CONCLUSION
text: 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.

heading: A DEFINITIONS
text: First, the definition of Fréchet subdifferential is shown as follows (Rockafellar & Wets (2009)):
Definition 1 (Fréchet Subdifferential). For each x1 ∈ dom(u1), the Fréchet subdifferential of u1 at x1, which is denoted as ∂̂u1(x1), is the set of vectors v, which satisfy
lim x2 6=x1 inf x2→x1
(u1(x2)− u1(x1)− vT (x2 − x1))/‖x2 − x1‖ ≥ 0.
The vector v ∈ ∂̂u1(x1) is a Fréchet subgradient.
Then the definition of the limiting subdifferential, which is based on Fréchet subdifferential, is given in the following (Rockafellar & Wets (2009)):
Definition 2 (Limiting Subdifferential). For each x ∈ dom(u2), the limiting subdifferential (or subdifferential) of u2 at x is
∂u2(x) ={v1|∃ xk → x, s.t. u2(xk)→ u2(x), vk ∈ ∂̂u2(xk), vk → v}
where xk is a sequence whose limit is x and the limit of u2(xk) is u2(x), vk is a sequence, which is a Fréchet subgradient of u2 at xk and whose limit is v. The vector v ∈ ∂u2(x) is a limiting subgradient.
Specifically, when u2 is convex, its limiting subdifferential is reduced to regular subdifferential (Rockafellar & Wets (2009)); The limiting subdifferential is used to prove the global convergence of the DLAM in the following convergence analysis. Without loss of generality, ∂R and ∂Ωl(l = 1, · · · , n) are nonempty, and the limiting subdifferential of F defined in Problem 2 is (Xu & Yin (2013)):
∂F (W,b, z, a)=∂WF ×∇bF × ∂zF × ∂aF where × means the Cartesian product. Next, recall the definition of quasilinearity (Boyd & Vandenberghe (2004)):
Definition 3. A function f(x) is quasiconvex if for any sublevel set Sα(f) = {x|f(x) ≤ α} is a convex set. Likewise, A function f(x) is quasiconcave if for any superlevel set Sα(f) = {x|f(x) ≥ α} is a convex set. A function f(x) is quasilinear if it is both quasiconvex and quasiconcave.

heading: B PRELIMINARY LEMMAS
text: In this section, we give preliminary lemmas which are useful for the proofs of three properties. The proofs of Lemmas 4 and 5 both require Assumption 1. The proof of Lemma 6 requires Lemmas 4 and 5. To simplify the notation, Wk+1≤l = {{W k+1 i } l i=1, {W ki }Li=l+1}, bk+1≤l = {{b k+1 i } l i=1, {bki }Li=l+1}, zk+1≤l = {{zk+1i } l i=1, {zki }Li=l+1} and ak+1≤l = {{a k+1 i } l i=1, {aki }L−1i=l+1}.
Lemma 4. equation 2 holds if and only if there exists s ∈ ∂Ωl(W k+1l ), the subgradient of Ωl(W k+1 l ) such that ∇Wk
l φ+ θk+1l ◦ (W k+1 l −W k l ) + s = 0
Likewise, equation 4 holds if and only if there exists r ∈ ∂I(hl(zk+1l )− εl ≤ a k l ≤ hl(zk+1l ) + εl) such that
∇zk l φ+ ρ(zk+1l − z k l ) + r = 0
equation 5 holds if and only if there exists u ∈ ∂R(zk+1L ; y) such that ∇zk
L φ+ ρ(zk+1L − z k L) + u = 0
equation 6 holds if and only if there exists v ∈ ∂I(hl(zk+1l )− εl ≤ a k+1 l ≤ hl(z k+1 l ) + εl) such that
∇ak l φ+ ρ(ak+1l − a k l ) + v = 0
Proof. These can be obtained by directly applying the optimality conditions of equation 2, equation 4, equation 5 and equation 6, respectively.
Lemma 5. For equation 4, equation 5 and equation 3, if Lb ≥ ρ and Lz ≥ ρ,then the following inequalities hold:
Uk+1l (b k+1 l ;Lb) ≥ φ(a k+1 l−1 ,W k+1 l , b k+1 l , z k l ) (8)
V k+1l (z k+1 l ;Lz) ≥ φ(a k+1 l−1 ,W k+1 l , b k+1 l , z k+1 l ) (9)
Proof. Because φ(al−1,Wl, bl, zl) is differentiable continuous with respect to bl and zl with Lipschitz coefficient ρ (the definition of Lipschitz differentiablity can be found in (Beck & Teboulle (2009))), we directly apply Lemma 2.1 in (Beck & Teboulle (2009)) to φ to obtain equation 8 and equation 9, respectively.
Lemma 6. It holds that for ∀k ∈ N and l = 1, 2, · · · , L, F (Wk+1≤l−1,b k+1 ≤l−1,z k+1 ≤l−1,a k+1 ≤l−1)−F (W k+1 ≤l ,b k+1 ≤l−1,z k+1 ≤l−1, a k+1 ≤l−1)
≥‖θk+1l ◦(W k+1 l −W k l ) ◦2‖1/2. (10)
F (Wk+1≤l , b k+1 ≤l−1, z k+1 ≤l−1, a k+1 ≤l−1)−F (W k+1 ≤l , b k+1 ≤l , z k+1 ≤l−1, a k+1 ≤l−1)
≥ (ρ/2)‖bk+1l − b k l ‖22. (11)
F (Wk+1≤l , b k+1 ≤l , z k+1 ≤l−1, a k+1 ≤l−1)−F (W k+1 ≤l , b k+1 ≤l , z k+1 ≤l , a k+1 ≤l−1)
≥(ρ/2)‖zk+1l −z k l ‖22. (12)
F (Wk+1≤l , b k+1 ≤l , z k+1 ≤l , a k+1 ≤l−1)−F (W k+1 ≤l , b k+1 ≤l , z k+1 ≤l , a k+1 ≤l )
≥ ‖τk+1l ◦ (a k+1 l − a k l ) ◦2‖1/2. (13)
Proof. Essentially, all inequalities can be obtained by applying optimality conditions of updating W k+1l , b k+1 l , zk+1l and a k+1 l , respectively. We only prove equation 10 and equation 12 since equation 13 and equation 11 follow the same routine of equation 10 and equation 12, respectively. Firstly, we focus on proving equation 10. The stopping criterion of Algorithm 2 shows that
φ(ak+1l−1 ,W k+1 l , b k l , z k l ) ≤ P k+1l (W k+1 l ; θ k+1 l ). (14)
Because ΩWl(Wl) is convex, according to the definition of subgradient, we have
Ωl(W k l ) ≥ Ωl(W k+1l ) + s T (W kl −W k+1l ) (15) where s is defined in the premise of Lemma 4. Therefore, we have
F (Wk+1≤l−1, b k+1 ≤l−1, z k+1 ≤l−1, a k+1 ≤l−1)−F (W k+1 ≤l , b k+1 ≤l−1, z k+1 ≤l−1, a k+1 ≤l−1)
= φ(ak+1l−1 ,W k l , b k l , z k l ) + Ωl(W k l )− φ(ak+1l−1 ,W k+1 l , b k l , z k l )
− Ωl(W k+1l ) (Definition of F in Problem 2)
≥ Ωl(W kl )− Ωl(W k+1l )− (∇Wk l φ)T (W k+1l −W k l ) − ‖θk+1l ◦ (W k+1 l −W k l ) ◦2‖1/2( equation 14)
≥ sT (W kl −W k+1l )− (∇Wk l φ)T (W k+1l −W k l )−
‖θk+1l ◦ (W k+1 l −W k l ) ◦2‖1/2( equation 15)
= (s+∇φTWk l )(W kl −W k+1l )−‖θ k+1 l ◦ (W k+1 l −W k l ) ◦2‖1/2 = ‖θk+1l ◦ (W k+1 l −W k l ) ◦2‖1/2 (Lemma 4).
Secondly, we focus on proving equation 12. For l < L, because I(hl(zl)− εl ≤ akl ≤ hl(zl) + εl) is convex with regard to zl, according to the definition of subgradient, we have
I(hl(zkl)−εl ≤ akl ≤ hl(zkl )+εl)
≥I(hl(zk+1l )−εl≤a k l ≤hl(zk+1l )+εl)+r T(zkl −zk+1l ) (16)
where r is defined in Lemma 4. F (Wk+1≤l , b k+1 ≤l , z k+1 ≤l−1, a k+1 ≤l−1)− F (W k+1 ≤l , b k+1 ≤l , z k+1 ≤l , a k+1 ≤l−1)
= φ(ak+1l−1 ,W k+1 l , b k+1 l , z k l )+I(hl(zkl )−εl ≤ akl ≤hl(zkl )+εl)
−φ(ak+1l−1 ,W k+1 l , b k+1 l , z k+1 l )−I(hl(z k+1 l )−εl≤a k l ≤hl(zk+1l )+εl)
(Definition of F in Problem 2)
≥−(∇zk l φ)T(zk+1l −z k l )−(ρ/2)‖zk+1l −z k l ‖22 +I(hl(zkl )−εl≤akl ≤hl(zkl )+εl)
−I(hl(zk+1l )−εl≤a k l ≤hl(zk+1l )+εl)( equation 9)
≥ −(∇zk l φ)T (zk+1l − z k l )− (ρ/2)‖zk+1l − z k l ‖22 + rT (zkl − zk+1l )( equation 16)
= −(∇zk l φ)T (zk+1l − z k l )− (ρ/2)‖zk+1l − z k l ‖22 + (∇zk l φ+ ρ(zk+1l − z k l )) T (zk+1l − z k l ) (Lemma 4) = (ρ/2)‖zk+1l − z k l ‖22.
For zL, the same routine applies.

heading: C PROOF OF LEMMA 1
text: Proof. This can be obtained by adding equation 10, equation 11 and equation 12 from l = 1 to l = L and equation 13 from l = 1 to l = L− 1.

heading: D PROOF OF LEMMA 2
text: Proof. (a). By Lemma 1, F (Wk, bk, zk, ak) is non-increasing. Also, F (Wk, bk, zk, ak) ≥ 0. According to the monotonic sequence theorem, F (Wk, bk, zk, ak) is convergent. Next, we take the limit of Inequality 7 to obtain
lim k→∞
(F (Wk, bk, zk, ak)− F (Wk+1, bk+1, zk+1, ak+1))
≥ lim k→∞ ∑L l=1 ‖θk+1l ◦ (W k+1 l −W k l ) ◦2‖1/2
+(ρ/2) ∑L
l=1 ‖bk+1l −b k l ‖22+(ρ/2) ∑L l=1 ‖zk+1l −z k l ‖22
+ ∑L−1
l=1 ‖τk+1l ◦ (a k+1 l − a k l ) ◦2‖1/2
≥ 0 Because F (Wk, bk, zk, ak) is convergent, limk→∞(F (Wk, bk, zk, ak)− F (Wk+1, bk+1, zk+1, ak+1)) = 0. Therefore, we have
lim k→∞ ∑L l=1 ‖θk+1l ◦ (W k+1 l −W k l ) ◦2‖1/2
+(ρ/2) ∑L
l=1 ‖bk+1l −b k l ‖22+(ρ/2) ∑L l=1 ‖zk+1l −z k l ‖22
+ ∑L−1
l=1 ‖τk+1l ◦ (a k+1 l − a k l ) ◦2‖1/2 = 0
Since θk+1l , τ k+1 l > 0, we obtain as k → ∞, ‖W k+1 l −W k l ‖ → 0, ‖bk+1l − b k l ‖ → 0, ‖zk+1l − z k l ‖ → 0, and ‖ak+1l − a k l ‖ → 0. This shows that (Wk, bk, zk, ak) converges to a point (W∗, b∗, z∗, a∗). BecauseF is continuous, limk→∞(Wk, bk, zk, ak) = F (limk→∞Wk, limk→∞ bk, limk→∞ zk, limk→∞ ak) = F (W∗, b∗, z∗, a∗). (b). Because (Wk, bk, zk, ak) is convergent and a convergent sequence is bounded, therefore it is also bounded.

heading: E PROOF OF LEMMA 3
text: Proof. As shown in (Wang et al. (2015); Xu & Yin (2013)), ∂Wk+1F = {∂Wk+11 F} × {∂Wk+12 F} × · · · × {∂Wk+1L F}.
∇bk+1F = ∇bk+11 F ×∇bk+12 F × · · · × ∇bk+1L F.
where × denotes Cartesian Product. For W k+1l ,
∂ Wk+1 l F
= ∂Ωl(W k+1 l )+∇Wk+1 l φ(ak+1l−1 ,W k+1 l , b k+1 l , z k+1 l )
(Definition of F in Problem 2)
= ∇ Wk+1 l φ(ak+1l−1 ,W k+1 l , b k+1 l , z k+1 l ) −∇Wk l φ(ak+1l−1 ,W k l , b k l , z k l )− θk+1l ◦ (W k+1 l −W k l ) + ∂Ωl(W k+1 l ) +∇Wk
l φ(ak+1l−1 ,W k l , b k l , z k l )
+ θk+1l ◦ (W k+1 l −W k l )
= ρ(W k+1l −W k l )a k+1 l−1 (a k+1 l−1 ) T + ρ(bk+1l − b k l )(a k+1 l−1 ) T
− ρ(zk+1l − z k l )(a k+1 l−1 ) T − θk+1l ◦ (W k+1 l −W k l )
+ ∂Ωl(W k+1 l ) +∇Wk l φ(ak+1l−1 ,W k l , b k l , z k l ) + θk+1l ◦ (W k+1 l −W k l )
On one hand, we have ‖ρ(W k+1l −W k l )a k+1 l−1 (a k+1 l−1 ) T + ρ(bk+1l − b k l )(a k+1 l−1 ) T
− ρ(zk+1l − z k l )(a k+1 l−1 ) T − θk+1l ◦ (W k+1 l −W k l )‖
≤ ρ‖(W k+1l −W k l )a k+1 l−1 (a k+1 l−1 ) T ‖+ ρ‖(bk+1l − b k l )(a k+1 l−1 ) T ‖
+ρ‖(zk+1l −z k l )(a k+1 l−1 ) T‖+‖θk+1l ◦(W k+1 l −W k l )‖(triangle inequality)
≤ ρ‖W k+1l −W k l ‖‖ak+1l−1 ‖‖a k+1 l−1 ‖+ ρ‖b k+1 l − b k l ‖‖ak+1l−1 ‖
+ ρ‖zk+1l − z k l ‖‖ak+1l−1 ‖+ ‖θ k+1 l ‖‖W k+1 l −W k l ‖
(Cauchy-Schwarz inequality)
≤ ρMa‖bk+1l − b k l ‖+ ρMa‖zk+1l − z k l ‖
(ρM2a + ‖θk+1l ‖)‖W k+1 l −W k l ‖(Lemma 2)
On the other hand, the optimality condition of equation 2 yields
0 ∈ ∂Ωl(W k+1l )+∇Wk l φ(ak+1l−1 ,W k l , b k l , z k l )+θ k+1 l ◦(W k+1 l −W k l )
Therefore, there exists gk+11,l ∈ ∂Wk+1 l F such that
‖gk+11,l ‖ ≤ ρMa‖b k+1 l − b k l ‖+ ρMa‖zk+1l − z k l ‖
+ (ρM2a + ‖θk+1l ‖)‖W k+1 l −W k l ‖
This shows that there exists gk+11 = g k+1 1,1 × g k+1 1,2 × · · · × g k+1 1,L ∈ ∂Wk+1F and C = max(ρMa, ρM 2 a + ‖θk+11 ‖, ρM2a + ‖θ k+1 2 ‖, · · · , ρM2a + ‖θ k+1 L ‖) such that
‖gk+1l ‖ ≤ C(‖W k+1 −Wk‖+ ‖bk+1 − bk‖
+ ‖zk+1 − zk‖)
Similarly, for bk+1l ,
∇F bk+1 l = ∇ bk+1 l φ(ak+1l−1 ,W k+1 l−1 , b k+1 l , z k+1 l )
= ∇ bk+1 l φ(ak+1l−1 ,W k+1 l−1 , b k+1 l , z k+1 l ) −∇bk l φ(ak+1l−1 ,W k+1 l−1 , b k l , z k l )− ρ(bk+1l − b k l )
(∇bk l φ(ak+1l−1 ,W k+1 l−1 , b k l , z k l ) + ρ(b k+1 l − b k l )) = 0 by
the optimality condition of equation 3)
= ρ(zk+1l − z k l ).
Therefore, there exists gk+12,l = ∇bk+1 l F such that
‖gk+12,l ‖ = ρ‖z k+1 l − z k l ‖
This shows that there exists gk+12 = g k+1 2,1 × g k+1 2,2 × · · · × g k+1 2,L = ∇bk+1F such that
‖gk+12 ‖ = ρ‖z k+1 − zk‖.
.

heading: F PROOF OF THEOREM 2
text: Proof. To prove this theorem, we will first show that ck satisfies two conditions: (1). ck ≥ ck+1. (2). ∑∞
k=0 ck is bounded. We then conclude the convergence rate of o(1/k) based on these two conditions. Specifically, first, we have
ck =min0≤i≤k( ∑L
l=1 ‖θi+1l ◦ (W i+1 l −W i l ) ◦2‖1/2
+(ρ/2) ∑L
l=1 ‖bi+1l −b i l‖22+(ρ/2) ∑L l=1 ‖zi+1l −z i l‖22
+ ∑L−1
l=1 ‖τ i+1l ◦ (a i+1 l − a i l) ◦2‖1/2)
≥min0≤i≤k+1( ∑L
l=1 ‖θi+1l ◦ (W i+1 l −W i l ) ◦2‖1/2
+(ρ/2) ∑L
l=1 ‖bi+1l −b i l‖22+(ρ/2) ∑L l=1 ‖zi+1l −z i l‖22
+ ∑L−1
l=1 ‖τ i+1l ◦ (a i+1 l − a i l) ◦2‖1/2)
= ck+1
Therefore ck satisfies the first condition. Second,∑∞ k=0 ck
= ∑∞
k=0 min0≤i≤k( ∑L l=1 ‖θi+1l ◦ (W i+1 l −W i l ) ◦2‖1/2
+(ρ/2) ∑L
l=1 ‖bi+1l −b i l‖22+(ρ/2) ∑L l=1 ‖zi+1l −z i l‖22
+ ∑L−1
l=1 ‖τ i+1l ◦ (a i+1 l − a i l) ◦2‖1/2)
≤ ∑∞ k=0 ( ∑L l=1 ‖θk+1l ◦ (W k+1 l −W k l ) ◦2‖1/2
+(ρ/2) ∑L
l=1 ‖bk+1l −b k l ‖22+(ρ/2) ∑L l=1 ‖zk+1l −z k l ‖22
+ ∑L−1
l=1 ‖τk+1l ◦ (a k+1 l − a k l ) ◦2‖1/2)
≤ F (W0, b0, z0, a0)− F (W∗, b∗, z∗, a∗)(Lemma 1) So ∑∞ k=0 ck is bounded and ck satisfies the second condition. Finally, it has been proved that the sufficient
conditions of convergence rate o(1/k) are: (1) ck ≥ ck+1, and (2) ∑∞
k=0 ck is bounded, and (3) ck ≥ 0 (Lemma 1.2 in (Deng et al. (2017))). Since we have proved the first two conditions and the third one ck ≥ 0 is obvious, the convergence rate of o(1/k) is proven.

heading: G DISCUSSION
text: We discuss convergence conditions of our DLAM compared with SGD-type methods and the ADMM method. The comparison demonstrates that our convergence conditions are more general than others.
G.1 DLAM VERSUS SGD
One influential work by Ghadimi et al. (Ghadimi & Lan (2016)) guaranteed that the SGD converges to a critical point, which is similar to our convergence results. While the SGD requires the objective function to be Lipschitz differentiable, bounded from below (Ghadimi & Lan (2016)), our DLAM allows for non-smooth functions such as Relu. Therefore, our convergence conditions are milder than SGD.
G.2 DLAM VERSUS ADMM
For ADMM, Zeng et al. showed that the ADMM is convergent to a critical point with a sublinear convergence rate O(1/k) (Zeng et al. (2019)), which is similar to our convergence results. However, the ADMM requires activation functions hl(•) to be twice-differentiable bounded, whereas our DLAM allows hl(•) to be non-smooth. This also shows that the assumptions of our DLAM are more general than those of the ADMM.

heading: H RELATED WORK
text: All of the existing works on optimization methods in deep neural network problems falls into two major classes: stochastic gradient descent methods and alternating minimization methods. This research related to both is discussed in this section. Stochastic gradient descent methods: The renaissance of SGD can be traced back to 1951 when Robbins and Monro published the seminal paper (Robbins & Monro (1951)). The famous backpropagation algorithm was introduced by Rumelhart et al. (Rumelhart et al. (1986)). Many variants of SGD methods have since been presented, including the use of Polyak momentum, which accelerates the convergence of iterative methods (Polyak (1964)), and research by Sutskever et al., who highlighted the importance of Nesterov momentum and initialization (Sutskever et al. (2013)). Many well-known SGD methods that incorporate with adaptive learning rates have been proposed by the deep learning community, including AdaGrad (Duchi et al. (2011)), RMSProp (Tieleman & Hinton), Adam (Kingma & Ba (2014)) and AMSGrad (Reddi et al. (2018)). Alternating minimization methods for deep learning: Previous work on the application of alternating minimization algorithms to deep learning problems can be categorized into two main types. The first research strand proposes the use of alternating minimization algorithms for specific applications. For example, Taylor et al. and Wang et al. presented an Alternating Direction Method of Multipliers (ADMM) algorithm to transform a fully-connected neural network problem into an equality-constrained problem, where many subproblems split by ADMM can be solved in parallel (Taylor et al. (2016); Wang et al. (2019)), while Zhang et al. handled very deep supervised hashing (VDSH) problems by utilizing an ADMM algorithm to overcome issues related to vanishing gradients and poor computational efficiency (Zhang et al. (2016)). Zhang and Bastiaan trained a deep neural network by utilizing ADMM with a graph (Zhang & Kleijn (2017)) and Askari et al. introduced a new framework for multilayer feedforward neural networks and solved the new framework using block coordinate descent (BCD) methods (Askari et al. (2018)). Others have proposed novel alternating minimization methods and proved their convergence results. For instance, Carreira and Wang suggested a method involving the use of auxiliary coordinates (MAC) to replace a nested neural network with a constrained problem without nesting (Carreira-Perpinan & Wang (2014)). Zeng et al. and Lau et al. both proposed BCD algorithms, proving its convergence via the Kurdyka-ojasiewicz (KL) property (Jinshan Zeng (2018); Lau et al. (2018)), while Choromanska et al. proposed a BCD algorithm for training deep feedforward neural networks based on the concept of co-activation memory (Choromanska et al. (2018)) and a BCD algorithm with R-linear convergence was proposed by Zhang and Brand to train Tikhonov regularized deep neural networks (Zhang & Brand (2017)). However, most of these researchers focused on specific applications of neural networks rather than their general formulations. Even though several do discuss general neural network problems and provide theoretical guarantees, the assumptions involved are hard to satisfy in practice.

Review summaries:
This paper proposes Deep Learning Alternating Minimization (DLAM) algorithm. First, deep learning optimization problems are formulated as multi-convex Problem 2, by introducing additional variables, constraints and relaxations. Second, alternating update is then used to solve Problem 2, the analysis shows that weights of update converge to a critical point with O(1/k) rate. Finally, some experiments are conducted on MNIST and Fashion-MNIST to show that DLAM is better than SGD, Adagrad, Adadelta and ADMM.