Search

We establish that first-order methods avoid strict saddle points for almost all initializations. Our results apply to a wide variety of first-order methods, including (manifold) gradient descent, block coordinate descent, mirror descent and variants thereof. The connecting thread is that such algorithms can be studied from a dynamical systems perspective in which appropriate instantiations of the Stable Manifold Theorem allow for a global stability analysis. Thus, neither access to second-order derivative information nor randomness beyond initialization is necessary to provably avoid strict saddle points.

The paper considers distributed gradient flow (DGF) for multi-agent nonconvex optimization. DGF is a continuous-time approximation of distributed gradient descent that is often easier to study than its discrete-time counterpart. The paper has two main contributions. First, the paper considers optimization of nonsmooth, nonconvex objective functions. It is shown that DGF converges to critical points in this setting. The paper then considers the problem of avoiding saddle points. It is shown that if agents' objective functions are assumed to be smooth and nonconvex, then DGF can only converge to a saddle point from a zero-measure set of initial conditions. To establish this result, the paper proves a stable manifold theorem for DGF, which is a fundamental contribution of independent interest. In a companion paper, analogous results are derived for discrete-time algorithms.

The paper develops and studies a very general notion of dichotomy, referred to as “nonuniform (h,k,µ,ν)-dichotomy”. The new notion contains as special cases most versions of dichotomy existing in the literature. The paper then provides corresponding new versions of robustness, Hartman-Grobman theorem, and stable manifold theorem for nonautonomous dynamical systems in Banach spaces in term of the nonuniform (h,k,µ,ν)-dichotomy.

In this paper, we discuss the existence of a center stable manifold for planar fractional damped equations. By constructing a suitable LyapunovPerron operator via giving asymptotic behavior of MittagLeffler function, we obtain an interesting center stable manifold theorem. Finally, an example is provided to illustrate the result.

This paper develops seminumerical methods for computing high-order polynomial approximations of stable/unstable manifolds attached to long periodic orbits in discrete time dynamical systems. Our approach extends a standard multiple shooting scheme for periodic orbits, allowing us to compute invariant manifolds for periodic orbits without considering compositions of the map. This leads to a system of conjugacy equations characterizing the complete collection of chart maps, with one chart attaching a local stable/unstable manifold to each point along the periodic orbit. We develop a formal series solution for the system of conjugacy equations and show that the coefficients of the series are determined by recursively solving certain linear systems of equations. We derive the recursive equations for a number of example problems in dimensions two and three, with both polynomial and transcendental nonlinearities, and present some numerical results which illustrate the utility of the method. We also highlight so...

In this paper, we provide some analysis on the asymptotic escape of strict saddles in manifold optimization using the projected gradient descent (PGD) algorithm. One of our main contributions is that we extend the current analysis to include non-isolated and possibly continuous saddle sets with complicated geometry. We prove that the PGD is able to escape strict critical submanifolds under certain conditions on the geometry and the distribution of the saddle point sets. We also show that the PGD may fail to escape strict saddles under weaker assumptions even if the saddle point set has zero measure and there is a uniform escape direction. We provide a counterexample to illustrate this important point. We apply this saddle analysis to the phase retrieval problem on the low-rank matrix manifold, prove that there are only a finite number of saddles, and they are strict saddles with high probability. We also show the potential application of our analysis for a broader range of manifold optimization problems.

The paper studies a distributed gradient descent (DGD) process and considers the problem of showing that in nonconvex optimization problems, DGD typically converges to local minima rather than saddle points. The paper considers unconstrained minimization of a smooth objective function. In centralized settings, the problem of demonstrating nonconvergence to saddle points of gradient descent (and variants) is typically handled by way of the stable-manifold theorem from classical dynamical systems theory. However, the classical stable-manifold theorem is not applicable in distributed settings. The paper develops an appropriate stable-manifold theorem for DGD showing that convergence to saddle points may only occur from a low-dimensional stable manifold. Under appropriate assumptions (e.g., coercivity), this result implies that DGD typically converges to local minima and not to saddle points.

An imbalanced rotor is considered. A system of moving balancing masses is given. We determine the optimal movement of the balancing masses to minimize the imbalance on the rotor. The optimal movement is given by an open-loop control solving an optimal control problem posed in infinite time. By methods of the Calculus of Variations, the existence of the optimum is proved and the corresponding optimality conditions have been derived. Asymptotic behavior of the control system is studied rigorously. By \L ojasiewicz inequality, convergence of the optima as time $t\to +\infty$ towards a steady configuration is ensured. An explicit estimate of the convergence rate is given. This guarantees that the optimal control stabilizes the system. In case the imbalance is below a computed threshold, the convergence occurs exponentially fast. This is proved by the Stable Manifold Theorem applied to the Pontryagin optimality system. Moreover, a closed-loop control strategy based on Reinforcement Learning is proposed. Numerical simulations have been performed, validating the theoretical results.

