Convergence Analysis of Homotopy-SGD for Non-Convex Optimization
Authors: Matilde Gargiani
Andrea Zanelli
Moritz Diehl
Quoc Tran-Dinh
Frank Hutter
Venue:  (2021)
Keywords: deep learning
numerical optimization
transfer learning

Abstract: First-order stochastic methods for solving large-scale non-convex optimization problems are widely used in many big-data applications, e.g. training deep neural networks as well as other complex and potentially non-convex machine learning
models. Their inexpensive iterations generally come together with slow global convergence rate (mostly sublinear), leading to the necessity of carrying out a very high number of iterations before the iterates reach a neighborhood of a minimizer. In this work, we present a first-order stochastic algorithm based on a combination of homotopy methods and SGD, called Homotopy-Stochastic Gradient Descent (H-SGD), which finds interesting connections with some proposed heuristics in the literature, e.g. optimization by Gaussian continuation, training by diffusion, mollifying networks. Under some mild and realistic assumptions on the problem structure, we conduct a theoretical analysis of the proposed algorithm. Our analysis shows that, with a specifically designed scheme for the homotopy parameter, H-SGD enjoys a global linear rate of convergence to a neighborhood of a minimizer while maintaining fast and inexpensive iterations. Experimental evaluations confirm the theoretical results and show that H-SGD can outperform standard SGD.

