Gradient-free Neural Network Training by Multi-convex Alternating Optimization
Authors: Junxiang Wang
Fuxun Yu
Xiang Chen
Liang Zhao
Venue:  (2020)
Keywords: neural network
alternating minimization
global convergence

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 minimization-based 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.

Under review as a conference paper at ICLR 2020
GRADIENT-FREE NEURAL NETWORK TRAINING BY MULTI-CONVEX ALTERNATING OPTIMIZATION
Anonymous authors Paper under double-blind review
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 gra- dients, excessive sensitivity to input, and difficulties solving highly non-smooth constraints and functions. To overcome these drawbacks, alternating minimization- based methods for deep neural network optimization have attracted fast-increasing attention recently. As emerging and open domain. however, several new chal- lenges 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 Mini- mization (DLAM) algorithm to deal with these two challenges. Our innovative iequuallty-constrinne 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.
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 simple to implement, but it also be applied in online settings where new coming training data used to train models. However, while many researchers have provided solid theoretical guarantees on the convergence of SGD (Kingma & Ba Ba| (2014); Reddi al. (2018); /Sutskever 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 backpropagated, which prevents 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 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 potential way to solve deep learning problems. Here, the loss function of a deep neural network 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 al. (2016); Wang et al.) 22199) and Block Coordinate Descent (BCD) @Jinshan Zeng (018)). with empirical evaluations demonstrating good scalability in terms of the number layers and high accuracy on the test sets, especially for neural networks that are very deep, thanks to parallelism (Taylor et al. (2016); Wang jet 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. (0155). as well as allowing for complex non- smooth regularization and the constraints that increasingly important for deep neural architectures that are required to satisfy practical requirements such as interpretability, enery--fffcciene and cost awareness Carreira- Carreira-PPrpiiaan Perpinan & Wang (2014).

---

Under review as a conference paper at ICLR 2020
Table 1: Notations Used in This Paper
Notations
Descriptions
Number of layers.
Wi
The weight vector the 1-th layer.
by
The intercepi in the 1-th layer.
The temporary variable of the linear mapping in the 1-th layer.
The nonlincar activation function in the 1-th layor.
The output the 1-th layer.
The input matrix of the neural network.
V
The predefined label vector.
R( M) (WW)
The risk function in the 1-th layer.
The regularization term in the I-th layer.
The tolerance of the nonlinear mapping in the 1-th layer.
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
deep learning has rarely been explored (Wang et al. (2019); Zeng et al. (019)). 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 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 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 wrguaalty-constraaiedd problem that can be infinitely approximate to the original one. Applying this innovation to an the convexity of all subproblems, and hence easily ensures global minima, the ceqquullit-constraiii 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-ojasiewiez (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:
constraint based transformation ensures
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 novel and efficient DLAM algorithm. A quadratic approximation technique and 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 follows. In Section 2 we present the problem formulation and the new DLAM algorithm. In Section we introduce the main convergence results for the DLAM algorithm. Section 4 reports the results of the extensive experiments conducted validate the convergence and effectiveness of the new DLAM. Section Sactiion@concciin elooccuudes by summarizing the research.
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

---

Under review as a conference paper at ICLR 2020
2.1 INEQUALITY APPROXIMATION FOR DEEP LEARNING
The important notations used in this paper are listed in Table [ A typical fully-connected deep neural network consists of layers, each of which are defined by linear mapping and nonlinear activation function. A linear mapping is composed of a weight vector Wi E - where nu is the number of neurons on the (-th layer and an intercept by E IR;;; a nonlinear mapping is defined by an activation function hy(+). Given an input 4t-1 E =R= from the (1-1)-th layer, the (-th layer outputs a, = ( + bt). By introducing an auxiliary variable 2/ as the temporary result of the linear mapping, the deep neural network problem is formulated mathematically as follows:
I. Wi bi. R(21; v) + Σi_ E (W,))
Problem 1:
8.L. 21 = Waa- by (1=1, 1,.......... L. ai a;= ===h(=)[==1,.... II-
where dg = x E IRd is the input of the deep neural network, d is the number of feature dimensions, and y is predefined label vector. (( 2 0 is the risk function for the L-th layer, which is convex and proper, and ( 2 0 is regularization term on the 1-th layer, which is also convex and proper. The equality constraint a h2(21) 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 global minimum when updating žι (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 I. To do this, we introduce a tolerance E > 0 and reformulate Problem I to reach the following form: L-1
minw, minw, b.. R(21;y) Σ (((W))+ + En (a
s.t.21 = Wiap-1 + 6111-1,....
((h((2)) - 81 a S hx(2)) + Ex) is an indicator function such that the value is Of hy hz S a S (x))) c and co otherwise. For the linear constraint 2 = Waa--+ this can be transformed into a penalty term in the objective function to minimize the difference between z and Wia-i+bi The formulation is shown as follows:
minw, bi F(W. b. a) = R(21; v) - P((W))
Problem 2:
J. +E' da- W,b Σ 1-1
11 (z) - -e sh(z)+++)
The penalty term is defined as ((a W/ by 21) = (p/2) 21 Wia--1-bll3 where p > 0 a penalty parameter. W [Wi)/= b- {b] is that it allows us to project the nonlinear constraint to a convex EI-ball, thus transforming the nonconvex Problem 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 p + oo and 0, Problem 2 approaches Problem 1.
{ =
{a] 1-11 The reason for introducing
2.2 ALTERNATING OPTIMIZATION
We present DLAM algorithm developed to solve Problem 2, shown in Algorithm | Lines 4, 5, 7, and 10 update Wi, 2ú,2) and o, respectively, and the four relevant subproblems are discussed as below:
1. Update W
The variables 1, L)) are updated as follows:
W/++ <- arg minw, ((a Wi. b/ 2/) + (Wi)
Because Wi and aj-1 are coupled in o()). solving Wi requires an inversion operation of a which is computationally expensive. Motivated by deep learning Alternating Direction Method of Multipliers (dIADMM) Wang et al. (2019), we define p/++1(W, 0x as a quadratic approximation
I++1
of 6 at W which is mathematically reformulated follows BBeck & Teboulle (2009))
ptt (W da .tt.tt////// & bf + < VwraWi-W'? w// +110/+1 o (W₂ w 11//
where of+1 is a parameter vector, denotes Hadamard product (the elementwise product), and ob denotes a to the Hadamard power of and * |/ is the l norm. o is Frobenius inner product. V w = p(W/ k+1 + bft 2/) ++177 (T(( = 1..... ...,,, L)) is the gradient of Φ with regard to W/ at W Obviously, p (W+;; 01-1 (( w/. 08 2/). Rather than minimizing the
3

---

Under review as a conference paper at ICLR 2020
Algorithm DLAM Algorithm for Solving Problem 2
Require: 3. do
Ensure:
Wt, b2, 21(1 1, L)
1: Initialize P.
2: repeat
3: for to do
4: Update W using Algorithm
5: Update 6, o equation B
6: if L then
7:
Update =!" in equation
8:
else
9:
Update x+1 in oquation
10: Update 0, using Algorithn
11: end
12:
end for
13:
14:
until convergence.
15:
Outpul a,, Wi. bc: St-
original subproblem equation
1 we instead minimize the following:
W arg minw; P +1 (Wr; 0 (W;(W)
(2)
For f2( (Wi). common regularization terms like & or lg regularizations lead closed-fome solutions. As for the choice of oh++1, the backtracking algorithm is shown in Algorithm 2 Specifically, for given gh++1, we minimize equation 2 to obtain W until the condition in Line 3 is satisfied. The time complexity of Algorithm 2 is O (dd)) where is the dimension of the neurons features.
Algorithm 2 Backtracking Algorithm to update Wh++1
Require: A-1. wir,
b2. some constant y >
Ensure: 1
1: Initialize
2: updale Ç in equation where of = ax
3: while d. of) pit ((; do
4:
azy
5: update in equation where of++1 1
6: end while
7:
Ourput 0 4-
8: Ourpun W
2. Update by
The variables (1 1,... are updated as follows:
b +- arg ming, d(a W bbs =
Similarly to updating W,, we define U (br; Ls) as quadratic approximation of & at bj, which is formulated mathematically as follows (Beck Teboulle (2009))
U+++1(bn La) o(a wh+1 bf =f)) (V Vf o (b:
bt)) + (In/2)llb) bā l12-
where L, 2 is parameter and V Yo = p(b + W a k+1 =/). Here, Ls 2 p is required for the convergence analysis (Beck & Teboulle (2009)). Without loss of generality, set La p. We can now solve the following subproblem:
b + arg mins, u (bri p)
(3)
The solution to equation is: b/ - Vy0/p.
3. Update ž The variables (1 1, I.) are updated as follows:
21 lH <- arg min,, ((a Whit 11tt1 21) +T)+((((=)))+---)))))))))))))))+ - S af S sh((z)+ei)( <T) k+1 Wk+1 _8+11 .22)) R(z(:v)
k+1 t arg ming, (latt1 2
4

---

Under review as a conference paper at ICLR 2020
As when updating bi, we define V Ls) as quadratic approximation of á at of, which is formulated mathematically as follows:
Vi (=gLz) = ((a W/ b/th , +V (Z) +U,,
where L3 2 p is parameter and V V p(zz - -W d; -b++) Without loss of generality, we
set I, p. Obviously, (= p) b(a W | , Hence, we solve the problems:
z + arg min,, v/ (21 + +I(()(z)))0 -a S af Shi(z)) <t)
(4)
"L k+1 + arg min,, V2++ (2L: p) + R(2L:V)
(5)
As for 2:(1 1.. 1), the solution is
=1 k+1 + min(max य V B
where Bi+1 and + represent the lower bound and the upper bound of the set { of & (z()))))))))) equation 5 is easy to solve using the Fast Iterative Soft Thresholding Algorithm (FISTA) (Beck & Tehoulle 2009)).
Update at The variables ai(1 = 1,... L 1) are updated as follows:
A+1 + arg mino, ((a,, W - + [(hr(z) El S a S ha(z)t)) + +a1)
As when solving W the quadratic approximation of o of is defined as
of (anT)*)) = o(af W W4e (4+=))==++++++++++++++))))+ + and this allows us solve the following problem instead: of k+1 + arg minl, Ql+t1 (ar;
(V) (a)
+ || (a: - ot))2
(a;; 7 + [(Iu(()
al S hu(z) 21) + E1)
(6)
where of .f+1 is a parameter vector. Vot = IT + - = 1, L L-1)
the gradient of & with regard to a at a. Obviously, Of (at: 7 -
olat. W bf+11 2
Because (a;,7) 1 is a quadratic function with respect to aj, the solution can be obtained by of + af Vot o/T given suitable ,(*+1, Now the main focus is how to choose 7/ x+1
+++11 Similar to Algorithm 2 the backtracking algorithm for finding suitable 7 is shown in Algorithm
The time complexity of Algorithm is (dd), where d is the dimension of neurons or features.
Algorithm 3 Backtracking Algorithm to update dj
k+1
Require: of, W. + =tt 2- bf+ some constant >> 1.
of V bn - S silsstt ec. Ensure: *kt1,a .af-1.
1: Pick up such
2: while 6(8, w/ 10 a) > @t+ (0:
3: 8 1+ in.
4:
B-aaf of Vo.g/e.
5: end while
6: Output 7i R++1
7: Output of +++1 +- B.
CONVERGENCE ANALYSIS
In this section, we present the main convergence analyses for the DLAM algorithm. Specifically, Section 3.1 introduces the assumption necessary guarantee convergence. The main convergence properties of the new DLAM algorithm are presented in Section Due to space limit, the discussion on the convergence conditions of the DLAM algorithm is in Section Gin the supplementary materials.
3.1 ASSUMPTION
Firstly, we make the following assumption: Assumption (Quasilinearity). irdivation_functtonn 11(=))(1=1,;.> n) are quasilinear functions.
=
The definition of Quasilinearity is given in the supplementary material. Assumption D is a mild condition to ensure that the nonlinear constraint dj = hu(2z)) in Problem 1 is projected in convex
5

---

Under review as a conference paper at ICLR 2020
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(=L:y) and the regularization term 22 (Wi). Therefore, they can be either smooth nonsmooth: R(ZL:y) y) can be a common least square loss or cross entropy loss; (Wi) can be either & 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 [ holds, then Lemmas] 33 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
3 stated as follows:
Lemma (Sufficient Descent). For any p > O and et > O, we have
F F(W*, ,b", "=""a") - F F(W*+1 b x+1 a k-1
110 o (W 222)0211100
(0/2) E 10 of + E | | +
1=1 | (apt1 - at) 11/2 (7)
Lemma depicts the monotonic decrease of the objective value during iterations. The proof of requires Assumption [and is detailed in the supplementary materials.
Lemma I
Lemma (Convergent Sequence). (a). (Wk: bb ,z a²) and F F(Wk, .b* ,²,zh, ,at)) are convergent. That is, as l- + 0o, (wh, ,,,b""/..e "=*"a"))++ (W", "W",b bb, ,²²,,a)) and F(W*, bb. x²,,a" - F(WW, ,,",,"", aa", (b). (Wh b² z² aa)))) is bounded. That is, there exist scalars Mw.Mg, M2 and Ma such that || [|W*| || S Mw. ||b*| || s Mo. ||*|| S Mr and ||a*|| Maa
Lemma guarantees that the variable (W bb: 2", a²) is convergent and bounded. The proof of Lemma requires Lemma can be found in the supplementary materials.
Lemma 3 (Subgradient Bound). There exist C = max(pMa, pM2 + |10 (i pMM +
|10
pM2 + [10 [), some 1+1 E :8 F and 92 k+1 V F such that
|1st +| S [[][ -+11++1b 6+1 -ba 11
11), -z
1|=
Lemma ensures that the subgradient of the objective function is bounded by variables. The proof of Lemma requires Lemma aadd 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 (Convergence the Critical Point). For (W, b) in Problem 2, starting from any (WO, b Algorithm 7 converges to a critical point (W", bb"). That is, 0 E dw- F and 0 E O..F.
Proof. By Lemma 2 (w*, b²) is convergent to (W*, b²). From Lemma there exist 9i k+1 e Owe+s F and g2 E Op F such that ||g k++ + O and ||g2 1 + O as + Do. we have O E Ow- F and 0 E 0,- F. In other words, (W*, b") is critical point of F.
Theorem [ shows that our proposed DLAM algorithm converges to a critical point globally no matter what p and E are chosen. This ensures that our DLAM algorithm is parameter- choice of hyperparameters has no effect on its convergence.
free, so the
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* bbt Zt a²)), define ek minosisk Ei_ 10 I (W
w |1 (p/2) 1 -
|| + Σ | (a) - (
which reflects the convergence rate of Algorithm then the convergence rate of cg 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-an methods. All experiments were conducted on 64-bit Ubuntu 1buntu16.04 16.04 LTS with Intel(R) Xeon processor and GTX G0810 GPU.

---

Under review as a conference paper at ICLR 2020
4.1 EXPERIMENT SETUP
4.1.1 DATASET
In this experiment, two benchmark datasets were used for comparison: MNIST (LeCun et al. (1998) and Fashion MNIST (Xiao al. (2017)). The MNIST dataset has classes of handwritten-diitt
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 Europes largest online fashion platform (Xiao et al. (2017)) The Fashion-MNIS" 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-1 e was initialized as 10 and updated adaptively as follows: if R(=1; y) > 10e", g max(2e*, ,1); if ex 10R(22; y). e++1 min(E* /2, 0.01), which balances between the loss function R(21; y) and e. 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 (010)). 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 an improved version of SGD: rather than fixing the learning rate during iteration, adapts the learning rate the hyperparameter. 3) Adaptive learning rate method (Adadelta) (Zeiler (2022). As an improved version of the Adagrad, the Adadelta is proposed to overcome the sensitivity hyperparameter selection. 4) Alternating Direction Method of Multipliers (ADMM) (Taylor et al. (2016)). ADMM is powerful convex optimization method because it can split an objective function into series of subproblems, which are coordinated to get global solutions. 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 The X axis and Y axis denote the number of iterations and the logarithm of objective value, respectively. Overall, the objective value de- creased monotonically during iteration what- ever network structures and datasets we choose.
Taation UNET
MILL
Specifically, the objective value dropped tremen- dously at the early stage and then converged smoothly towards the critical point of the prob- lem. We also found that the objective value for the Fashion MNIST dataset decreased more quickly than that for the MNIST dataset.
20
40
66
300
120
340
120 120
Olgedd 500
Figure 1: Convergence curves of DLAM algorithm on MNIST and Fashion MNIST datasets for two neural network structures: DLAM algorithm converged.
4.2.2 PERFORMANCE
Figure and Figure show the curves of the training accuracy and test accuracy of our proposed DLAM algonihhm and baselines, respectively. Overall, both the training accuracy
7

---

Under review as a conference paper at ICLR 2020
68:
Sen
Tuling Acar
300
503
Adyind
13.
ADNM
ADVN
ADMM
611
DLAN
DLAN
DUAM
DLAN
30
4
x
166
30
146
28
30
66
369
120
540
60
49
86
03
3K
353
34
66
x
324
120 346
(2) Size of 100x100 on MNNST
(b) Size of 100x100 on Fashion MNIST
(6) Size of 500x500 on MNNST
(d) Size of 500x300 on Fashion MNIST
Figure 2: Training accuracy of all methods for the MNIST and Fashion MNIST datasets on two neural network structures: DLAM algorithm performed competitively.
Toc- 6.5-
SGD
520
62
63:
DUN
DLAN
DJAM
DLAM
ife 125
140
65 P2 166
15s
190
40
159
140
60 40
324
141
(A) Size of 100x100 on MNIST
(b) Size of 100x100 on Fishion MNIST
(c) Size 500x600 on MNIST
(d) Size 500x500 on Fashion MNIST
Figure 3: Test accuracy of all methods for the MNIST and Fashion MNIST datasets on two neural network structures: DLAM algorithm performed competitively.
and the test accuracy of our proposed DLAM outperformed all baselines for the MNIST dataset, while those of our proposed DL.AM algortihm performed competitively for the Fash- 0.001
MINITT
From
training samples
size
11000
44000
55000
0.0001
0.1692
0.5010
0.7164
0,9613
0,2061
0,4328
0.6951
0.9792
1,2442
ion MNIST dataset. Specifically, the curves of our DLAM algorithm soared to 0.7 at the early stage, and then raised steadily towards to
0.01
0.3334
0.6516
1.0277
1.3956
1.7783
0.4795
0.9428
1.4524
1,959
2,4410
0,7684
1 1,4810
2.2626
3.0299
3,7504
0.8 or more. The curves of the SGD-related methods, SGD, Adadelta, and Adagrad, moved more slowly than our proposed DLAM algo- rithm. The curves of the ADMM also rocketed to around 0.8, but decreased slightly later on.
Fashion MNIST dataset: From 12,000 to 60,000 training samples
12,000
24,000
36,000
48,000
60,000
0,0001
0,2500
0.3081
0.8492
1.1911
1,5092
0.001
0.2980
0.5980
0.9595
1,3265
1,6744
0.01
0,4159
0.8028
1,2787
1,7535
2.2023
0.1
0.5758
1 1.0928
1.7230
2.3261
2.9234
1.6464
2.5580
3.4492
4.2902
4.2.3 EFFICIENCY
Table 2: The relation hetween 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.
In this subsection, the relationship between run- ning time per itcration of our proposed DLAM algorithm and two potential factors, namely, the value of p. the size of training sample was ex- plored. The running time was calculated by the average of 150 iterations. The computational result for the MNIST dataset and Fashion MNIST dataset the 100 100 neural network is shown in Table 2 The number of training samples of the MNIST dataset ranged from 1 1,000 to 55,000, with an increase of 11 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 p 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 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 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 rerl-world datasets demonstrate the convergence, effectiveness, and efficiency of our DLAM algorithm.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Armin Askari, Geoffrey Negiar, Rajiv Sambharya, and Laurent El Ghaoui. Lifted neural networks. arXiv preprint arXiv: 100.005205.. 2018.
Amir Beck and Mare Teboulle. A fast iterative shrinkage-thresholdnng algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-202, 2009.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010, pp. 177-186. Springer, 2010.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Miguel Carreira-Perpinan and Weiran Wang. Distributed optimization of deeply nested systems. In Artificial Intelligence and Statistics, pp. 10-19, 2014.
Francois Chollet. Deep learning with python. Manning Publications Co., 2017.
Anna Choromanska, Sadhana Kumaravel, Ronny Luss, Irina Rish, Brian Kingsbury, Ravi Tejwani, and Djallel Bouneffouf. Beyond backprop: Alternating minimization with co-activation memory. arXiv preprini arXiv: 1806.09077 2018.
Matthicu Courbariaux, Yoshua Bengio, and rean-Pierre David. Binaryconnect: Training deep neural networks with binary weights during propagations. In Advances in neural information processing systems, pp. 3123-3131, 2015.
Wei Deng, Ming-Jun Lai, Zhimin Peng, and Wotao Yin. Parallel multi-block admm with (1/k) convergence. Journal of Scientific Computing, (1nm)nng7111)))))) 71(2):712-736, 2017.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal Machine Learning Research, 1201u))2121-2159, 2011.
Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Progrumming, 156(1 (5((1-2):59999 2016.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256 2010.
Tim Tiz-Kit Lau Shaobo Lin Yuan Yao Jinshan Zeng, Shikang Ouyang. Global convergence in deep learning with variable splitting via the WrXiv:1833.00225 2018.
property. arXiv preprint
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 11X1v:1412.6980, 2014.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pp. 1095-1105. 2012.
Tim Tiz-Kit Lau, Jinshan Zeng, Baoyuan Wu, and Yuan Yao. A proximal block coordinate descent algorithm for deep neural network training. 2018.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, (0(1)):277-23222 1998.
Andrew L. Maas, Awni Y Hannun, and Andrew Y Ng. Rectifier nonlinearities improve neural network acoustic models. 30(1):3, 2013.
Tomáš Mikolov, Martin Karafiát, Lukášs Burget, Jan Černocký, and Sanjeev Khudanpur. Recurrent neural network based language model. In Eleventh Annual Conference of the International Speech Communication Association, 2010.
Boris T Polyak. Some methods of speeding up the convergence iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.

---

Under review as a conference paper at ICLR 2020
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018. URL /RL/aatpss://ppeeeeeaa met/Eot Etw.://ounnuddaa------a---
Herbert Robbins and Monro. *a stochastic approximation method, annals math. Statistics, 22: 400-407, 1951.
R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
David E Rumelhart, Geoffrey E Hinton, and Ronald Williams. Learning representations by back-propagating error.. nature, 323(688)):333, 1986.
lyya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pp. 1139-1147, 2013.
Gavin Taylor, Ryan Burmeister, Zheng Xu, Bharat Singh, Ankit Patel, and Tom Goldstein. Training neural networks without gradients: A scalable admm approach. In International Conference on Machine Learning, pp. 2722-2731, 2016.
Tieleman and G Hinton. Divide the gradient by running average of its recent magnitude. coursera: Neural networks for machine learning. Technical report, Technical Report. Available online: https://zh. coursera. wtgp/learnheeuralttwoook///eee wttps////ecceee//////////nnooo
(accessed on 21 April 2017).
Junxiang Wang, Fuxun Yu, Xiang Chen, and Liang Zhao. Admm for efficient deep learning with global convergence. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledgee Discovery Data Mining, KDD '19, pp. 111-119, New York, NY, USA, 2019. ACM. ISBN 978- 1-450036200--6 doi: 10.1 00.1145/3292500.33309090
URL //do: amm org/10
1145/32925 3330936
Yu Wang, Wotao Yin, and Jinshan Zeng. Global convergence of admm nonconvex nonsmooth optimization. Journal of Scientific Computing, pp. 1-35, 2015.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms, arXiv preprint arXiv:1708.07747, 2017.
Yangyang Xu and Wotao Yin. A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM Journal on imaging sciences, 6(3):1758-178)) 2013.
Babak Zamanlooy and Mitra Mirhassani. Efficient vlsi implementation of neural networks with hyperbolic tangent activation function. JEEE Transactions on Very Large Scale Integration (VLSI) Systems, 22(1):39-48, 2014.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5700 2012.
Jinshan Zeng, Shao-Bo Lin, and Yuan Yao. A convergence analysis of nonlinearly constrained admm in deep learning. arXiv preprint arXi::1902.02066 2019.
Guoqiang Zhang and W Bastiaan Kleijn. Training deep neural networks via optimization over graphs. arXiv preprini arXiv: 0e02:0302000 2017.
Ziming Zhang and Matthew Brand, Convergent block coordinate descent for training tikhonov regularized deep neural networks. In Advances in Neural Information Processing Systems, pp. 1721-1730, 2017.
Ziming Zhang, Yuting Chen, and Venkatesh Saligrama. Efficient training very deep neural networks for supervised hashing. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 1487-1495, 2016.
10

---

Under review as a conference paper at ICLR 2020
Appendix
A DEFINITIONS
First, the definition of Fréchet subdifferential is shown follows (Rockafellar & Wets (2009)) Definition 1 (Fréchet Subdifferential). For each Iι dom(u1), the Fréchet subdifferential of at Fi, which is denoted as (un(x)) ). is the of vectors v, which satisfy
lim inf (un (122 un (x - v² (x2 x1 ))/ [2 x1 0.
2248, #2
The vector Öuy(1s) is a Fréchet subgradient.
Then the definition of the limiting subdifferential, which is based on Fréchet subdifferential, given in the following |Rockafellar & Wets (2009)):
Definition 2 (Limiting Subdifferential), For each E dom((u2), the limiting subdifferential (or subdifferential) of Ug
Ouz(x) -vv1l3 + I. s.t. uz(x²) uz(x),
N E Quz Oouz(""), --
where x² is sequence whose limit is x and the limit of u2 uz(x*) is u2(2),, we is a sequence, which Fréchet subgradient of u2 xt and whose limit v. The vector v E @u2(z) is limiting subgradient.
Specifically, when 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, 0R and (1 1,...,,,000.. ,n) are nonempty, and the limiting subdifferential of defined in Problem (Xu & Yin (0013))
b, = X V&F x 0,F X O.F
where x means the Cartesian product.
Next, recall the definition of quasilinearity (Boyd & Vandenberghe (000
Definition 3. A function fxx is quasiconver if for any sublevel set S,(f) [x]f(x) aa is convex set. Likewise, A function f(x) is quasiconcave if for any supertevel set = z a} is convex set. A function (x) is quasilinear if it is both quasiconvex and quasiconcave.
B PRELIMINARY LEMMAS
In this section, give preliminary lemmas which are useful for the proofs of three properties.
The proofs
of Lemmas 4 and 5 both require Assumption 0 The proof of Lemma requires Lemmas
4 and
To
simplify the notation, st = ([W*+1) - (W+)
k+1
[10+
+1 H (bt) Z
kt (1z) H (2, k and a
k+1 k+1 = (la 1 {a, 44-1411 (111).
Lemma equation holds if and only if there exists s (00((w)+1) the subgradient of (W(Wltt)) such that
V Vww + of+1 a (W - w/) +
Likewise, equation 4 holds if and only if there exists E (2((11(2) +11 - S at <hu(ztt)) + Ei) such that
V o p(= 2t) +
equation 5 holds if and only if there exists E 0n( ;,) y) such that
V 6 + p(z zt.) + u 0
equation 6 holds and only there exists E 00 (1) - 5 oft < hh(zttt) E1) such that
V. p(a) 6+1 at) +v=0
Proof. These can he obtained by directly applying the optimality conditions of equation equation equation and equation respectively.
11

---

Under review as a conference paper at ICLR 2020
Lemma 5. For equation f equation Fand equation if La p and La 2 p.then the following inequalities hold:
(b) [a) 2 + w/+ bb ) ( T.,) 2 o(a wh+ , b , +
(8)
(9)
Proof. Because Φ(a-11, Wi, bt, 21) is diffcrentiable continuous with respect to by and 2 with Lipschitz cooffi- cient (the dcfinition of Lipschitz differentiablity can be found in (Beck & Teboulle (eboolleg(000)))), we directly apply Lemma 2.1 in (Beck& & Teboulle 2009)) to & to obtain equation 8 aand equation 9 respectively.
Lemma 6. It holds that for Vk E N and = 1,2,
F F(W hil Si- Si ) F
(W wh
2 110 oW - 1/)
(10)
F(W gi : AHl Atd Atl
3 ((-) F(W
gi
2 (p/2) - b/ 11.
(11)
F(W gi b :4gi-1: ( - P(
ful kil
P
2 2
(12)
F( b ,āg
J+l
k+]
F(
Rz .asi)
Atl 641
2 |
(a)
ke1 1111/2
(13)
Proof. Essentially, all inequalities can be obtained by applying optimality conditions of updating W/ 2 and af+1 respectively. only prove equation 10 and equation 12 since equation 13 and equation 11 follow the same routine of equation [0] and equation 12 respectively.
Firstly, we focus on proving equation I0 The stopping criterion of Algorithm 2 shows that (w-tt(tt+,
(a k+1 wh+t +) <
(14)
Because (Wi) is convex, according to the definition of subgradient, we have
(u(W)) 2 (W + s [W? - -w/+t)
(15)
where s is defined in the premise of Lemma 4 Therefore, we have
F(W hi1 ااLي a - b 2gLn aLL) SLn,
= s(attl. w bf 2t) + 2. - slatt1. wi+1, =()
(wF++) (Definition of F in Problem 2)
2 su(")) (w (V o) (w w/')
110tt2 o (W+++ |1/2(1 equation 14
/
s(w!. -W(+1) (V )) (WA++1 W
110 (W/++1 - w || ( equation 1.5
= (s+ Vo (W: - W/ k+ |10 o "w##h= 02
| (w -
02 1/2 (Lemma
Secondly, we focus on proving equation 12 For < L, because [(h)(z)) - 82 af < h1(z)) + +x) is convex with regard to = according to the definition of subgradient, we have
[(hr(2)) < af < he()))+))
21((1(2 |1t ) at <hazt 111 ) +ex)++++ + -2
(16)
12

---

Under review as a conference paper at ICLR 2020
where is defined in Lemma 4
F(Wer bii Zgi-1 F(W bii 2gi ;
= o(aft wit,, bftt = (()()((()))) sh(
Aa ttl Wh 1/
[((( s (2) )e))
(Definition of F in Problem 2)
2 2-(44 - = (0/2)|| ابع -
+I(h(z)) - - < +Ei)
[(1( k+1 1 - S <at v hu(2 hi1 + equation 9
2 -V (E) k+ zx - (p/2))l t 2 11
+r (=f 21 * (equation 16
(V of) (=)
k+1 = (p/2)]|= k+1 =
+ - 2t) (Temmaa + (V uo p( h-1 -x =)²)²² (=t
= (p/2)||z/ = 112.
For L, the same routine applies.
C PROOF OF LEMMA
Prouf. This can obtained by adding equation 10 equation equation 13 from = too =
IT and equation
12 from = 1 to = and
D PROOF OF LEMMA 2
Proof. (a). By Lemma F(W*, bb zt, a*) is non non-increasing. Also, F(W* bb, b²,"",,,,," ,²,aat 2 0. According to the
monotonic sequence theorem, F(W by a²) is convergent.
Next, we take the limit of Incquality 7 to obtain
lim (F(W", bt 1 a²) F(W*+1 ba b
++1 a +
lim
110lt3 (W/ 1
(p/2)
|B bt (p²+ Σne
| 1+z -
1=1 ||=| (at at )²² ||1/2
0
Because F(W*: b² x" a* is convergent, (Fok- , b² x², a² F(W 2
xt =-1))) 0.
Therefore, we have
Σ
110 (W/ - w/' w//)0'11//
(p/2) |BA 1/ 112 (p/2) Σ
|| 11141_10
Σ 1=1 ||
(a 44 )² 111/2 0
Since 0/:41, 7/ .+1 > O. we obtain as l + co, | W - O. ||b 8/ || - 0. || 2t || - 0. and ||a
at' I1 - This shows that (W* b² b²,z" a²) converges to a point (W" b², b²,z", Be- cause F is continuous, limg (W* k b² a²t olime W lim by limp- z., lime- a² F(W", P((W"bb,zz zz, 2=,aaa) a²).
(b). Because (wi b zt a²) is convergent and convergent sequence is bounded, therefore it is also bounded.
13

---

Under review as a conference paper at ICLR 2020
E PROOF OF LEMMA 3
Proof. As shown in Wang et al. (2155 ; Xu & Yin 2013).
Owi+1 F (0 w F) (0 we F) (0 F).
bett F= Vitt F x W x x Ve
12
where denotes Cartesian Product. For W
= (W, waw 1a Whit 1/41 ,2 (
(Definition of F in Problem 2)
V Wuptrolatti. wt+! ,uft : )
-Vazola 4-1 W bi, at - tf (WHt1 W/)
aai(w, ) + V Vw ( w.,, 14
+ft (W, -W")
=((W wt jo
k+1 (o (o==)) p0b - bb (att)))
p( - (a of (W w/))
(W:+t) + V V k+1 W 2t)
+ of+ (W/+1 - -W²)
On one hand, we have
ll Wr)a 6+1 " + plb +1 b/)
p( (a 0 (W - WW
ol - -W/"a |- pl((b (a)
+ +=] -2 "1 [W"] incquality)
ollW - w/ - pl6 - ||
+ p||x|11 - +||||| -
|10
w!ll
Cauchy-Schwarz inequality)
$ pMa - 8/ pMM
+ II
(pM2 |10| | W | ([emma 2
On the other hand, the optimality condition of equation equation[lyields yiiilss
E (W/ + V w w ot " o(W/41-WW
Therefore, there exists ,²,²² E 0 w +1 F such that
l || S pMallbff+ - of + palll 2t1
+ (pM, + -10 IDI - -W'll
This shows that there exists of k+1 = o x 1+1 x ... x si.t." E Owii1 F and C' = max(pMa, +
||0*+*1, [1, pM² + |10] ||,
M + |10 [I) such that
l1 +1+ '11 S C([[w++ w1 + |[b b²1l
+ ||z ++1 z²())
14

---

Under review as a conference paper at ICLR 2020
Similarly, for t/+
V. 14+1 Veptolaat whit oft .
Vywolaat 4H w "f"" (z(
Vy0lo
1 W be =t) p(b) 6b¹)
(V w 6/ = + p(b b1)) = by
the optimality condition equation 3)
Therefore, there exists $2.1
V of F such that
11 1
p 2||2// 21
This shows that there exists J2
92.1
k++1
x 92.2
12.L Vpe+i F such that
11.3 + = p||z +1 z²t
F PROOF OF THEOREM 2
Proof. To prove this theorem, we will first show that cs satisfies two conditions: (1). c 2 c++1. (2). Ex= Ck is bounded. We then conclude the convergence rate of o(1/k) based on these two conditions. Specifically, first, we have
minos
10 (W7+t - w/) 111/22
+ (p/2)
16 + Ei1 || 4 2
(attt at) (1112)
2 minlssst+11 - |10 o (W - -w)) 1///2
(p/2) |b b112 (p/2) Σ' 2
#1 (a (11/))
Ck+11 Therefore O2 satisfies the first condition. Second,
minogisa E 1. 110/t (Witt - 11/2
11b, 1 -b + E1 11 21
+
|| o (att) - at) 11/22)
$ Σ
110 (W w
+(//2) EL 11b, 11 (p/2) Σ1 -
|| -
117 (a at) ) (
S F(W". b". 2.......... a²) F(W", ,'',"", 2". (Lemma
So EIe Ck is bounded and cu satisties the second condition. Finally. it has been proved that the sufficient conditions of convergence rate o(1k are: (1) cs 2 ck+1. and (2) > k is bounded. and (3) c 2 0 (Lemma 1.2 in (Deng et al. (2017)). Since we have proved the first two conditions and the third one 2 0 is obvious, the convergence rate of o(1/k) is proven.
15

---

Under review as a conference paper at ICLR 2020
G DISCUSSION
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. (Gaadimi & Lan (0166) 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 (Chadimi & Lan (2016). our DLAM allows for non-smooth functions such Relu. Therefore, 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 ((1/k) (Zeng
2019)), which is similar to our convergence results. However, the ADMM requires activation functions ()) to be twice-differentiable bounded, whereas our DLAM allows hy (() to be non-smooth. This also shows that the assumptions of our DLAM are more general than those of the ADMM.
H RELATED WORK
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 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 (195T)). The famous back- propagation algorithm was introduced by Rumelhart et al. (humelhart et al. (1886). Many variants of SGD methods have since been presented, including the use Polyak momentum, which accel- erates 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. (201T), RMSProp (Tieleman & Hinton), Adam (Kingma & Ba ))144) and AMSGrad (Reddi et al. (0088)
Alternating minimization methods for deep learning: Previous work on the application of alter- nating 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 ap- plications. For example, Taylor et al. and Wang al. presented an Alternating Direction Method of Multipliers (A (ADMM) algorithm to transform a fully-comnected neural network problem into an equality-constrainee problem, where many subproblems split by ADMM can be solved parallel (Taylor et al. (2016); Wang al. 2219)), 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 graph (Zhang & Kleijn (2017) and Askari et al. introduced a new framework for multilayer feedforward neural networks and solved the framework using block coordinate descent (BCD) methods (Askari et al. (2018)) Others have proposed novel alternat- ing 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. (Carreira-Perpinan
and Lau et al. both proposed BCD algorithms, proving its convergence via the oujsyka-ojasiewiiz (KL) property (Jinshan Zeng 20188 Lau al. (2018), while Choromanska et al. proposed BCD algorithm for training deep feedforward neural networks based on the concept of co-activation memory (Choromanska 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.
16


Reviews:
[{"review_id": "HyxgOkVPcS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The motivation for this paper is as follows: \n\nWhy SGD:\n1. Easy\n2. applied in online settings \n\nHowever:\n1. 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\n2. Suffer from gradient vanish\n3. sensitive to the input\n\nThe 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)\nHowever, these methods suffer from problems:\n1. Convergence properties are sensitive to penalty parameters.\n2. Lack of unified theoretical frameworks with general conditions. (Not fully proved the\nconvergence. Most of the work is based on some assumptions)\n\n\nMain Assumption: Activation functions are quasilinear functions. \n\n\npros (+):\n1. Generic, easy to extend it to convolutional layers and recurrent layers.\n\n2. Transform the Neural network optimization problem into inequality constrained\nproblem (new point of view)\n\n3. Ensure convexity of subproblems. (quadractic approximation of activation function).\n4. Ensure global minima, and converges to the critical point (where 0 is in the set of\npartial differential of F(F(W,b,,z,a) is the augment loss function) with respect to W*,\nand set of partial differential of F with respect to b*).\n5. The convergence rate is O(1/k), k is the number of iterations of updating (W,b,z,a).\n6. inequality-constraint prevents the output of a nonlinear function from changing much\nand reduces sensitivity to the input.\n7. Matrix inversion is avoided by quadratic approximation\n8. No need strict and complex condition, such as KL properties to prove convergence.\nInstead, this algorithm needs simple and mild conditions to guarantee convergence,\nand cover most of the loss function and activation functions.\n9. The choice of hyperparameters has no effect on convergence.\n10. Much better performance on MNIST\n\ncons(-):\n1. penalty parameters need to be tuned as ADMM does.\n\n2. The regularizations $\\omega$ is l1 and l2, otherwise, it will not be closed-form\nsolutions. The regularization like dropout, batch-norm can not be added into this algorithm.\n\n3. 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).\n\n4. 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. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HyxSFgn2YS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\n1. DLAM follows dlADMM in Wang et al. (2019), and the only difference between Problem 2 and Problem 2 in Wang et al. (2019) is the indicator function rather than squared l2 loss for a_l. The update is quite similar with dlADMM, with the same convergence result. The technical contribution is incremental.\n\n2. The author claim that Problem 2 is multi-convex. However, I did not see why this is a good point. First, multi-convexity does not imply that gradient update can find global optimum. Second, the results presented here is standard, i.e., O(1/k) convergence to a critical point, which does not show any advantage over Problem 2 in Wang et al. (2019).\n\n3. The experiments are also questionable.\na) The most related dlADMM (Wang et al. (2019)) is not compared here, which can not empirically show why Problem 2 here is a better choice than dlADMM.\nb) The accuracy on MNIST is pretty low. In Wang et al. (2019), the results are about 0.9x, here only 0.7x. Why? And such low accuracy on MNIST seems not convincing to claim \"convergence\".\nc) Please compare with Adam.\nd) What is the ADMM update in the experiments? Directly use ADMM on Problem 1 or 2?\n\n4. The term \"global convergence\" seems misleading. It is not convergence to global optima.\n\nOverall, I found the formulation quite similar with dlADMM (Wang et al. (2019)), the contribution is incremental, the analysis did not show why multi-convex formulation Problem 2 is good (the rate is the same as standard results), and the experiments are questionable and also did not show advantages of the formulation and proposed method.\n\n\n=======Update=======\nThanks for the rebuttal. I keep my rating since there is no updated version of the paper to address my concerns.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new learning algorithm for deep neural networks that first reformulates the problem as a multi-convex and then uses an alternating update to solve. The reviewers are concerned about the closeness to previous work, comparisons with related work like dlADMM, and the difficulty of the dataset. While the authors proposed the possibility of addressing some of these issues, the reviewers feel that without actually addressing them, the paper is not yet ready for publication. 
Decision: Reject