This chapter provides an introduction to our main contributions concerning the development of the novel methods of CoCoSSC.

As mentioned in Chap. 3, gradient descent (GD) and its variants provide the core optimization methodology in machine learning problems. Given a C1 or C2 function \(f: \mathbb {R}^{n} \rightarrow \mathbb {R}\) with unconstrained variable \(x \in \mathbb {R}^{n}\), GD uses the following update rule: $$\displaystyle x_{t+1} = x_{t} - h_t \nabla f\left (x_t\right ), $$ where ht are step size, which may be either fixed or vary across iterations. When f is convex, \(h_t < \frac {2}{L}\) is a necessary and sufficient condition to guarantee the (worst-case) convergence of GD, where L is the Lipschitz constant of the gradient of the function f. On the other hand, there is far less understanding of GD for non-convex problems. For general smooth non-convex problems, GD is only known to converge to a stationary point (i.e., a point with zero gradient).

We consider general difference equations \(u_{n+1} = F(u)_n\) for \(n \in \mathbb {Z}\) on exponentially weighted \(\ell _2\) spaces of two-sided Hilbert space-valued sequences u and discuss initial value problems. As an application of the Hilbert space approach, we characterize exponential stability of linear equations and prove a stable manifold theorem for causal nonlinear difference equations.

This paper investigates the combination of optimal feedback control with the dynamical structure of the three-body problem. The results provide new insights for the design of continuous low-thrust spacecraft trajectories. Specifically, the attracting set of an equilibrium point or a periodic orbit (represented as a fixed point) under optimal control with quadratic cost is obtained. The analysis reveals the relation between the attractive set and original dynamics. In particular, it is found that the largest dimensions of the set are found along the stable manifold and the least extent is along the left eigenvector of the unstable manifold. The asymptotic behavior of the structure of the attractive set when time tends to infinity is analytically revealed. The results generalize the use of manifolds for transfers to equilibrium points and periodic orbits in astrodynamic problems. The result is theoretical and developed for a linearized system, but it can be extended to nonlinear systems in the future.

In this paper, we investigate local stable manifold for planar Hadamard fractional differential equations. By adopting Lyapunov–Perron operator approach and establishing new estimation of Mittag-Leffler function associated with Hadamard fractional derivative, we derive another interesting local stable manifold theorem for our problem. Finally, an example is given to illustrate our theoretical results.

We study small C1-perturbations of systems of differential equations that have a weakly hyperbolic invariant set. We show that the weakly hyperbolic invariant set is stable even if the Lipschitz condition fails.

In this article we analyze n -dimensional slow–fast systems in a piecewise linear framework. In particular, we prove a Fenichel's-like Theorem where we give an explicit expression for the invariant slow manifold, that leads to the proof of the existence and location of maximal canards orbits. We show that these orbits perturb from singular orbits through contact points, of order greater than or equal to two, between the reduced flow and the fold manifold. In the particular case n = 3 , we show that the unique contact point is a visible two-fold singularity.

We develop and implement a computer assisted argument for proving the existence of heteroclinic/homoclinic connecting orbits for compact infinite dimensional maps. The argument is based on a posteriori analysis of a certain “discrete time boundary value problem,” and a key ingredient is representing the local stable/unstable manifolds of the fixed points. For a compact mapping the stable manifold is infinite dimensional, and an important component of the present work is the development of computer assisted error bounds for numerical approximation of infinite dimensional stable manifolds. As an illustration of the utility of our method we prove the existence of some connecting orbits for a nonlinear dynamical system which appears in mathematical ecology as a model of a spatially distributed ecosystem with population dispersion.

The paper studies properties of best-response (BR) dynamics in potential games with continuous action sets. It is known that BR dynamics converge to the set of Nash equilibria (NE) in potential games. The set of NE in potential games is composed of local maximizers and saddle points of the potential function. The paper studies non-convergence of BR dynamics to saddle points of the potential function. Under relatively mild assumptions it is shown that BR dynamics may only converge to an interior saddle-point from a measure-zero set of initial conditions. This provides a weak stable manifold theorem in this context.

International audience; This paper considers near-equilibrium systems of ordinary differential equations with explicit separation of the slow and stable manifolds. Formal B-series like those previously used to analyze highly-oscillatory systems or to construct modified equations are employed here to construct expansions of the change of variables, the center invariant manifold and the reduced model. The new approach may be seen as a process of reduction to a normal form, with the main advantage, as compared to the standard view conveyed by the celebrated center manifold theorem, that it is possible to recover the complete solution at any time through an explicit change of variables.

