{'fraction_non_alphanumeric': 0.051011871113623514, 'fraction_numerical': 0.018224985867721876, 'mean_word_length': 4.156949626865671, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Escaping spurious local minimum trajectories in online time-varying nonconvex optimization

Devising efficient online algorithms that can track the optimizers of time-varying nonconvex optimization problems has many real-world applications. A major limitation of the existing online tracking methods is that they only focus on tracking a specific local minimum trajectory, which may lead to finding poor spurious local solutions. In this paper, we study the role of the natural temporal variation in helping simple online tracking methods find and track time-varying global minima for online nonconvex optimization problems. To this end, we investigate the properties of a time-varying gradient flow system with inertia, which can be regarded as the continuous-time limit of (1) the stationary condition for a discretized sequential optimization problem with a proximal regularization and (2) the online tracking scheme. We show that the inherent temporal variation of a time-varying optimization problem could re-shape the landscape by making it one point strongly convex over a large region during some time interval. Sufficient conditions are derived to guarantee that no matter how a local search method is initialized, it will track a time-varying global solution after some time. The results are illustrated in a benchmark example with many local minima.


Introduction
In this paper, we study an unconstrained online optimization problem whose objective function varies continuously in time, namely, min where t ≥ 0 denotes the time and x(t) is the optimization variable that depends on t. For each time t, the function f (x, t) could potentially be nonconvex in x with many local minima. The objective is to solve the above problem in an online fashion under the assumption that at any given time t the function f (x, t) is known while no knowledge about f (x, t ) is available for any t > t. The optimization at each time instance could be highly complex due to NP-hardness, which is an impediment to finding its global minima. This paper aims to investigate under what conditions simple local search algorithms can solve the above online optimization problem to almost global optimality after some finite time. More precisely, consider a global solution of f (x, t) as a function of time t, which defines a global minimum solution trajectory. It is desirable to devise an algorithm that can track this trajectory with some error at the initial time and a diminishing error after some time.
If f (x, t) does not change over time, the problem reduces to a classic (time-invariant) optimization problem. It is known that simple local search methods, such as stochastic gradient descent (SGD) [19], may be able to find a global minimum of the problem (under certain conditions) for almost all initializations due to the randomness embedded in SGD [23,14,27]. The objective of this paper is to significantly extend the above result from a single optimization problem to infinitely-many problems parametrized by time t. In other words, it is desirable to investigate the following question: Can the temporal variation in the landscape of time-varying nonconvex optimization problems enable online local search methods to track global trajectories? To answer this question, we study a first-order time-varying ordinary differential equation (ODE), which is the counterpart of the classic gradient flow system for the time-invariant optimization problem and serves as a continuous-time limit of the discrete online tracking method for (1). This ODE is given asẋ where α > 0 is a constant parameter named inertia due to a proximal regularization. A system of the form (ODE) is called a time-varying gradient system with inertia α. The behavior of the solutions of this system initialized at different points depends on the value of α. We offer a motivating example below before stating the goals of this paper.

Motivating example
Example 1. Consider the objective function f (x, t) := g(x − b sin(t)), where g(y) := 1/4y 4 + 2/3y 3 − 1/2y 2 − 2y The differential equation (ODE) can be written aṡ This time-varying objective has a spurious (non-global) local minimum trajectory at −2 + b sin(t), a local maximum at −1 + b sin(t), and a global minimum at 1 + b sin(t). In Figure 1 1 , we show a bifurcation phenomenon numerically. The red lines are the solutions of (ODE). In the case with α = 0.3 and b = 5, a trajectory initialized at a local minimum of f (·, 0) winds up in the region of attraction of the global minimum trajectory. However, for the case with α = 0.1 and b = 5, a trajectory initialized at a local minimum of f (·, 0) remains in the region of attraction of the same local minimum trajectory. In Figure 1c, we study the scenario with α = 0.8 and b = 5, and initialize the trajectory at the spurious local minimum of f (·, 0). The solution of (ODE) fails to track any local minimum trajectory. In Figure 1d, we take α = 0.1, b = 10 and initialize the trajectory at the spurious local minimum of f (·, 0). The solution of (ODE) again winds up in the region of attraction of the global minimum trajectory. The observations in this example can be summarized as: 1. Jumping from one trajectory to another trajectory tends to occur with the help of a relatively large inertia when the local minimum trajectory changes the direction abruptly and there happens to exist another local minimum trajectory in the direction of the inertia.
2. When the inertia α is relatively small, the solution of (ODE) tends to track a local minimum trajectory closely and converges to a local minimum trajectory quickly.

Our contributions
To mathematically study the observations made in Example 1 for a general online optimization problem, we focus on the aforementioned time-varying gradient flow system with inertia α as a continuous-time limit of an online updating scheme for (1). We show that the time-varying gradient flow system with inertia α is also a continuous-time limit of the stationary condition for a discretized sequential optimization problem with a proximal regularization. The existence and uniqueness of the solution of such ODE is proven. As a main result of this work, it is proved that the natural temporal variation of the time-varying optimization problem encourages the exploration of the state space and re-shaping the landscape by making it one point strongly convex over a large region during some time interval. We show that if a given spurious local minimum trajectory is a shallow minimum trajectory compared to the global minimum trajectory, then the temporal variation of the time-varying optimization would trigger escaping the spurious local minimum trajectory for free. We develop two sufficient conditions under which a certain local minimum trajectory will jump to another local minimum trajectory. We then derive a sufficient condition on the inertia α to guarantee that the solution of (ODE) can track the local minimum trajectory from an arbitrary point in the region of locally one point strong convexity around this local minimum trajectory. We also provide an ultimate tracking error bound and estimate the time for reaching the tracking error bound. To illustrate the technical results on how the time variation nature of an online optimization problem enables escaping a spurious minimum trajectory, we offer a case study with many shallow minimum trajectories.

Related work
Online time-varying optimization problems: Time-varying optimization problems of the form (1) arise in the real-time optimal power flow problem [43] for which the power loads and renewable generations are time-varying and operational decisions should be made every 5 minutes, as well as in the real-time estimation of the state of a nonlinear dynamic system [35]. Other examples include model predictive control [7], timevarying compressive sensing [36,3] and online economic optimization [25,46]. There are many papers on designing efficient online algorithms to track the optimizers of time-varying convex optimization problems [39,13,4,38]. With respect to time-varying nonconvex optimization problems, the work [16] presents a comprehensive theory on the structure and singularity of the KKT trajectories for time-varying optimization problems. On the algorithm side, [43] provides regret-type results in the case where the constraints are lifted to the objective function via penalty functions. [42] develops a running regularized primal-dual gradient algorithm to track a KKT trajectory, and offers asymptotic bounds on the tracking error. [32] obtains an ODE to approximate the KKT trajectory and derives an algorithm based on a predictor-corrector method to track the ODE solution. Recently, [11] asked the question of whether the natural temporal variation in a time-varying nonconvex optimization problem could help a local tracking method escape spurious local minimum trajectories, but lacked theoretical results on this phenomenon.
Online optimization for machine learning: A common framework in machine learning for analyzing a time-varying optimization problem is online optimization [19]. In general, the main goal in such online convex optimization is to propose a sequential algorithm and measure its performance through the notion of stationary regret [48] or dynamic regret [48,5,22], depending on whether there is any additional condition on the temporal variability of the sequence of objective functions. Most of the literature have focused on online convex optimization, while the main challenges are in the non-convex case. With respect to online nonconvex optimization, [20] proposes to minimize a surrogate notion of local regret, which measures the sub-optimality compared to a local point-wise solution to the problem. Contrary to this line of research, we focus on the global landscape and the ultimate tracking error bound of time-varying nonconvex optimization problems.
Local search methods for global optimization: Nonconvexity is inherent in many real-world problems: the classical compressive sensing and matrix completion/sensing [10,8,9], training of deep neural networks [31], the optimal power flow problem [29], and others. From the classical complexity theory, this nonconvexity is perceived to be the main contributor to the intractability of these problems. However, it has been recently shown that simple local search methods, such as gradient-based algorithms, have a superb performance in solving nonconvex optimization problems. For example, [30] shows that the gradient descent with a random initialization could avoid the saddle points almost surely and [23,14] proves that a perturbed gradient descent and SGD could escape the saddle points efficiently. Furthermore, it has been shown that nearly-isotropic classes of problems in matrix completion/sensing [6,15,47], robust principle component analysis [12,24], and dictionary recovery [41] have benign landscape, implying that they are free of spurious local minima (a non-global local minimum is called spurious). The work [27] proves that SGD could help escape sharp local minima of a loss function by taking the alternative view that SGD works on a convolved (thus smoothed) version of the loss function. However, these results are all for time-invariant optimization problems for which the landscape is time-invariant. In contrast, many real-world problems should be solved sequentially over time with time-varying data. Therefore, it is essential to study the effect of the temporal variation on the landscape of time-varying nonconvex optimization problems.
Continuous-time interpretation of discrete numerical algorithms: Many iterative numerical optimization algorithms for time-invariant optimization problems can be interpreted as a discretization of a continuous-time process. Then, several new insights have been obtained due to the known results for continuous-time dynamical systems [26,18]. Perhaps the simplest and oldest example is the gradient flow system for the gradient descent algorithm with an infinitesimally small step size. The recent papers [40,28,45] study accelerated gradient methods for convex optimization problems from a continuous-time perspective. In addition, the continuous-time limit of the gradient descent is also employed to analyze various non-convex optimization problems, such as deep linear neural networks [37] and matrix regression [17]. It is natural to analyze the continuous-time limit of an online algorithm for tracking a KKT trajectory of time-varying optimization problem [39,42,32,11].

Paper organization
This paper is organized as follows. Section 2 presents the preliminaries for time-varying optimization and the derivation of time-varying gradient flow with inertia. Section 3 offers an alternative view on the landscape of time-varying nonconvex optimization problems after a change of variables. Section 4 analyzes the jumping, tracking and escaping behaviors of local minimum trajectories. Section 5 illustrates the phenomenon that the time variation of an online optimization problem can assist with escaping spurious local minimum trajectories, by working on a benchmark example with many shallow minimum trajectories. Concluding remarks are given in Section 6. To streamline the presentation, the proofs are deferred to the appendix.

Notations
The notation · shows the Euclidian norm. The interior of the intervalĪ t,2 is denoted by int(Ī t,2 ). The symbol B r (h(t)) = {x ∈ R n : x − h(t) ≤ r} denotes the region centered around a trajectory h(t) with radius r at time t. We denote the solution ofẋ = f (x, t) starting from x 0 at the initial time t 0 with x(t, t 0 , x 0 ) or the short-hand notation x(t) if the initial condition (t 0 , x 0 ) is clear from the context.

Preliminaries and Problem Formulation
In this work, we assume that f : R n × [0, ∞) → R is twice continuously differentiable in x and continuously differentiable in t ≥ 0. Moreover, suppose that f is uniformly bounded from below, meaning that there exists a constant M such that f (x, t) ≥ M for all x ∈ R n and t ≥ 0.

Time-varying optimization
The first-order stationary condition for the time-varying optimization (1) is as follows: Since the solution is time-varying, we define the notion of stationary trajectories below.

Definition 1. Given a time interval
In this work, we assume that the real roots of (2) are all isolated at each time t.

Definition 2. A stationary trajectory h(t)
: I t → R n is said to be isolated if, given any other stationary trajectory h (t) : An isolated stationary trajectory h(t) can theoretically be a mix of local minima, local maxima and saddle points of the function f (x, t) at different times. However, the goal of this work is to study only isolated local minimum trajectories of the time-varying optimization (1).

Definition 3. A continuous trajectory h(t)
: I t → R n is said to be a local I t -minimum trajectory of the time-varying optimization (1) if I t is a maximal interval such that each point of h(t) is the local minimum of the time varying optimization (1) at time t ∈ I t . It is said to be a global I t -minimum trajectory of the time-varying optimization (1) if I t is a maximal interval such that each point h(t) is the global minimum of the time-varying optimization (1) at time t ∈ I t . In particular, h(t) is called a local (or global) ∞-minimum trajectory of the time-varying optimization (1) After freezing the time t in (1) at a particular value, one may use local search methods to minimize f (x, t). If the initial point is close enough to a local solution and the step size is small enough, the algorithm will converge to the local minimum. This leads to the notion of region of attraction defined by resorting to the continuous-time model of local search algorithms (for which the step size is not important anymore).

c, r)-one point strong convexity around h(t).
Note that (4) resembles the (locally) strong convexity condition for the function f (x, t), but it is only expressed around the point h(t). This restriction to a single point constitutes the definition of one-point strong convexity and it does not imply that the function is convex. If the minimum trajectory h(t) is defined only over a finite maximal time interval I t , then when t approaches the upper bound of I t , the function f (x, t) may tend to become a saddle point or even local maximum solution. Then, one could expect that the one point strong convexity holds only for a subset of the intervalĪ t ⊂ I t . On the other hand, if the minimum trajectory h(t) is defined over the entire time horizon, the locally one point strong convexity could hold on the unbounded interval. Figure 2 illustrates the difference between the region of convexity and the region of one point convexity with respect to a certain point using the time-invariant univariate objective function given in example 1. In this paper, we assume any local I t -minimum trajectory h(t) satisfies the following assumptions.

