summaries: 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. 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. 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?
abstractText: 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 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 minimum while maintaining fast and inexpensive iterations. Experimental evaluations confirm the theoretical results and show that H-SGD can outperform standard SGD.
references.authors: E.L. Allgower Kurt Georg
references.title: Introduction to Numerical Continuation Methods
references.venue: Society for Industrial and Applied Mathematics,
references.authors: Yoshua Bengio Pascal Lamblin Dan Popovici Hugo Larochelle
references.title: Greedy layer-wise training of deep networks
references.venue: In Proceedings of the 19th International Conference on Neural Information Processing Systems,
references.authors: Yoshua Bengio Jérôme Louradour Ronan Collobert Jason Weston
references.title: Curriculum learning
references.venue: In Proceedings of the 26th Annual International Conference on Machine Learning,
references.authors: Andrew Blake Andrew Zisserman
references.title: Visual Reconstruction
references.authors: Léon Bottou Frank E. Curtis Jorge Nocedal
references.title: Optimization methods for large-scale machine learning
references.venue: SIAM Review,
references.authors: Thomas Brox Jitendra Malik
references.title: Large displacement optical flow: descriptor matching in variational motion estimation
references.venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,
references.authors: O. Chapelle B. Schölkopf A. Zien
references.title: Semi-Supervised Learning. Adaptive computation and machine learning
references.authors: Yann N Dauphin Razvan Pascanu Caglar Gulcehre Kyunghyun Cho Surya Ganguli Yoshua Bengio
references.title: Identifying and attacking the saddle point problem in highdimensional non-convex optimization
references.venue: Advances in Neural Information Processing Systems
references.authors: Peter Deuflhard
references.title: Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms
references.venue: ISBN 364223898X
references.authors: John Duchi Elad Hazan Yoram Singer
references.title: Adaptive subgradient methods for online learning and stochastic optimization
references.venue: Journal of Machine Learning Research,
references.authors: Chelsea Finn Pieter Abbeel Sergey Levine
references.title: Model-agnostic meta-learning for fast adaptation of deep networks
references.venue: In Proceedings of the 34th International Conference on Machine Learning Volume 70,
references.authors: Matilde Gargiani Andrea Zanelli Quoc Tran Dinh Moritz Diehl Frank Hutter
references.title: Transferring optimality across data distributions via homotopy methods
references.venue: In International Conference on Learning Representations (ICLR),
references.authors: Michael Gashler Dan Ventura Tony Martinez
references.title: Iterative non-linear dimensionality reduction with manifold sculpting
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Saeed Ghadimi Guanghui Lan
references.title: Stochastic first- and zeroth-order methods for nonconvex stochastic programming
references.venue: SIAM Journal on Optimization,
references.authors: Elad Hazan Kfir Yehuda Levy Shai Shalev-Shwartz
references.title: On graduated optimization for stochastic non-convex problems
references.venue: Proceedings of the 33nd International Conference on Machine Learning,
references.authors: Geoffrey E. Hinton Nitish Srivastava Alex Krizhevsky Ilya Sutskever Ruslan Salakhutdinov
references.title: Improving neural networks by preventing co-adaptation of feature detectors
references.venue: arXiv e-prints,
references.authors: Hamed Karimi Julie Nutini Mark Schmidt
references.title: Linear convergence of gradient and proximalgradient methods under the polyak-undefinedojasiewicz condition. In European Conference on Machine Learning and Knowledge Discovery in Databases - Volume 9851
references.venue: ECML PKDD
references.authors: Hamed Karimi Julie Nutini Mark Schmidt
references.title: Linear convergence under the Polyak-Łojasiewicz inequality, February 2017
references.authors: Kenji Kawaguchi
references.title: Deep learning without poor local minima
references.venue: Advances in Neural Information Processing Systems
references.authors: Diederik P. Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations,
references.authors: S. Kirkpatrick C.D. Gelatt M.P. Vecchi
references.title: Optimization by simulated annealing
references.venue: Science,
references.authors: Shijun Liao
references.title: Homotopy Analysis Method in Nonlinear Differential Equations
references.venue: ISBN 978-3-642-25131-3
references.authors: Qihang Lin Lin Xiao
references.title: An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization
references.venue: Proceedings of the 31st International Conference on Machine Learning,
references.authors: Hossein Mobahi
references.title: Training recurrent neural networks by diffusion
references.venue: arXiv e-prints,
references.authors: Hossein Mobahi John W. Fisher III
references.title: On the link between gaussian homotopy continuation and convex envelopes
references.venue: URL https://doi.org/10.1007/
references.authors: Hossein Mobahi C.L. Zitnick Yi Ma
references.title: Seeing through the blur
references.venue: 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,
references.authors: Arkadi Nemirovski Anatoli Juditsky Guanghui Lan Alexander Shapiro
references.title: Robust stochastic approximation approach to stochastic programming
references.venue: SIAM Journal on Optimization,
references.authors: Sinno Jialin Pan Qiang Yang
references.title: A survey on transfer learning
references.venue: IEEE Trans. on Knowl. and Data Eng.,
references.authors: Alexandru Suciu
references.title: Math 4565 topology homotopy, Spring 2016
references.venue: URL https:// web.northeastern.edu/suciu/MATH4565/MATH4565-sp16-handout2.pdf
references.authors: Ilya Sutskever James Martens George Dahl Geoffrey Hinton
references.title: On the importance of initialization and momentum in deep learning
references.venue: In Proceedings of the 30th International Conference on International Conference on Machine Learning - Volume
references.authors: Ilya Sutskever James Martens George Dahl Geoffrey Hinton
references.title: On the importance of initialization and momentum in deep learning
references.venue: Proceedings of the 30th International Conference on Machine Learning,
references.authors: Shinya Suzumura Kohei Ogawa Masashi Sugiyama Ichiro Takeuchi
references.title: Outlier path: A homotopy algorithm for robust svm
references.venue: Proceedings of the 31st International Conference on Machine Learning,
references.authors: Sharan Vaswani Francis Bach Mark Schmidt
references.title: Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron
references.venue: Proceedings of Machine Learning Research,
references.authors: Lin Xiao Tong Zhang
references.title: A proximal-gradient homotopy method for the sparse least-squares problem
references.venue: SIAM Journal on Optimization,
references.authors: Jason Yosinski Jeff Clune Yoshua Bengio Hod Lipson
references.title: How transferable are features in deep neural networks
references.venue: Advances in Neural Information Processing Systems
sections.heading: 1 INTRODUCTION
sections.text: This paper focuses on the theoretical development and analysis of a stochastic optimization algorithm, called Homotopy-Stochastic Gradient Descent (H-SGD), based on 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
  w∗ ∈ arg min w∈Rd f(w) := 1N N∑ j=1 fj(w)  , (1) where f : Rd → 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 1 via a 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 et al., 2018), Adagrad (Duchi et al., 2011), Adam (Kingma & Ba, 2015). At the iteration t, the algorithms of this class acquire a stochastic estimate of the function value f(wt, ξt) and the gradient g(wt, ξt) by calling the oracle with input wt, where ξt is a random variable, i.e. when the noise comes from subsampling as in the mini-batch scenarios, then ξt ∈ {0, 1}N with ‖ξt‖1 = M and g(wt, ξt) = 1 M ∑N j=1 ξt,j · ∇fj(wt). In the case of SGD, for a given w0 ∈ Rd and α > 0, the iterates are generated as follows
  wt+1 := wt − αg(wt, ξt) . (2)
  Consequently, the iterate wt+1 = wt+1(ξ[t]) is a function of the history ξ[t] := (ξ0, . . . , ξt) (also w0 should be included in case it is a random initial point) of the generated random process and hence is itself random.
  In general, stochastic first-order methods enjoy fast convergence when the problem is characterized by a certain structure. In particular, when the Polyak-Łojasiewicz (PL) condition (see Karimi et al., 2016, for more details on the PL condition) holds for the objective function in Problem 1, then, with a “small enough” value for the step-size, the SGD iterates converge linearly to a minimizer’s neighborhood (Karimi et al., 2016; Vaswani et al., 2019). Unfortunately, in many machine learning applications, the PL condition is not a realistic assumption as the landscape is generally characterized by the presence of multiple local minima and saddle points (Dauphin et 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, a 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 landscape which we generally dispose of. In addition, these heuristics 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 a minimizer and independently from the starting point. In this regard, homotopy methods are a 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. (Deuflhard, 2011), (Liao, 2012). Such methods are also suitable to solve complex non-convex optimization problems where no or 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 et al., 2014; Gargiani et al., 2020).
  In this work, we propose a stochastic first-order numerical method to solve Problem 1, called Homotopy-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 2), our contributions are as follows
  1. In Section 3, we provide a general theoretical analysis of H-SGD under some mild assumptions, 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 a global linear rate of convergence to a minimizer’s neighborhood when used in combination with a specific schedule for the homotopy parameter, i.e. ∆λi 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 a smartly designed homotopy map can outperform SGD.