In this paper we prove existence of local stable manifold around a hyperbolic equilibrium point of a fractional system. We illustrate this result with an example and plot corresponding local stable manifold.

In this paper, the solvability and the existence of asymptotically stable solutions for a nonlinear functional integral equation are studied. The main tools are a fixed point theorem of Krasnosel’skii type, the dominated convergence theorem, and other results from functional analysis. In order to illustrate the result obtained here, an example is given.

The Multi-revolution Elliptic Halo (ME-Halo) orbit is a special kind of symmetric periodic orbits generated in the Elliptic Restricted Three-Body Problem (ERTBP). Its special properties, including a long period and a redundant stable direction, make it a promising nominal orbit in space mission design. In this paper, direct transfer to an ME-Halo orbit using its three-dimensional stable manifold is investigated in the Earth–Moon system. At first, perigee transfers along the main stable manifold are constructed, and different orbit injection points are surveyed. Then the manifold injection point is optimized locally. The impact of the redundant stable direction of the ME-Halo orbit is analyzed through a survey of apogee transfers using both of its two stable directions. This paper presents a first exploration of transferring to ME-Halo orbits, which is directly performed in the ERTBP. Results in this paper will enrich the preliminary space mission design by providing feasible strategies to reach ME-Halo orbits.

In this paper, we show a fixed point theorem which deduces to both of Lou’s fixed point theorem and de Pascale and de Pascale’s fixed point theorem. Moreover, our result can be applied to show the existence and uniqueness of solutions for fractional differential equations with multiple delays. Using the theorem, we discuss the fractional chaos neuron model.

In this paper, we investigate the existence of local center stable manifolds of Langevin differential equations with two Caputo fractional derivatives in the two-dimensional case. We adopt the idea of the existence of a local center stable manifold by considering a fixed point of a suitable Lyapunov-Perron operator. A local center stable manifold theorem is given after deriving some necessary integral estimates involving well-known Mittag-Leffler functions.

A class of discrete dynamical systems is introduced to unify various dynamical systems that appeared in the study of phase transition phenomenon of Ising model on the Cayley tree. We give an alternative method to study the stable fixed points of these dynamical systems. The regions of non-uniqueness of stable fixed point and single stable fixed point are immediately obtained. All the previous results could be derived using this criterion.

We examine the behavior of accelerated gradient methods in smooth nonconvex unconstrained optimization, focusing in particular on their behavior near strict saddle points. Accelerated methods are iterative methods that typically step along a direction that is a linear combination of the previous step and the gradient of the function evaluated at a point at or near the current iterate. (The previous step encodes gradient information from earlier stages in the iterative process.) We show by means of the stable manifold theorem that the heavy-ball method method is unlikely to converge to strict saddle points, which are points at which the gradient of the objective is zero but the Hessian has at least one negative eigenvalue. We then examine the behavior of the heavy-ball method and other accelerated gradient methods in the vicinity of a strict saddle point of a nonconvex quadratic function, showing that both methods can diverge from this point more rapidly than the steepest-descent method.

We prove that in the case of an isometric action α : G × M → M of a Lie group G on a semi-Riemannian manifold M the union of the maximal dimensional orbits is an open and dense set in M. Moreover, if M is a Lorentz manifold and α is an isometric action on it, then in the set of the maximal dimensional orbits local stability and normalizability are equivalent, and there is no open invariant set U ⊂ M such that all the orbits G ( x ) ⊂ U are non-normalizable and have the same infinitesimal type. These results are useful in the extension of the principal orbit type theorem.

The aim of our paper is to use common limit range property for two pairs of mappings deriving common fixed point results under a generalized altering distance function. Some examples are given to exhibit different type of situation which shows the requirements of conditions of our results. At the end the existence and uniqueness of solutions for certain system of functional equations arising in dynamic programming with the help of a common fixed point theorem is presented.

For a compact (without boundary) hyperbolic n -manifold M with n ≥ 4 , we show that there exists a finite bound B such that for any homeomorphism f : M → M and any fixed point class F of f , the index | ind ( f , F ) | ≤ B , which is a partial positive answer of a question given by Jiang in [3] . Moreover, when M is a compact hyperbolic 4-manifold, or a compact hyperbolic n -manifold ( n ≥ 5 ) with isometry group Isom ( M ) a p -group, we give some explicit descriptions of the bound B .

We prove a stable version of the Lindeberg–Feller theorem and apply this result to an approximation of stable processes that are represented by stochastic integrals.

In this paper, we establish a local stable manifold theorem near a hyperbolic equilibrium point for planar fractional differential equations. The construction of this stable manifold is based on the associated Lyapunov-Perron operator. An example is provided to illustrate the result.