Assumption 1. h(t) is isolated.
for some constants c and r as well as an intervalĪ t .

Derivation of time-varying gradient flow system
In practice, one can only hope to sequentially solve the time-varying optimization problem (1) at some discrete time instances 0 = τ 0 < τ 1 < τ 2 < τ 3 < · · · as follows: In many real-world applications, it is neither practical nor realistic to have solutions that abruptly change over time. To meet this requirement, one may impose a constraint to ensure that the solution at each time τ i will not be away from the one obtained in the previous time τ i−1 by a given threshold d( This leads to a modified optimization problem at time τ i : where x * i−1 denotes an arbitrary local minimum of the modified optimization problem obtained using a local search method at time iteration i − 1. An alternative way is to move the constraint in (6) to the objective function by penalizing the deviation of its solution from the one obtained in the previous time step. More precisely, we employ a regularization term that is proportional to a fixed inertia α ≥ 0 and inversely proportional to the time difference τ i − τ i−1 . This leads to the following sequence of optimization problems with proximal regularization (except for the initial optimization problem): Note that α could be time-varying (and adaptively changing) in the analysis of this paper, but we restrict our attention to a fixed regularization term to simplify the presentation. Now, one can formally define the notion of discrete local trajectories for the above sequential regularized optimization problem.

Definition 6. Given evenly spaced-out time steps
. . is said to be a discrete local trajectory of the sequential regularized optimization (7) if the following holds: 2. x * k is a local minimum of (7b) for k = 1, 2, . . ..
Due to the first-order optimality condition, the local minimum x * i of (7) at time step τ i satisfies the equation: Since the function f (x, τ i ) is nonconvex, the problem (7b) may not have a unique solution x * i . In order to cope with this issue, we study the continuous-time limit of (8) as the time step τ i+1 − τ i attenuates to zero. This yields a time-varying ordinary differential equation: When α = 0, the differential equation (9) reduces to the algebraic equation (2), which is indeed the first-order stationary condition for the unregularized time-varying optimization (1). When α > 0, we will show that (9) has a unique solution defined for all t ≥ 0 under the assumption that the solutions of (9) lies in a compact set 2 .

Theorem 1 (Existence and uniqueness)
. Assume that f (x, t) is piecewise continuous in t, and that its gradient is locally Lipschitz in x for all t ≥ 0 and x ∈ R n . Let α > 0 and D be a compact subset of R n containing x 0 such that every solution oḟ lies entirely in D. Then, the above differential equation has a unique solution and is defined for all t ≥ 0.
Note that (8) can be written in the form of the backward Euler method: A direct application of the classical results on convergence of the backward Euler method [21] immediately shows that the solution of (ODE) starting at a local minimum of (7a) is the continuous limit of the discrete local trajectory of the sequential regularized optimization (7).

Proposition 1 (Convergence of backward Euler)
. Given x * 0 as a local minimum of (7a), as the time difference ∆ τ = τ i+1 − τ i approaches zero, any sequence of discrete local trajectories (x ∆ k ) introduced in Definition 6 converges to the (ODE) in the sense that for all fixed T > 0.
In online optimization, it is desirable to predict the solution at a future time (namely, τ i ) only based on the information at the current time (namely, τ i−1 ). This can be achieved by implementing the forward Euler method to obtain a numerical approximation to the solutions of (ODE): (note thatx * 0 ,x * 1 ,x * 2 , ... show the approximate solutions). Similar to Theorem 1, classic results on the convergence of the forward Euler method [21] imply that the solution of (ODE) starting at a local minimum of (7a) is the continuous limit of the sequence updated by (12).
Proposition 2 (Convergence of forward Euler). Givenx * 0 as a local minimum of (7a), as the time difference ∆ τ = τ i+1 − τ i approaches zero, any sequence of (x ∆ k ) updated by (12) converges to the (ODE) in the sense that lim for all fixed T > 0.
Propositions 1 and 2 together guarantee that the solution of (ODE) is a reasonable approximation in the sense that it is the continuous-time limit of both the solution of the sequential regularized optimization problem (7) and the solution of the online updating scheme (12). Fo this reason, we only study the continuoustime problem (ODE) in the remainder of this paper.

Jumping, tracking and escaping
In this section, the objective is to study the case where there are at least two local minima at different time instances of the online optimization problem. Consider a local I t,1 -minimum trajectory h 1 (t) and a local I t,2 -minimum trajectory h 2 (t). Suppose that the time-varying function f (x, t) is locally (Ī t,1 , c 1 , r 1 )one point strongly convex around h 1 (t) and locally (Ī t,2 , c 2 , r 2 )-one point strongly convex around h 2 (t). Let [t 1 , t 2 ] ⊂Ī t,1 ∩Ī t,2 be a non-empty interval. We provide the definitions of jumping, tracking and escaping below.
If I t,2 is a finite time interval andĪ t,2 ⊂ I t,2 , then h 2 (t) will disappear after the time interval I t,2 . In this case, one could only expect that the solution of (ODE) temporarily tracks h 2 (t).

Definition 8.
It is said that x(t, t 0 , x 0 ) temporarily u-tracks h 2 (t) if there exist a constant u > 0 and a finite time T in the interior ofĪ t,2 and such that The term "temporary" in the above definition emphasizes tracking over a possibly finite interval. The counterpart of this definition for an infinite interval will be given below.
In this paper, the objective is to study the scenario where a solution x(t, t 0 , x 0 ) tracking a poor solution h 1 (t) at the beginning ends up tracking a better solution h 2 (t) after some time. This needs the notion of "escaping" introduced below. Figure 3: Illustration of jumping and tracking Figure 3 illustrates the definitions of jumping and tracking for Example 1 with α = 0.3 and b = 5. The objective of this paper is to study when the solution of (ODE) started at a poor local minimum at the initial time jumps to and tracks a better (or global) minimum of the problem after some time. In other words, it is desirable to investigate the escaping property from h 1 (t) and h 2 (t).

Optimization landscape after a change of variables
Given two isolated local minimum trajectories h 1 (t) and h 2 (t), one may use the change of variables x(t, t 0 , x 0 ) = e(t, t 0 , e 0 ) + h 2 (t) to transform (ODE) into the forṁ We use e(t, t 0 , e 0 ) to denote the solution of this differential equation starting at time t = t 0 with the initial point e 0 = x 0 − h 2 (t 0 ). Note that h 1 (t) and h 2 (t) are local solutions of f (x, t) and as long as f (x, t) is time-varying, these functions cannot satisfy (ODE) in general.

Inertia encouraging the exploration
The first term ∇ x f (e + h 2 (t), t) in (18) can be understood as a time-varying gradient term that encourages the solution of (18) to track the local minimum h 2 (t) while the second termḣ 2 (t) represents the inertia from this trajectory. In particular, ifḣ 2 (t) points toward outside of the region of attraction of h 2 (t) during some time interval, the termḣ 2 (t) acts as an exploration term that encourages the solution of (ODE) to leave the region of attraction of h 2 (t). The parameter α balances the roles of the gradient and the inertia.
In the extreme case where α goes to infinity, e(t) converges to −h 2 (t) and x(t) approaches a constant trajectory determined by the initial point x 0 ; when α is sufficiently small, the time-varying gradient term dominates the inertia term and the solution of (ODE) would track h 2 (t) closely. With the appropriate proximal regularization α that balances the time-varying gradient term and the inertia term, the solution of (ODE) could temporarily track a local minimum trajectory while keeping the potential of exploring other local minimum trajectories.

Inertia creating a one point strongly convex landscape
The differential equation (18) can be written aṡ This can be regarded as a time-varying gradient flow system of the original objective function f (e + h 2 (t), t) plus a time-varying perturbation αḣ 2 (t) e. During some time interval [t 1 , t 2 ], the time-varying perturbation αḣ 2 (t) e may enable that the time-varying objective function f (e+h 2 (t), t)+αḣ 2 (t) e over the neighborhood of h 1 (t) becomes one point strongly convexified with respect to h 2 (t). Under such circumstances, the time-varying perturbation αḣ 2 (t) e prompts the solution of (19) starting in a neighborhood of h 1 (t) to move to a neighborhood of h 2 (t). Before analyzing this phenomenon, we illustrate the concept in an example. Consider again Example 1 and recall that g(x) has 2 local minima at x = −2 and x = 1. By taking b = 5, h 1 (t) = −2 + 5 sin(t) and h 2 (t) = 1 + 5 sin(t), the differential equation (19) can be expressed aṡ . The landscape of the new time-varying function g(1+e)+5α cos(t)e with the variable e is shown for two cases α = 0.3 and α = 0.1 in Figure 4. The red curves are the solutions of (19) starting from e = −3. One can observe that when α = 0.3, the new landscape becomes one point strongly convex around h 2 (t) over the whole region for some time interval, which provides (19) with the opportunity of escaping from the region around h 1 (t) to the region around h 2 (t). However, when α = 0.1, there are always two locally one point strongly convex regions around h 1 (t) and h 2 (t) and, therefore, (19) fails to escape the region around h 1 (t). To further inspect the case α = 0.3, observe in Figure 5a that the landscape of the objective function g(1 + e) + 1.5 cos(0.9π)e shows that the region around the spurious local minimum trajectory h 1 (t) is one point strongly convexified with respect to h 2 (t) at time t = 0.9π. This is consistent with the fact that the solution ofė = − 1 0.3 ∇ x g(1 + e) − 5 cos(t) starting from e = −3 jumps to the neighborhood of 0 around time t = 0.9π, as demonstrated in Figure 5c. Furthermore, if the time interval [t 1 , t 2 ] is relatively large enough to  allow transitioning from a neighborhood of h 1 (t) to a neighborhood of h 2 (t), then the solution of (19) would move to the neighborhood of h 2 (t). In contrast, the region around 1 + b sin(t) is never one point strongly convexified with respect to −2 + b sin(t), as shown in Figure 5b.
From the right-hand side of (19), it can be inferred that if the gradient of f (·, t) is relatively small around some local minimum trajectory, then its landscape is easier to be re-shaped by the time-varying linear perturbation αḣ 2 (t) e. The local minimum trajectory with a neighborhood of small gradients usually correspond to a shallow minimum trajectory in which the local minimum trajectory is relatively flat and has a relatively small region of attraction. Thus, the one point strong convexication introduced by the time-varying perturbation could help escape the shallow minimum trajectories.

Main results
In this section, we study the jumping, tracking and escaping properties for online optimization.

Jumping
In this part, we derive different sufficient conditions under which the solution of (ODE) jumps from a poor local minimum trajectory to a better (or global) trajectory. (Ī t,1 , c 1 , r 1 )-one point strongly convex around h 1 (t) and locally (Ī t,2 , c 2 , r 2 )-one point strongly convex around h 2 (t) in the region D 1 = {e ∈ R n : e ≤ r 2 }. Assume that there exist a nonempty time interval [t 1 , t 2 ] ⊂ I t,1 ∩Ī t,2 , a regularization parameter α, a connected subset D 4 , and a constant θ ∈ (0, 1) such that five conditions are satisfied:

t 1 ))} and D 4 is a compact positively invariant subset with respect to
3. One point strong convexification: The time-varying function f (e + h 2 (t), t) + αḣ 2 (t) e is locally one point w-strongly convex aroundē(t) for all e ∈ D 4 and for all t ∈ [t 1 , t 2 ], i.e. , where w > 0 is a constant.