sections.heading: 2 HOMOTOPY-SGD
sections.text: Homotopy-Stochastic 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 f(w, λ) : Rd × [0, 1]→ R, such that, when λ = 0 we recover a well-behaved function, e.g. convex, or a function with a known minimizer’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 f(w, 1) = f(w) (see Suciu, 2016, for more details on homotopy functions). By using such a homotopy map, H-SGD finds an approximate solution of Problem 1 by approximately solving a series of parametric problems that gradually leads to the target one. In particular, in each homotopy
  iteration i, H-SGD tackles a parametric problem of the form
  w∗i ∈ arg min w∈Rd f(w, λi) , (3)
  where the homotopy parameter λi is slightly increased at each homotopy iteration. As confirmed by our theoretical analysis, if the variations of the homotopy parameter, i.e. ∆λi, are “small enough” across homotopy iterations, the method is able to track in expectation an r-optimal solution from source to target problem. As shown in Algorithm 1, H-SGD takes as input an approximate solution for the problem associated with f(w, 0), i.e. w0, and is then characterized by two loops: in the outer loop (homotopy iterations) the method defines a new objective function by increasing the homotopy parameter (line 5 in Algorithm 1), and in the inner loop (warm-started SGD iterations) the current homotopy problem is approximately solved with k iterations of SGD starting from the previously derived approximate solution, i.e. wi−1 (line 6 in Algorithm 1). Different functions h : N→ (0, 1] to determine the increment ∆λi 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 a specifically designed scheme for ∆λi is deployed, i.e. exponentially decreasing schedule, H-SGD is effective in guaranteeing a global linear rate of convergence to a neighborhood of a minimizer of our target problem, while, given the same setting, vanilla SGD can only ensure a global sublinear rate of convergence.
  Algorithm 1 Homotopy-Stochastic Gradient Descent (H-SGD) 1: input: w0 ∈ Rd, n ∈ N, k ∈ N, h : N→ (0, 1] with ∑n i=1 h(i) = 1 and α > 0
  2: initialization: i = 0, λ0 = 0 3: for i = 1, . . . , n do 4: ∆λi ← h(i) 5: λi ← λi−1 + ∆λi 6: wi ←SGD(wi−1, α, k, f(·, λi)) 7: output: wi
