AN EFFICIENT HOMOTOPY TRAINING ALGORITHM FOR NEURAL NETWORKS
Authors: Qipin Chen
Wenrui Hao
Venue:  (2020)
Keywords: Homotopy training algorithm
Convergence analysis
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.

Under review as a conference paper at ICLR 2020
AN EFFICIENT HOMOTOPY TRAINING ALGORITHM FOR NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We present a Homotopy Training Algorithm (HTA) to solve optimization prob- lems arising from neural networks. The HTA starts with several decoupled sys- tems with low dimensional structure and tracks the solution to the high dimen- sional 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 ho- motopy 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 better accuracy on several examples including VGG models on CIFAR-10 10. Moreover, the HTA would be combined with the dropout technique to provide an alternative way to train the neural networks.
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 [Cag et al. (2018); Cang & Weil (2018); Yin et al. (2018) 2016) on deep learning have been made in the last few years. However, as the size of new state oftte--f-theean 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 iet al. (2012). auto-pilot automobiles Hammerla et al. (2016), and acrial systems Maire et al. 20014). At present, there are two big challenges in fundamentally understanding deep neural networks:
the application scenarios of nerual netowrks robotics
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 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 al.] (20TT: 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 (() where 0 E R.
We then divide f in two groups, namely, 02 U02, where 0, E R. and 0g E R (n1 + n2 n). (Although that it can be easily extended to any m decompositions, we use = 2 as an illustration of the HTA idea.) Then we first solve the following decoupled simplified optimization problems
min f(01, and min f(0i, 02) 0,
0,
where 0 = 0, U 0g is random chosen point in En for instance we choose Ø = 0 in the dropout Srivastava et al. 2014). Second we define the following homotopy function
H(e, L) = f() + L| 0111 + f(n) + L| - -zll + L
110 1/1
(3)

---

Under review as a conference paper at ICLR 2020
where θ = (8,n) and L E (0, o0) is the homotopy parameter. When - oc, have two decoupled optimization problems which we have already solved in the first step; when - O, recover the original optimization by forcing are able to construct a continuous path @[T.beeween two decoupled low-dimensional optimization problems and the original optimization problem.
17. By gradually increasing parameter L,
Remark The HTA can be reviewed in point view of nonlinear equations by considering the neces- sary condition of the optimization problem (T):
(o,f(o)
H(O, - (Vo((o) (v)])) 17 7-8/ 8 L +L
01 0
Wm ((1
1/2 02
respectively. When When is large, 02 and 1/ can be solved by (() = 0 and v,,
L is small, we have the solution of Vof(0) 0 by the diagonal homotopy 0 --1 = 0. This technique has been widely used in solving systems of nonlinear equations especially for polynomial systems Bates et al. 2 Wampler & Sommese (2005). Since the Ø randomly chosen, the universal approximation theory Park & Sandberg (1991) can guarantee that the random point 0 in In is always connected to the solution of Vo = O. In another word, the solution path (L)
always exists or the probability that (L) is not connected is zero Wampler & Sommese (2005)
APPLICATIONS OF HTA ON NEURAL NETWORK
2.1
CONVOLUTIONAL NEURAL NETWORKS
In this subsection, we will specify the variable 0 and the objective function f(0) of (3 in the convo- lutional neural network (CNN) setup.
Definition 2.1. Suppose we have two tensors, Atxmxn (aig)) sish.issmmm.mmmmm..... Isksn Bexxxm' = (bhiija) (acsiji)shee
IkkEn', where c, m, n, m² n', I E N and m S
m, m,n' n' S n. The convolution of two tensors is defined by the following:
m
x2'
A Bn.jk
ΣΣ
av a- b
(4)
where B3 called the convolutional kernel.
Then with the input and the output y, the CNN is written as
yl:; 0) - (a((- poa(----aaat aa(( W1 + bi) W2 + b2) bn-1) 1) Wn + bn)
(5)
where W, E mo.. and o is the activation function. Then we have f = [We by b which can be easily divided into two subgroups 0, [Waj. 4. where Wij E R 2 m,n The objective function f(0) in Bp defined by the cross entropy loss function Goodfellow et al. (2016) and defined as C(x, y) rry) + log(E, e=bl).. Due to the random algorithms in machine learning Bottou 20100): Kingma & Ba 2014). the homotopy function in can be rewritten as H( E, L) where random variable due to random algorithms.
2.2 FULLY CONNECTED NEURAL NETWORKS
Similar to the CNN, a fully connected neural network with n hidden layers is written as
y(2, 0) o
61) + 62) + bn-1) + bn),
(6)
where W, E Rd xd; (3 E Rd the dimension of the input and d, the width of the i-th layer.
Then we have 0 = (W,, by ) which can be easily divided into two subgroups 0₃ {W, b, 6/ n/2 and 02 = (W,, by 1n i=n//211 Or we can use the dropout technique randomly split 0 as 0, and
82 Similarly, the homotopy function in 3 can be also rewritten as H(O; E. L) due to the random algorithms |Botoou (2010): Kingma & Ba 2014
2

---

Under review as a conference paper at ICLR 2020
3 THEORETICAL ANALYSIS
In this section, we will provide a theoretical analysis of the HTA by using stochastic gradient scheme solve (3) for each L. We redefine our stochastic gradient scheme for the homotopy process
0k+1
0z Gx Ck. Lk),
where L) VoF(0; ç, L), " is the learning rate, Lo M, Lx / and M is given large number. Then we consider the expectation of the homotopy function as Eg (H(0: L)), for simplicity, and denote [H[H00 L)] g(0; L).
3.1 CONVERGENCE OF THE HTA FOR ANY GIVEN IN THE NON-CONVEX CASE
Theorem 3.1. (Nonconvex Convergence) If {8&} } is contained in bounded open set, supposing that 7 is run with a step size sequence satisfying
7he
30 and
7k
2
00,
then we have
E
7
( 1) as K + with A
Σ
7kk
(9)
km
Proof. First, prove the Lipschitz-continuout objective gradients condition Bottou et al. 2018
which means that ((; L) is C² and (g L) is Lipschitz continuous:
g0; L) is C Since yςzę; 0) E Ca and L(:y) is C²,, we have that ((0 O that VoH [, L) is continuous. Considering
Veg(O; L)
L)) = (e
(10)
we have that Vag(O, L) is continuous that g(0; L) E C².
gg(0; L) is Lipschitz continuous. Since Vog(t: L) E& (V, only need to prove E. (VoL(v(re ve) is Lipsehitz continuous. In fact
VeCly(ag 0), Me) = v=L(y(x;;0)) 0), Voy(zz;;)
(11)
we will show that V.C(y(Ze; 0), ME) and Voy(rE: 0) are bounded and Lipschitz continu- ous. Since that both ar (a:) Ite- and oxx) = (1) - (x:) are bounded and Lipschitz continuous, and that {0x} is an open set (assumption of Theorem 3.1.. Voy(#g 0) is bounded and Lipschitz continuous. (xgg is bounded because the size of our dataset is finite.)
By differentiating [(x, y), we have
T
VaL(a, y) = (-8)
-8 +
(12)
Σ
en
Σ
E
where is the Kronecker delta. since
# E, E0
esy
k=i
(13)
Ozx E, E
k x
which implies that bounded. Therefore V ( 0), ve) is Lipschitz continuous and bounded. Therefore
8 24
S 2, we have v. is Lipschitz continuous and
Jue Σ, 55
we have that Vg(0; L) is Lipschitz continuous.
Second, prove the first and second moment limits condition Bottou al. 2018
3

---

Under review as a conference paper at ICLR 2020
According to our theorem assumption, {0x} is contained in an open set which is bounded.
Since that is continuous, is bounded;
b. Since that Gk L) = VoF(Bxx: L) is continuous, we have
Es, GG.kG( Ea. L)] = VoLe, [ (0x: Ek. L)] = vog(OR;L).
(14)
Therefore
Vg(Os: Eç, [G(Ok; [G([ Ex, L)] Vg(On: L)" (g(OA: L) = Vo L)ll 2 u/
V// L)lB
(15)
for 0 1. On the other hand, we have
[| [G(Ok: ER. L)lll [[Vg(O;;))l> S vcllVo(0=:L)11
(16)
for ug 1.
Since that (Ogi Ek. L) bounded for a given L, we have E8 11| (0; Ek. L) also bounded. Thus
Ve. [G(02: Ek. L)] == Eg, [I]G(( L) [[s (G( 1)]1 < E. [[]G((e;: Ex. 1)
(17)
which implies that Ve., [G((Os Ek. 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,
8
O 7h 0o and
7k
00;
(18)
k=1
k=1
the following convergence is obtained
E
7h
0 K
(19)
A
3.2 EXISTENCE OF SOLUTION PATH (LL) FOR THE CONVEX CASE
Second explore the existence of solution path ((L) when varies from M to 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(O: S Mp- Then for stochastic gradient scheme we have
lim Elg(O,, Inn] 9(62.0), n
(20)
where 0, Eizo 7896 and L,, 20-0 7
DizonuLy 2nmo 78
Proof.
0 0:2 = Ell10 nh G(Ox: Eo, Txp) 0%. [12]
-2 - G.0i Eks Lb) 0L*, l 042)
+E|10! 117.
(21)
By defining
Ag --B TxG(Ox: Ek. Tx.) 0.h,, ,bt+: 0%:3)] + B11loe+11111--1-- 02:x1133
(22)
4

---

Under review as a conference paper at ICLR 2020
and assuming that Σx A& A < cc, we obtain
11 0.++1 112]
E|| TaG(Oes Eke Lu) 0.' ] + Ak
B|[10: 0.*² 11²] 27 (G((s: Ek. Itk), 0x -0-001 + (1 [x, + A
I B||[0s t [| 2 2 (G(Ok: Ea. Tx)), 02 - 0-*11] + +22 + An
Since that
[[k] Ex. LR), 02 0-* = Ee Ea [( Ek. Lk). 0x - 0%h²1 >lE ... E1-1
Es La (V (Ox; Lx), 02 0 )150 Ek-11
(Ok( Lx), 02 0.4² )]
(23)
have
B[1 0 [|3] S B[ a || 2 (V Lx), 0k 0.++}] + +2EM² Ak-
(24)
Due to the convexity of g(: Lx), namely,
(Vg(Ok. LR), 02 - 0 2 g(0s; Lx) - g(00h; Ln).
(25)
we conclude that
B||0++1 8 1 S R| g 2 E g(( I+) 9(0 [[x]] +2.M2 Ak
[1]
(26)
or
27x Digki LR) g00 ; S 11110 0 1|2-1110 100 0.h 1| T2 Ag.
By summing up h from O to
2
The Elg(((;; g(0 La)l S -Ellln+1 - 0 1|2 110 6 + M Σ
+
Σ
A
k=0
k=0
k=0
S D2 M
7kk
Ak
(27)
k=0
k=0
where = =100- 0111. Dividing 2 Eh Tt on both sides, we have
1
n
Elo(ss [x) g(0!n; [+)]
D2 + M Σ
k= the + Ek=o A
D2 + M
M
k=0 7k
+
Lk 7k
" 7h
2>100 7/K
k=0
According to the convexity of g( and Jensen's inequality Jensen 1906)).
n Eig Lx)1 s E[g( (B.: I..)
(28)
Ek=o 7k A=0
where 0, Σr Ei n0 and Ln Tun _n-o 7h
En-o 74
Then we have
Ek=o mgg(be;;I
D2 + M Σkーo 3he
(fg T.,)]
<
(29)
2km 7kk
> k= ?k
We choose 7* such that Eh 7h and Σk=o 2he co, for example, 7k infinite, we have
Taking n
E.
Σn (ng( Tuk)
0 < lim Elg(On, E.) lim
S.
(30)
#00
n
Σk 7k
Because Ls 7 0, .). is continuous and En 9 0c, then
En 0= nog (h. Lb)
lim
g(00000000
(31)
Lk 7/
which implies that
lim Elg(On, Ln)] = g(.%.0).
(32)
n-0
n
5

---

Under review as a conference paper at ICLR 2020
150
130
10
-10
Figure 1: TWoo-dimensional highly non-convex function
NUMERICAL EXPERIMENTS
4.1 A NON-CONVEX EXAMPLE
We first use the following multi multi-dimensional highly non-convex example Chow et al. (2033 to illustrate the feasibility and efficiency of the HTA.
min f(x) (m/n) ls sisin + Σ (us A)) + ksin + (vo A)2 {.
(33)
i=1
where
x= (x1, ,nn) E R", V1 1+ (xq 1)/4, 1, n and k 10, ==1.
(34)
The function has roughly 5" local minima in the region {|æ,/ < 10} and a unique global minimum located at x, = 1, = 1, n. (See Figure 4.1 for an illustration of 2.)
The idea of the homotopy setup of this problem splitting the n dimensional optimization problem into two n/2 dimensional problems which can be optimized separately and are tracked to 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:
F(x, y: L) = fz) + [Z] ... .2g) (x), ... ...,2.9)12 + g(v) + L +I... .Bn) (v
+ +1
1
+ T, 1 - v11
(35)
where
x (x). vn) E R" y= (y)..... : yn) R
(36)
(af. .. 2 +2) R., (v +1,
9 E R² are fixed and chosen based on the initial guess. When
is large, F' is equivalent to optimize
min
Fn) min glvi. ... -Vz.yE+H vir-.
(37)
which can be solved separately. When L becomes small, the last term of 35 forces x and y to be equal. Then F(z, y: L) is equivalent to optimizing fæ) which is the original n-dimensional opti- mization problem. Therefore F(x, y; L) connects optimization problems by gradually decreas- ing penalty factor and builds a continuous path between the decoupled systems and the original optimization function / (xx).

---

Under review as a conference paper at ICLR 2020
Dimensions (n)
Initial Values
Quasi-newton with the ho-
Quasi-newton
motopy setup
2
00, 1, ... _51 (6" points)
36
24
4
0, .. .5 (6 points)
1296
864
6
[3, 33,4,5, 5, 6] (4 points)
4096
991
Table 1: Finding global minimums by two algorithms
Base Name
Model
Original Rate
Error
Error Rate with
Rate of Imrpove- ment(ROIs)
HTA
VGGII
7.83%
7.02%
10.34%
VGG13
5.82%
5.14%
11.68%
VGG16
6.14%
5.71%
7.00%
VGG19
6.35%
5.88%
7.40%
Table 2: The results of HTA and traditional method of VGG models on CIFAR-10
We compared the traditional optimization method (the quasi- quasi-Newton method) and the quasi-Newton with the homotopy setup. For = 4, we chose the same initial value [5, 4, 5, and set from 0.9 to 0.1 for the quasi-newton with the homotopy setup. It takes 8 steps and 14 steps for the quasi-newton method and the quasi-newton with the homotopy setup converge, respectively. However, the quasi-newton method does not find the global minimum while the HTA does. We also compared two algorithmss with different initial values and count the times when converging global minimums. Table I shows the results of n = 2, 4, n 6 and n = 8.
4.2 APPLICATIONS ON VGG
Secondly, we applicd the HTA to both CNN and fully connected neural networks on the CIFAR- 10 dataset (https: www. CS www.ttoroooo..... www.oto..d.doo.eeeoooooo
carfrar.r... html) with the training and validation datasets from the CIFAR-10 website. terms of the pre-processing step: for training dataset, we used random horizontal flip, random crop and normalization; for the validation dataset, we just used the same normalization. We implemented the HTA with stochastic gradient descent (SGD) method on VGG11, VGG13, VGG16 and VGG19 as our base models with batch normaliza- tion Simonyan & Zisserman (2014). In order to compare the SGD with the HTA method, we set all the regular parameters (e.g. learning rate, batch size, momentum, epochs, weight decay and etc) to be exactly the same, varied the homotopy parameter J. from /. = 0.01 to I. = 0.005 with stepsize AT. = 0.001. For each I., we run epochs with the SGD method. The code for this method can be found at https: /tittub.......g. com/ Bill wreeeachhhooottgrr which has been run the DGX-1 (p100 version) with p100 GPUs and Tesla structures. Figure 2 shows the comparison of validation loss between the HTA with fully connected neural networks and traditional method the VGG13 model. The HTA has a less error rate (5.14%) than the traditional method (6.35%) by improving 11.6 1.688. All the results for different models shown in Table is clearly seen that accuracies of HTA for different models are better than that of the traditional method. For example, vgg with HTA gets 7.02% error rate while traditional method only gets 7.83%: The vgg with HTA has an етгог rate of 5.88% while traditional method only has 6.35%. We run the numerical experiments for times for each model and the results are shown in Table We also applied HTA to the only CNN part of two VGG models: vggll and vgg13. Figure 3 shows the validation accu- racies of two models which has been improved by the HTA (91.66 6. (vggl) 1) and 93.09% (vgg13)) comparing with the traditional method (91.01% % (vggl) I) and 92.29% (vgg13))
Base
Model
mean
stddey
max
Name
VGGTI
91.53% 92.76%
0.09%
91.66%
VGG13
0.22%
93.09%
Table 3: The validation accuracies of HTT method of VGG models on CIFAR-10

---

Under review as a conference paper at ICLR 2020
Traditional Method
HTA
Error Rate(%)
7-
1000
2000
3000
4000
Epochs
Sta
State2:
State2:
State3:
State3:
Figure 2: Comparison of error rate of VGGI3 between HTA and the traditional method.
10
080
Traditioall Nathed
Thadit Nethod
HTA
HTA
200
902
200
500
Tooche
Sacchs
Figure 3: The performance the HTA on the CNN part of vggl1 (left) and vgg13 (right) and comparisons with the traditional method
5 CONCLUSION
In this paper, we developed 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 proved for the non-convex optimization. Then existence of solution path ((L) is demonstrated theoretically for the convex case although that 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 new way to couple with the dropout techniques to improve the training accuracy which will explore in the future.
REFERENCES
D. Bates, J. Hauenstein, A. Sommese, and C. Wampler, Adaptive multiprecision path tracking. SIAM Journal on Numerical Analysis, 46(2):722-746, 2008
8

---

Under review as a conference paper at ICLR 2020
D. Bates, J. Hauenstein, and A. Sommese. Efficient path tracking methods. Numerical Algoritims, 58(4):451-43 4599 2011.
L. Bottou, Large-seer scale machine learning with stochastic gradient descent. In Proceedings of COMP- 2010 pp. 177-186. Springer, 2010.
L. Bottou, F. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-3111 2018.
Z. Cang and G. Wei. Integration of element specific persistent homology and machine learning for protein-ligand binding affinity prediction. International journal for numerical methods in biomedical engineering, 34(2):e2914, 2018.
Z. Cang, L. Mu, and G. Wei. Representability of algebraic topology for biomolecules in machine learning based scoring and virtual screening. PLoS computational biology, (4(1)=e100592) 2018.
S. Chow, T. Yang, and H. Zhou. Global optimizations by intermittent diffusion. In Chaos, CNN, Memristors and Beyond: Festschrift for Leon Chua With DVD-ROM, composed by Eleonora Bilotta, pp. 466 479. World Scientific, 2013.
Goodfellow, Y. Bengio, and Courville. http://www.deelleaiigbbokkkkk
Deep Learning.
MIT Press, 2016.
N. Hammerla, Halloran, and T. Ploetz. Deep, convolutional, and recurrent models for human activity recognition using wearables. IJCAI 2016, 2016.
W. Hao and J. Harlim. An equation-by-equee constrained maximum entropy problem. Communications in Applied Mathematics and Compu- tational Science, 13.
method for solving the multidimensional moment
W. Hao, Hauenstein, B. Hu, Y. Liu, A. Sommese, and Y.-T. Zhang. Bifurcation for a free boundary problem modeling the growth of tumor with necrotic core. Nonlinear Analysis: Real World Applications, 13(2):694-70) 709, 2012.
J. Jensen. Sur les fonctions convexes et les inégalités entre les valeurs moyennes, Acta mathematica, 30(1):175-193, 1906.
D. Kingma J. J Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: arXiv: 1412.6980, 2014.
K. Konda, A. Königs, H. Schulz, and D. Schulz. Real time interaction with mobile robots using hand gestures. In Proceedings of the seventh annual ACM/IEEE international conference on Human--Rbbe Interaction, 177-178. ACM, 2012.
Maire, L.. Mejias, and A. Hodgson. convolutional neural network for automatic analysis of aerial imagery. In Digital Image Computing: Techniques and Applications (DICTA), 2014 International Conference on, pp. 1-8. IEEE, 2014.
A. Morgan and A. Sommese. Computing all solutions to polynomial systems using homotopy con- tinuation. Applied Mathematics and Computation, 24(2):115-13) 1987.
Park and Sandberg. Universal approximation using radial-basis-function networks. Neural computation, 3(2):246-257, 1991.
K. Simonyan and Zisserman. Very deep convolutional networks for large-scale image recogni- tion. Computer Science, 2014.
N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting, The Journal of Machine Learning Research, 15(1): 1929-1958, 2014.
C. Wampler and A. Sommese. The Numerical solution of systems of polynomials arising engi- neering and science. World Scientific, 2005.

---

Under review as a conference paper at ICLR 2020
P. Yin, S. Zhang, Y. Qi, and J. Xin. Quantization and training of low bit-width convolutional neural networks for object detection. arXiv preprint arXiv:1612.06032. 2016.
P. Yin, S. Zhang, J. Lyu, S. Osher, Y. Qi, and J. Xin. Binaryrelax: A relaxation approach for training deep neural networks with quantized weights, arXiv preprint arXiv:/801.063//. 2018.
10


Reviews:
[{"review_id": "SygsJ2af9H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 work proposes to learn neural networks using homotopy-based continuation method. The method divides the parameter space into two groups (extendable to multiple groups) and introduces a homotopy function which includes the original optimization problem as an extreme case.  By varying the homotopy parameter, one can construct a continuous path from a supposedly easier to solve optimization problem to the problem of interest. The authors prove convergence in the non-convex case, the existence of solution path in the convex case and demonstrate the effectiveness of the proposed method on synthetic and real datasets.\n\nWhile the idea itself is rather intriguing and seems promising, the current presentation and experimentation does not meet the acceptance threshold.  The writing of the draft needs a lot of improvement, in particular the notations the authors used are not consistent throughout the paper, which is very confusing. \n\nThe synthetic example the authors used in section 4.1 are naturally decoupled among the different dimensions of the parameters, which is no surprise the proposed method would achieve 100% convergence as shown in table 1. \n\nIt seems the division of the parameter space would matter. One would imagine there exists certain division leading to much easier to solve subproblems. Do the authors have any insight or experiments comparing different division strategies?\n\nHere's a very closely-related work that should be cited and discussed:\nWang, Xin. \"An efficient training algorithm for multilayer neural networks by homotopy continuation method.\" Proceedings of 1994 IEEE International Conference on Neural Networks (ICNN'94). Vol. 1. IEEE, 1994.\n\n\nTypos:\n1) Equation following remark in page 2, should H() be replaced by G() or \\nabla H()?\n2) After equation (7), should G():= \\nabla H instead of F?\n", "extra_scores": {"experience_assessment": "I do not know much about 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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Skla9ft35S", "reviewer": "AnonReviewer2", "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": "Summary\n\nThis paper proposes an algorithm to address the issue of nonlinear optimization\nin high dimensions and applies it to convolutional neural networks (VGG models) on CIFAR 10. \nThey show 11% relative reduction in error for this particular task with this\nparticular network. In addition, they prove additional theoretical results on\nthe convergence of SGD using their method in the convex case as well as\nconvergence of SGD to a stationary point in the nonconvex case when the homotopy\nparameter is fixed which is not done in practice.\n\nGiven an optimization problem, their method first solves multiple independent\nlower-dimensional optimization problems each with a subset of the parameters and\nthen optimizes a new objective function controlled by a monotonically decreasing\nparameter L that interpolates the original objective function and the\npreviously-solved lower dimensional problems. L can be seen as a regularization\nparameter that is gradually decreased as we optimize the new optimization\nfunction. When L = 0, we recover the original optimization problem.\nThe authors prove that (1) SGD with their procedure will find a stationary point\nunder the Robbins-Monro conditions for a fixed L and (2) SGD with their\nprocedure will converge for convex problems as L is decreased to 0.\n\nDecision and reasoning\n\nThis paper should be rejected because (1) the proposed algorithm attempts to address \nthe original issue of high dimensional nonlinear optimization of neural networks but\nviolates the algorithm's assumption in practice, (2) the\nempirical evaluations are lacking - having only evaluated their method on a toy\nproblem with up to only 6 dimensions and a relatively simple image classification task,\nand (3) the assumption of fixing the homotopy parameter in the theorem on the\nnon-convex case directly violates the intention of the algorithm. \n\nRegarding (1): The proposed procedure requires initializing L at a large value\nand reducing L towards 0 in order to recover the original optimization problem.\nHowever, in practice for CIFAR 10, the authors initialize L to be 0.01 and\ngradually reduces it to 0.005 which is hardly the original intent of the\nalgorithm. There is also no demonstration whether or not this gradual reduction in\nL actually has an effect on the optimization of the new objective function. For\nexample, since the start and end values of L are similar, will we get similar\nresults if we simply fix L to be 0.005 or 0.01? The authors also show that their\nmethod outperforms a quasi-newton method by combining the optimization with\ntheir procedure on a non-convex example by Chow et al. 2013. However, this example\nonly goes up to n=6 dimensions, which is hardly comparable to the original\nproblem of high dimensional non-convex optimization that this paper sought to\naddress.\n\nRegarding (2): The authors evaluated their procedure on CIFAR10, a relatively\nsimple image classification task that modern neural networks can solve easily\nand is not representative of the types of nonlinear optimization problems\nprevalent in deep learning. There's also an issue of using only VGG networks for\ntheir evaluations while VGGs are typically eschewed in favor of ResNets today.\nGiven that the optimization is easier with residual connections, it may be the case that\ntheir procedure does not significantly improve the accuracy of ResNets.\n\nRegarding (3): By fixing L in Theorem 3.1, the authors essentially show that SGD\nconverges to a stationary point for their new objective function which can be\nseen as a regularized version of the original objective function, which is not a\nstrong result. Furthermore, fixing L goes against the original procedure's\nmotivation of recovering the original optimization function as L decreases to 0.\n\nAdditional comments and questions\n\nThere are passages that are difficult to understand because not enough context\nis given. For example in the \"remark\" passage, it is not clear where the\n\"necessary condition\" comes from. In addition it seems like it doesn't even\ntype-check since the first term is 2n dimensional while the second term is 4n\ndimensional. \n\nThere are also many errors in the writing that hinder the presentation. A subset of\nthem includes:\n- \"nerual netowrks on roboticsKonda et al.\" -> \"neural networks on robotics Konda et al.\"\n- \"based on homotopy continuation method\" -> \"based on the homotopy continuation methods\"\n- \"random chosen point\" -> \"randomly chosen point\"\n- \"we choose \\tilde{\\theta} = 0 in the dropout\" -> reword\n- Fourth term in Equation 3 should be \\theta_2 - \\tilde{\\theta_2}\n- \"By gradually increasing parameter L\" -> \"By gradually decreasing parameter L\"\n- \"where \\xi is a random variable due to random algorithms\" -> reword and possibly say the randomness is from SGD\n- After equation 6, should have b_i instead of \\beta_i\n- In equation 20, should be g(\\theta_*^0) instead of g(\\theta_*^1)\n- In theorem 3.2 you never explained what \\theta_*^{L_k} is\n- \"We compared the traditional optimization method (the quasi-Newton method)\" -> which quasi-Newton method?\n- 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\"\"\n\nBesides improving the quality of writing in the paper, I would strongly suggest that the\nauthors improve their empirical evaluation.  Possibilities include evaluating on\nCIFAR 100 or ImageNet, using a wider variety of networks including ResNets,\nevaluating on tasks other than image classification.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "H1xf8Ek2FB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "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. \nMy major concerns are as follows.\n1. 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.\n2. 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].\n3. 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.\n4. The authors make a mistake in the proof of Theorem 3.1. The claim that “{\\theta_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}, x\\in (0,1).\n\n[1] L. Bottou, F. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223–311, 2018.\n[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.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The work proposes to learn neural networks using a homotopy-based continuation method. Reviewers found the idea interesting, but the manuscript poorly written, and lacking in experimental results. With no response from the authors, I recommend rejecting the paper.
Decision: Reject