Upper bound on inertia
.

Lower bound for the time interval:
The following inequality holds: Then, the solution of (ODE) will (v, To avoid directly solving for the real roots of ∇ x f (e + h 2 (t), t) + αḣ 2 (t) = 0 and checking the condition (21) for all t ∈ [t 1 , t 2 ], we propose an approach based on the time-averaged dynamics over a small time interval and named it "small interval averaging" 3 . This technique guarantees that the solution of the timevarying differential equation (or system) will converge to a residual set of the origin of (18), provided that: (1) there is a time interval [t 1 , t 2 ] such that the temporal variation makes the averaged objective function during this interval locally one point strongly convex around h 2 (t) not only just over the neighborhood of h 2 (t) but also over the neighborhood of h 1 (t), (2) the original time-varying system is not too distant from the time-invariant averaged system, (3) [t 1 , t 2 ] is relatively large enough to allow the transition of points from the neighborhood of h 1 (t) to the neighborhood of h 2 (t). Therefore, this time interval [t 1 , t 2 ] and its time-averaged dynamics over this time interval serve as a certificate for jumping from h 1 (t) to h 2 (t). In what follows, we introduce the notion of averaging a time-varying function over a time interval [t 1 , t 2 ].

Definition 11. A function f h2
av (e) is said to be the average function of f (e+h 2 (t), t) over the time interval is said to be a partial interval averaged system of the time-varying system (18) over the time interval [t 1 , t 2 ] with the perturbation term Theorem 3 (Sufficient conditions for jumping from h 1 (t) to h 2 (t) using averaging). Given a local I t,1minimum trajectory h 1 (t) and a local I t,2 -minimum trajectory h 2 (t), suppose that the time-varying function f (x, t) is locally (Ī t,1 , c 1 , r 1 )-one point strongly convex around h 1 (t) and locally (Ī t,2 , c 2 , r 2 )-one point strongly convex around h 2 (t) in the region D 1 = {e ∈ R n : e ≤ r 2 }. Assume that there exist a nonempty time interval [t 1 , t 2 ] ⊂Ī t,1 ∩Ī t,2 , a regularization parameter α, and a connected subset D 4 such that the following five conditions are satisfied: 1. Equilibrium point of the averaged system: The system (24) has an equilibrium pointē in the region D 2 = {e ∈ R n : e ≤ ρ}, where ρ < r 2 .

Identifying a positively invariant set:
)} and D 4 is a compact positively invariant subset with respect to (18), i.e.,