sections.heading: 2.1 RELATED WORK
sections.text: Finding a solution of Problem 1 when 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 et al., 2009; Hinton et al., 2012; Sutskever et al., 2013a). We now briefly discuss some of the state-of-the-art optimization techniques and initialization strategies for solving Problem 1 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 a 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-to-grained optimization method, is a general heuristic to solve complex non-convex problems that relies on the basic principles of the homotopy method. As the name suggests, at first a coarse-grained and “easy-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., 2007), 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, 2014) and (Hazan et al., 2016), they rely on an expensive method, i.e. Gaussian smoothing, to construct coarsegrained versions of the original target problem. Regarding theoretical contributions on graduated optimization methods for solving Problem 1, 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 on their
  Gaussian smoothing approximation as 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 a quite strong requirement and hence might lead to considerably smaller local regions than those considered in our analysis (Karimi et 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, to homotopy methods, such as curriculum learning (Bengio et al., 2009), simulated annealing (Kirkpatrick et al., 1983), noise injection techniques (Hinton et al., 2012), smart initialization (Sutskever et al., 2013a) and layer-wise pretraining (Bengio et al., 2006).
  Transfer Learning. Due to the massive amount of computational resources required by the development 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 transfer-learning algorithms, e.g. (Torrey & Shavlik, 2010; Pan & Yang, 2010; Yosinski et al., 2014; 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-learning algorithm based on the homotopy method and SGD via the definition of a homotopy map that transforms a 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.e. optimality-tracking. Unfortunately, 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 a sublinear one for the homotopy-based method. In addition, as in (Hazan et al., 2016), 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).
sections.heading: 3 THEORETICAL ANALYSIS
sections.text: In this section, we provide a general theoretical analysis of H-SGD as described in Algorithm 1. In particular, after discussing the required underlying assumptions (Section 3.1), and the fundamental theoretical preliminaries (Section 3.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 to a minimizer’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 3.1 hold.
  Recall that the proposed method is based on sequentially and approximately solving a series of n unconstrained parametric problems of the form
  arg min w∈Rd
  f(w, λi) , ∀i = 1, . . . , n , (4)
  where λi < λi+1, λn = 1, λi ∈ (0, 1]. In addition, H-SGD relies on the availability of an approximate solution w0 for the source problem with λ0 = 0 as starting point. We use wi to denote the derived approximate solution for the problem associated with parameter λi that is obtained by applying k > 0 iterations of SGD starting from the previously derived approximate solution for the problem with parameter λi−1, ∀i = 1, . . . , n. Notice that wi−1,t = wi−1,t(ξ[i−1,t−1]) for t = 1, . . . , k with wi−1,k = wi(ξ[i]) is used to refer to the random vector generated at the i-th homotopy iteration after t iterations of SGD, where ξ[i−1,t−1] = (w0, ξ10 , . . . , ξ 1 k−1, . . . , ξ i−1 0 , . . . , ξ i−1 k−1, ξ i 0, . . . , ξ i t−1) and ξ[i] = (w0, ξ 1 0 , . . . , ξ 1 k−1, . . . , ξ i−1 0 , . . . , ξ i−1 k−1, ξ i 0, . . . , ξ i k−1) with ξ[0] = w0 are used to refer to the collection of all random sources up to the current iteration. We use U∗(λ) to denote the set of local (and global) minimizers of the parametric Problem 1.
sections.heading: 3.1 ASSUMPTIONS
sections.text: 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
  assumptions, which describe the localization of the solution map and how the objective function f changes by varying the homotopy parameter across iterations. In addition to these assumptions, we also consider a more general and local version of the standard PL condition.Consequently, unlike the settings considered in (Karimi et al., 2016) and (Vaswani et al., 2019), where the standard PL 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 Ω ⊆ Rd × [0, 1]z such that W ∗(λ) := Ω ∩ U∗(λ) and Σ := { (y, λ) ∈ Rd × [0, 1]z | y ∈W ∗(λ) } are both non-empty and connected. Moreover, we assume that for a given λ all the points in W ∗(λ) are associated with the same objective function value, which we denote as f∗(λ) := f(y, λ) for all y ∈W ∗(λ).
  Notice that Assumption 3.1 does not imply vector-valued solutions of the parametric Problem 1.
  Assumption 3.2 (regularity 1). Assume there exists δ > 0 such that
  |f(w, λ̃)− f(w, λ̂)| ≤ δ‖λ̃− λ̂‖, ∀w ∈ Rd, ∀λ̃, λ̂ ∈ [0, 1]z . (5)
  Assumption 3.3 (regularity 2). Assume there exists γ > 0 such that
  |f∗(λ̃)− f∗(λ̂)| ≤ γ‖λ̃− λ̂‖, ∀λ̃, λ̂ ∈ [0, 1]z . (6)
  Assumption 3.4 (L-smoothness). Assume there exists L > 0 such that
  ‖∇wf(w̃, λ)−∇wf(ŵ, λ)‖ ≤ L ‖w̃ − ŵ‖, ∀w̃, ŵ ∈ Rd, ∀λ ∈ [0, 1]z . (7)
  See Remark C.1 in Section C of the Appendix for more details on Assumptions 3.2 and 3.3.
  Assumption 3.5 (bounded “variance”). Consider f(w, λ) with λ ∈ [0, 1]z and let g(w, ξ, λ) be the stochastic estimate of the true gradient∇wf(w, λ) used in SGD with noise ξ. Assume that
  Eξ [g(w, ξ, λ)] = ∇wf(w, λ), ∀w ∈ Rd, ∀λ ∈ [0, 1]z. (8)
  and that there exists σ2 ≥ 0 such that Eξ [ ‖g(w, ξ, λ)−∇wf(w, λ)‖2 ] ≤ σ2, ∀w ∈ Rd, ∀λ ∈ [0, 1]z. (9)
  Assumption 3.6 (“expected” PL condition). Consider f(w, λi) with λi ∈ [0, 1]z and let wi−1,t = wi−1,t(ξ[i−1,t−1]) denote the iterate that is obtained at the i-th homotopy iteration after t iterations of SGD with t ≤ k. Assume that there exist B > σ 2
  2µ and µ > 0 such that, if Eξ[i−1,t−1] [f(wi−1,t, λi)]− f∗(λi) ≤ B, then
  Eξ[i−1,t−1] [ ‖∇wf(wi−1,t, λi)‖2 ] ≥ 2µ · [ Eξ[i−1,t−1] [f(wi−1,t, λi)]− f ∗(λi) ] . (10)
  See Remark C.2 for additional details on Assumption 3.6.
sections.heading: 3.2 FUNDAMENTAL THEORETICAL PRELIMINARIES
sections.text: 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., 2019), to also hold in the considered setting. The extended results are then used for the derivations in Section 3.3 and 3.4.
  Proposition 3.7. Consider f(w, λi) with λi ∈ [0, 1]z and let wi−1,t = wi−1,t(ξ[i−1,t−1]) denote the iterate obtained at the i-th homotopy iteration by applying t iterations of SGD with t ≤ k − 1 and α ≤ 1L . Under Assumptions 3.1 and 3.4-3.6, if Eξ[i−1,t−1] [f(wi−1,t, λi)] − f
  ∗(λi) ≤ B, then Eξ[i−1,t] [f(wi−1,t+1, λi)]− f∗(λi) ≤ B.
  Proof. See Section D in the Appendix for a proof.
  Theorem 3.8. Consider the minimization of f(w, λi) with λi ∈ [0, 1]z via SGD. Let wi−1 = wi−1(ξ[i−1]) be the random initial point associated with the i-th homotopy iteration with
  Eξ[i−1] [f(wi−1, λi)] − f∗(λi) ≤ B and wi−1,t = wi−1,t(ξ[i−1,t−1]) denote the t-th SGD iterate with t ≤ k. Under Assumptions 3.1 and 3.4-3.6, SGD with a constant step-size α ≤ 1L attains the following convergence rate to a minimizer’s neighborhood
  Eξ[i−1,t−1] [f(wi−1,t, λi)− f ∗(λi)] ≤ ρtEξ[i−1] [f(wi−1, λi)− f ∗(λi)] + σ2
  2µ , (11)
  with ρ := (1− αµ). With α = 1L , we obtain ρ = ( 1− µL ) .
  Proof. See Section E in the Appendix for a proof.
sections.heading: 3.3 OPTIMALITY TRACKING
sections.text: In the following, we define the function φv(λi) := Ev [f(v, λi)]− f∗(λi) where v is d-dimensional real random vector. As in (Gargiani et al., 2020) but in a more relaxed setting, i.e. local PL in place of local strong-convexity, 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 φwi(λi) ≤ r, then also φwi+1(λi+1) ≤ r. The upper bound that we derive depends on the number of iterations k 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 an r-optimal solution from source to target problem.
  Before proceeding with the actual optimality tracking analysis (Theorem 3.10), we study the conditions on wi and ∆λi+1 such that φwi(λi+1) ≤ B, where wi is the approximate solution of the problem associated with parameter λi that is also used as starting point for the next parametric problem. Lemma 3.9. Assume ‖λi+1 − λi‖ ≤ , 0 ≤ < Bδ+γ and let wi denote the i-th iterate of Algorithm 1 with α ≤ 1L . Under Assumptions 3.1- 3.3 and 3.4- 3.6, if φwi(λi) ≤ B − (δ + γ) ,
  then φwi(λi+1) ≤ B. In addition, let kmax := ⌈ logρ ( 1− 2µ(δ+γ) +σ 2
  2µB
  )⌉ . If φwi(λi+1) ≤ B,
  0 ≤ < 1δ+γ ( B − σ 2 2µ ) and k ≥ kmax, then φwi+1(λi+1) ≤ B − (δ + γ) .
  Proof. See Section F in the Appendix for a proof.
  Theorem 3.10. Assume there exists σ 2
  2µ < r ≤ B and ̃ := min { 1, 2} with
  1 := 1
  (δ + γ) (B − r), 2 := (1− ρk) r − σ2/2µ ρk (δ + γ) . (12)
  In addition, let kmax := ⌈ logρ ( 1− σ 2
  2µr )⌉ . Consider Algorithm 1 with α ≤ 1L , k ≥ kmax and
  ‖λi+1 − λi‖ ≤ , where 0 ≤ ≤ ̃. Under Assumptions 3.1- 3.3 and 3.4- 3.6, if φwi(λi) ≤ r, then φwi+1(λi+1) ≤ r.
  Proof. See Section G in the Appendix for a proof.
  See Figure 2 in Section B of the Appendix for a graphical representation of the derived results.
sections.heading: 3.4 LINEAR CONVERGENCE RATE
sections.text: We now study the convergence rate of H-SGD and, in particular, if it is possible to recover a global linear rate of convergence to a minimizer’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.
  Theorem 3.11. Let ρ̃ ∈ ( 1− σ 2
  2µ 1 B , 1 ) and consider Algorithm 1 with α ≤ 1L , φw0(λ0) ≤ r with
  σ2 2µ 1 (1−ρ̃) ≤ r ≤ B and k ≥ logρ(ρ̃). In addition, let 1 := 1 (δ+γ) (B − r) and
  Cρ̃ := 1 if k ≥ logρ(ρ̃)− logρ ( 1 + δ+γε0 ) ρ̃−ρk ρk ε0 (δ+γ) otherwise,
  (13)
  with ε0 := Eξ[0] [f(w0, λ0)]− f∗(λ0). Under Assumptions 3.1- 3.3 and 3.4- 3.6, if ‖λi+1 − λi‖ ≤ min { e−η i, 1 } with η ≥ ln (Cρ̃ ρ̃), then
  Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρ̃i+1 [ Eξ[0] [f(w0, λ0)]− f ∗(λ0) ] + σ2
  2µ i∑ j=0 ρ̃j . (14)
  Proof. See Section H in the Appendix for a proof.
sections.heading: 4 EXPERIMENTAL EVALUATION
sections.text: In this section, we empirically validate the theoretical results derived in Theorem 3.11. First, we consider a 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- 4 in the Appendix). We then move to more complex and high-dimensional scenarios where the assumptions can not be verified. Inspired by Finn et al. (2017) 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., 2006). 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.
sections.heading: 4.1 TOY-PROBLEM
sections.text: We start with an easy regression problem motivated by Mobahi (2016): a 1-dimensional neural network with erf as activation function (see Figure 9 in Section B of the Appendix for a graphical representation). We generate a synthetic dataset of N = 100 samples, where xj ∈ [−1, 1], yj = 3 · xj + j and j ∼ N (0, 1). Regarding the choice of a value for the step-size, we use an estimate L̃ of the smoothness constant L and set α = 1/L̃. As loss, we use the mean squared error, which, composed with the regressing model, leads to the following non-convex optimization problem
  w∗ = arg min w∈R
  1
  N N∑ j=1 (yj − erf(w · xj))2 . (15)
  By plotting the objective function with respect to w (see Fig. 3 in Section B of the Appendix), it is easy to observe that the PL condition holds globally, with the value of µ increasing by approaching the minimizer and µ→ 0 for w → ±∞ (see Fig. 4 in the Appendix). Consequently, SGD enjoys a global linear convergence rate as proved in (Vaswani et 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 to 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 Figures 7 and 8 in Section B of the Appendix). In order to achieve that, given w0 as initial value, we set yj,0 = w0 · xj for all j = 1, . . . , N and define the following homotopy transformation
  yj, λ = λ yj + (1− λ) yj, 0 . (16) As suggested by the theory (see Theorem 3.11), we select an exponentially decreasing scheme for the increment ∆λi in order to achieve linear convergence. As shown in Figure 5 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 a faster global convergence rate than that of SGD.
