Title: AN EFFICIENT HOMOTOPY TRAINING ALGORITHM FOR NEURAL NETWORKS

Abstract: We present a Homotopy Training Algorithm (HTA) to solve optimization problems arising from neural networks. The HTA starts with several decoupled systems with low dimensional structure and tracks the solution to the high dimensional coupled system. The decoupled systems are easy to solve due to the low dimensionality but can be connected to the original system via a continuous homotopy path guided by the HTA. We have proved the convergence of HTA for the non-convex case and existence of the homotopy solution path for the convex case. The HTA has provided a better accuracy on several examples including VGG models on CIFAR-10. Moreover, the HTA would be combined with the dropout technique to provide an alternative way to train the neural networks.
By defining
we have
we conclude that
or
By summing up k from 0 to n,

1. INTRODUCTION:

Deep learning methods, as the rising star among all machine learning methods in recent years, have already had great success in many applications. Many advancements Cang et al. (2018) ; Cang & Wei (2018) ; Yin et al. (2018; 2016) on deep learning have been made in the last few years. However, as the size of new state-of-the-art models keep growing larger and larger, they rely more and more heavily on efficient algorithms for training and making inferences from such models. This clearly puts strong limitations on the application scenarios of nerual netowrks on roboticsKonda et al. (2012) , auto-pilot automobiles Hammerla et al. (2016) , and aerial systems Maire et al. (2014) . At present, there are two big challenges in fundamentally understanding deep neural networks:

• How to efficiently solve the highly nonlinear and non-convex optimization problems that arise during the training of a deep learning model? • How to design a deep neural network structure for specific problems?

In order to solve these challenges, in this paper, we will present a new training algorithm based on homotopy continuation method Bates et al. (2011; 2008) ; Morgan & Sommese (1987) which has been successfully used to study nonlinear problems such as nonlinear differential equations and optimizations Hao et al. (2012) ; Hao & Harlim. In order to tackle the nonlinear optimization problem in neural networks, the homotopy training algorithm is designed and shows efficiency and feasibility for both convolutional and fully connected neural networks with complex structures. The idea of the HTA is to start with a simplified optimization problem and construct a continuous path to the original problem. Specifically, let's consider the following general optimization problem

min θ f (θ) where θ ∈ R n .

(1)

We then divide θ in two groups, namely,

θ = θ 1 ∪ θ 2 , where θ 1 ∈ R n1 and θ 2 ∈ R n2 (n 1 + n 2 = n).

(Although that it can be easily extended to any m decompositions, we use m = 2 as an illustration of the HTA idea.) Then we first solve the following decoupled simplified optimization problems

min θ1 f (θ 1 , θ2 ) and min θ2 f ( θ1 , θ 2 ) (2)

where θ = θ1 ∪ θ2 is a random chosen point in R n for instance we choose θ = 0 in the dropout Srivastava et al. (2014) . Second we define the following homotopy function

EQUATION

where Θ = (θ, η) and L ∈ (0, ∞) is the homotopy parameter. When L → ∞, we have two decoupled optimization problems which we have already solved in the first step; when L → 0, we recover the original optimization by forcing θ = η. By gradually increasing parameter L, we are able to construct a continuous path Θ(L)between two decoupled low-dimensional optimization problems and the original optimization problem.

Remark The HTA can be reviewed in point view of nonlinear equations by considering the necessary condition of the optimization problem (1):

H(Θ, L) = ∇ θ f (θ) η -θ 1 L + L      ∇ θ2 f (θ) θ 1 -θ1 ∇ η1 f (η) η 2 -θ2      .

When L is large, θ 2 and η 1 can be solved by ∇ θ2 f (θ) = 0 and ∇ η1 f (η) = 0 respectively. When L is small, we have the solution of ∇ θ f (θ) = 0 by the diagonal homotopy θ -η = 0. This technique has been widely used in solving systems of nonlinear equations especially for polynomial systems Bates et al. (2008) ; Wampler & Sommese (2005) . Since the θ is randomly chosen, the universal approximation theory Park & Sandberg (1991) can guarantee that the random point θ in R n is always connected to the solution of ∇ θ f (θ) = 0. In another word, the solution path Θ(L) always exists or the probability that Θ(L) is not connected is zero Wampler & Sommese (2005) .

2 APPLICATIONS OF HTA ON NEURAL NETWORK

2.1. CONVOLUTIONAL NEURAL NETWORKS:

In this subsection, we will specify the variable θ and the objective function f (θ) of ( 3) in the convolutional neural network (CNN) setup. Definition 2.1. Suppose we have two tensors, A l×m×n = (a i,j,k ) 1≤i≤l,1≤j≤m,1≤k≤n ,