One point strong convexification: The time invariant function
e is locally one point w-strongly convex aroundē for all e ∈ D 4 , i.e., where w > 0 is a constant.

Tracking
In this subsection, we study the tracking property of the local minimum trajectory h 2 (t). First, notice that if h 2 (t) is not constant, the right-hand side of (ODE) is nonzero while the left-hand side is zero. Therefore, h 2 (t) is not a solution of (ODE) in general. This is because the solution of (ODE) approximates the continuous limit of a discrete local trajectory of the sequential regularized optimization problem (7). However, to preserve the optimality of the solution with regards to the original time-varying optimization problem without any proximal regularization, it is required to guarantee that the solution of (ODE) is close to h 2 (t). First, consider the case when the maximal time interval of h 2 (t) is the entire time horizon [t 0 , ∞]. If the solution of (18) can be shown to be in a small residual set around 0, then it is guaranteed that x(t, t 0 , x 0 ) tracks its nearby local minimum trajectory. Notice that (18) can be regarded as a time-varying perturbation of the systemė Since h 2 (t) is a local minimum trajectory, it is obvious that e(t) ≡ 0 is an equilibrium point of (35). In addition, since f (e + h 2 (t), t) is locally (∞, c 2 , r 2 )-one point around h 2 (t), the stability property of e = 0 for (35) can be proved, as discussed below. t) is locally (∞, c 2 , r 2 )-one point strongly convex around h 2 (t) in the region D = {e ∈ R n : e ≤ r 2 }, then e = 0 is a locally exponentially stable equilibrium point of (35).
Since the system (35) has an exponentially stable equilibrium point at e = 0, one would expect that the solution of the time-varying perturbed system (18) stays in a small residual set of e = 0 if the perturbatioṅ h 2 (t) is relatively small. The perturbationḣ 2 (t) being small is equivalent to α being small. The next theorem shows that every local ∞-minimum trajectory can be tracked for a sufficiently small α. Theorem 4 (Sufficient condition for tracking). Assume that the time-varying function f (x, t) is locally (∞, c 2 , r 2 )-one point strongly convex around h 2 (t). Then, h 2 (t) can be tracked if α is sufficiently small. In particular, given 0 < θ < 1, γ := sup t≥0 ḣ 2 (t) , u := αγ θ c2 , x 0 − h 2 (0) ≤ r 2 and α < c2θ r2 γ , the solution x(t, t 0 , x 0 ) will u-track h 2 (t) exponentially with the convergence rate (1 − θ ) c2 α , namely, Furthermore, if the region B u (h 2 (t)) lies inside the region of strong convexity of f (x, t) around h 2 (t), we can show that the solutions of (18) starting from any points in B r2 (h 2 (t)) will converge to each other.

