Transferring Optimality Across Data Distributions via Homotopy Methods
Authors: Matilde Gargiani
Andrea Zanelli
Quoc Tran Dinh
Moritz Diehl
Frank Hutter
Venue:  (2020)
Keywords: deep learning
numerical optimization
transfer learning

Abstract: Homotopy methods, also known as continuation methods, are a powerful mathematical tool to efficiently solve various problems in numerical analysis, including complex non-convex optimization problems where no or only little prior knowledge regarding the localization of the solutions is available. 
In this work, we propose a novel homotopy-based numerical method that can be used to transfer knowledge regarding the localization of an optimum across different task distributions in deep learning applications. We validate the proposed methodology with some empirical evaluations in the regression and classification scenarios, where it shows that superior numerical performance can be achieved in popular deep learning benchmarks, i.e. FashionMNIST, CIFAR-10, and draw connections with the widely used fine-tuning heuristic. In addition, we give more insights on the properties of a general homotopy method when used in combination with Stochastic Gradient Descent by conducting a general local theoretical analysis in a simplified setting. 

Published as a conference paper at ICLR 2020
TRANSFERRING OPTIMALITY ACROSS DATA DISTRI- BUTIONS VIA HOMOTOPY METHODS
Matilde Gargiani', Andrea Zanelli?, Quoe Tran-Dinh', Moritz Diehl Frank Hutter "Department of Computer Science. University of Freiburg (gargiani, fh] uni uni-freiburg de *Department of Microsystems Engineering (IMTEK), University of Freiburg (andrea. zanelli, moritz diehlllpp... (eeimee... uni freiburgeburg.... de DDepartment of Statistics and Operations Research, University of North Carolina quoctdéema 1. wnc.udduu.u.
*Department of Mathematics, University of Freiburg 'Bosch Center for Artificial Intelligence
ABSTRACT
Homotopy methods, also known as continuation methods, are a powerful math- ematical tool to efficiently solve various problems in numerical analysis. In this work, we propose a novel homotopy-based numerical method that can be used to gradually transfer optimized parameters of neural network across different data distributions. This method generalizes the widely-used heuristic of pre-training parameters on one dataset and then fine-tuning them on another dataset of inter- est. We conduct a theoretical analysis showing that, under some assumptions, the homotopy method combined with Stochastic Gradient Descent (SGD) is guaran- teed to converge in expectation to an rn-optimal solution for target task when started from an expected re- re-optimal solution on a source task. Empirical evalua- tions on toy regression dataset and for transferring optimized parameters from MNIST to Fashion-MNin and CIFAR- 10 show substantial improvement of the numerical performance over random initialization and pre-training.
INTRODUCTION
Homotopy methods (Allgower & Georg 1980), also known continuation methods, are powerful mathematical tool to efficiently solve various problems numerical analysis (e.g.. Tran-Dinh et al. (2012), Zanelli et al. ). The core idea consists in sequentially solving series of parametric problems, starting from an easy-to-solve problem and progressively deforming it, via a homotopy function, to the target one. Homotopy methods are suitable to solve complex non-convex optimiza- tion problems where no or only little prior knowledge regarding the localization of the solutions is available. In addition, in contrast state-of-the-art algorithms in deep learning (e.g., BBttou (2010). Duchi et al. (2011), Kingma & Ba (2015)), these methods often achieve global convergence guarantees by only exploiting local structures of the problem. Concepts, such curriculum-learning and warm-starting, that are related to different degrees to homotopy methods, have been explored both in the deep learning (e.g., Gulcehre et al. (2016), Mobahi] (2016), Gulcehre et al. (0017 and in the reinforcement learning (e.g.. Narvekar (2017) communities.
In this work, we propose a novel homotopy-based numerical method to transfer knowledge regarding the localization of a minimizer across different task distributions in deep learning. This method grad- ually tracks a neural network's (close-to- Joptimal parameters from one data distribution another one via the homotopy method (Allgower & Georg 1980) and can be interpreted as generalization of the very common heuristic fine-tuning a pre-trained network. After discussing related work (Section 2 and background homotopy methods (Section B). contributions are follows:
1. We provide general theoretical analysis of the homotopy method when using SGD as an iterative solver, proving that under some local assumptions it tracks in expectation an ro-omtimal solution from the source task to the target task (Section 4).

---

Published as a conference paper at ICLR 2020
2. We introduce homotopy functions for transferring optimality across data distributions for supervised regression and classification tasks (Section 5).
3. For toy regression dataset and for transferring optimized parameters from MNIST to Fashion-MNIS" MNNIT and from MNIST to CIFAR-10, we show that our method obtains up to two orders of magnitude better numerical performance than random initialization and sub- stantial improvement of the numerical performance over pre-training (Section 6
2 RELATED WORK
Deep neural networks have led to establish a new state of-te-of-the-art in many applications. Despite their great success and the many theoretical studies that have been published in the last years (e.g.. [all- duzzi et al. (2017). 7) Li et al. (2018), Feizi et al. (2018), Kunin et al. (2019), training these deep models remains big challenge. Various stochastic optimization algorithms (e.g.. Duchi al.
20011. Kingma& & Ba (2015), Reddi et al. )0188) and initialization heuristics (c.g.. Daniely et al. (0116 Klambauer al.J (2017). Hanin Rolnick (2018) have been recently suggested in order to improve and speed up the training procedure. We now briefly discuss the state-of-thee learning optimization techniques and initialization strategies that are most related with the proposed homotopy-based method, drawing connections with existing and ongoing research works in the field.
deep
Curriculum Learning. First introduced by [Bengio et al. 2009) and then extended in different works (e.g.. Graves et al. (2017), Weinshall et al. (2018) Hacohen & Weinshall (2019)), curriculum learning can also be listed among the optimization heuristics proposed to alleviate the complexity of solving high dimensional and non-convex problems. In particular, taking inspiration from the fact that humans and animals learn "better" when exposed to progressively more complex situations in an organized manner, curriculum learning techniques guide the training by starting with "easy-to- leam" samples and progressively introducing more "complex- complex-to-leart ones. This guided learning process can also be rephrased in homotopy-like fashion (see Algorithm [T] solving a sequence of optimization problems where the target training distribution gradually changes from considering only the "easy" examples to the full original training distribution.
Meta-Learning and Transfer-Lerningg Due to the massive amount of computational resources required by the development of modern deep learning applications, the community has started to explore the possibility of re-using learned parameters across different tasks, leading to the develop- ment of many new cransfer-earniigg (e.g.. Rohrbach et al. (2013), Wang Schneider (2014). Cui et al. (2019) and meta-learning (e.g.. Schmidhuber (1987). ). Hochreiter et al. (2001), Finn et al. (2017). y. Zintgraf et al. (2019) algorithms. The simplest way to transfer knowledge across different tasks consists in using warm-start initialization. This heuristic is amply used in computer vision ap- plications, where it is also known as the fine-tuning technique (c.g., .rizheekryykkk et al. (2012), Yosin- ski et al. (2014), Reyes et al. (2015), Käding et al. (2016)). So far, there is rigorous explanation of why and when fine-tuning works. However, numerous empirical evaluations on different bench- marks show that warm-starting the parameters of deep models often leads to faster convergence and better generalization than using random initialization.
3 BACKGROUND
In this work, we will focus on solving problems of the form
0 E arg min DERd
1 N
Σ 6())
J=)(
where J: Rd + RR our target objective function and 0" is a minimizer. Problems as described in arise, for instance, in classification and regression scenarios.
In the following section we briefly review the main concepts of homotopy and continuation methods, which the proposed technique to solve problem (1) is based on.
2

---

Published as a conference paper at ICLR 2020
3.1 HOMOTOPIC FUNCTIONS AND CONTINUATION METHODS FOR OPTIMIZATION
Given two topological spaces Z and Y, homotopy is a continuous deformation between two con- tinuous functions 9. f Z - Y that fulfills certain properties. We can formalize this concept with the following definition
Definition 3.1. Let g. f: Z + be continuous maps on the topological spaces Z, Y. homotopy from g to f is continuous function H Z x [0, 1] Y such that
(z, 0) g(z),
H f()),
V
If such function H exists, is said to be homotopic of J, and this relation is denoted by g = f.
It is straightforward to show that, A C _" being convex set, any two continuous maps g, f + are homotopic (see (Suciu) 2016) for a derivation). From this fact it follows that any two continuous and real functions are homotopic. See Figures 4a 4b in the appendix for graphical representation of two different homotopy maps between the probability density functions of two Gaussian distributions, where E [0, 1] denotes the homotopy parameter. See also Section A in the appendix for details on some of the main properties of homotopic functions.
Continuation methods (also known homotopy methods) solve complex non-convex optimization problems where no or only very limited prior knowledge regarding the localization of optimal solutions is available (see (Allgower & Georg, 1980) for full characterization of continuation methods). The core idea of a homotopy approach consists in defining a homotopy function (6, A) with À E [0, such that H 0) Jo( is trivial to optimize smooth map (or smooth map of which surrogate 6g of an optimal solution is available) and (0, 1) = (() our target objective function. Instead directly addressing problem [ we
widely used mathematical tool to
approximately and sequentially solve y > 0 parametric optimization problems of the form
0r E arg min
Σ J=1
(0. A.).
(3)
DER N
((0,A:))
for increasing values of the parameter X, for fo and warm-starting each problem with the previously derived approximate solution. Conceptually, Algorithm [ describes the basic steps of general homotopy algorithm. Under appropriate assumptions, if the increment AA is sufficiently small, then the iterative procedure in Algorithm | will converge to a neighborhood of an optimal solution the target objective J that depends in some sense on the number of iterations > performed (Allgower & Georg 1980). Many different variations of Algorithm exist. In particular,
Algorithm A Conceptual Homotopy Algorithm
1: 0g R 0g E arg ming (0,00)
2: 7 > 0,7 Z
3: Ao = 0,
AA Ax=11 1/7 =A=
4: ド> 0,k
5:
6: x 1--1+++ AA
7: procedure 0g - A H(,
8:
return 0,
different update schemes for the homotopy parameter be adopted (c.g., geometric sublinear rate increase), various iterative solvers can be used under distinct and specific assumptions, and, finally, also diverse levels of approximation for the solutions 0r be considered, i.e. different values.
Before going into the details of two concrete formulations of the conceptual homotopy method outlined in Algorithm (see Section(5) when applied to transfer optimality knowledge in regression and classification scenarios, we provide a general theoretical analysis in simplified setting.
3

---

Published as a conference paper at ICLR 2020
4 THEORETICAL ANALYSIS
In this section, we provide a local theoretical analysis homotopy methods when Stochastic Gra- dient Descent (SGD) (Bottou, 2010 is used as iterative solver in Algorithm [ The locality of the analysis consists in the definition of hyperspheres of radius B 2 0 around the optimal solutions of each homotopy problem H (0, X²) where it is possible to exploit certain structures of the problem. In particular, we approximately and sequentially solve > 0 unconstrained optimization problems of the form
or E arg min (.), Vi = vi......77. BERd
(4)
where HO,, A.) fulfills the assumptions described Section and A E [0. Let 0, be an ap- proximate solution of the problem associated with parameter A derived by applying & >> 0 iterations of SGD (in the limit, = 1) and also the starting point for the problem associated with parameter In addition, let 0g denote approximate solution for the source task, i.e. Ap = 0, that is used as initial point for the problem associated with '1 In this section we charac- terize the maximum allowed variation of the homotopy parameter in order for the method to able to track in expectation an ra-optimal solution from source to target task.
A++1, Vi 1, ...... y
4.1 ASSUMPTIONS
We now expose the fundamental assumptions for our general local theoretical analysis on which all the derivations in Sections 4.2 and 4.3 rely. In addition, throughout the analysis the Ê-functions in (3) are implicitly assumed to differentiable in 0. We start by giving the definition of the regions around the optimal solutions of the homotopy problems where the analysis is conducted.
Definition 4.1. Given 02 and B 2 0, let BB be the following set of vectors
BB == {0 s.t. |00 0,1 S B},
vi= O....,y.
Assumption 4.2 (local L-smoothness). Assume that there exists constant L >> such that VV, A,) VoH Ax)I s L|00- 1 0|I
vθ, 0 E BB vi O.....7.
(5)
Corollary 4.2.1. If H is locally L-smooth in 6, then the following inequality holds
1
H A.) x)) < 2L (0, vÓ BB.0 Vi 1==0.... 0.....
(6)
Proof. See Lemma 1.1 in (Gower 2018) for proof.
Assumption 4.3 (local p-strong convexity). Assume that there exists μ > 0 such that H(θ, A,) (,) + VoH((,,))TT (0-
0)+ 5 0112, vO, θ B Vi 0...,..,,
(7)
Assumption 4,4 (bounded f-derivative). Assume that there exists > 0 such that
(e) vθ E BB Vi = 0, O...., 7 =,
(8)
Assumption 4.5 (local bounded "variance"). Let g(ô, X1) denote an unbiased estimate of the gra- dient Ho >z). Assume that there exists a constant C 2 O such that the following bound on the expected squared norm of the estimate of the gradient holds
IE
[g(0, xDIP C²,
40 E BB =i= =i
Remark 4.6. Assumption 4.5 standard for proving error bounds on SGD iterates (see (Schmidt 2014)) In addition, notice that, since
E [l00 {]II =Var Var Var (11000
xilI) (11(0.A)11) + [11(0,A00]]
the C constant is proportional to the variance and the squared expected value of the norm of the gradient estimate. Therefore, it decreases when the iterates approach a minimizer and by reducing the noise in the estimate of the gradient. In the limit (i.e. exact gradient and convergence to minimizer), C
4

---

Published as a conference paper at ICLR 2020
Recall that 8* (A,) -.
Assumption 4.7 (strong regularity). Assume that there exists > 0 such that the following inequal- ity holds
10 (A++)) 00 S 8|4+11 - Aul Vi 0,......
Remark 4.8. Assumption 4.7 follows directly from the application of the Implicit Function Theorem by introducing some milder assumptions on the problem structure (see Lemma 2.1.8 in Alllgwer & Georg 1980l).
4.2 FUNDAMENTAL THEORETICAL PRELIMINARIES
Before proceeding with the main theoretical contributions, extend the existing results in the literature on global еттоr bounds for the iterates of Stochastic Gradient Descent such that they can be applied when the underlying assumptions are only required to hold locally. The derived local error bounds for SGD iterates are used in Proposition 4.11 and Theorem 4.12
Proposition 4.9. Let 0; BB be the starting point for the problem described in (3). and let 8, = 00,0 and 0.41 == 8s. denote the iterate after k 0 SGD steps, where an SGD step is defined as
0,,x -0g.-1-a((0AA-11
Under Assumptions
and by setting the batch size M S to a value such that
M)
(1-ka)
B with Rid = V(1- aup) and the learning rate to a constant value such that
N
200
0 < S min
L). the following error bound on the iterates holds
E [1|:++1 0++11 (1- 204) E [110: 0++1113] aC
(10)
2
Proof. See Section Di the appendix.
Remark 4.10. The expectation in (T0) is taken w.rl. all the random variables, i.e. estimates the gradients and initial point Og. involved in the optimization procedure to the current i+ iteration of the algorithm.
4.3 MAIN THEORETICAL CONTRIBUTIONS
Under the considered assumptions and by exploiting the previously derived results on local error bounds for SGD iterates, we show that, if the approximate solution O, for the problem with parameter
X; is "sufficiently close" to minimizer 0r in expectation, i.e. E [[[0: [|]] < <ră. then, for "sufficiently small" change in the homotopy parameter, the same vicinity to a minimizer 0 is preserved in expectation for the approximate solution 0 of the problem with parameter A4+1. L.c. [| - 11 & r-- In particular, with Theorem 4.12 12 we characterize the maximum allowed variation of the homotopy parameter based on the properties of the parametric problems and the convergence characteristics of the adopted iterative solver, i.e. rate of convergence and number of iterations.
First, in order to apply the results derived in Theorem 4.12 given a realization of 0, E BB we have to derive the conditions on ||0 - |] such that | 8 I B. In addition, we derive the necessary conditions in order to apply these results recursively across the iterations of Algorithm
Proposition 4.11. Let 0g E BB,0 and |\; A+t1l & c, with 0 S S
B 8- If [|0 07 < B 8c,
then |0, - ال11| S B. Moreover, Ka v(1 cxp) and assume that
(N .)
(1 n1) ka)
N
2av
and
(1 (1- (N - M) 2av
(1 Kat
Then, after applying k iterations of SGD. we obtain that
|0+11 0/411 |l
B 8c.

---

Published as a conference paper at ICLR 2020
Proof. See Section E.1 in the appendix.
See Figure the appendix for graphical representation of the results derived in Proposition 4. where the continuous and dashed lines are used to represent the circles of radius B and B de, respectively.
Theorem 4.12. Consider Algorithm]
7 with Stochastic Gradient Descent as solver and let > be the number of iterations, 0 < min 2p +) be the step size and O M S N be the batch size
such that
(N - M) (1 n (1 Ka)
N
201
where Kd V(I aa)). For 0o E BB- 66
and re E R. such that
aC²
r 2
(11)
2p
then, iʃ [110, -0,113] < ră and }i; Xitil S é, where ē := min {E,E) with
59 +
r2 aC:² aC/2/2p
(12)
(1 200
the following inequality holds
E [10
8i
11
S r
(13)
Proof. See Section F.2 in the appendix.
The results derived in Theorem 12 show that the homotopy method used in combination with SGD allows to track in expectation re opptimal solution across the parametric problems for "small enough" variations of the homotopy parameter, i.e. A < ह. Notice that re can potentially be smaller than B de and has be bigger than the radius of the "noise-dominant" hypersphere centered the minimizers, i.e. r aC2 2p In particular, by exploiting the local structure of the parametric problems we derive the maximum allowed variation of the homotopy parameter across the iterations of Algorithm|1 []] The derived upper bound is inversely proportional to the strong regularity constant and depends on the number of iterations performed with SGD, such that the more iterations we perform each parametric problem the Finally, notice that these results can be applied recursively across the parametric problems.
allowed to change the homotopy parameter.
5 TRANSFERRING OPTIMALITY VIA HOMOTOPY METHODS
In this section we describe possible application of homotopy methods to solve supervised regres- sion and classification tasks. We address the case where deep neural networks are used as models. We start by introducing the problem framework of supervised learning and then we propose two different homotopy functions for the regression and classification scenarios, respectively.
5.1 PROBLEM FORMULATION
Despite the generality of the proposed methodology, in this work we specifically address the su- pervised learning framework, and, in particular, when the predictive model is constituted by a deep neural network [x;; 0) parameterized by R
In the supervised learning scenario, independently from the type of task t, we typically dispose of training set D, consisting of N pairs of examples (z), The goal of the learning process is to find a value of that minimizes an objective function which measures the discrepancy between the outputs produced by the network process consists in minimizing the following empirical objective function
f(x; 0) and the target outputs y. In particular, the learning
1 J(0)
Σ (D
ely,, f();
(14)
N

---

Published as a conference paper at ICLR 2020
whose non-convexity originates from the high non-convexity of our model
In the classical setting. J/ chosen based on the KL divergence between the target data distribution Quyy with density ys.y = ((2)(==)((()) and the learned data distribution (0), with density Pa.v ply[a; (z)( where p(y|æ; 0) is modeled via a neural network, (Goodfellow et al. 2016). With the appropriate approximations, this leads to the following form for the objective function
((O) - N Σ
1
(v)x) log g(ylx)
(15)
p(y]=;;)
(1g.85)ED
5.2 HOMOTOPY FUNCTIONS ACROSS DATA DISTRIBUTIONS
Finding a value of 9 that attains a local minimum of the objective function in (14 is often a hard optimization task, given the high dimensionality and non-convexity of the problem. In addition, prior knowledge regarding the localization of the solutions is rarely available. The complexity of minimizing such functions also depends in some non-trivial way on the task distribution Qr.y that is addressed (e.g.. [onescu et al. (2016). Zendel et al. (2017)). For some tasks, convergence to good approximate solution is achieved after a few epochs, while for other tasks, orders of magnitude more iterations are required to reach the neighborhood of solution. In this perspective, different heuristics have been recently proposed in the attempt of re-using across different data distributions the prior knowledge gained from approximately solving the learning problem associated with certain task. The question whether we could exploit easy-to-solve or already-solved tasks to speed up and improve the learning of unsolved hard tasks arises. The method we propose in this paper addresses this question and attempts to do so by using a rigorous and well-established mathematical framework, with the goal of speeding up the learning process in presence of hard-to-solve tasks.
In the perspective of homotopy methods, this goal can be achieved under some assumptions by defining homotopy transformation between starting and target tasks and by following the procedure described in Algorithm| I Despite the flexibility and generality of the method, with this work we only focus on homotopy deformations across different task distributions, but similar transformations can be applied in numerous different manners that are also worth exploring, e.g., progressively modifying the architecture of the network or the weights of the objective function terms.
Let be the source task with training data D, of pairs (I.,, Us) ~ Q2,.9. whose good approximate solution 0 for the minimization of the objective in (4) is available (or cheaply computable), and let é denote the target task with training data D, of pairs (Ie, Mr) Qua whose conditional distri- bution we aim to learn. We propose two different homotopy deformations from task to task t for regression and classification, respectively.
5.2.1 SUPERVISED REGRESSION
In the supervised regression scenario, by modeling the density of the conditional learned distribu- tion as p(y|=; 8) N (y: fz, 6), o² I) and using the approximate KL divergence objective func- tion described in 15)p. we recover the mean squared error as minimization criterion. The proposed homotopy deformation is based on the following equations
y사 = (1 (1- A) yo vola l Ayylz.
(16)
<()|=) = Nyx f(x;0),
(17)
Notice that the transformation described in (16) preserves the unimodality of the conditional distri- bution (see caption of Figures 4a and 4b in the appendix), and, when used in combination with the objective function defined in Equation 15). leads to the minimization w.r.t. 0 of
H A) = FO(R.N))) II(1 - X) (v. - [xx 0)) + (y+ - [(a; 0)) 1|2
(18)
See Figure 6aa in the appendix for a graphical representation of this homotopy deformation when applied to gradually transform a one-dimensional sine wave function with a frequency into one-dimensional sine wave function with frequency of 137 radians. A downside of this homotopy deformation is that the same support for x is required (the absence of the subscripts s and t on stands to indicate that the same realization for x, and z; has to be considered). Alternatively, is possible to approximate (16) by using a Gaussian filter (see Figure 6b and Section in the appendix).
radian
7

---

Published as a conference paper at ICLR 2020
5.2.2 SUPERVISED CLASSIFICATION
In the case of supervised classification, by modeling the density of the conditional learned distribu- tion as p(y|2;; 0) M Multinoulli(y; f(r;0) 0)), and using the approximate KL divergence objective function described in (5), we recover the cross-entropy loss function, (Goodfellow et al. 2016). A
possible homotopy deformation for the classification case consists in applying the following trans- formations
x = (1 - X) + A
(19)
yx (1- y.l + A Ft.
(20)
which corresponds to the use of probabilistiic labels. See Figure g in the appendix for a graphical representation of the proposed homotopy deformation. The corresponding label vector for the de- formed image represented in Figure 8b is yo.5 [0. 0, 0.5, 0, O, 0.5, 0, 0, 0), given that À = 0.5 and that the sampled realizations of I, and It. represented in Figures Sa and 8c belong class and 5, respectively.
EXPERIMENTAL EVALUATION
In this section, we present some experimental evaluations of homotopy methods when applied to solve supervised regression and classification tasks. As homotopy functions we adopt the ones discussed in Section 5.2 We empirically show that homotopy methods outperform random and warm-start initialization schemes in terms of numerical performance. In particular, when the target task is complex and/or, in the transfer-learing scenario, when the data distributions are signifi- cantly different, continuation methods can achieve significant speed-up compared to random and warm-start initializations. We believe that their superior numerical performance relies on the use of homotopy functions that progressively deform the data distribution from casy-to-solve or already- solved task to the target data distribution. In addition, consistently across all the benchmarks, our homotopy-based method shows faster convergence than inniiiiinttializationn and faster compa- rable convergence than warm-start initialization. When the source task is "similar" to the target one, there is indeed no need to gradually vary the À parameter in Algorithm [] but it suffices directly set it to 1. In this extreme case, our homotopy method boils down to warm-start initialization.
6.1 REGRESSION
For the supervised regression scenario, the problem we address is how transfer "optimality knowl- edge" across two tasks that involve regressing from the input to the output of two sine wave functions with different values of phase w. Each considered dataset has 10000 samples split across training and testing, where x and y are defined as follows
x ((,
y = sin(wr) + E, E (00,00...
(21)
The goal to start with an "easy-to-learn" task, i.e. w A rad, whose optimum available by performing only few epochs with first-order optimizer, e.g. SGD, Adam, and progressively transfer the "optimality knowledge" to a more complex task, i.c. w >> rad, by approximately solving the homotopy problems for increasing values of À described in Algorithm [] We set w = rad for our source task distribution, and study the performance of the proposed approach with homotopy function as described in Equation (16) for different target distributions with w >> 1 rad. See Figures 5a and 55 the appendix for a visualization of the source data distribution with w = 1 rad and the target data distribution when = 137 rad, respectively. The regressor a feedforward neural network with 6 hidden layers of 100 units each and relu as activation function. In order to make the experiments more robust with respect to the choice of the step size a, we use Adam as optimizer. For the experiments in Figures Ia [b Figures 7b in the appendix. and Figure 2a we set a = 0.001, 7 = 10, & 200 and then performed an additional 500 epochs on the final target problem, while for the experiments in Figure 2bb we set y 10, k = 300 and performed an additional 600 epochs on the final target problem. In this last scenario we set a = 0.001 and then decrease it with cosine annealing schedule to observe convergence to optimum. As shown in Figures la lb Figures 7a 7b in the appendix, and Figures 2a and 2b the homotopy method leads to faster convergence than the considered baselines by preserving the vicinity an optimal solution for problems (6, A) across the different values. In particular, we achieve a training loss up to two orders of magnitude better than the considered baselines.
8

---

case the Published as a conference paper at ICLR 2020
homslopy war stnn random
moder Dannton manntaa
nemottay Warm
10-1
10.1
(a) We rad, W/ 74 rad.
(b) Ws rad, We 137 rad.
Figure 1: Median train loss across 100 runs versus epochs for sine wave regression tasks with different frequency values. The shaded areas represent the 25th and 75th percentiles. See Section in the appendix for an evaluation of the test performance.
hemotapy
somn sbor
random in!
1..
medin 20th 1085
10-9
10:
10'
homstogy warm start
nander Ind.
560
1002
1500
2000
2000
1000
2500
spechs
(a) Median train loss versus omega values.
(h) 1 rad, 137 rad.
Figure 2: Comparison of homotopy method, warm start and random initialization on sine wave regression tasks. The shaded areas represent the 25th and 75th percentiles. On the left, the median train loss achieved by the considered methods after 2500 epochs across 100 runs versus different omega values for the target task plotted. For the homotopy method and warm-start initialization, wis = 1 rad is used. On the right, the median train loss across 100 runs versus epochs for target task with w 137 rad is plotted. With respect Figure [b] in Figure 2b a cosine decay schedule used for the learning rate, and more epochs are performed to better observe the convergence properties of the different methods.
6.2 CLASSIFICATION
For the supervised classification scenario, we first apply the continuation method with the homotopy deformation described in Equations (19) and (20) order to transfer optimality from the MNIST task, a notoriously "casy-to-learn" task for neural networks, to the FashionMNIST task. Since the two datasets have the same input dimensionality and the same number of classes, no additional pre- processing of the data is required. As network architecture, we use VGG-type network, (Simonyan Zisserman 2015). and Adam as optimizer with a step size a = 0.001.
Secondly, we consider CIFAR-10 target data distribution. Differently from the previous scenario, padding of the MNIST samples required in order to apply Equation (19). The MNIST samples are also replicated across three channels. Also in this case adopt VGG-type network, (Simonyan Zisserman 2015), and Adam as optimizer with a step size a = 0.0001.
As shown in Figures 3a and 3b in both benchmarks the homotopy method leads to faster con- vergence than random initialization. While in the second benchmark our method reaches a lower value of training loss in fewer epochs than warm-start, in the MNNIS:to-FashionMNNN performance is comparable to using warm-start initialization. A possible interpretation is that, when the source and target task distributions are "too similar". hypothesize in the MNIST-

---

Published as a conference paper at ICLR 2020
torratoyy y- 2,24
2=5:2=2
medinn medhin 1952
random int
1100 on toan 1930
10
slart rendom Int
120
140
1.00
120
340
spochs
*pachic
(a) FashionMNIST.
(b) CIFAR-10.
Figure 3: Median train loss across 10 runs versus epochs for different target task distributions. In both cases, the source task is the classification of the MNIST dataset. See Section F2 in the appendix for an evaluation of the test performance.
to ON-S scenario, then there no need for homotopy deformations to be applied, i.e. 0 < À < but we can directly apply À 1 in scheme, which corresponds simply using warm-start initialization.
CONCLUSIONS
In this paper we propose new methodology based homotopy methods in order to transfer knowl- edge across different task distributions. In particular, our homotopy-basee method allows one to exploit easy-to-solve or already-solved learning problems to solve new and complex tasks, by ap- proximately and sequentially solving a sequence of optimization problems where the task distribu- tion gradually deformed from the source to the target one. We conduct a theoretical analysis of general homotopy method in simplified setting, and then test method some popular deep learning benchmarks, where it shows superior numerical performance compared to random and warm-start initialization schemes. The proposed framework, in its limiting case, corresponds to the widely used fine-tuning heuristic, allowing for a new and more rigorous interpretation of the latter. Finally, the generality of homotopy methods also opens many novel and promising research directions in fundamental fields for deep learning, such as stochastic non-convex optimization and transfer-learning.
ACKNOWLEDGMENTS
This work has partly been supported by the European Research Council (ERC) under the European Union's s Horizon 2020 research and innovation programme under grant 716721 well by the German Federal Ministry for Economic Affairs and Energy (BMWi) via DyConPV (0324166B), and DFG via Research Unit FOR 2401. In addition, Q. Tran-Dinh has partly been supported by the National Science Foundation (NSF), grant. no. 1619884, The authors thank Stefan Falkner for his helpful suggestions and comments.
REFERENCES
Eugene L. Allgower and Kurt Georg. Numerical continuation methods. An introduction. Springer- Verlag, 1980.
David Balduzzi, Brian McWilliams, and Tony Butler-Yeoman, Neural taylor approximations: Con- vergence and exploration in rectifier networks. In Proceedings of the 34th International Confer- ence on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. pp. 351-360, 2017. URL StLLtt::/// pttp::://..ceeeinn......seessses
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learn ing. In Proceedings the 26th Annual International Conference Machine Learning, ICML.
10

---

Published as a conference paper at ICLR 2020
2009, Montreal, Quebec, Canada, June 14-18, pp. 41 48, 2009. URL https: 101155/55334.5538
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Pro- ceedings of COMPSTAT'2010, pp. 177-186, 2010. URL [atts::/leonbottooo..c0
Wanyun Cui, Guangyu Zheng, Zhiqiang Shen, Sihang Jiang, and Wei Wang. Transfer learning for sequences via learning to collocate. In International Conference on Learning Representations, 2019. /tRLLttsss//peeeeiiiiieettttt//p ottpr//ew...ett....o.ooooooooooa
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 2253-2261, 2016. URL
wttps/iwwp..pcpppp///pppppp Eoward deeper unwe -ngegppr--neeeetttddngg--o-- www.aadddonooooooeaeaaaaanreetro
initialization: and a dual - -n wtw wxw.eesoccn.xxeeessityy....e poweee--owo----
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning
and stochastic optimization. Journal of Machine Learning, 12:2121-2159, 2011. URL URLhtt::
// www. www.jmmr..rrgpppeee...
ume htch//cchhhhaaaahhhcaaaaaaa
Soheil Feizi, Hamid Javadi, Jesse Zhang, and David Tse. Porcupine neural networks: Approximating neural network landscapes. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and Garnett (eds.), Advances in Neural Informa- tion Processing Systems 31. pp. 4831 4841. Curran Associates, Inc., 2018. URL /2tp://a....pppppaaaa/a///0/---0
approxi www.:eiiiaaiingggooooooo neural networkk catttttoor-lldddscce landscapes.pdff
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Doina Precup and Yee Whye Teh (eds.), Pro- ceedings of the 34th International Conference Machine Learning, volume 70, pp- 1126-1135. PMLR, 2017. URL Bttp::///zooeecnngggoorreesss///
lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. URL attp://ww.cepplermingoooooo
Robert M. Gower. Convergence theorems for gradient descent, 2018 URL https:// misiatiion
ppersotelecome
grad.conv.pdf
Alex Graves, Marc G. Bellemare, Jacob Menick, Rémi Munos, and Koray Kavukcuoglu. Automated curriculum learning for neural networks. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. pp. 1311-1320, 2017. ngs.m
URL htt.:http://oooeeeee http://pcccccccaaaloppeeee////// 7tt.
Caglar Gulcehre, Marcin Moczulski, Misha Denil, and Yoshua Bengio. Noisy activation functions. arXiv 1603.00391, 2016.
Caglar Gulcehre. Marcin Moczulski, Francesco Visin. and Yoshua Bengio. Mollifying net- works. In International Conference on Learning Representations, 2017. URL https://
Guy Hacohen and Daphna Weinshall, On the power of curriculum learning in training deep networks. In Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 2535-2544, 2019. URL http: 7/proceed nas.ming......
9a.html
Boris Hanin and David Rolnick. How to start training: The effect of initialization and architec- ture. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- -isa-Binnchi, and R. Gar- nett (eds.). Advances in Neural Information Processing Systems 31, pp. 571-581. Curran As- sociates, Inc., 2018 URL /Btp//tt.p//pppeeeaaa/c///pp////

---

Published as a conference paper at ICLR 2020
Sepp Hochreiter, A. Steven Younger, and Peter R. Conwell. Learning to learn using gradient descent. In Georg Dorffner, Horst Bischof, and Kurt Homik (eds.), Artificial Neural Networks - ICANN 2001, pp. 87-94. Springer Berlin Heidelberg, 2001. URL https: http:///iiinn.ssiigee..o.. Shapter/10.1007//
540- 4 6688 13
R. Tudor Ionescu, Bogdan Alexe, Marius Leordeanu, Marius Popescu, Dim P. Papadopoulos, and Vittorio Ferrari. How hard can it be? Estimating the difficulty of visual search in an image. In 2016 IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pp. 2157-2166. 2016. URL
77806066tag=1
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Proc. 3rd International Conference for Learning Representations, 2015. URL
3bss/1112.922
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Gameett (eds.), Advances in Neural Information Processing Systems 30, pp.
971-980. Curran Associates, Inc., 2017. URL http:t/ppp//pppsss/p/sc///pppppp self-norma
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convo- lutional neural networks. In F. Pereira, C. J. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 25, pp. 1097-1105. Curran Associates, Inc.,
2012. URL http:::/ppaperssnpssccpppppeeeep
http://ppppeee4444mmemmmmeeeeee- -ewaeggeeetttsaeeeee fictiioon
w
Daniel Kunin, Jonathan M. Bloom, Aleksandrina Goeva, and Cotton Seed. Loss landscapes of regularized linear autoencoders. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 3560-3569, 2019. URI. http::/ ngs.ml r.press/ / v kunini 9a.html
Christoph Käding. Erik Rodner, Alexander Freytag, and Joachim Denzler. Fine-tuning deep neural networks continuous learning scenarios. In ACCV Workshop on Interpretation and Visualiza- fion of Deep Neural Nets, 2016.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land- scape of neural nets. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 6389-6399. Curran Associates, Inc., 2018 URL
the loss landscape of neural Saaural-neets.pe nets.pdf
Hossein Mobahi. Training recurrent neural networks by diffusion. arXiv 1601.04114, 2016. URL
https: htttp:::aaaxiv.org///o
Sanmit Narvekar. Curriculum learning in reinforcement In International Joint Conference
on Artificial Intelligence, 2017. URL http:://wwww.geeooooooo/ccceeeer
0757.pdf
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In Inter- national Conference on Learning Representations, 2018. M httts:://oooee reviewnet/
ferrmmiddryyu77. RZ
Angie K. Reyes, Juan C. Caicedo, and Jorge E. Camargo. Fine-tuning deep convolutional networks for plant recognition. In Linda Cappellato, Nicola Ferro, Gareth J. F. Jones, and Eric SanJuan (eds.), Working Notes of CLEF 2015- Conference and Labs of the Evaluation forum, Toulouse, France, September 8-11, 2015, volume 1391 of CEUR Workshop Proceedings. CEUR-WS.org, 2015. URL/tttp://ceus www.eeurwww.og//oo/.. 1ttpa////VV111111111-1..111 11111111--111-1
Marcus Rohrbach, Sandra Ebert, and Bernt Schiele. Transfer learning in transductive set- ting. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26. pp. 46-54. Curran Associates, Inc., 2013. URL transduct ve sestttttngg..d
12

---

Published as a conference paper at ICLR 2020
Jürgen Schmidhuber. Evolutionary principles in self-referential learning. On learning now to lear:: The metu--meta-metta.-hooo Diploma thesis, Technische Universität München, Germany, May 1987.
Mark
Schmidt.
Convergence
rate of stochastic gradient with constant step size,
July 2014.
URL https:// http://wwwww..b.c.////./ http:/ccaa/sccmmmmmm/m.m -sschmiddtt/Dooumeett.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Truck Proceed-
ings, 2015. URL httt:://axxiv.rxs abs awwaaasss1199 1409.1556
Alexandru I. Suciu. Lecture notes in topology, February 2016. URL www.orttheaster..ed.
Quoc Tran- Dinh, Carlo Savorgnan, and Moritz Dichl. Adjoint-based predictor-corrector sequential convex programming for parametric nonlinear optimization. SIAM Journal on Optimization, 22 (4): 1284, 2012.
Xuezhi Wang and Jeff Schneider. Flexible transfer learning under support and model shift. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27, pp. 1898-1906. Curran Associates, Inc., 2014. URL http:::///..rrr..p...cccaapppeee httppppcca.a.ccpaaooooeaaaaaaaaa learning-unen under- support- and pooodel-shif..pp
Daphna Weinshall, Gad Cohen, and Dan Amir. Curriculum learning by transfer learning: Theory and experiments with deep networks. In Proceedings of the 35th International Conference on Machine Learning. JCML 2018, Stockholmsmässoon, Stockholm, Sweden, July 10-15, 2018, pp. 5235-5555550 5233,,243, 2018. URL http: http::::/pproceeenngsso.o w.w.:spppesseeemmmmmmm. /v00 wwwhsha 118a.html
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks?
Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27, pp. 3320- 3328. Curran Associates, Inc., 2014. transferable are- features- in meeu-- DatBaccc//aaaer/54--tooo
Andrea Zanelli, Quoc Tran-Dinh, and Moritz Diehl. Contraction estimates for abstract real-time algorithms for NMPC. In Proceedings of the IEEE Conference on Decision and Control, Nice, France, 2019.
Oliver Zendel, Katrin Honauer, Markus Murschitz, Martin Humenberger, and Gustavo Fernández Domínguez. Analyzing computer vision data the good, the bad and the ugly. In 2017 IEFE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 6670- 6680, 2017. TtL.attpe/pppncccetttett..c Zendel Ana Aww.aaaly....nnoomomtteetssisits 2011 ppp.ppp......ppppppppppp.......
content centeetttevrrreeeeeeeeee 2w17/
Luisa M. Zintgraf, Kyriacos Shiarlis, Vitaly Kurin, Katja Hofmann, and Shimon Whiteson. Cavia: Fast context adaptation via leaanne. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 7693-7700 2019. URL UtLp:ptpp//prroceeenngaaaerreses http:///////ttttttaaaa 9a.htm]
13

---

Published as a conference paper at ICLR 2020
A PROPERTIES OF HOMOTOPIC FUNCTIONS
Among the numerous properties of homotopic functions, we recall the following ones
Proposition A.1. Suppose that there exists a homotopy H Z x [0, + from to f. i.e. f. Then
(reflexive property)
f = g
(symmetric property)
9 f and f = h = 9 h
(transitive property)
Proof. See proof of Theorem 1.5 in Suciu 2016
Proposition A.2. Let g.g': - Y and f, f' + W be continuous maps, and let og. f og' Z W be the respective composite maps. If g g' and = f', then o 9 f o og.
Proof. See proof of Proposition 1.7 in Suciu 2016).
B APPROXIMATION VIA GAUSSIAN FILTER
For the supervised regression scenario, we propose the following homotopy deformation
y/ I = Ayal + (1 A) yr
(22)
downside of this homotopy function is that the same support for required (the absence of the subscripts and t on x stands to indicate that the same realization for and zy has to be considered). Alternatively, possible to approximate Equation (22 by using Gaussian filter, as depicted in Figure 6b
In particular, having sampled one realization 2 of the pair (s) from the training set D,, < McF < N realizations of the pair (Ia, Vt) are sampled from D. Each Yts realization is then weighted based on the vicinity of æt to the sampled Ta,z realization. This leads to the following approximation of the realization of y/x
Mar
A
yA (1 A) Us. +
wi Mr.
(23)
MGF
|| xe.
exp
(24)
V 2m
2ga
where & the standard deviation of the Gaussian filter.
14

---

Published as a conference paper at ICLR 2020
C ADDITIONAL FIGURES
40
1w0
4.3
0.
(1-1XX00)) 30 40 -AX 12
39
0-2
3.
2-03
30
3.
25
23
2.0
22
1.3
13
1.0
1.-
03
0.5
0.0
0.0
(a) Homotopy
(b) Homotopy 2.
Figure 4: Two different homotopy deformations between the probability density functions of two one-dimensional Gaussian distributions with mean and standard deviation given by #l = 1, 01 and μt 5, d2 0.1, respectively. The homotopy represented in Figure 4a results in mixture of Gaussian distributions, with mixture coefficient given by the homotopy parameter A. Figure 4b the deformation concerns instead the parameters μu and of the original distributions. Preserving unimodality is desirable property when the homotopy function is used in combination with a together with
continuation method since, shown in Figure 4b] the location of the optimum the function deformation, allowing the optimizer to track it and gradually reach the optimum of the final larget task. On the contrary, deforming the function as shown in Figure 4a does lead to gradual shift of the optimal solutions. Consequently, approximately and sequentially solving the problems corresponding to intermediate values of the homotopy parameter i.e. 0 1, will not allow the homotopy method to gradually approach the desired final optimal solution.
0.6
0.
0.4
-3.0
(a) rad.
(b) 137 rad.
Figure 5: Graphical representations of the source (left) and target with w = 137 rad (right) data distributions used for the sine- wave regression evaluation.
15

---

Published as a conference paper at ICLR 2020
0.25
0.00
0.7
0.3
-0.25
6.4
-0.2
+0.50
-0.50
(a) Homotopy transformation described in Equation (16).
(b) Approximation of the homotopy transfor- mation in Equation (T6) (also Equation (22) with Gaussian filter as described Equa- tions and (24).
Figure 6: Graphical representation of the proposed homotopy transformation for the supervised regression scenario when applied to progressively deform a sine wave function with frequency of radian into sine wave function with frequency of 137 radians for different values of homotopy parameter.
homstopy
strrt
16-1
13
10"
wim Start
horrelopy
randam Init
520
1003
1500
2000
2000
500
1000
3503
2000
2500
spochs
opodhs
(a) WP 1 rad, We 95 rad.
(b) W. = rad, 116 rad.
Figure Median train loss across 100 runs versus epochs for sine wave regression tasks with different omega values.
2
10-
17-
32-
(a) Sampled image of handwritten digit (class 2) from the MNIST dataset.
(b) Homotopy deformation of the images represented Figures Sa and Sc corre-
(c) Sampled image of sandal (class 5) from the FahionMNIST dataset.
sponding to X 0.5.
Figure 8: Graphical representation of the homotopy transformation from x, to T, as described in Equation (9) for two sampled images from the MNIST and FashionMNIST datasets.
16

---

Published as a conference paper at ICLR 2020
D LOCAL ERROR BOUNDS FOR SGD ITERATES
Before proving local crror bounds for SGD iterates the considered framework, given the local nature of assumptions, we need to demonstrate two important facts, which the proof relies. In particular, we need to show:
local linear contraction of Gradient Descent (GD) iterates, and that
starting in hypersphere of radius B around minimizer and given "big enough" batch size, the next SGD iterate is also contained in this region for all possible realizations of the gradient estimate.
( with fixed parameter A, in the following subsections we will refer to 8" 0 8g 8s,k and Ok g(8,, where drop the subscript, and the explicit dependence on X; in order to simplify the notation. The analysis holds for all fixed parameters A;-
Considering problem
D.1 LOCAL LINEAR CONTRACTION OF GD ITERATES
Let us GD to solve the following optimization problem
8" E arg min (0, As)
where the objective function H fulfills Assumptions 4.2 and 4.3 We now derive error bounds on the iterates of GD
0k+1 0₂ a a ())
where 0g E BB..- and 0 < < is the step size.
We start by applying the definition of GD iterates and then we exploit the introduced assumptions
[10x+1 8- 11
10x a ( A,) 1²1
0x 0-|| 2 H T 0-) + Ax)1
strong convexity
(1 (1-a4))104 8-12 - 20 A.) H(0 A,)) + + Vo 2:)1
corollary
- a--))) 2- - 2a(1 aL) [ A:) - H10" x:))
Since H (Ox,
Ar) H A₂) 2 0 and -2a(1 - ab) S when < a S J., we can safely drop the
second term and obtain the final result
|0 1²1 < (1 11 8-12
See also Theorem 2.3 in (Gower 2018) for a derivation where Assumptions 4.2 and 4.3 are required to hold globally.
D.2
REALIZATION OF THE SGD ITERATES IN THE STRONG CONVEXITY AND L- E-SMOOTHNESS REGION AROUND A MINIMIZER
We address the following optimization problem
N Σ (0,A),,
0* arg min N
-H(A..)
where H fulfills Assumptions 4.2
4.4
As proved in Section D.I under Assumptions 4.2 and 4.3 whenever Bu E BB,0- and 0 < a < }
deterministic gradient descent iterates converge linearly with contraction rate Ra v(1 - a4).
In particular, the following inequality holds
10 10 0*1l Kid |10g
0"
17

---

Published as a conference paper at ICLR 2020
for any 0g such that ||0 8- S B, and superscript P denotes iterates obtained by applying the full gradient VH == (Ok: A4)
O = 0% - HV
Let fx+1 denote the iterate obtained by applying one iteration of stochastic gradient descent
D 0g ogk
where gk := M ΣjeM Vey(Ok. Ax) and M is set of 0 < M < N indexes randomly sampled from N = (1)....,N:
Given any realization of 0g s.t. 10x- - 0-1 B and any realization of gr. by exploiting Assump- tion 4.4 and the results derived in Section D.I. we have that
[0++1 - 0-
||
= 10 agk - 1'
10x H4 + aV agg. 0*
10p a V H4 1- + all
142 9kl
|0
aVH; l1 + a
1
E
Vl, +
E Ve,
1 M
Σ
Vly
N
JENN
JEM
JEM
= 10 - aVH - l1 +
1
Σ
Vl, +
M N
Vly
N
NM
JEN(
JEM
(25)
$ 10 - AVH. - +'1 +a
Σ
IVG/T
N-M
Σ 1V61
N
NM
JENNM
JEM
(N M)
S 110 - 0-1l 2a
N
(N M)
$ ka]l0x - 801 + 2a
V.
N
Since we have assumed that the current realization of 0% lies in the hypersphere of radius B around the optimal solution 8", by solving for N-M the following inequality
(N- - M) Kg B 2a
BS
N
obtain that, whenever (N-M) (I~wa) B, the realization of 0k+1 will also lie in this region.
These derivations show that when the realization the current iterate 0₂ lies in the hypersphere of radius B around the minimizer 6*, and (N-M) N_ < [1-xa) 2av B, then the next iterate 0 will also lie in this region. Consequently, in our scenario, if we assume that the initial point d lies in the hypersphere of radius B around the minimizer 6*, then, by applying the derivations recursively, we can show that the iterates will remain in this local region around the minimizer where strong convexity and smoothness hold.
D.3 PROOF OF PROPOSITION 4.9
Let us use SGD to solve the following optimization problem
0" E arg min H(0, A:):
where the objective function Hl fulfills Assumptions iterates of SGD
We now derive error bounds for the
02+1 = 02 osk
where 9k is the unbiased estimate of V VH₃ defined in the previous section and fulfills Assump-
tion 4.5 0g BB,.- < a S min
1 is the step size and the batch size is set to value M 3 7,
such that (N-M) (1-Ra) B.
2av
18

---

Published as a conference paper at ICLR 2020
We start by applying the definition of SGD iterates
||0x+1 0²1 SGD iterate
| 0gfi - 11
110 - (0x. 8*) + 19
We now take the expectation w.r.f. Oo, go. ................................ Ik-1. and, considering Assumptions
4.5
we
obtain the following series of inequalities
Egg 00000.0.....-1111111
[10x+1
8 11]
so
1.90 |110- 1-11
-2og T (0x- 0*)
+a 19 12]
law of iterated expectations
Eo go..g........... 96-1
E [|10: - 11
20gh
T' (0x
8r) + a² 11 12 00. 9u. ..... ,........999......
unbinsed Sle + h-oundded "variance"
E0.. [1|0 0
-2aV (0g - 0¹) + a C²
strong convexity
(1 - 2014) -00.9o....9-- [|0a - 0*11]] + c²c².
By applying this result recursively, we derive the following bound on the error for the SGD iterates
aC
9k- [1|0++1
1-] < (1 2az Es, [100 1-] + 2p
See also Section in (Schmidt 2014) for derivation where Assumptions 4.2 and are required to hold globally.
E MAIN THEORETICAL CONTRIBUTIONS
E. PROOF OF PROPOSITION 4.11
Proposition E.1. Let E BB, and }ox A411l S e, with 0 S e S B.
If
071 S B dc, 10,
then 10, 1. ll & B. Moreover, let /(1 -ap) and assume that
(N M) (1 n²) KA)
N
20v
and
c5 8 (1 (1- x()-
(N M) 20v
N (1 ka))
Then, after applying iterations of SGD, we obtain that
||0++1 0/+1 B Sc.
Proof.
110, 0,41l1 ||
110, 07 + 07 0ft1ll
Triangle Inog.
||0, 8.11 + |10| 0.+1l
Assumption 4.7
|10, 0 0| 8\}; - A4+1l.
Finally, using the fact that [}g A4tal S c, it follows that, ||0 0; < B de with 0 <
then 100, - 0++1l B.
We now derive the conditions on such that |0++1 results derived in Section D.2 (25). we obtain that
07-1l S B dc. By applying recursively the
k-1 (N M).
10+41
8 S n
0
|l
2a
N v
Σ
1=0
19

---

Published as a conference paper at ICLR 2020
By using the limit of the geometric series, we have that
(N M) 20v
||.+1 0,+111 - x @2 0++1l++
N (1-ka)
Finally, by considering that |10; 01+1 || S B and by solving in the following inequality
B + (N M) 20w
S -de,
N
- (1-ka)
we obtain the following upper bound on e
S 3 (1 ( (1-x))--
(N M) 20v
(1 Kid)
from which also the extra condition on the batch size
(N M)
(1
k (1 Kid) Ka) B
N
20v
H(e:A:-1)
6
H(0:A)
8
9
HIB:A-
1
0/1
Figure 9: Graphical representation of the results derived in Proposition 4.11 dashed lines are used to represent the circles of radius and de around the optimal solutions, respectively.
The continuous and
E.2 PROOF OF THEOREM 4.12
Theorem E.2. Consider Algorithum] D with Stochastic Gradient Descent solver and let be
the number of iterations, 0 < S min 2p +) be the step size and 0 < M S N be the batch size such that
(N (N-M) M)
< (1 (1- (1-wz)(1 KA)
N
2ov
where Kdd (1 -..). For 0g E BB-BBs 05,03 and ro TR such that
a02
1 2
(26)
2/
then, TB [[]0, -0:11-] < rg and 1>; A4til E, where غ == min (2,e) with
ビ= + 1 r aC2/221
(27)
V
(1 2aμ1)*
the following inequality holds
E [10 0 11]
S rz
(28)
20

---

Published as a conference paper at ICLR 2020
Proof.
Ineq
20 |1|0 0 1-+1 aC²
E [10
24
(1 - 2014)* [1|0 03 0, 11+111 + aC²
2
Triangle Incq.
a²
S (1 - 20 'B (110:: 0, + 100 0f++11)
+
2p
(1 22 E [[100: -;:12 + 100 0/ 112
aC²
+2|10, 8 11|05 0 [I)] 2f
Asamption
(1 2a/1) E [110, 07 +
A111 2
+201 0, ||| )--11)) aC²
2p
a0²
S (1 21-20 (8 + 2ôrØē + 13)
24
We now solve the following second degree inequality
(1 2ap)) (8222 + 2ôrgě + r8) + aC
S rg.
(29)
2/
The inequality (29) admits solutions if and only if r3 2 aC
In particular, inequality 29 holds
2n
Ve [0, {). where
- + V
(1 20
21

---

Published as a conference paper at ICLR 2020
F EXPERIMENTAL EVALUATION: TEST PERFORMANCES
F.1 REGRESSION
Feretaay
terutaay
12-1
500
1000
1566
2303
500
1506
2500
spachs
opode
(a) W.
rad, We 74 rad.
(b) We rad, We 95 rad.
116
S/ 137
1928 1000 lok
38*
varm Mtc::
randem
(c) W. = rad, We 116 rad.
(d) We 1 rad, W. 137 rad.
Figure 10: Median test loss across 100 runs versus epochs for target tasks with different values. The shaded areas represent the 25th and 75th percentiles. For warm-start initialization and homotopy method, wi rad is used for the source task.
F.2 CLASSIFICATION
Method
Final Mean Test Accuracy
Best Mean Test Accuracy
homotopy 5, k = 2
0.89 0.003
0.91 + 0.002
homotopy = 5, k = 4
0.89 0.002
0.91 + 0.003
homotopy 10,
0.89 + 0.004
0.91 + 0.001
homotopy 10,
0.90 + 0.002
0.91 + 0.003
warm start
0.89 0.003
0.90 + 0.002
random init
0.89 + 0.004
0.90 + 0.003
Table 1: MNIST-FashhonMMIIST
Method
Final Mean Test Accuracy
Best Mean Test Accuracy
homotopy 5, = 2
0.55 0.004
0.59 1 0.003
homotopy 10. A:
0.55 + 0.005
0.60 : 0.002
homotopy 10,
0.56 0.003
0.60 = 0.003
homotopy 10,
0.56 + 0.005
0.61 = 0.004
warm start
0.54 0.006
0.59 + 0.005
random init
0.64 + 0.02
0.64 0.02
Table 2: MNIST-CIFAR-10
22


Reviews:
[{"review_id": "HJl5vl0pKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Contribution\nThis paper proposes algorithm for transferring knowledge from easy -to-solved to complex tasks or from already solve to new tasks. It relies on homotopy functions and sequentially solves a sequence of optimization problems where the task distribution is gradually deformed from a source task to the target task. Theoretical guarantees are provided and proven in a strongly convex setting. The main results from the theory show that the distance between the final solution and its optimal are less or equal to  relative to the distance of the initial source solution to its optimum. So a near optimal solution for the source task will lead to near optimal solution for the target task. Regression and Classification experimentations show competitive results compared to  random and warm-start initialization schemes.\n\nClarity\nOverall, the paper is well written, well motivated and well structured. The technical content is also very clear and excellent.\n Minor point: Seems that there is a notation error in proposition G.1 and its proof (i instead of i+1).\n\n\nNovelty\nThe novelty in this work seems to be the application of homotopy methods to the transfer learning settings. The mathematical guarantees are also new and may even offer new ways to interpret fine tuning methods that have been so successful in recent literature. \n\nHowever, given the  non-convexity of DNNs, it seems like the analysis in the non-convex settings and its implications  should be part of the main text.\n\nExperiments:\nOverall, the experiments are very insightful but limited since you only show the training loss and the validation performance is not evaluated at all. Other things that would could be  beneficial in better assessing the quality of your method are: comparison to Curriculum learning methods, more in depth analysis of the impact of k, and gamma in both regression and classification settings, and solving  toy convex optimization problems to bridge the gap between theory and application.\n\n\nPreliminary rating:\n* Accept *", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BylA50cmqB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Based on homotopy,, the paper describes a more rigorous approach to transfer learning than the so called ‘fine-tuning’ heuristic. Progress in the direction of more principled approaches for transfer learning would be tremendously impactful, since one of the core promises of deep learning is the learning of features, which can be used in different downstream tasks.  \nEssentially, (if this reviewer understood this correctly) the idea behind this paper works by interpolation between the original task of interest and a potentially easier to optimize surrogate task. Overall, this reviewer found the concept simple and elegant, and well motivated, and also well introduced. However, since this reviewer does not have a formal background in mathematics, they cannot assess the soundness of the proofs.\n\n\nThe paper tests the hypothesis by a simple function approximation regression task, and a classification task to learn to transfer from MNIST to fashion MNIST and MNIST to CIFAR, with promising results. One might argue that a more thorough evaluation would have been desirable, since the claims made by the paper are quite general, and it would have been in the authors’ best interest to present more thorough evidence that their concept works on wider scale of problems, ideally on an NLP task, given the current hype on pre-training with Transformer-based models.\n\n\n\n\nPrevious work & citations:\n\nI would recommend to cite Schmidhuber 1987 (Evolutionary principles in self-referential learning) and Hochreiter et al 2001 (Learning to Learn with gradient descent) in the context of Meta learning. \nIt would be nice to cite Klambauer et al (Self normalizing Networks) in the context of speeding up deep neural network training. \nThe citations of the VGG paper is currently referenced by first names of the authors, not their last names, I am not sure if this was intended.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Byl6u9ZhtH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors propose a very general framework of Homotopy to the deep learning set up and explores a few relevant theoretical issues.\n\nThough the proposed idea is interesting, the depth and breadth of authors' presentation are simply lacking. The entire paper lacks focus and I suggest authors consider focusing on 1-2 well thought-out ideas. There are many 3-4 line long sentences that are hard to decipher. Please also consider making the presentation more accessible.\n\nOverall, this paper does not meet the bar for ICLR.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a theoretically motivated method based on homotopy continuation for transfer learning and demonstrates encouraging results on FashionMNIST and CIFAR-10. The authors draw a connection between this approach and the widely used fine-tuning heuristic. Reviewers find principled approaches to transfer learning in deep neural networks an important direction, and find the contributions of this paper an encouraging step in that direction. Alongside with the reviewers, I think homotopy continuation is a great numerical tool with a lot of untapped potentials for ML applications, and I am happy to see an instantiation of this approach for transfer learning. Reviewers had some concerns about experimental evaluations (reporting test performance in addition to training), and the writing of the draft. The authors addressed these in the revised version by including test performance in the appendix and rewriting the first parts of the paper. Two out of three reviewers recommend accept. I also find the homotopy analysis interesting and alongside with majority of reviewers, recommend accept. However, please try to iterate at least once more over the writing; simply long sentences and make sure the writing and flow are, for the camera ready version.
Decision: Accept (Poster)