B c×l×m ×n = (b h,i,j,k ) 1≤h≤c,1≤i≤l,1≤j≤m ,1≤k≤n

, where c, m, n, m , n , l ∈ N and m ≤ m, n ≤ n. The convolution of two tensors is defined by the following:

EQUATION

where B is called the convolutional kernel.

Then with the input x and the output y, the CNN is written as

y(x; θ) = σ(σ(• • • σ(σ(x * W 1 + b 1 ) * W 2 + b 2 ) • • • + b n-1 ) * W n + b n ) (5)

where W i ∈ R ci,li,mi,ni and σ is the activation function. Then we have θ 3) is defined by the cross entropy loss function Goodfellow et al. (2016) and defined as L(x, y) = -x(y) + log( j e x [j] ). Due to the random algorithms in machine learning Bottou (2010) ; Kingma & Ba (2014) , the homotopy function in (3) can be rewritten as H(Θ; ξ, L) where ξ is a random variable due to random algorithms.

= {W i , b i } n i=1 which can be easily divided into two subgroups θ j = {W ij , b i } n i=1 where W ij ∈ R c i 2 ,li,mi,ni . The objective function f (θ) in (

2.2. FULLY CONNECTED NEURAL NETWORKS:

Similar to the CNN, a fully connected neural network with n hidden layers is written as

EQUATION

where

W i ∈ R n×di , β i ∈ R di

, n is the dimension of the input x and d i is the width of the i-th layer.

Then we have θ = {W i , b i } n i=1 which can be easily divided into two subgroups

θ 1 = {W i , b i } n/2 i=1 and θ 2 = {W i , b i } n i=n/2+1

. Or we can use the dropout technique to randomly split θ as θ 1 and θ 2 . Similarly, the homotopy function in (3) can be also rewritten as H(Θ; ξ, L) due to the random algorithms Bottou (2010) ; Kingma & Ba (2014) .

3. THEORETICAL ANALYSIS:

In this section, we will provide a theoretical analysis of the HTA by using stochastic gradient scheme to solve (3) for each L. We redefine our stochastic gradient scheme for the homotopy process as

EQUATION

where G(θ; ξ, L) := ∇ θ F (θ; ξ, L), γ k is the learning rate, L 0 = M , L k 0 and M is a given large number. Then we consider the expectation of the homotopy function as E ξ (H(θ; ξ, L)), for simplicity, and denote E ξ [H(θ; ξ, L)] as g(θ; L). 7) is run with a step size sequence satisfying

3.1. CONVERGENCE:

EQUATION

then we have

EQUATION

Proof. First, we prove the Lipschitz-continuous objective gradients condition Bottou et al. (2018) , which means that g(θ; L) is C 1 and ∇g(θ; L) is Lipschitz continuous:

EQUATION

we have that ∇ θ g(θ, L) is continuous or that g(θ; L) ∈ C 1 .

• ∇g(θ; L) is Lipschitz continuous. Since ∇ θ g(θ; L) = E ξ (∇ θ H(θ; ξ, L)), we only need to prove E ξ (∇ θ L(y(x ξ ; θ), y ξ )) is Lipschitz continuous. In fact

EQUATION

we will show that ∇ x L(y(x ξ ; θ), y ξ ) and ∇ θ y(x ξ ; θ) are bounded and Lipschitz continuous. Since that both σ(x) = 1 1+e -x and σ (x) = σ(x)(1-σ(x)) are bounded and Lipschitz continuous, and that {θ k } is in an open set (assumption of Theorem 3.1), ∇ θ y(x ξ ; θ) is bounded and Lipschitz continuous. (x ξ is bounded because the size of our dataset is finite.) By differentiating L(x, y), we have

EQUATION

where δ is the Kronecker delta. since 

EQUATION

EQUATION

Therefore

∇g(θ k ; L) T E ξ k [G(θ k ; ξ k , L)] = ∇g(θ k ; L) T •∇g(θ k ; L) = ∇g(θ k ; L) 2 2 ≥ u ∇g(θ k ; L) 2 2

(15) for 0 < u ≤ 1. On the other hand, we have

E ξ k [G(θ k ; ξ k , L)] 2 = ∇g(θ k ; L) 2 ≤ u G ∇g(θ k ; L) 2 2 (16) for u G ≥ 1. c. Since that ∇H(θ k ; ξ k , L) is bounded for a given L, we have E ξ k [ ∇H(θ k ; ξ k , L) 2 2 ] is also bounded. Thus V ξ k [G(θ k ; ξ k , L)] := E ξ k [ G(θ k ; ξ k , L) 2 2 ]-E ξ k [G(θ k ; ξ k , L)] 2 2 ≤ E ξ k [ G(θ k ; ξ k , L) 2 2 ], (17) which implies that V ξ k [G(θ k ; ξ k , L)] is bounded.