Definition 12.
It is said that f (x, t) is locally (Ī t ,c,r) strongly convex around the local I t -minimum trajectory h(t) if there exist a constantc > 0 and a regionD = {e ∈ R n : e ≤r} such that The regionD = {e ∈ R n : e ≤r} is called the region of locally (Ī t , c, r) strong convexity around h(t).

Theorem 5 (Sufficient conditions for contraction).
Assume that the conditions of Theorem 4 are satisfied, and that the time-varying function f (x, t) is locally (∞,c 2 ,r 2 ) strongly convex around h 2 (t). Then, for all points x 1 0 and x 2 0 such that x 1 0 − h 2 (0) ≤ r 2 and x 2 0 − h 2 (0) ≤ r 2 , the solutions x(t, t 0 , x 1 0 ) and x(t, t 0 , x 2 0 ) will converge to each other in the sense that if α < c2θ r2 γ . Next, we consider the case when h 2 (t) is define only over a finite maximal time interval I t,2 . The system after the change of variables x(t, t 0 , x 0 ) = e(t, t 0 , e 0 ) + h 2 (t) is defined on a finite time interval: In this case, the notion of uniformly asymptotic stability is not well-defined. However, the following result on temporary tracking can be developed.

Remark 4.
For a fixed ultimate bound u, the convergence rate (1 − θ ) c2 α shows that x(t, t 0 , x 0 ) converges faster to B u (h 2 (t)) as the regularization parameter α reduces.