sections.heading: 4.2 REGRESSION WITH DEEP NEURAL NETWORKS
sections.text: 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 a sinusoidal function corrupted by Gaussian noise. In particular, the input data are sampled uniformly from the interval [−1, 1] and yj = sin(10 · xj) + j with j ∼ N (0, 0.1) for all j = 1, . . . , 500. 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 α 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 yj,0 = x2j + j with j ∼ N (0, 0.01) and employ the same homotopy mapping as in Equation 16. As shown in Figure 6 in the Appendix, also in this scenario H-SGD shows a superior numerical performance than SGD, i.e. H-SGD reaches a loss of 10−1 roughly 4 times faster and achieves convergence more than 2 times faster than SGD. The superior numerical performance of H-SGD can be attributed to its ability of tracking a solution across homotopy iterations (see Figure 10 in the Appendix) which ensures the method to always work in the vicinity of a minimizer.
sections.heading: 4.3 NON-LINEAR BINARY CLASSIFICATION WITH LOGISTIC REGRESSION
sections.text: 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., 2006) with 1000 samples corrupted by Gaussian noise. As the dataset is clearly not linearly separable, we opt for a cubic model, which, used in combination with the logistic regression framework, leads to a non-convex objective function where the optimization variable w 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-linearity 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 is obtained by multiplying the coefficients of the non-linear terms in the model by λ as follows
  λ(c1 x 3 j,1 + c2 x 3 j,2 + c3 x 2 j,1 + c4 x 2 j,2 + c5 x 2 j,1 xj,2 + c6 xj,1 x 2 j,2) + c7 xj,1 + c8 xj,2 + c9 . (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 11 in the Appendix).