We have checked assumptions 4.1 and 4.3 in Bottou et al. (2018) . By theorem 4.10 in Bottou et al. (2018) , with the diminishing stepsize, namely,

EQUATION

the following convergence is obtained

EQUATION

)

3.2. EXISTENCE OF SOLUTION PATH θ(L) FOR THE CONVEX CASE:

Second we explore the existence of solution path θ(L) when t varies from M to 0 for the convex case theoretically. This is quite difficult for the non-convex case although we may find it numerically. However, theoretical analysis of the convex case would also give us some guidance on how the HTA obtains an optimal solution for L = 0. Theorem 3.2. Assume that g(•, •) is convex and differentiable and that G(θ; ξ, L) ≤ M 0 . Then for stochastic gradient scheme (7), we have

EQUATION

where θn =

n k=0 γ k θ k n k=0 γ k and Ln = n k=0 γ k L k n k=0 γ k .

Proof.

E[ θ k+1 -θ L k+1 * 2 ] = E[ θ k -γ k G(θ k ; ξ k , L k ) -θ L k * 2 ] -2E[ θ k -γ k G(θ k ; ξ k , L k ) -θ L k * , θ

and assuming that

EQUATION

where D = θ 0 -θ 0 * . Dividing 2 n k=0 γ k on both sides, we have

1 n k=0 γ k n k=0 γ k E[g(θ k ; L k ) -g(θ L k * ; L k )] ≤ D 2 + M 2 n k=0 γ 2 k + n k=0 A k 2 n k=0 γ k ≤ D 2 + M 2 n k=0 γ 2 k + A 2 n k=0 γ k .

According to the convexity of g(•; •) and Jensen's inequality Jensen (1906) ,

EQUATION

where θn =

EQUATION

We choose γ k such that

EQUATION

)

Because L k 0, g(•, •) is continuous and

EQUATION

which implies that lim 

EQUATION

where

EQUATION

)

The function has roughly 5 n local minima in the region {|x i | < 10} and a unique global minimum located at x i = 1, i = 1, • • • , n. (See Figure 4 .1 for an illustration of n = 2.)

The idea of the homotopy setup of this problem is splitting the n dimensional optimization problem into two n/2 dimensional problems which can be optimized separately and are tracked to an optimal of solution of f (x) with respect to the homotopy parameter L. Then the objective function of the homotopy method is written as follows:

EQUATION

EQUATION

(x 0 1 , • • • , x 0 n 2 ) ∈ R n 2 , (y 0 n 2 +1 , • • • , y 0 n ) ∈ R n 2

are fixed and chosen based on the initial guess. When L is large, F is equivalent to optimize min

EQUATION

which can be solved separately. When L becomes small, the last term of (35) forces x and y to be equal. Then F (x, y; L) is equivalent to optimizing f (x) which is the original n-dimensional optimization problem. Therefore F (x, y; L) connects two optimization problems by gradually decreasing penalty factor L and builds a continuous path between the decoupled systems and the original optimization function f (x). In this paper, we developed a homotopy training algorithm for solving the optimization problem arising from neural networks. This algorithm starts from decoupled low dimensional systems and gradually transforms to the coupled original system with complex structure. Then the complex neural networks can be trained by the HTA with a better accuracy. The convergence of the HTA for any given L is proved for the non-convex optimization. Then existence of solution path θ(L) is demonstrated theoretically for the convex case although that it exists numerically in the non-convex case.

Several numerical examples have used to demonstrate the efficiency and feasibility of HTA. The application of HTA to VGG models on CIFAR-10 provides a better accuracy than the traditional method. Moreover, the HTA method would provide a new way to couple with the dropout techniques to improve the training accuracy which we will explore in the future.

:



Figures and Tables:

OF THE HTA FOR ANY GIVEN L IN THE NON-CONVEX CASE Theorem 3.1. (Nonconvex Convergence) If {θ k } is contained in a bounded open set, supposing that (

Figure 1: Two-dimensional highly non-convex function

Figure 2: Comparison of error rate of VGG13 between HTA and the traditional method.

Figure 3: The performance of the HTA on the CNN part of vgg11 (left) and vgg13 (right) and comparisons with the traditional method

According to our theorem assumption, {θ k } is contained in an open set which is bounded. Since that g is continuous, g is bounded;b. Since that G(θ k

Table content: <table><tr><td>∂x k which implies that ∂</td><td>e x i</td></tr></table>

Peer review (iclr2020):
Summary This paper proposes an algorithm to address the issue of nonlinear optimization in high dimensions and applies it to convolutional neural networks (VGG models) on CIFAR 10. They show 11% relative reduction in error for this particular task with this particular network. In addition, they prove additional theoretical results on the convergence of SGD using their method in the convex case as well as convergence of SGD to a stationary point in the nonconvex case when the homotopy parameter is fixed which is not done in practice. Given an optimization problem, their method first solves multiple independent lower-dimensional optimization problems each with a subset of the parameters and then optimizes a new objective function controlled by a monotonically decreasing parameter L that interpolates the original objective function and the previously-solved lower dimensional problems. L can be seen as a regularization parameter that is gradually decreased as we optimize the new optimization function. When L = 0, we recover the original optimization problem. The authors prove that (1) SGD with their procedure will find a stationary point under the Robbins-Monro conditions for a fixed L and (2) SGD with their procedure will converge for convex problems as L is decreased to 0. Decision and reasoning This paper should be rejected because (1) the proposed algorithm attempts to address the original issue of high dimensional nonlinear optimization of neural networks but violates the algorithm*s assumption in practice, (2) the empirical evaluations are lacking - having only evaluated their method on a toy problem with up to only 6 dimensions and a relatively simple image classification task, and (3) the assumption of fixing the homotopy parameter in the theorem on the non-convex case directly violates the intention of the algorithm. Regarding (1): The proposed procedure requires initializing L at a large value and reducing L towards 0 in order to recover the original optimization problem. However, in practice for CIFAR 10, the authors initialize L to be 0.01 and gradually reduces it to 0.005 which is hardly the original intent of the algorithm. There is also no demonstration whether or not this gradual reduction in L actually has an effect on the optimization of the new objective function. For example, since the start and end values of L are similar, will we get similar results if we simply fix L to be 0.005 or 0.01? The authors also show that their method outperforms a quasi-newton method by combining the optimization with their procedure on a non-convex example by Chow et al. 2013. However, this example only goes up to n=6 dimensions, which is hardly comparable to the original problem of high dimensional non-convex optimization that this paper sought to address. Regarding (2): The authors evaluated their procedure on CIFAR10, a relatively simple image classification task that modern neural networks can solve easily and is not representative of the types of nonlinear optimization problems prevalent in deep learning. There*s also an issue of using only VGG networks for their evaluations while VGGs are typically eschewed in favor of ResNets today. Given that the optimization is easier with residual connections, it may be the case that their procedure does not significantly improve the accuracy of ResNets. Regarding (3): By fixing L in Theorem 3.1, the authors essentially show that SGD converges to a stationary point for their new objective function which can be seen as a regularized version of the original objective function, which is not a strong result. Furthermore, fixing L goes against the original procedure*s motivation of recovering the original optimization function as L decreases to 0. Additional comments and questions There are passages that are difficult to understand because not enough context is given. For example in the *remark* passage, it is not clear where the *necessary condition* comes from. In addition it seems like it doesn*t even type-check since the first term is 2n dimensional while the second term is 4n dimensional. There are also many errors in the writing that hinder the presentation. A subset of them includes: - *nerual netowrks on roboticsKonda et al.* -> *neural networks on robotics Konda et al.* - *based on homotopy continuation method* -> *based on the homotopy continuation methods* - *random chosen point* -> *randomly chosen point* - *we choose 	ilde{	heta} = 0 in the dropout* -> reword - Fourth term in Equation 3 should be 	heta_2 - 	ilde{	heta_2} - *By gradually increasing parameter L* -> *By gradually decreasing parameter L* - *where xi is a random variable due to random algorithms* -> reword and possibly say the randomness is from SGD - After equation 6, should have b_i instead of _x0008_eta_i - In equation 20, should be g(	heta_*^0) instead of g(	heta_*^1) - In theorem 3.2 you never explained what 	heta_*^{L_k} is - *We compared the traditional optimization method (the quasi-Newton method)* -> which quasi-Newton method? - Figures 2 and 3 label the x-axis with *epochs*. However only 4 epochs were run, so I believe the x-axis should be *iterations** Besides improving the quality of writing in the paper, I would strongly suggest that the authors improve their empirical evaluation. Possibilities include evaluating on CIFAR 100 or ImageNet, using a wider variety of networks including ResNets, evaluating on tasks other than image classification.