Remark 5.
In the case that the local minimum trajectory h 2 (t) is a constant, the upper bound on α simply becomes α < ∞. This implies that if the local minimum trajectory h 2 (t) is constant, then it will be perfectly tracked with any regularization parameter and can not be escaped by tuning the regularization parameter.

Escaping
Combining Theorem 2 or 3 with Theorem 4 or 6 immediately yields a sufficient condition on escaping from one local minimum trajectory to another local minimum trajectory. The proof is omitted for brevity. Theorem 7 (Sufficient conditions for escaping from h 1 (t) to h 2 (t)). Given a local I t,1 -minimum trajectory h 1 (t) and a local I t,2 -minimum trajectory h 2 (t), suppose that the time-varying function f (x, t) is locally (Ī t,1 , c 1 , r 1 )-one point strongly convex around h 1 (t) and locally (Ī t,2 , c 2 , r 2 )-one point strongly convex around and u = αγ θ c2 . Under the conditions of Theorem 2 or 3 , if α < r2c2θ γ , the solution of (ODE) will (v, r 2 )escape from h 1 (t) to h 2 (t) after t ≥ t 2 .

Discussions
Adaptive inertia: To leverage the potential of the time-varying perturbation αḣ 2 (t) e in re-shaping the landscape of the objective function to become locally one point strongly convex over a large region, the regularization parameter α should be selected relatively large. On the other hand, to ensure the solution of (19) will end up tracking a local minimum trajectory (or hopefully, a global minimum trajectory), Theorem 4 prescribes small values for α. In practice, especially when the time-varying objective function has many spurious shallow minimum trajectories, this suggests using a relatively large regularization parameter α at the beginning of the time horizon to escape spurious shallow minimum trajectories and then switching to a relative small regularization parameter α for reducing the ultimate tracking error bound.
Sequential jumping: When the time-varying objective function f (x, t) has many local minimum trajectories, the solution of (ODE) may sequentially jump from one local minimum trajectory to a better local minimum trajectory. To illustrate this concept, consider the local minimum trajectories h 1 (t), h 2 (t), ..., h m (t), where h m (t) is a global tarjectory. Assume that there exists a sequence of time intervals [t i 1 , t i 2 ] for i = 1, 2, . . . , m − 1 such that the conditions of Theorem 2 or 3 are satisfied for h i (t) and h i+1 (t) during each time interval. Then, by sequentially deploying Theorem 2 or 3, it can be concluded that the solution of (ODE) will jump from h 1 (t) to h m (t) after t ≥ t m 2 . Furthermore, if h m (t) is tractable with the given α, the solution of (ODE) will escape from h 1 (t) to h m (t) after t ≥ t m 2 .