Under review as a conference paper at ICLR 2021
CONVERGENCE ANALYSIS OF HOMOTOPY-SGD FOR NON-CONVEX OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
First-order stochastic methods for solving large-scale non-convex optimization problems are widely used in many big-data applications, e-g. training deep neural networks as well as other complex and potentially non-convex machine learning models. Their inexpensive iterations generally come together with slow global convergence rate (mostly sublinear), leading the necessity of carrying high number iterations before the iterates reach a neighborhood of a minimizer. In this work, we present first-order stochastic algorithm based on combination Gradient Descent
very
of homotopy methods and SGD, called PooooooyyStochaaee (H-SGD), which finds interesting connections with some proposed heuristics the literature, e.g. optimization by Gaussian continuation, training by diffusion, mollifying networks. Under some mild assumptions on the problem structure, we conduct theoretical analysis of the proposed algorithm. Our analysis shows that, with specifically designed scheme for the homotopy parameter, H-SGD enjoys global linear rate of convergence to neighborhood of minimum while maintaining fast and inexpensive iterations. Experimental evaluations confirm the theoretical results and show that H-SGD can outperform standard SGD.
INTRODUCTION
This paper focuses on the theoretical development and analysis of stochastic optimization algorithm. called Homotopy-Storn -Stochhsttt Gradient Descent (H-SGD), based the combination of homotopy methods and stochastic gradient descent (SGD). The algorithm we propose is specifically designed to solve finite-sum problems of the following form
N f(w)= = Σ
w" arg min 1o Rdd
fy(W))
where f RR + R is continuously differentiable, bounded below and not necessarily convex. In particular, we assume that we only have access to noisy function values and gradients of the objective function in equation via stochastic first-order oracle, as in (Nemirovski et al. 2009) and (Ghadimi & Lan 2013). Problems of this form typically arise in machine learning and deep learning applications, where the dimensionality of the datasets makes the full function and gradient evaluations too expensive. This class of problems is generally approximately solved by stochastic first-order iterative algorithms, e.g. SGD (Bottou al. 2018), Adagrad (Duchi et al. (01T)) Adam (Kingma & Ba 2015). At the iteration f, the algorithms of this class acquire a stochastic estimate of the function value f(we, &.) and the gradient g (e, { by calling the oracle with input wi, where & is a random variable, i.c. when the noise comes from subsampling as in the mini-batch scenarios, then & E {0, 1) with || 1 = M and g(w,, & M Σ Et.j Vfz(w:). In the case of SGD, for a given wo E Rd and 0, the iterates are generated as follows
W++1 == ag( (w,, &t
Consequently, the iterate W1+1 W (E()) ((+)(E is function of the history Eμq (Eo. .... {e) (also wo should be included in case it is a random mitial point) the generated random process and hence is itself random.

---

Under review as a conference paper at ICLR 2021
In general, stochastic first-order methods enjoy fast convergence when the problem is characterized by a certain structure. In particular, when the Mojasi--ojasiewiizz (PL) condition (see Karimi et al. 2016 for more details on the PL condition) holds for the objective function in Problem D then, with a "small enough" value for the step-size, the SGD iterates converge linearly to a minimizer's neighborhood (Karimi al.; 2016] Vaswani et al., 2019). Unfortunately, in many machine learning applications, the PL condition is not realistic assumption as the landscape is generally characterized by the presence of multiple local minima and saddle points (Dauphin al. 2014; Kawaguchi 2016] Karimi et al., 2017). At the same time, in the vicinity of the minimizers the problems generally show stronger structures, i.e. PL or even strong convexity, allowing for a faster local convergence (Karimi et al. 2017). In such a scenario, smart initialization hence becomes crucial for the numerical performance of the method (Sutskever et al. 2013b). Unfortunately, the power of the existing smart initialization heuristics is often quite limited given the small knowledge of the problem's 's landscape which we generally dispose of. In addition, these hcuristics typically can not guarantee that the SGD iterates start "close enough" to a minimizer, i.e. in the region where the PL condition holds, such that the method enjoys a linear rate of convergence. Therefore, the ideal scenario would be to be able to exploit the stronger local structure while the method's iterates gradually approach minimizer and independently from the starting point. In this regard, homotopy methods are general strategy for tackling difficult optimization problems by gradually transforming a simplified version of a target problem, or a version with a known minimizer, back to its original form while following a solution along the way. Consequently, they preserve in each step the vicinity to a minimizer of the currently tackled problem, allowing the solver to always work in regions where the problems exhibit stronger structures. In general terms, homotopy methods (Allgower & Georg, 2003) are a widely and successfully used mathematical tool to efficiently solve various problems in numerical analysis, e.g. (Deuffhard, (00I)) (Liao) 2012). Such methods are also suitable to solve complex non-convex optimization problems where no only little prior knowledge regarding the localization of the solutions is available, allowing for the exploitation of the stronger local structures of the problems in order to achieve fast global convergence, e.g. (Xiao & Zhang 2012
Lin & Xiao 2014 Suzumura
ct al. 2014 Gargiani et al. 2020).
In this work, we propose stochastic first-order numerical method to solve Problem 1 called Stochastic Gradient Descent (H-SGD), which is based on the combination of the homotopy method and SGD. After introducing the method and discussing the related work (Section contributions are as follows
1. In Section 3 we provide a general theoretical analysis of H-SGD under some mild assump- tions, showing that, if the increments in the homotopy parameter are "small enough", the proposed method tracks in expectation an r-optimal solution across homotopy iterations. We then show that, in the same setting, H-SGD can achieve global linear rate of convergence to a minimizer's 's neighborhood when used in combination with a specific schedule for the homotopy parameter, i.e. A); decreases exponentially across homotopy iterations.
2. In Section[4] we empirically evaluate the performance of H-SGD. Our experiments not only confirm the theoretical results derived in Section 3 but also show that H-SGD with smartly designed homotopy map can outperform SGD.
2 HOMOTOPY-SGD
Soomotopy-Stochaste Gradient Descent (H-SGD) is based on the combination of the homotopy method and SGD, in the hope of combining the best of both worlds. In particular, the goal is that of maintaining the advantageous properties of SGD, such as its cheap iterations and fast local convergence under PL. condition, while maximally exploiting the stronger local structures via the homotopy scheme. Therefore, H-SGD relies on the definition of a homotopy map fww, A) Rd x [0, + IR, such that, when = we recover a well-behaved function, e.g. convex, or a function with a known minimizer's 's localization, and by increasing the À parameter, also called homotopy parameter, we gradually morph it in order to finally end up with our target objective function fww 1) f(w) (see Suciil 2016, for more details on homotopy functions). By using such homotopy map, H-SGD finds an approximate solution of Problem by approximately solving a series of parametric problems that gradually leads to the target one. In particular, in each homotopy
2

---

Under review as a conference paper at ICLR 2021
iteration i, H-SGD tackles parametric problem of the form
" E arg min [ww, As); weRd
where the homotopy parameter X; is slightly increased at each homotopy iteration. As confirmed by our theoretical analysis, if the variations of the homotopy parameter, i.e. AX, are "small enough" across homotopy iterations, the method is able to track in expectation r-optimal solution from source to target problem. As shown in Algorithm H-SGD takes as input an approximate solution for the problem associated with fww, 0), i... Wo, and is then characterized by two loops: in the outer loop (homotopy iterations) the method defines new objective function by increasing the homotopy parameter (line 5 in Algorithm [ and in the inner loop (warm-started SGD iterations) the current homotopy problem is approximately solved with & iterations of SGD starting from the previously derived approximate solution, i.e. w (line in Algorithm Db. Different functions N - (0, 1] to determine the increment Aλ; in the homotopy parameter at each homotopy iteration can be used. As shown in our analysis, this function greatly impacts on the method's properties and convergence rate. In particular, our theoretical analysis confirms that, when specifically designed scheme for Aλ, is deployed, i.c. exponentially decreasing schedule, H-SGD is effective in guarantceing a global linear rate of convergence to neighhorhood of minimizer of our target problem, while, given the same setting, vanilla SGD can only ensure a global sublinear rate of convergence.
Algorithm 1 Chomotopy-Stochasse Gradient Descent (H-SGD)
1: input: Wi E R. E N, & E N.N. + (0, 1] with Σ h(i) = 1 and a > 0
2: initialization: i 0, Ào
3: for i = -1-1,.. ...... 17. do
4:
Δλ; - h(1)
5:
A; - -
6:
w/ + S--SGD(;;-,, k, f(;
7:
output: Wi
2.1 RELATED WORK
Finding a solution of Problem Whenn the objective function is non-convex is often quite challenging. Different heuristics hence have been proposed to speed up and improve the optimization of such problems, many of which to be used in combination with stochastic first-order methods such as SGD. In this regard, the proposed method, despite being new in its general formulation and analysis, finds many interesting similarities and connections with existing heuristics in the machine learning literature, e.g. (Bengio al.) 2009 Hinton et al.] 20122) Sutskever et al.) (013a). We now briefly discuss some of the state-of-the-an thr optimization techniques and initialization strategies for solving Problem that are most related to H-SGD, drawing connections with existing and ongoing research works and in the hope that our analysis can also lead to new interpretation of some widely used techniques which so far lack a more rigorous theoretical description and analysis.
Graduated Optimization. The graduated optimization approach (Blake & Zisserman 1987), also known as coarse-fe to- ro-grained optimization method, a general heuristic to solve complex non-convex problems that relies the basic principles of the homotopy method. As the name suggests, at first a coarse-grained and "casy-to-solve" version of the target problem is generated via a smoothing operation. The method then proceeds by gradually refining the problem versions, using the previous solution as initial point. Graduated optimization has been utilized explicitly and implicitly as heuristic in many machine learning and computer vision applications, e.g. object localization (Mobahi et al.) 2012). manifold learning (Gashler et al. (007). optical flow (Brox & Malik] 2011). Unfortunately. many of these techniques have practical and/or theoretical gaps, as they generally lack a rigorous running time and convergence analysis, and/or, as in (Mobahi & Fisher III, (2044) and (Hazan ct al. 2016), they rely on an expensive method, i.c. Gaussian smoothing, to construct coarse- grained versions of the original target problem. Regarding theoretical contributions on graduated optimization methods for solving Problem I Hazan et al. (2016) are the first and only, to the best of our knowledge, to provide a theoretical analysis for the running time and convergence rate of a graduated optimization method based on an approximate, yet still expensive, type of Gaussian smoothing and SGD. Unfortunately, their analysis shows two major limitations. First, it relies their
3

---

Under review as a conference paper at ICLR 2021
Gaussian smoothing approximation homotopy map, which limits the generality of the conducted analysis, while our analysis is independent from the specific formulation of the homotopy map used. Second, the analysis is based on the assumption of local strong convexity, which is quite strong requirement and hence might lead to considerably smaller local regions than those considered in our analysis (Karimi al., 2017). To conclude this short overview on graduated optimization, many successful optimization heuristics proposed in the machine learning literature are implicitly related to graduated optimization and, consequently, homotopy methods, such as curriculum learning (Bengio et al. 2009), simulated annealing (Kirkpatrick et al. 1983), noise injection techniques (Hinton et al. smart initialization (Sutskever et al. 2013a) and layer-wist pretraining (Bengio al., (0066.
2012
Transfer Learning. Due to the massive amount of computational resources required by the develop- ment of modern machine learning applications, the community has started to explore the possibility of re-using learned parameters across different tasks, leading to the development of many new transigr-lernning algorithms, e.g. (Torrey & Shavlik 20100 Pan & Yang 2010 Yosinski et al.) 22014) Gargiani et al. 2020). A simple yet often effective way to transfer knowledge across different tasks consists in using warm-start initialization. In this perspective, transfer-learning boils down to a sort of smart initialization heuristic. A first connection between homotopy methods and transfer-learning was underlined in (Gargiani et al. 2020). The authors propose a transfer-learingg algorithm based on the homotopy method and SGD via the definition of homotopy map that transforms source task into a target task. The method comes together with a general theoretical analysis that is independent from the specific homotopy map adopted and shows that, under some assumptions, the algorithm can track in expectation an approximate solution from source to target task, i.c. cilimality-tracking Un- fortunately, the method's analysis is limited as it only considers constant increments of the homotopy parameter, which automatically degrades the linear rate of the local solver to sublinear one for the homotopy- based method. In addition, as in (Hazan et al., (016)) the analysis relies on the assumption of local strong convexity, which might hold in a significantly smaller neighborhood of the minimizers than the PL condition (Karimi et al. 2017).
THEORETICAL ANALYSIS
In this section, we provide general theoretical analysis of H-SGD described in Algorithm In particular, after discussing the required underlying assumptions (Section [31). and the fundamental theoretical preliminaries (Section (.2). first we analyze the optimality tracking properties of the proposed method (Section 3.3). and then we show that, with a specifically designed scheme for the homotopy parameter, H-SGD enjoys linear convergence a minimizer's 's neighborhood (Section (3.4). The analysis we conduct is independent from the specific type of homotopy map adopted and it applies to any scenario where the assumptions listed in Section holdd
Recall that the proposed method is based on sequentially and approximately solving a series of n unconstrained parametric problems of the form
arg min fw,, A1) Vi 1,.1,...,77 WERd
(4)
where A < A, = 1, (0, 1]. In addition, H-SGD relies the availability of approximate solution wi for the source problem with Ag = 0 as starting point. We use w; to denote the derived approximate solution for the problem associated with parameter A, that is obtained by applying k 0 iterations of SGD starting from the previously derived approximate solution for the problem with parameter A Vi I,...,n. n.
Notice that W;-1.e = wi- ($R=-1 for t = 1,...,k k with Wi-1. = wx(E(s) is used to refer to the random vector generated the i-th homotopy iteration after iterations of SGD,, where f---11--]
(wo, ................................ Sl..............66. S6-
_t_ 56 Si and Eμy -i-l Eo. . ( with Ejo = wy are used to refer to the col-
(wy, ........__n lection of all random sources up to the current iteration. We use U (A) to denote the set of local (and global) minimizers of the parametric Problem T
S.......E-...................... Ek- -i-l
3.1 ASSUMPTIONS
We now list and discuss the assumptions that we consider throughout our analysis. Together with the standard smoothness and bounded variance assumptions, we also introduce three regularity
4

---

Under review as a conference paper at ICLR 2021
assumptions, which describe the localization of the solution map and how the objective function changes by varying the homotopy parameter across iterations. In addition to these assumptions, we also consider more general and local version of the standard PL condition. condition.Conseuuee Consequently, unlike the settings considered in (Karimi et al. 2016) and (Vaswani et al. 2019). where the standard PI. condition is unrealistically required to hold globally, ours is often encountered in many different non-convex scenarios (see Karimi et al. 2017 for more details).
Assumption 3.1 (existence of a regular localization of the solution map). Assume there exists a set
a S - [0, 1] such that (*(X) = - n and > = {(y, A) E R [0, 1]= y E (*)) are both non-empty and connected. Moreover, assume that for given À all the points in W (A) are associated with the same objective function value, which we denote as (* = f(y, 2) for all
y E (X)..
Notice that Assumption 3.1 does not imply vector-valued solutions of the parametric Problem
Assumption 3.2 (regularity 1). Assume there exists >> 0 such that
If(w, X) - f(w, ; Å) s 8||ă Å|| Vw E Rd, VI, Å [0.
(5)
Assumption 3.3 (regularity 2). Assume there exists > such that
(²) (*) ~/パĀ Åll Vš, 10
Assumption 3.4 (L-smoothness), Assume there exists L such that
I A) f(r A)II S L i rll. Vū, v E Rd, KA E [0,
See Remark C.I in Section of
f the Appendix for more details on Assumptions 3.2 and 3.3
Assumption 3.5 (bounded "variance"), Consider f(w, A) with À E [0, 1]a and ler g(w, E, X) be the stochastic estimate of the true gradient w (w, X) used in SGD with noise &. Assume that
Eg [g(w, &, ^)] = Vwf(w, A),
Ye E ERR AA E [0, 1|
(8)
and that there exists o² 2 O such that
Eg [1l &, A) (wf(w, >) s0², Vw R., AA [0,1]3
(9)
Assumption 3.6 ("expected" PL condition). Consider fw,, Xd) with d E [0, 1]a and let w1-1,t
w4-1,((5R11.r denote the iterate that is obtained at the i-th homotopy iteration after I iterations of
SGD with t S k. Assume that there exist > and >> O such that, if EgG 1. [f( A:)
s²
24
(Ax) S B, then
E E [I[V II {)11 2 2p- [Egg- [f( -
(10)
See Remark C.2 for additional details on Assumption 3.6
3.2 FUNDAMENTAL THEORETICAL PRELIMINARIES
Before proceeding with the main theoretical contributions, we revise and adjust the existing results in the literature on global error bounds of SGD, i.e. (Vaswani et al. (019)) to also hold in the considered setting. The extended results are then used for the derivations Section 3.3 and 3.4
Proposition 3.7. Consider [w, >x) with >; E [0, 1)s and let w;-1,t = wi wi-1 wi-L.-((g-1,--1) denote the iterate obtained at the i-th homotopy ieration by applying t iteeaations of SGD with & < k -
and a < J. Under Assumptions 3.1 and 3.4 3.6 if E ([;;,1,,,,)) (A,)) S B, then
1.1 [ [[]1 (2,) B B.
Proof. See Section Din the Appendix for proof.
Theorem 3.8. Consider the minimization of fw, Xd) with d E [0. 1]a via SGD. Let Wi-1 (E be the random initial point associated with the i-th homotopy iteration with
5

---

Under review as a conference paper at ICLR 2021
Bqn-1 1 - f* S B and w1-1.1 (;-1,(5(--12-1) denote the t-th SGD iter- ate with t S k. Under Assumptions 3.1 and 3.4 3.6 SGD with constant step-size S I attains the following convergence rate to minimizer neighborhood
o² s S P' [5( Ao) (0 EEg [[(0 Xa) - (*.)
(11)
2p
with p = (1 ap). With I. obtain p (1 41- 4
Proof. See Section E in the Appendix for proof.
3.3 OPTIMALITY TRACKING
In the following, define the function (A.) = E., [S(v, (*))) where is d-dimensional real random vector. As in (Gargiani et al. 2020 but a more relaxed setting, i.e. local PL in place of local sroong-conveitty. we study the optimality tracking properties of H-SGD. In particular, under the considered assumptions and by exploiting the previously introduced results on the convergence of SGD, with Theorem 3.10 we characterize the maximum allowed variation of the homotopy parameter across homotopy iterations of H-SGD such that, if &u., (A;) r, then also 0re4y (As+1) S r. The upper bound that we derive depends on the number iterations performed with SGD as well as on the convergence characteristics of SGD and the structural properties of the parametric problems. This result applied recursively across homotopy iterations leads to conclude that, if we adopt a "small enough" increasing step for the homotopy parameter, H-SGD can track in expectation r-optimal solution from source to target problem.
Before proceeding with the actual optimality tracking analysis (Theorem 3.10p, study the con- ditions on w, and AA++1 such that &w, (Ac+1) S B, where Wi is the approximate solution of the problem associated with parameter X; that is also used starting point for the next parametric problem.
Lemma 3.9. Assume ||A++1 - A 5.
B
and let wi denote the i-th iterate of Al-
84y
gorithm 0 with < +. Under Assumptions 3.1
3.3 and 3.4 3.6 if Own (A:)
S B (6 7),,
then Dwi (A141) S B. In addition, let kinxx =
log, (1
2p(8+2)c=o"
If ofu S B,
0SE< B 2² 2p
and l 2 kmax then own (d++1) SB - 77
Proof. See Section F in the Appendix for proof.
Theorem 3.10. Assume there exists d² 24
< S B and === min (61, (2) with
62 (1 p²) o² /2/2p
1 = (8+7) (B r),
(12)
p (6 x7)
logp (1- g²) 2pr)
In addition, let kmax
Consider Algorithm with a S 1, k kmax and
||x+11 Aall < c, where 0 <es ē. Under Assumptions @w4+ (A++1) < r.
3.1
3.3 and
3.6 if 0w (Ax) then 3.4
Proof. See Section Gin the Appendix for a proof.
See Figure 2 in Section B of the Appendix for graphical representation of the derived results.
3.4 LINEAR CONVERGENCE RATE
We now study the convergence rate of H-SGD and, in particular, it is possible to recover a global linear rate of convergence minimizer's 's neighborhood. The results derived in Theorem 3.11 confirm that, in the considered setting and with a specifically designed schedule for the homotopy parameter, H-SGD achieves the desired rate of convergence.

---

Under review as a conference paper at ICLR 2021
Theorem 3.11. Let p (1
d² 1 and consider Algorithm 2p B:
with a S L. pun (20) S r with
24 [1- Sr B and log,(0) (ō). In addition, let El == [0+7] ( r) and
if 2 logp (ō) logp (1+
Cp =
cD
(13)
p-p² Eo (647)
otherwise,
ph
with Eu == Egjo [ Xo)1
-fo)).. Under Assumptions 3.1
3.3 and
3.4
3.6
if
dell -
min {e-ve, e1) with 1j 2 In (Cp then
o²
i
Beyey [f(we+,, A++1)] (Net1) S p0+1 [Fgg [f(wo, Ao)] 8 (~o)]]
+
Σ
(14)
2
1=0
Proof. See Section H in the Appendix for a proof.
EXPERIMENTAL EVALUATION
In this section, empirically validate the theoretical results derived in Theorem 3.11 First, consider 1-dimensional toy regression problem to illustrate and visualize some of the basic properties of H-SGD. In this easy scenario, the introduced assumptions can be trivially verified by inspection (see the Figures 3 in the Appendix). We then move to more complex and high-dimensional scenarios where the assumptions can not be verified. Inspired by Finn al. (0017) and Gargiani et al. (2020), we consider the task of regressing with a neural network from input to output of a sinusoidal wave. Finally, we also consider a non-convex classification task based on the combination of logistic regression with a non-linear model for moon-shaped binary data (Chapelle et al., (006). In all the considered scenarios, we compare the numerical performance of H-SGD with those of SGD and tune the step-size based on the performance of the latter.
4.1 TOY-PROBLEM
We start with an easy regression problem motivated by Mobahi (016)): 1-dimensional neural network with erf as activation function (see Figure 9 in Section B of the Appendix for graphical representation). We generate synthetic dataset of N = 100 samples, where Ij E [-1, 1], Y/ 3 3, + Ej and ej ~ (0, 1). Regarding the choice of value for the step-size, we use estimate of the smoothness constant L and a L/L. As loss, we use the mean squared error, which, composed with the regressing model, leads to the following non-convex optimization problem
N
w = arg min WER N
Σ (u) - erf(w xz))). 1=1
(15)
By plotting the objective function with respect to w (see Fig. 3 in Section of the Appendix). is easy observe that the PI. condition holds globally, with the value of μ increasing by approaching the minimizer and fa - 0 for w - = (see Fig, F in the Appendix). Consequently. SGD enjoys a global linear convergence rate as proved in (Vaswani al. (2019) but the rate itself, which depends on the value of will dramatically worsen the further the iterates are from the minimizer, leading to a great overall sensitivity of the method in terms of convergence rate the initialization. On the other side, H-SGD, thanks to the homotopy principle, goes around that issue by preserving the vicinity to the minimizer of the current homotopy problem at each homotopy iteration (see Figures7 and 8 in Section B of the Appendix). In order to achieve that, given wi as initial value, we set Uj.0 Wo Iz
for all I...., N and define the following homotopy transformation
Uj Ay + (1 - A) Mj.0.
(16)
As suggested by the theory (see Theorem B.11), we select an exponentially decreasing scheme for the increment Λ in order to achieve linear convergence, As shown in Figure in the Appendix, both H-SGD and SGD enjoy a linear rate of convergence, but H-SGD shows a superior numerical performance. This is due to the fact that the method is designed such that its iterates always lie in the neighborhood of the minimizers where more favorable values of μ lead to a faster convergence. This fact allows H-SGD to enjoy faster global convergence rate than that of SGD.
7

---

Under review as a conference paper at ICLR 2021
4.2 REGRESSION WITH DEEP NEURAL NETWORKS
Our second experiment is inspired by Finn et al. (2017) and Gargiani et al. (2020) and focuses on studying the numerical performance of H-SGD on the task of regressing from input to output of sinusoidal function corrupted by Gaussian noise. In partieular, the input data are sampled uniformly from the interval [-1, 1] and y/j = sin(10- 21) + Ej with Ej ~ *N(0,,0,) for all j = ...... .0000 The regressor is a feedforward neural network with two hidden layers, each of 10 units, and hyperbolic tangent as activation function. As for the previous benchmark, we use the mean squared error as loss. We employ the same values of step-size a and mini-batch M for both H-SGD and SGD, where the step-size value is tuned based on the numerical performance of SGD for the selected mini-batch size (M- = 5). Regarding H-SGD, we set 1/,0 = =² + E, with ej _N(0 (O, 0.01) and employ the same homotopy mapping as in Equation [6 As shown in Figure 6 in the Appendix, also in this scenario H-SGD shows superior numerical performance than SGD, i.c. H-SGD reaches loss of 100- roughly times faster and achieves convergence more than 2 times faster than SGD. The superior numerical performance of H-SGD can be attributed its ability of tracking solution across homotopy iterations (see Figure 10 in the Appendix) which ensures the method to always work in the vicinity of minimizer.
4.3 NON-LINEAR BINARY CLASSIFICATION WITH LOGISTIC REGRESSION
Finally, we test H-SGD also on a classification benchmark with a logistic regression task. In particular, we use a 2-dimensional binary moon shaped dataset (Chapelle et al.) (006) with 1000 samples corrupted by Gaussian noise. As the dataset is clearly not linearly separable, we opt for cubic model, which, used in combination with the logistic regression framework, leads to a non-convex objective function where the optimization variable is the collection of the model's coefficients. For both H-SGD and SGD we use a mini-batch size of 20 and tune the value of the step-size on the SGD's performance for that mini-batch size. Regarding H-SGD, we use as source task the one obtained considering a linear instead of a cubic model, which results in a convex and hence "easy" optimization problem. We then gradually increase the non-liica of the model, i.e. non-convexity of the problem, until reaching in the final homotopy iteration the target problem with the desired cubic model. This homotopy map obtained by multiplying the coefficients of the non-linear terms in the model by À as follows
X(e1 23,1 + + "3,2 + Cg 42,1 + c4 2322 + cs (sxx), JJ,1 2z.2 + ca 23,2) + 07 Tz.1 + Cs 2322 + co. (17)
For the homotopy parameter we adopt the increasing schedule that is suggested in Theorem 3.11 H-SGD outperforms SGD by reaching an error of 0.1 more than two times faster than SGD (see Figure in the Appendix).
5 CONCLUSIONS AND FUTURE WORK
In this paper we propose a new first-order stochastic method for non-convex large-scale problems, called Homotopy- SGD (H- (H-SGD), based on the combination of homotopy methods and SGD. This new homotopy-busee optimization method allows one to exploit easy-to-solve or already-solved problems to solve new and complex ones. This is achieved by approximately and sequentially solving a sequence of optimization problems where the source problem is gradually morphed via homotopy map into the target one. We conduct a theoretical analysis of the optimality tracking properties and convergence rate of H-SGD under some realistic and mild assumptions. The theoretical results are confirmed by some empirical evaluations, which also show the great potential in terms of performance of combining SGD with an homotopy strategy. In addition, H-SGD shows interesting connections with many practical existing heuristics proposed the machine learning literature to speed up the convergence of first-order methods, allowing for a new and more rigorous interpretation of the latter. The current major limitation of the method relies the design the homotopy map. Future work should focus on exploiting the specific problem structure to design optimal homotopy maps. Moreover, under additional assumptions, more theoretical results concerning the quality of the tracked solutions could be derived.
8

---

Under review as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
REFERENCES
E. L. Allgower and Kurt Georg. Introduction to Numerical Continuation Methods. Society for Industrial and Applied Mathematics, USA, 2003. ISBN 089871544X.
Yoshua Bengio. Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. In Proceedings of the 19th International Conference on Neural Information Processing Systems, NIPS'06, 06, pp. 153-160, Cambridge, MA, USA, 2006. MIT Press.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 41-48, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 1781605585161. doi:
11144//555334.155333885 URL htt.:ttps///oooor//0111/////////
Andrew Blake and Andrew Zisserman. Visual Reconstraction. MIT Press, Cambridge, MA, USA, 1987. ISBN 0262022710.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-3) 2018. ISSN 0036-1445. doi: 10.1137/16M1080173
Thomas Brox and Jitendra Malik. Large displacement optical flow: descriptor matching in variational motion estimation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(3): 500 513, 2011. URL http::::mmm.iinormmmtt..o htw.://.................oererarr
2011/Bro1ia,
O. Chapelle, B. Schölkopf, and A. Zien. Semi-Supervised Learning. Adaptive computation and machine learning. MIT Press, Cambridge, MA, USA, September 2006.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high- dimensional non-convex optimization. In 7. Ghahramani, M. Welling, C. Cortes,
N. D. Lawrence. and K. Q. Weinberger (eds.), Advances in Neural Information Pro- cessing Systems 27, pp. 2933-2941. Curran Associates, Inc., 2014. URL http: //sppprsnips.cccppppr//666----11 identtiffidd and attackttackingg the saddle
Peter Deuflhard. Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algo- rithms. Springer Publishing Company, Incorporated, 2011. ISBN 364223898X.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(61):2121-22 2011. URL
http:// jml w.org/papers/ v 1 2/ duchi a.tmm
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, pp. 1126-1 106--133- 135. JMLR.org. 2017.
Matilde Gargiani, Andrea Zanelli, Quoe Tran Dinh, Moritz Diehl, and Frank Hutter. Transferring optimality across data distributions via homotopy methods. In International Conference on Learning Representations (ICLR), 2020.
Michael Gashler, Dan Ventura, and Tony Martinez. Iterative non-linear dimensionality reduction with manifold sculpting. In Advances in Neural Information Processing Systems, volume 20, 01 2007.
Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming, SIAM Journal on Optimization, 23(4):2341-236 2013.
Elad Hazan, Kfir Yehuda Levy, and Shai Shalev-Shwarzz. On graduated optimization for stochastic non con-cc problems. In Maria-FForinn, Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference Machine Learning, ICML 2016, New York City, NY. USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 1833-1841. IMLR.org. org, 2016. URL htttp:/pproceett/ i wwt.:saa.rrrrraa.a/mmmmmm htt.://eeeiaaaaapprrrrraa///aaaa 6.htm

---

Under review as a conference paper at ICLR 2021
Geoffrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Improving neural networks by preventing co-adaptation of feature detectors. arXiv e-prints, 2012. arXiv:1207.0580.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- condition. European Conference on Machine Learning and Knowledge Discovery in Databases Volume 9851, ECML PKDD 2016, pp. 795-811, Berlin, Heidelberg. 2016. Springer-Verie Verlag. URL URL//ttpss///0..org/11.....
gradient methods under the aolyal-undefieedoassiewwee
978-3-319-46128-1 50
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence under the Polyak-Loojsiewiic inequality, February 2017.
Kenji Kawaguchi. Deep learning without poor local minima. In D. D. Lee, M. Sugiyama, Luxburg. I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29,
pp. 586-594, Curran Associates, Inc., 2016. URL wtthttp: D http:p///apprrsnpps.cc//ppppppp
deep www.ninannnngg- wenggg-withhut poor- local minima.pdf
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL //arxiv.org/ hta.///11..99....
Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220 (4598))671-680, 1983. doi:
Shijun Liao. Homotopy Analysis Method in Nonlinear Differential Equations. Springer-Veriie Verlag Berlin Heidelherg, 2012. ISBN 978-3-642-25131-3, doi: 10.1007/998--9-642225122
Qihang Lin and Lin Xiao. An adaptive accelerated proximal gradient method and its homo- topy continuation for sparse optimization. In Eric P. Xing and Tony Jebara (eds.), Proceed- ings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 73 81, Bejing, China, 22 24 Jun 2014. PMLR. URL wwt.ppessssss....eeee /32/1in14.html
Hossein Mobahi. Training recurrent neural networks by diffusion. arXiv e-prints, 2016.
arXiv:1601.04111
Hossein Mobahi and John W. Fisher III. On the link between gaussian homotopy continuation and convex envelopes. In Xue-Cheng Tai, Egil Bae, Tony F. Chan, and Marius Lysaker (eds.), Energy Minimization Methods in Computer Vision and Pattern Recognition 10th International Conference, EMMCVPR 2015, Hong Kong, China, Jamuary 13-16, 2015. Proceedings, volume 8932 of Lecture Notes in Computer Science, pp. 43-56. Springer, 2014. http:ttpp./.....og.......o
978-3-319-14612-
Hossein Mobahi, C.L. Zitnick, and Yi Ma. Seeing through the blur. In Proceedings CVPR, IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 1736-1743, 06 2012. ISBN 978-1-4673-1226-4, doi: 10.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach stochastic programming. SIAM Journal Optimization, 19(4): 1574-1609, 2009.
Sinno Jialin Pan and Qiang Yang. A survey on transfer learning. IEEE Trans. on Knowl, and Data Eng., 1353):335333,, October 2010. ISSN 1041-4347. doi: 10. 2099 URL
Alexandru Suciu. Math 4565
topology homotopy, Spring 2016.
URL https:/
w 6-handout2.pdff
10

---

Under review as a conference paper at ICLR 2021
Iya Sutskever, James Martens, George Dahl, and Geoffryy Hinton. On the importance of initializa- tion and momentum deep learning. In Proceedings of the 30th International Conference on International Conference Machine Learning Volume 28, ICML 13, pp. 11-1119-111-1147. JMLR.org. 2013a.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum deep learning. In Sanjoy Dasgupta and David McAllester (eds.). Proceedings of the 30th International Conference on Machine Learning. volume 28 of Proceedings of Machine Learning Research, pp. 1139-1147, Atlanta, Georgia, USA, 17-19 Jun 2013b. PMLR. URL. http::/ nttp:://proceeddngs.. r.press/ /V2/.vv222. /ttt//t 3.htm 3.html
Shinya Suzumura, Kohei Ogawa, Masashi Sugiyama, and Ichiro Takeuchi. Outlier path: A ho- motopy algorithm for robust svm. In Eric Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference Machine Learning, volume 32 of Proceedings of Ma- chine Learning Research, pp. 1098-1106, Bejing, China, 22-24 Jun 2014. PMLR. URL
http::/pproeeclnss...ppeeess http:///////uuuuuaae/eee suzumural4.aun. 14.tmml
Lisa Torrey and Jude Shavlik. Transfer learning, 2010.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for wver-parameterized models and an accelerated perceptron. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of Machine Learning Research, volume 89 of Pro- ceedings of Machine Learning Research, pp. 1195-1204. PMLR, 2019. URL http://
pprcceddi r.press/v88 vvrress/v///aassaiii www.wawwww.wa.mmmmmmm..
Lin Xiao and Tong Zhang. A proximal-gradient homotopy method for the sparse least-squares problem. SIAM Journal on Optimization, 23(2):1062-109H 2012. doi: 10. 10.1137/120869999
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances Neural Information Processing Systems 27, pp. 3320-3328. Curran Associates, trans wwr.feeeeeeee
Inc., 2014. http://tpp//ppeerssapppcc//ppppp
feat Bretures-ti in- deep- www.uuuraannttttttsreoeoe

---

Under review as a conference paper at ICLR 2021
A APPENDIX
B ADDITIONAL FIGURES
[io]
Fiv. Ad), As 0.3
250
Ao
f(or). Ea..1 [[ LJ)
f(00, X0
10
100
W
10g. A0 [(e): Ag)
Figure 1: Graphical representation of a 1- dimensional function with w;-1,1 ~ / (0, 1) that satisfies the "expected" PL condition (As- sumption 3.6) but not the classical condi- tion in the considered region.
Figure 2: Graphical representation of the re- sults derived in Theorem 3.10 on the optimal- ity tracking properties of H-SGD for general non-convex 1-dimensional function. ticular, as shown in the figure, under the con- sidered assumptions and for "small enough" variations of the homotpy parameter, H-SGD tracks in expectation an r-optimal solution across homotopy iterations.
par-
1.0
0.6
55 [0rwl
0.4
10-2
10-5
0.0
10-7
-30
200
100
-10
10
Figure 3: Graphical representation of the ob- jective function Problem equation 15 vs
Figure 4: Visualization of the estimated parameter for the objective function in Prob- lem equation 15 vs
w.
12

---

Under review as a conference paper at ICLR 2021
16
H-SGD, 32, 4
[[f(o]] - -(we))
10-4
Eiftw]]
107
H-SGD, 6 001
epocks
spochs
Figure 5: Expected optimality gap of H-SGD (blue) and SGD (black) averaged across 100 runs vs epochs for the toy-case described in Section
Figure 6: Expected loss of H-SGD (blue) and SGD (black) averaged across 100 runs epochs for the sine-wave regression case described in Section 4.2
1.0
1.0
fbou
0.0
0.0
0.2
0.0
-20
-10
10
10
Figure 7: Visualization of the homotopy ob- jective functions vs w for different values of homotopy parameter. The black stars repre- sent (w,, f(w,, Az)), ie. the H-SGD iterates with associated objective function value.
Figure 8: Visualization of the target objec- tive functions vs w. The black stars represent (Wk. f(w)), i.e. the SGD iterates with asso- ciated objective function value.
13

---

Under review as a conference paper at ICLR 2021
orf((r a)
Figure 9: Graphical representation of the 1-dimensional neural network deployed for the toy-case experiment descrihed in Section 4.1
600
250
200
37
200
10
-50
-10
-2.0 2.0
-0.75
0.30
-0.8
0.00
0:20
0.30
0.75
1.00
-2.0
-0.70
-0.50
-2.20
0.00
0.20
0.50
0.75
1.00
(a) 0.63
(b) 0.75
100
50
00
-50
1100
100
2.00
-0.25
-0.50
-0.55
0.00
0.35
0.50
0.75
1.00
2.00
00.55
00.00
-0.05
0.00
0.25
0.50
0.75
3.00
(c) 0.86
(d) 0.98
Figure 10: Predicted values S사 (blue) vs true values (black) for different values of generated by using H-SGD.
14

---

Under review as a conference paper at ICLR 2021
H-SGD
SGD
error
10
0
200
400
600
800
1000
1200
1400
epochs
Figure 11: Error averaged across 100 runs of H-SGD (blue) and SGD (black) vs epochs for the classification task described Section 4.3
C ADDITIONAL REMARKS
Remark C.1. Assumption 3.2 can be read as a local Lipschitz continuity of f with respect to its second argument. Regarding the second regularity assumption (Assumption (.3). equation relates the variation of the optimal objective function value for the subset of solutions introduced in Assumption 3.7 across homotopy iterations with the variations of the homotopy parameter, When the solution localization of the solution map is vector-valued, i.e. ws (X) = W (X) (this is the case for instance when the Hessian the objective function is positive definite at those points), this assumption can also be derived directly by combining Assumption 3.2 with the following Lipschitz continuity requirements:
Let > O, we assume that
[s(w" ()), Å) s(w" (2), 2)1 S Kil| killw" - -
Vî, Åe [0,1
(18)
Let K2 O, assume that
|| (²) [(w"(A)
(2)ll S k2llā Åll
(19)
In particular, by combining Inequalities equation 18 18and equation
19 obtain
If(w" (X), 2) f(w" (((w((()) (2), 2)1 I 122 K 1|ā ÅlI
Vλ, Å 10.
(20)
To recover Inequality equation equation y = 8+k2 12,, we use Inequalities equation| equation
20
together with the triangle inequality as follows
If ())) f(w" (A), = ( (й), 2) - (A), f(w (A), f(w" (Δ), A)
< [ (A), 2) -(( + 1/( (A), A) f(wo (1)) 2)
< (6 + ks k2) I| Å11-
(21)
15

---

Under review as a conference paper at ICLR 2021
Notice that the Assumption in equation 18 is less restrictive condition of the following general Lipschitz continuity requirement
If(u, 2) f(w, 2)1 & Cile - wIl, Ve, w E RR, AÅ E [0,
(22)
where C O.
Remark C.2. Assumption 3.6 is more general version of the classical PL condition (see Section 2 Karimi et al.) 2016 for more details on the classical PL condition). In particular, il is straighfforward to observe that the classicul PL condition implies Assumption 3.6 but not vice versa. See Figurell Section B of the Appendix for a graphical representation of a one dimensional example with w1-1,t (0. 1) where Assumption 3.6 holds, while the classical PL condition does not. The expected value operates a smoothing of the function landscape resulting in convexity, while the original function shows many bumps that make it non-convex.
D PROOF OF PROPOSITION 3.7
Proposition D.I. Consider f(w, X)) with A; [0, 1|a and let Wi-1,t Wi-1-(((p-1,-- denote the iterate obtained at the i-th homotopy iteration by applying itterations of SGD with S k -
and a 1. Under Assumptions 3.4 3.5 and 3.6 if Eg; [f(w;-1,1, Xx)] f (2x) S B, then
Egp [[(16-1,+1,,.)) (1a) B
Proof. For ease of notation, we use the shorthands w4-1, g(w--10s <i, Az).
((-1,(((-11,-11) and g:
Considering Assumption 3.4 together with the definition of SGD iterate and using Assumptions 3.5 and 3.6 we obtain the following inequalities
Eq [f(4--1441 A:)1 s EEu-i.
[ a 9t)
La²
11
2
Law of Iterated Exp.
-gp-1.e-1] Fes
S(ws-10s - aaaaaV((ii-- )c)s + 2
La²
|1gell 2
S1-1,-11
Assumption 3.5
f(15-1,1 Ai) + (-a+
La²
/Vff(;; }m]1?
+ La20²
E E
2
2
If a S 1 then
D.
B [fWi- A:)] S Eeg-n.en [[ Ad) + (-2) | (.)),,))))))1
LaZo²
(23)
We now make use of the "expected" PL condition and derive the following inequalities
La202
Egg-1. [f(W-11,41 Xx) f Xx) S E [1V5 10]
2
Assumption
Lazo²
J E [Egg-n. (WW X,) - (Mi)] + 2
(24)
From Inequality equation 24 it follows that, whenever Eg [S( A,)l (A,) 2
a²
2n
the objective function decreases expectation, i.c. Egg-1.0 (f [f A1) f(W,-1,t: Ax)] S Given that by assumption
d² we can consequently conclude that, if E Egg--1e-1 [f (1 A,)
2p fww A²) < B, then E [[ Ax)] - -*(As) B.
E PROOF OF THEOREM 3.8
Theorem E.1. Consider the minimization of f(w, A²) with d E [0, 1] via SGD. Let Wi-1 (E-1(ER-1)) be the random initial point associated with the i-th homotopy iteration with
16

---

Under review as a conference paper at ICLR 2021
Bin-1 1x - ate with I Under Assumptions 3.4 3.5 the following convergence rate to a minimizer's 's neighborhood
I B and w1-1, (0-1,((5(-11--1) denote the t-th SGD iter-
and 3.6 SGD with a constant step-size a S attains
o²
E5 [f( Aa) - f" E ( [f(We-1, 2o) (A,]+
(25)
2μ
with p = af). With a .. we obtain p == (1 2)
Proof. For ease of notation, we use the shorthands 11-1,1 = (6-1,(((--111-11) and 9: g(4 E/ A²).
By combining Assumption 3.4 with the definition of SGD iterate, for all 1,.... k 1, we obtain the following bound on f(w++1, Ax)
[w1-1,441 X:) S [w1-111 1,,, X:) (W[(Wi-1,) Xz), 11-1, wi-1,)) + 2 ||wi-1,411 1x
La
- f(11-111 Ac) a. (V[(Wii1, Xz). gt)
|1
We now take the expectation with respect to all the sources of randomness involved and then we apply the law of iterated expectations, together with Assumption 3.5
Ee (1 d:)1 s Een-i.
[[ui-La Ao) aVV gt) +
La
119011?
2
Law lterated Exp.
Egp-1 Beg
Mws-110 2 -a) aVV[((u=11, Ae),
La²
|1gell
S--1,-11
2
Assumption 3.5
f(u5-1,t3 2₂) (-a+
La²) ( |V xt]1
La202
E
2
If a S J. then
Eq [11--1441, X,) S Pep-ne-n [(wi-1)))))) 21) + (-5) V x0]13]
La²o²
+
2
(26)
We now apply the PL condition to Inequality equation 26 and we obtain
Assumption 5.6
Equ-na [[W1 Az)
Eq - [f(W;-14; As)
(27)
oapp flis Ar) (*())) La2o²
2
By subtracting (Ai) on both sides and setting t. we obtain the following inequality
o²
Eg [f(W1-1,411 Ax) f* (1- (')
(1-1) EG 1. [f(w--1,, Xd) f*
2L
(28)
By applying Inequality equation 28 recursively, we derive the following bound
Eep-re-11 [f(1-11, Ad) (A)) < (1 () Ben-- [f(w;-1, Ar) / (Ax))
2 A-1
(29)
4)
+
1
1)
2L
Finally, by using the limit of geometric series, we obtain
Eqp-1.--1 (1 Ar) (Ax)] < (1 (1-1) (1- 4) Eep-1 [s(wi-1, X:) (A:)]] + o²
(30)
2p
17

---

Under review as a conference paper at ICLR 2021
F PROOF OF LEMMA 3.9
Lemma F.1. Assume || - Aull c,
S
and let wi denote the i-th iterate of Algorithmi /
b4
with S J. Under Assumptions 3.4 B. In addition, let
3.3 and
3.5
3.6
if Ow, (A.) S B - (6 (00+7)c then Ow, (N++1)
2p(6 + 7) + 0²
kiax
logp
(31)
B
If uw, (1+11) BBO 847
B
and t 2 kmax then Pwits (1+11) S B (6 + 7)
Proof. We start by deriving an upper bound on Egyy [f(ws and ||A+1 - >ul S e. For that we use the regularity Assumptions 3.2 and 3.3 together with the triangle and Jensen inequalities as follows
(N++1) with Φw. (Ax) S B
Eg [f(w, A++1)] - (*+11) = [Eeg [f(ws A1+1)l - -f ()++1))
[B [f(wi, (1t1) f(we, Ao) f(ws, X.] - (A:41)
+ + (2()
Triangle and Jensen Ineq.
(32)
[Bgn [f(ws, Ae] - (A:) + Egg [If(wi Ast1) - f(ws, A,)I
(Aa)) 100---"(-- (*(+++)]
Assumptions
E1 [f(w,, X,]] - f + (8+
From Inequality equation 32 it follows that, if own, (2i) s B (5 + 7)c with Qw, (A++1) S B.
B then (647)²
We now use the results of Theorem 3.8 derive lower bound on the number of SGD-steps such that, if @w, (Ae+1) < B, then owne (A++1) B (5 + 7)cc. We start considering the following inequality
d²
Equay [[(w411, Aet1)l - 1 (As=1) S p² [Een [[ws,, (+t1)) - +
2/1
(33)
S S o²
24
From Inequality equation
33
follows that, ow (di+1) S B, then Sioc (Ai+1) B (6 77
with < 84y
B
whenever
2p
2 log, 1- 2u(6 + 7) + o²
)
(34)
2pB
G
PROOF OF THEOREM 3.10
Theorem G.I. Assume there exists 2μ < S B and č== min fci, 62) with
4 = 78+7) B r), 62 = (1 - p²) 0² /2p
(35)
p (5 7)
In addition, let
kinax log, (1- o²
2p1r )
(36)
Consider Algorithm
with < I. k: 2 himax and ||itt1 - >ill S e, where 0 S S ē.
Under Assumptions
3.4
3.3 and 3.5 3.6 drn, (2e) then Durgps (de41) Sr.
18

---

Under review as a conference paper at ICLR 2021
Proof. We consider ow; (A,) S lf - (B
-0rr r) with r S B, then ow, (A,) B (ā + 7)
and, as shown Lemma 3.9. Φw: (At+1) S B. This allows us to use the results of Theorem 3.8
We now derive upper bound Eggry [f(W41 A++1)l - -
(" by considering the results of Theorem t.gtthr with the regularity Assumptions 3.2 and 3.3 and the triangle and Jensen inequalities as follows
Eqjia) [[(s++,, (++1)] - (Mct1) S p [Een [[(we, Act1)l I (Ai+1)] + o²
2/1
p Egn [f(wi, Aeti) + -(ww, 2:) f(ws, 2,)] f (*c+1)
o²
+ ( -Aii
24
(37)
Triangle and Jensen Ineq.
p [EEM) [S(ws, - [ + EEEee [[[(wrs Aot1) - [(ws, X:)I]
o²
(M* - (((Aa+1) +
24c
Assumption and 3.3
0²
[En [f(wi, X:)] - f +
())AA - -
2p
Using the fact that ow,, (A,) S and that || - A S we now solve the following inequality for order to find an upper bound on the variation of the homotopy parameter such that Pw; (Ai+1) S
o²
p r + p (5 + +
Sr.
(38)
24
Inequality equation 38 holds whenever
h 2 log (1 o²
(39)
2/1r)
and
(1 p²)rr 12/2
e<
(40)
2 (ō + 7)
with r > 2/c
H PROOF OF THEOREM 3.1 1
Theorem H.1. Let ý E (1 0² B 1) and consider Algorithm
with S E.
Dwo (2o) S r with
24 (1-Ø) Srg B and (p), addition, let 6 = (647) B r) and
if 2 (0) logp (1+ 8=م
C5 =
(41)
p=pp
en (0+7)
othenwise,
with Eo = Egjor [w No)1
f (No)-
Under Assumptions 3.4 3.3
and 3.5
3.6
11 Asll s min {e-n ( with In (Cp p), then
0²
Egj4 [f A++1)] - fr (1+r)) < g [Ego [f إo)> (*(o)) +
Σ
(42)
j=0
Proof. We start assuming that ow, (Ai) S r, with <r S B and | - Aull S with 6 =
(847) (B r) such that ow., (A++1) < B.
19

---

Under review as a conference paper at ICLR 2021
In partieular, consider the following upper bound Esc+i1 [f A++1)l - (*(++1),
Esito [f(w+11, (++1)] f (A++1) S pK [Een [f(w, Aa) - [f
pe (6 7) Ads+1 a²
(43)
2/1
See the the proof of Theorem 3.10 for a derivation. We then proceed by induction. Therefore, we assume
0² f-1
Egg [f - (AA,) S pz [Esoa] [f(wo, do)l f*uo]]
p
(44)
2p
1=
and derive the conditions on AA+41 such that
i
Eejia [f(W++,, A++1)] f (A+t1) S 10t [Egol [f Ao)1 - ff (Au)] +
p
(45)
2p
3=
In order to achieve that, we consider the upper bound on Eggin) [f(W++1, d(t1)l (As41) given by Inequality equation 43 and solve the following inequality for A4++1
a²
x [Bij [f(w;, - f" + p* (6 + 7)) Ad++1
+
2μ
(46)
0²
s 5 EEj [f Ao)] - (Ao)
p
2μ 5=0
We obtain that Incquality equation 46 satisfied whenever
g+
Ee
[uw,, do)] (Ao) p² EEjs [f(ws, As) - (Ar)
a²
Ej
AA++1
2p
(47)
p=15 +
RHS
We derive lower bound on the right-had side of equation 47 by considering the induction assumption, ie. Inequality equation (44 and we obtain
ge (p x²) [E [wo, Ao)1 (*oo)
2
2p
Σ
E
RHS >
(48)
(77)
Considering that l 2 log then
0²
i-1 Σ E
20.
(49)
2/
j=0
j=0
Consequently, Inequality equation
47 is satisfied whenever
Aditi (p- p²) p
60
D'
(50)
where 6o Eejo [f(wa, Ao)] -
f (Ao).
To conclude this first part of derivations, we obtain that, whenever Inequality equation 50 is satisfied, then
Eggera [f(W++1, A(+1)1 - fr (As+1) S pi+1 (Eşg) [f 2o)1 - fr (Ao)) +
Σp
p..
(51)
2μ
j=
In order to ensure that owits (1+11) < consider Inequality equation 51 and use the fact
that &veg (Ap) S r, i.c Eggl [f An) - (*n) I r, to upper bound the right-hand side of Inequality equation 51] We then solve the resulting inequality for
0² EE Sr.
(52)
2μ 1=0
20

---

Under review as a conference paper at ICLR 2021
(1-p"t1) (1-1)
Considering that Ej= 0
obtain that Inequality equation 52 is satisfied whenever
(53)
24 (1-p)
By combining Inequality equation 53 with the fact that r S B, we obtain the following upper bound on أ
0²
(54)
2p B
To further simplify the bound equation 50 we define the following constant
if > lo) logp (1 6+2
Cp
=
20
(55)
p-p
En (64%)
otherwise,
and obtain that Inequality equation holds whenever A1+11 Se with 1j 2 1Cp
21


Reviews:
[{"review_id": "umBpbSwGhvD", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "\nSummary: \n\nThe paper proposes a homotopy approach for minimizing finite sum optimization problems. The idea behind HSGD is to gradually solve a more and more similar problem to the original one using SGD, and always use the approximate solution of the previous problem as a good starting point to solve the new one.\n\n\n\nMain reason to accept the paper : \nI believe that homotopy is a nice idea that is still under-explored in the optimization/machine learning literature. I find the topic to be interesting for the ICLR community. \nTo the best of my knowledge, H-SGD is a novel (in the form that it is stated).\n\n\nMain reason to reject the paper:\n\nThe main problem I have with this paper is that HSGD is not justified to outperform vanilla SGD in any scenario. \nBesides that, nothing else about this paper stands out, and a lot of other criticism can be made (see detailed comments). \n\n\nOverall, I believe that the paper's contributions are not substantial enough for acceptance, and thus I'm recommending to reject this paper. I am willing to change my evaluation, given that the authors persuade me that the provided theory of HSGD is indeed better than the theory of vanilla SGD. (see points 3b, 5,6 below) \n\n\n\nDetailed comments: \n\n1) Proof of Proposition 3.7 seems incorrect/incomplete. I have a problem with the last paragraph of the proof, which does not justify the proposition at all. I have checked myself and the proposition indeed holds as a consequence of (24); please fix the proof. \n\n2) Theorem 3.8.: This is nothing new, but rather a standard analysis of SGD under the uniformly bounded variance. Please reference. \n\n3) There are a few misleading claims throughout the paper. \n3a) First of all, the paper sells the application as a nonconvex optimization while only providing the results in the PL setting. Note that PL is rather a generalization of the strong convexity; the class of PL problems is significantly rather similar to the strongly convex problems than the general nonconvex objectives. In fact, the whole motivation of PL inequality was to find the broader class of problems where one can get a strongly convex-like rate. I thus find misleading to present the paper as a nonconvex optimization. \n3b) It is claimed that Homotopy SGD converges linearly to the neighborhood of the optimum, while \"vanilla SGD can only ensure a global sublinear rate of convergence\". A similar claim is made in the abstract too. This is simply not true. Vanilla SGD converges linearly to a neighborhood of the optimum as well! This is even proven in the paper; Theorem 3.8 provides such a rate with $\\lambda=1$.\n\n4) Assumptions are very strong. Specifically, the boundedness of the variance is very rarely satisfied in practice and is not required for the state-of-the-art SGD analysis under relaxed, strong convexity [1,2]. Note that in certain scenarios, one should not assume bounded variance and strong convexity (or its realizations) at the same time as it significantly shrinks the class of functions [1]. \n\n5) The theory is not complete. It would be great to have to state what exactly the complexity of HSGD is, namely, how many stochastic gradients in total one needs to get to some\nspecific neighborhood of the optimum of (1). Without such a result, one can not argue that HSGD is better than any baseline, such as vanilla SGD. In fact, I do believe that the overall rate of HSGD would be inferior to the rate of vanilla SGD. Note that Thm 3.11 does not provide anything close to it, as it gives a suboptimality of $f(x,\\lambda_i)$ only (we want $\\lambda =1$). \n\n6) Following the point 3b) and 5), I do not see any advantage (in theory) of homotopy SGD over classical vanilla SGD. There is maybe only one -- while vanilla SGD and HSGD require a PL condition among a different set of points; there is thus a chance that the \"empirical PL\" would be better for the HSGD. However, one can not know this in advance; and one can not know this even during the run of the algorithm. Further, the current theory does not allow to exploit \"better\" PL constant in certain areas of the objective since Assumption 3.6 considers a single $\\mu$ throughout $R^d\\times [0,1]$ (vanilla\nSGD requires PL to hold only over $R^d$ so it is even less restrictive).\n\n7) An approach similar to homotopy optimization (gradually solving easier problem instances, which could be presented as homotopy optimization if one wanted to) already made a significant impact in the optimization field. Specifically, it was shown that such an approach -- Catalyst -- might accelerate (in the sense of Nesterov) almost any optimization algorithm [3]. \n\n8) Please add some comments next to the assumptions explaining how strong each of those is. \n\n9) Correctness: I did a detailed check of some results and a high-level check of the rest. I did not find any major or non-fixable flaws; the obtained results are reasonable.\n\n10) Experiments: Experiments are not very strong either. HSGD is shown to outperform SGD in three toy examples only (often no by a large enough margin); this is not enough. \n\n11) Question: Why do you limit yourself to the homotopy SGD method? I see no reason why the homotopy method can not be coupled with other optimizers; i.e., one can do SGD without bounded gradients, variance reductions, acceleration, or possibly even second-order methods. I also see that some of these methods would directly fit into the proposed homotopy theory. \n\n\n\n[1] Nguyen, Lam M., et al. \"SGD and Hogwild! convergence without the bounded gradients assumption.\" arXiv preprint arXiv:1802.03801 (2018).\n\n[2] Gower, Robert Mansel, et al. \"SGD: General analysis and improved rates.\" ICML 2019.\n\n[3] Lin, Hongzhou, Julien Mairal, and Zaid Harchaoui. \"A universal catalyst for first-order optimization.\" Advances in neural information processing systems. 2015.\n\n\n************EDIT***************\nI have raised my score to \"5\" after the author's response. While now I believe that once can come up with a scenario where the proposed theory of Homotopy SGD outperforms the vanilla SGD, it is still not properly demonstrated in the paper; there are a lots of hidden strings attached to the provided convergence bound (explained in my response). ", "extra_scores": {}, "extra_text": {}}, {"review_id": "DR9VsHYzqlE", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 proposed a Homotopy-Stochastic Gradient Descent (H-SGD) algorithm by applying homotopy strategy to explore the nice local structures of problems. H-SGD can gradually approximate to the target objective function and enjoys a global linear convergence to reach a neighborhood of a minimizer. As verified by the author, the assumption of this paper is weaker than its predecessors, Karimi et al., 2016; Vaswani et al., 2019. Further, the numerical experiments verified the effectiveness of H-SGD on regression and classification tasks.\nHowever, there are still some concerns about this paper:\nRecently, people are focusing on investigating convergence to achieve the global minimizer or $\\epsilon$-stationary points. It is quite novel that authors brought the convergence to a sub-level set up. However, by the main theorem 3.11 of the paper, the sublevel set is $O(\\frac{1}{u})$. It still remains unclear whether it is acceptable as $\\mu$ could be $1e-6$, $1e-7$ as shown by the author. Further, achieving the global linear convergence to a sublevel set is not new, it is even achievable for the widely used SGD with momentum for the quadratic function without any assumptions on it.\nOn the other hand, the author didn’t provide a detailed formulation (examples) of $f(w,\\lambda)$ throughout the whole paper, which would increase the difficulty for the reader to understand. Suppose the loss $f_i(\\w)$ satisfies the assumption of $\\w$, then losses with the l2_morn (l2_norm^2) regularization,  $f(\\w,\\lambda) = 1/N\\sum\\limits_{i=1}^N f_i(\\w)  + \\frac{\\lambda}{2}\\|\\w\\|^2$ satisfies the assumptions of the paper as long as $||\\w||$ is bounded. The global convergence to the optimal solution which also has been well studied in other literatures with or without PL condition, such as,https://arxiv.org/pdf/1812.03934.pdf. As reaching a neighborhood of a minimizer is an unavoidable step to reach the global minimizer, the theory contribution of the paper is required to be considered more carefully.\nLastly, the numerical experiments are quite limited. https://arxiv.org/pdf/1811.03962.pdf  has shown that deep neural networks with relu activation, such as resnets, satisfies PL condition. The effectiveness of H-SGD would be more persuasive if the experiments could be conducted on real data sets (cifar, imagenets, etc) using well recognized backbones (resnets, etc) even though it probably violates the assumption to some degree..", "extra_scores": {}, "extra_text": {}}, {"review_id": "BEgjKkahj_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 homotopy SGD (H-SGD) which solves a sequence of unconstrained problems with a homotopy map and homotopy parameter. The authors analyze the algorithm for solving nonconvex problems satisfying PL condition. The analysis works with a generic homotopy map and homotopy parameter satisfying certain conditions (given in Sec 3.1). The authors show linear convergence to a neighborhood of the minimizer. The theoretical results are validated with experiments with clear explanations.\n\nIn Gargiani et al, 2020, it was shown that using homotopy with SGD is a useful approach for transfer learning. This paper paper continues along this line, and relaxes the assumption of local strong convexity used in Gargiani et al, 2020 to PL inequality.  \n\nThis being said, I found the writing of the paper unclear, making the motivation of the paper also unclear. For example, the paper keeps comparing H-SGD with SGD throughout. But in the regular optimization setting, it is not clear why one needs to utilize homotopy. For example, in page 3 it is written \"given our setting, vanilla SGD can only ensure a global sublinear rate of convergence\". First, what is the reference for this claim? Second, I think with the PL assumption, it is well known that SGD gets linear convergence to a neighborhood of the minimizer (In Vaswani et al, 2019, proof of Thm 4, we will not let $\\sigma=0$, but keep it, which will determine the neighborhood to which the algorithm converges linearly).\n\nOn the other hand, in Sec 4.1 the authors explain that even if PL holds globally, the constant might be getting worse as moving to the solution, so SGD suffers from the worst case constant in the rate and H-SGD has a better \"conditioning\". I think such explanations are useful and should be given throughout.\n\nIn terms of the assumption, the authors claim in Remark C.2 that it is weaker than PL of Vaswanit et al, 2019. In the proof of Prop 3.7, the authors use law of iterated expectation to iterate the expectation one step and use the expected PL condition. Why can't the same be done in the proof of Thm 4 of Vaswani et al, 2019? From what I see, the same assumption can be used in Vaswani et al, 2019 to get the same result with SGD. Can the authors clarify this part?\n\nAnother point about Assumption 3.6 is the following: the authors state in page 5 that compared to PL, this assumption is local. If the assumption is local, this means that convergence results of the paper will also be local. The natural question will then be, what does H-SGD do until it reaches to local region where the expected PL inequality holds?\n\nAssumption 3.1 is quite unclear, and the notations are undefined. Given that the assumption is not explained in words, it makes it quite difficult to understand what it means. Moreover, what is $z$ that is used in Assumption 3.1? I did not see it defined anywhere. Could the authors be more explicit here, by defining the notation used in Assumption 3.1 (for example $U^*(\\lambda)$ and $z$).\n\nIn Alg.1, $h(i)$ needs to be chosen such that its sum from i=1 to n will be 1. Does it mean that one needs to know $n$ to run the algorithm? If so, then this will require setting an horizon before running the algorithm. Is there a way to ensure this \"sum to 1\" condition holds, adaptively?\n\nAssumptions given in Sec 3.1 are quite vague, is it possible to give examples? For example, the authors might add some examples of homotopy map and show if the assumptions are satisfied.\n\nIn the experimental part, only toy examples are considered. I would suggest the authors to include more \"real-life\" problems to show the merit of the new approach in practice.\n\nMinor comment: Is the algorithm of https://arxiv.org/abs/1902.00126 a special case of H-SGD? The idea in that paper seems similar.\n\nOverall, I think that presenting H-SGD as an alternative to SGD makes the motivation of the method unclear. Moreover, the notation and explanations for the assumptions, theorems are missing and necessary for judging the significance of the results, compared to related work. As a follow-up on Gargiani et al, 2020, I find the paper interesting, however, the assumptions given in Sec 3.1 should be compared with Gargiani et al, 2020 clearly. In the current situation, the presentation of the paper is problematic, which in my opinion, also shadows the concrete contribution. If the authors clarify my questions, I can reconsider my score.\n\n============ after discussion phase =============\n\nMy important questions about locality of PL are not explained. For example, on why the same locality argument cannot be done on Vaswani et al, 2019's analysis on standard SGD. As I also stressed in my original review, I believe the idea of the paper is interesting and can be useful, however the merit of the paper is not explained clearly in the paper. Rather than comparing by SGD with vague arguments, I think the authors should clearly explain under what setting is homotopy preferable to SGD and why, which will make the paper much more accessible and impactful. Given the lack of explanations, unfortunately, I keep my score for rejection.", "extra_scores": {}, "extra_text": {}}, {"review_id": "AGqSNDYzB2A", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "1. It seems to me the proposed Homotopy-SGD is not a practical algorithm, as in each iteration the algorithm has to solve a nontrivial (possibly nonconvex) subproblem. In other words, each subproblem can be as difficult as the original problem. This leads to an essential question that what is the practical motivation of this algorithm?\n\n2. Algorithm 1 is not complete. The authors should explicitly write down Step 6: w_i \\leftarrow SGD(.)\n\n3. I do not understand the notation [0,1]^z.\n\n4. I do not understand why do you define W*(\\lambda) in Assumption 3.1, it seems to be exactly the same as U*(\\lambda). It looks this assumption is nothing else than assuming the set of minimizers of each subproblem is nonempty. If it is, I would suggest making the statement simpler. \n\n5. What is the difference between Assumption 3.2 and 3.3? \n\n6. I do not agree that Assumption 3.6 (the key assumption for local convergence rate analysis) is weaker than the original PL condition. I agree that the global PL condition is quite strong for a nonconvex problem and is indeed unrealistic. But this is not the reason that your assumption is weaker. Note that you involve expectation over the past random samplings and algorithmic iterates in this assumption. How can one guarantee that the algorithmic trajectory should satisfy a specific function growth condition? A function regularity should always be stated with respect to the problem itself and should be independent of the algorithm. That is, it should be a problem-intrinsic property. Typical examples include Lipschitz continuity, quadratic growth, strong convexity, etc. On the other hand, I tend to think the expectation used in this assumption is also tailored for the analysis. If the authors assume a local version of the PL condition, the first difficulty would be to show the iterates of H-SGD method stay within this local region (in which the PL condition holds). It is because the convergence result is in expectation (due to the randomness of the algorithm), in order to use a deterministic local PL condition, a natural way is to bound the iterates within this local region with high probability, but this is often the hardest part. \n\n7. The convergence result seems to be a local one as you have to assume a good initialization, which you should explicitly state in abstract and introduction rather than saying ‘H-SGD can achieve a global linear rate of convergence’. Also, this good initialization requirement is related to my last comments on your assumption 3.6. You directly assume the algorithm can be initialized within a local region in expectation and the then ‘expected PL condition’ can help H-SGD to make a good progress towards the minimizer. Lastly, local convergence can be established. However, as I commented above, these assumptions are too tailored and stringent. \n\n8. I do not see why Theorem 3.11 implies a linear rate of convergence. The last term in (14) is divergent when i tends to infinity.\n\n9. I suggest change ‘problem 1’ to ‘problem (1)’ globally.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors provide a homotopy framework for SGD in order to exploit structures that arise by construction, such as PL. I very much liked the delineated homotopy analysis which is general (i.e., as opposed to simply adding a quadratic, the authors consider a homotopy mapping). While the algorithm should not be considered new, it is still a good proposal to consider in the SGD applications setting. Unfortunately, I cannot recommend acceptance because of several issues that the reviewers raised in detail: Strength of the assumptions, unclear performance improvement in practice, applicability of the locally PL condition, among others. 
Decision: Reject