sections.heading: 5 CONCLUSIONS AND FUTURE WORK
sections.text: In this paper we propose a new first-order stochastic method for non-convex large-scale problems, called Homotopy-SGD (H-SGD), based on the combination of homotopy methods and SGD. This new homotopy-based 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 a 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 in 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 in the design of 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.
sections.heading: ACKNOWLEDGMENTS
sections.heading: B ADDITIONAL FIGURES
sections.heading: A APPENDIX
sections.heading: C ADDITIONAL REMARKS
sections.text: 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.3), equation 6 relates the variation of the optimal objective function value for the subset of solutions introduced in Assumption 3.1 across homotopy iterations with the variations of the homotopy parameter. When the solution localization of the solution map is vector-valued, i.e. w∗(λ) ≡W ∗(λ) (this is the case for instance when the Hessian of 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 κ1 > 0, we assume that
  |f(w∗(λ̃), λ̂)− f(w∗(λ̂), λ̂)| ≤ κ1‖w∗(λ̃)− w∗(λ̂)‖, ∀λ̃, λ̂ ∈ [0, 1]z . (18)
  • Let κ2 > 0, we assume that
  ‖w∗(λ̃)− w∗(λ̂)‖ ≤ κ2‖λ̃− λ̂‖, ∀λ̃, λ̂ ∈ [0, 1]z . (19)
  In particular, by combining Inequalities equation 18 and equation 19, we obtain
  |f(w∗(λ̃), λ̂)− f(w∗(λ̂), λ̂)| ≤ κ2 κ1‖λ̃− λ̂‖, ∀λ̃, λ̂ ∈ [0, 1]z . (20) To recover Inequality equation 6 where γ := δ+κ1 κ2, we use Inequalities equation 5 and equation 20 together with the triangle inequality as follows
  |f(w∗(λ̃), λ̃)− f(w∗(λ̂), λ̂)| = |f(w∗(λ̃), λ̃)− f(w∗(λ̃), λ̂) + f(w∗(λ̃), λ̂)− f(w∗(λ̂), λ̂)| ≤ |f(w∗(λ̃), λ̃)− f(w∗(λ̃), λ̂)|+ |f(w∗(λ̃), λ̂)− f(w∗(λ̂), λ̂)| ≤ (δ + κ1κ2)‖λ̃− λ̂‖ .
  (21)
  Notice that the Assumption in equation 18 is a less restrictive condition of the following general Lipschitz continuity requirement
  |f(v, λ̂)− f(w, λ̂)| ≤ C‖v − w‖, ∀v, w ∈ Rd, ∀λ̂ ∈ [0, 1]z , (22)
  where C > 0. Remark C.2. Assumption 3.6 is a 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, it is straightforward to observe that the classical PL condition implies Assumption 3.6, but not vice versa. See Figure 1 in Section B of the Appendix for a graphical representation of a one dimensional example with wi−1,t ∼ N (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.
sections.heading: D PROOF OF PROPOSITION 3.7
sections.text: Proposition D.1. Consider f(w, λi) with λi ∈ [0, 1]z and let wi−1,t = wi−1,t(ξ[i−1,t−1]) denote the iterate obtained at the i-th homotopy iteration by applying t iterations of SGD with t ≤ k − 1 and α ≤ 1L . Under Assumptions 3.4, 3.5 and 3.6, if Eξ[i−1,t−1] [f(wi−1,t, λi)]− f
  ∗(λi) ≤ B, then Eξ[i−1,t] [f(wi−1,t+1, λi)]− f∗(λi) ≤ B.
  Proof. For ease of notation, we use the shorthands wi−1,t = wi−1,t(ξ[i−1,t−1]) and gt = g(wi−1,t, ξ i t, λi).
  Considering Assumption 3.4 together with the definition of SGD iterate and using Assumptions 3.5 and 3.6, we obtain the following inequalities
  Eξ[i−1,t] [f(wi−1,t+1, λi)] ≤ Eξ[i−1,t] [ f(wi−1,t, λi)− α〈∇f(wi−1,t, λi), gt〉+ Lα2
  2 ‖gt‖2 ] Law of Iterated Exp.
  = Eξ[i−1,t−1] [ Eξit [ f(wi−1,t, λi)− α〈∇f(wi−1,t, λi), gt〉+ Lα2 2 ‖gt‖2 ∣∣∣ξ[i−1,t−1]]] Assumption 3.5
  ≤ Eξ[i−1,t−1] [ f(wi−1,t, λi) + ( −α+ Lα 2
  2
  ) ‖∇f(wi−1,t, λi)‖2 ] + Lα2σ2
  2 .
  If α ≤ 1L , then
  Eξ[i−1,t] [f(wi−1,t+1, λi)] ≤ Eξ[i−1,t−1] [ f(wi−1,t, λi) + ( −α
  2
  ) ‖∇f(wi−1,t λi)‖2 ] + Lα2σ2
  2 .
  (23)
  We now make use of the “expected” PL condition and derive the following inequalities
  Eξ[i−1,t] [f(wi−1,t+1, λi)− f(wi−1,t, λi)] ≤ − α
  2 Eξ[i−1,t−1]
  [ ‖∇f(wi−1,t, λi)‖2 ] + Lα2σ2
  2 Assumption 3.6 ≤ −αµ [ Eξ[i−1,t−1] [f(wi−1,t, λi)]− f ∗(λi) ] + Lα2σ2
  2 .
  (24)
  From Inequality equation 24 it follows that, whenever Eξ[i−1,t−1] [f(wi−1,t, λi)] − f∗(λi) ≥ σ 2
  2µ , the objective function decreases in expectation, i.e. Eξ[i−1,t] [f(wi−1,t+1, λi)− f(wi−1,t, λi)] ≤ 0. Given that by assumptionB > σ 2
  2µ , we can consequently conclude that, if Eξ[i−1,t−1] [f(wi−1,t, λi)]− f(w∗i , λi) ≤ B, then Eξ[i−1,t] [f(wi−1,t+1, λi)]− f∗(λi) ≤ B.
sections.heading: E PROOF OF THEOREM 3.8
sections.text: Theorem E.1. Consider the minimization of f(w, λi) with λi ∈ [0, 1]z via SGD. Let wi−1 = wi−1(ξ[i−1]) be the random initial point associated with the i-th homotopy iteration with
  Eξ[i−1] [f(wi−1, λi)] − f∗(λi) ≤ B and wi−1,t = wi−1,t(ξ[i−1,t−1]) denote the t-th SGD iterate with t ≤ k. Under Assumptions 3.4, 3.5 and 3.6, SGD with a constant step-size α ≤ 1L attains the following convergence rate to a minimizer’s neighborhood
  Eξ[i−1,t−1] [f(wi−1,t, λi)− f ∗(λi)] ≤ ρtEξ[i−1] [f(wi−1, λi)− f ∗(λi)] + σ2
  2µ , (25)
  with ρ := (1− αµ). With α = 1L , we obtain ρ = ( 1− µL ) .
  Proof. For ease of notation, we use the shorthands wi−1,t = wi−1,t(ξ[i−1,t−1]) and gt = g(wi−1,t, ξ i t, λi).
  By combining Assumption 3.4 with the definition of SGD iterate, for all t = 1, . . . , k − 1, we obtain the following bound on f(wt+1, λi)
  f(wi−1,t+1, λi) ≤ f(wi−1,t, λi) + 〈∇f(wi−1,t, λi), wi−1,t+1 − wi−1,t〉+ L
  2 ‖wi−1,t+1 − wi−1,t‖2
  wi−1,t+1:=wi−1,t−αgt = f(wi−1,t, λi)− α〈∇f(wi−1,t, λi), gt〉+
  Lα2
  2 ‖gt‖2 .
  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
  Eξ[i−1,t] [f(wi−1,t+1, λi)] ≤ Eξ[i−1,t] [ f(wi−1,t, λi)− α〈∇f(wi−1,t, λi), gt〉+ Lα2
  2 ‖gt‖2 ] Law of Iterated Exp.
  = Eξ[i−1,t−1] [ Eξit [ f(wi−1,t, λi)− α〈∇f(wi−1,t, λi), gt〉+ Lα2 2 ‖gt‖2 ∣∣∣ξ[i−1,t−1]]] Assumption 3.5 ≤ Eξ[i−1,t−1] [ f(wi−1,t, λi) + ( −α+ Lα 2
  2
  ) ‖∇f(wi−1,t, λi)‖2 ] + Lα2σ2
  2 .
  If α ≤ 1L , then
  Eξ[i−1,t] [f(wi−1,t+1, λi)] ≤ Eξ[i−1,t−1] [ f(wi−1,t, λi) + ( −α
  2
  ) ‖∇f(wi−1,t, λi)‖2 ] + Lα2σ2
  2 .
  (26)
  We now apply the PL condition to Inequality equation 26, and we obtain
  Eξ[i−1,t] [f(wi−1,t+1, λi)] Assumption 3.6 ≤ Eξ[i−1,t−1] [f(wi−1,t, λi)
  −αµ( f(wi−1,t, λi)− f∗(λi) )] + Lα2σ2
  2 .
  (27)
  By subtracting f∗(λi) on both sides and setting α = 1L , we obtain the following inequality
  Eξ[i−1,t] [f(wi−1,t+1, λi)− f ∗(λi)] ≤
  ( 1− µ
  L
  ) Eξ[i−1,t−1] [f(wi−1,t, λi)− f ∗(λi)] + σ2
  2L .
  (28)
  By applying Inequality equation 28 recursively, we derive the following bound
  Eξ[i−1,t−1] [f(wi−1,t, λi)− f ∗(λi)] ≤
  ( 1− µ
  L
  )k Eξ[i−1] [f(wi−1, λi)− f ∗(λi)]
  + σ2
  2L k−1∑ j=0 ( 1− µ L )j .
  (29)
  Finally, by using the limit of geometric series, we obtain
  Eξ[i−1,t−1] [f(wi−1,t, λi)− f ∗(λi)] ≤
  ( 1− µ
  L
  )k Eξ[i−1] [f(wi−1, λi)− f ∗(λi)] + σ2
  2µ . (30)
sections.heading: F PROOF OF LEMMA 3.9
sections.text: Lemma F.1. Assume ‖λi+1−λi‖ ≤ , 0 ≤ < Bδ+γ and let wi denote the i-th iterate of Algorithm 1 with α ≤ 1L . Under Assumptions 3.4- 3.3 and 3.5- 3.6, if φwi(λi) ≤ B− (δ+γ) , then φwi(λi+1) ≤ B. In addition, let
  kmax := ⌈ logρ ( 1− 2µ(δ + γ) + σ 2
  2µB
  )⌉ . (31)
  If φwi(λi+1) ≤ B, 0 ≤ < 1δ+γ ( B − σ 2 2µ ) and k ≥ kmax, then φwi+1(λi+1) ≤ B − (δ + γ) .
  Proof. We start by deriving an upper bound on Eξ[i] [f(wi, λi+1)] − f∗(λi+1) with φwi(λi) ≤ B and ‖λi+1 − λi‖ ≤ . For that we use the regularity Assumptions 3.2 and 3.3 together with the triangle and Jensen inequalities as follows
  Eξ[i] [f(wi, λi+1)]− f ∗(λi+1) = |Eξ[i] [f(wi, λi+1)]− f ∗(λi+1)|
  = |Eξ[i] [f(wi, λi+1) + f(wi, λi)− f(wi, λi)]− f ∗(λi+1)
  + f∗(λi)− f∗(λi)| Triangle and Jensen Ineq.
  ≤ |Eξ[i] [f(wi, λi)]− f ∗(λi)|+ Eξ[i] [|f(wi, λi+1)− f(wi, λi)|]
  + |f∗(λi)− f∗(λi+1)| Assumptions 3.2 and 3.3
  ≤ |Eξ[i] [f(wi, λi)]− f ∗(λi)|+ (δ + γ) .
  (32)
  From Inequality equation 32 it follows that, if φwi(λi) ≤ B − (δ + γ) with < B(δ+γ) , then φwi(λi+1) ≤ B. We now use the results of Theorem 3.8 to derive a lower bound on the number of SGD-steps such that, if φwi(λi+1) ≤ B, then φwi+1(λi+1) ≤ B − (δ + γ) . We start considering the following inequality
  Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρk [ Eξ[i] [f(wi, λi+1)]− f ∗(λi+1) ] + σ2
  2µ
  ≤ ρkB + σ 2
  2µ .
  (33)
  From Inequality equation 33 it follows that, if φwi(λi+1) ≤ B, then φwi+1(λi+1) ≤ B − (δ + γ) with < 1δ+γ ( B − σ 2 2µ ) whenever
  k ≥ ⌈ logρ ( 1− 2µ(δ + γ) + σ 2
  2µB
  )⌉ . (34)
sections.heading: G PROOF OF THEOREM 3.10
sections.text: Theorem G.1. Assume there exists σ 2
  2µ < r ≤ B and ̃ := min { 1, 2} with
  1 := 1
  (δ + γ) (B − r), 2 := (1− ρk) r − σ2/2µ ρk (δ + γ) . (35)
  In addition, let
  kmax := ⌈ logρ ( 1− σ 2
  2µr
  )⌉ . (36)
  Consider Algorithm 1 with α ≤ 1L , k ≥ kmax and ‖λi+1 − λi‖ ≤ , where 0 ≤ ≤ ̃. Under Assumptions 3.4- 3.3 and 3.5- 3.6, if φwi(λi) ≤ r, then φwi+1(λi+1) ≤ r.
  Proof. We consider φwi(λi) ≤ r. If ≤ 1(δ+γ) (B − r) with r ≤ B, then φwi(λi) ≤ B − (δ + γ) and, as shown in Lemma 3.9, φwi(λi+1) ≤ B. This allows us to use the results of Theorem 3.8. We now derive an upper bound on Eξ[i+1] [f(wi+1, λi+1)] − f∗(λi+1) by considering the results of Theorem 3.8 together with the regularity Assumptions 3.2 and 3.3, and the triangle and Jensen inequalities as follows
  Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρk [ Eξ[i] [f(wi, λi+1)]− f ∗(λi+1) ] + σ2
  2µ = ρk ∣∣∣Eξ[i] [f(wi, λi+1) + f(wi, λi)− f(wi, λi)]− f∗(λi+1)
  + f∗(λi)− f∗(λi) ∣∣∣+ σ2
  2µ Triangle and Jensen Ineq. ≤ ρk [ Eξ[i] [f(wi, λi)]− f ∗(λi) ] + ρkEξ[i] [|f(wi, λi+1)− f(wi, λi)|]
  + ρk|f∗(λi)− f∗(λi+1)|+ σ2
  2µ Assumptions 3.2 and 3.3 ≤ ρk [ Eξ[i] [f(wi, λi)]− f ∗(λi) ] + ρk(δ + γ)‖λi+1 − λi‖+ σ2
  2µ .
  (37)
  Using the fact that φwi(λi) ≤ r and that ‖λi+1−λi‖ ≤ , we now solve the following inequality for in order to find an upper bound on the variation of the homotopy parameter such that φwi+1(λi+1) ≤ r
  ρk r + ρk (δ + γ) + σ2
  2µ ≤ r . (38)
  Inequality equation 38 holds whenever
  k ≥ ⌈ logρ ( 1− σ 2
  2µr
  )⌉ , (39)
  and
  ≤ (1− ρ k) r − σ2/2µ
  ρk (δ + γ) , (40)
  with r > σ 2
  2µ .
sections.heading: H PROOF OF THEOREM 3.11
sections.text: Theorem H.1. Let ρ̃ ∈ ( 1− σ 2
  2µ 1 B , 1 ) and consider Algorithm 1 with α ≤ 1L , φw0(λ0) ≤ r with
  σ2 2µ 1 (1−ρ̃) ≤ r ≤ B and k ≥ logρ(ρ̃). In addition, let 1 := 1 (δ+γ) (B − r) and
  Cρ̃ := 1 if k ≥ logρ(ρ̃)− logρ ( 1 + δ+γε0 ) ρ̃−ρk ρk ε0 (δ+γ) otherwise,
  (41)
  with ε0 := Eξ[0] [f(w0, λ0)]− f∗(λ0). Under Assumptions 3.4- 3.3 and 3.5- 3.6, if ‖λi+1 − λi‖ ≤ min { e−η i, 1 } with η ≥ ln (Cρ̃ ρ̃), then
  Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρ̃i+1 [ Eξ[0] [f(w0, λ0)]− f ∗(λ0) ] + σ2
  2µ i∑ j=0 ρ̃j . (42)
  Proof. We start assuming that φwi(λi) ≤ r, with 0 ≤ r ≤ B and ‖λi+1 − λi‖ ≤ 1 with 1 := 1 (δ+γ) (B − r) such that φwi(λi+1) ≤ B.
  In particular, we consider the following upper bound on Eξ[i+1] [f(wi+1, λi+1)]− f∗(λi+1),
  Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρk [ Eξ[i] [f(wi, λi)]− f ∗(λi) ]
  + ρk (δ + γ) ∆λi+1 + σ2
  2µ .
  (43)
  See the the proof of Theorem 3.10 for a derivation.
  We then proceed by induction. Therefore, we assume
  Eξ[i] [f(wi, λi)]− f ∗(λi) ≤ ρ̃i [ Eξ[0] [f(w0, λ0)]− f ∗(λ0) ] + σ2
  2µ i−1∑ j=0 ρ̃j , (44)
  and derive the conditions on ∆λi+1 such that
  Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρ̃i+1 [ Eξ[0] [f(w0, λ0)]− f ∗(λ0) ] + σ2
  2µ i∑ j=0 ρ̃j . (45)
  In order to achieve that, we consider the upper bound on Eξ[i+1] [f(wi+1, λi+1)]− f∗(λi+1) given by Inequality equation 43 and solve the following inequality for ∆λi+1
  ρk [ Eξ[i] [f(wi, λi)]− f ∗(λi) ] + ρk (δ + γ) ∆λi+1 + σ2
  2µ
  ≤ ρ̃i+1 [ Eξ[0] [f(w0, λ0)]− f ∗(λ0) ] + σ2
  2µ i∑ j=0 ρ̃j .
  (46)
  We obtain that Inequality equation 46 is satisfied whenever
  ∆λi+1 ≤ ρ̃i+1
  [ Eξ[0] [f(w0, λ0)] − f ∗(λ0) ] − ρk [ Eξ[i] [f(wi, λi)] − f ∗(λi) ] + σ 2 2µ ∑i j=1 ρ̃ j
  ρk(δ + γ)︸ ︷︷ ︸ RHS
  . (47)
  We derive a lower bound on the right-had side of equation 47 by considering the induction assumption, i.e. Inequality equation 44, and we obtain
  RHS ≥ ρ̃i ( ρ̃− ρk ) [ Eξ[0] [f(w0, λ0)]− f∗(λ0) ] − σ 2 2µρ k ∑i−1 j=0 ρ̃ j + σ 2 2µ ∑i j=1 ρ̃ j
  ρk(δ + γ) . (48)
  Considering that k ≥ logρ(ρ̃) then
  − σ 2
  2µ ρk i−1∑ j=0 ρ̃j + σ2 2µ i∑ j=1 ρ̃j = σ2 2µ ( 1− ρ k ρ̃ ) i−1∑ j=0 ρ̃j ≥ 0 . (49)
  Consequently, Inequality equation 47 is satisfied whenever ∆λi+1 ≤ ( ρ̃− ρk ) ρk ε0 (δ + γ) ρ̃i , (50)
  where ε0 := Eξ[0] [f(w0, λ0)]− f∗(λ0). To conclude this first part of derivations, we obtain that, whenever Inequality equation 50 is satisfied, then
  Eξ[i+1] [f(wi+1, λi+1)]− f ∗(λi+1) ≤ ρ̃i+1 ( Eξ[0] [f(w0, λ0)]− f ∗(λ0) ) + σ2
  2µ i∑ j=0 ρ̃j . (51)
  In order to ensure that φwi+1(λi+1) ≤ r we consider Inequality equation 51 and use the fact that φw0(λ0) ≤ r, i.e. Eξ[0] [f(w0, λ0)] − f∗(λ0) ≤ r, to upper bound the right-hand side of Inequality equation 51. We then solve the resulting inequality for r
  ρ̃i+1r + σ2
  2µ i∑ j=0 ρ̃j ≤ r . (52)
  Considering that ∑i j=0 ρ̃ j = (1−ρ̃i+1) (1−ρ̃) , we obtain that Inequality equation 52 is satisfied whenever
  r ≥ σ 2
  2µ
  1
  (1− ρ̃) . (53)
  By combining Inequality equation 53 with the fact that r ≤ B, we obtain the following upper bound on ρ̃
  ρ̃ ≤ 1− σ 2
  2µ
  1 B . (54)
  To further simplify the bound in equation 50, we define the following constant
  Cρ̃ := 1 if k ≥ logρ(ρ̃)− logρ ( 1 + δ+γε0 ) ρ̃−ρk ρk ε0 (δ+γ) otherwise,
  (55)
  and obtain that Inequality equation 50 holds whenever ∆λi+1 ≤ e−η i with η ≥ − ln (Cρ̃ ρ̃).