Numerical Example
Example 2. Consider the two-dimensional non-convex function This function has a global minimum at (0, 0) with the optimal value 0 and many spurious local minima. Its landscape is shown in Figure 6a. When d = 0, this function is called the Ackley function [1], which is a benchmark function for global optimization algorithms. To make this function twice continuously differentiable, we take d = 0.01. Thus, one could expect that the solution of (ODE) would jump from h 1 (t) to h 2 (t). More formally, it can be shown that g(x) is locally (3.3, 1.1)-one point strongly convex with respect to the origin, which implies that f (x, t) is locally (∞, 3.3, 1.1)-one point strongly convex around h 2 (t). To ensure that the solution of (ODE) will track h 2 (t), we need to take α < c2r2θ sup t≥0 ż(t) for 0 < θ < 1. In this case, α = 0.5 simply satisfies the tracking condition. Then, by the change of variables x = e + h 2 (t), the differential equation (18) can be written aṡ By selecting the time interval [0, π 8 ], the averaged system can be obtained aṡ √ 0.5(e 2 1 +e 2 2 )+d 2 + 0.5πe (0.5(cos(2πe1)+cos(2πe2))) sin(2πe 1 ) 10e − ]. This implies that D 4 is a positively invariant set with respect to (42) for t ∈ [0, π 8 ]. This shows that Condition 2 in Theorem 3 is also met. Furthermore, (27) and (33) are satisfied for w = 1.3. Thus, the conditions of Theorem 7 are all met, and therefore the solution of (42) will (0.1, 1.1)-escape from h 1 (t) to h 2 (t). Furthermore, we have verified for 1000 runs of random initialization over x 0 − z(0) ∈ [−5, 5] × [−5, 5] that all solutions of (42) will sequentially jump over the local minimum trajectories and end up tracking the global trajectory [0, 0] + z(t) after t ≥ 10π.

