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):
In this paper, the authors propose the Homotopy Training Algorithm (HTA) for neural network optimization problems. They claim that HTA starts with several simplified problems and tracks the solution to the original problem via a continuous homotopy path. They give the theoretical analysis and conduct experiments on the synthetic data and the CIFAR-10 dataset. My major concerns are as follows. 1. The authors may want to give more detailed explanations of HTA. For example, they may want to give the pseudocode for HTA and explain its advantages compared to other optimization methods. 2. The theoretical analysis is trivial. The proof of Theorem 3.1 is to verify Assumptions 4.1 and 4.3 in [1]. Moreover, the proof of Theorem 3.2 is similar to the analysis for the convergence of SGD for convex problems in [2]. 3. The experiments do not show the efficiency of HTA, as the original quasi-newton method is faster than the quasi-newton method with the homotopy setup. 4. The authors make a mistake in the proof of Theorem 3.1. The claim that “{	heta_k} is contained in an open set which is bounded. Since that g is continuous, g is bounded.” is incorrect. We can find a counterexample g(x) = frac{1}{x}, xin (0,1). [1] L. Bottou, F. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223–311, 2018. [2] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009.