Conclusion
In this work, we study the landscape of time-varying nonconvex optimization problems. The objective is to understand when simple local search algorithms can find (and track) time-varying global solutions of the problem over time. We introduce a time-varying gradient flow system with controllable inertia as a continuous-time limit of the stationary condition for discretized sequential optimization problems with proximal regularization and online updating scheme. Via a change of variables, the time-varying gradient flow system is regarded as a composition of a time-varying gradient term and a time-varying perturbation term due to the inertia. We show that the time-varying perturbation term due to the inertia encourages the exploration of the state space and re-shapes the landscape by potentially making it one point strongly convex over a large region during some time interval. We introduce the notions of jumping and escaping, and use them to develop sufficient conditions under which the time-varying solution jumps from a poor local trajectory to a better (or global) minimum trajectory over a finite time interval. We illustrate in a twodimensional benchmark example with many shallow minimum trajectories that the natural time variation of the problem enables escaping spurious local minima over time. Avenues for future work include the extension of the current work to constrained time-varying nonconvex optimization problems. Furthermore, it is useful to study how to systematically introduce an exogenous temporal variation to a time-invariant nonconvex optimization problem in order to find its global minimum using an online-optimization-based local search method.
Therfore, the solution x(T ) is defined and since W is closed, it holds that x(T ) ∈ W . Then, it follows from Proposition 3 (applied to the point (T, x(T ))) that there is a δ > 0 with the property that the solution can be extended to [t 0 , T + δ]. This contradicts the fact that [t 0 , T ) is the maximal interval of existence, and completes the proof.
Proof of Theorem 1 . If f (x, t) is piecewise continuous in t and its gradient is locally Lipschitz in x for all t ≥ 0 and x ∈ D ∈ R n , then ∇ x f (t, x) satisfies the conditions of Propositions 3-4. It results from Propositions 3-4 that there exists a unique solution for (ODE) over [t 0 , T ) that is the maximal interval of unique existence. It is enough to show that T = ∞. Due to Lemma 2, if the time T is finite, the solution must leave every compact subset of D. However, the solution never leaves the compact set W . This implies that T = ∞.

Proof of Lemma 1
First, we show that if u := αγ θ c2 < r 2 or α < c2θ r2 γ , the set D has the property that any trajectory starting in D at t 1 stays in the set D for all t ∈Ī t,2 . Notice that since the derivativeV is negative on the boundary ∂D, (72) implies that the set D is positively invariant. Since D is also a compact set, it follows from Theorem 1 that (18) has a unique solution defined for all t ∈Ī t,2 whenever e 1 := x 1 − h(t 1 ) ∈ D. Then, the set D being positively invariant implies that x(t, t 1 , x 1 ) ∈ B r2 (h 2 (t)) ⊆ RA(h 2 (t)), ∀t ∈Ī t,2 By choosing x(t 1 , t 0 , x 0 ) = x 1 , one can conclude that x(t, t 0 , x 0 ) will temporarily r 2 -track h 2 (t). Next, we show that if the finite time intervalĪ t,2 is large enough, the solution of (39) will enter the set B u (0) = {e ∈ R n : e ≤ u} with an exponential convergence rate and stays in B u (0) for all future times. SinceV is negative in Γ = {e ∈ R n : u ≤ e ≤ r 2 } for all t ∈Ī t,2 , a trajectory starting from Γ must move in a direction of decreasing V (e) and the function V (e) will continue decreasing until the trajectory enters the set B u (0) or until time t 2 . The fact that the trajectory enters B u (0) before t 2 if t 2 − t 1 > α c2(1−θ ) ln r2 u is based on the same argument used in the proof of Theorem 4.