On the Absence of Spurious Local Trajectories in Time-Varying Nonconvex Optimization

DOI10.1109/TAC.2021.3137147MaRDI QIDQ6137487zbMATH OpenOpenAlexFDO

Authors Salar Fattahi, Cédric Josz, Reza Mohammadi, Javad Lavaei, Somayeh Sojoudi

Publication date 4 September 2023

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.09937

Mathematics Subject Classification ID

Systems theory; control (93-XX)

Abstract: In this paper, we study the landscape of an online nonconvex optimization problem, for which the input data vary over time and the solution is a trajectory rather than a single point. To understand the complexity of finding a global solution of this problem, we introduce the notion of extit{spurious (i.e., non-global) local trajectory} as a generalization to the notion of spurious local solution in nonconvex (time-invariant) optimization. We develop an ordinary differential equation (ODE) associated with a time-varying nonlinear dynamical system which, at limit, characterizes the spurious local solutions of the time-varying optimization problem. We prove that the absence of spurious local trajectory is closely related to the transient behavior of the developed system. In particular, we show that if the problem is time-varying, the data variation may force all of the ODE trajectories initialized at arbitrary local minima at the initial time to gradually converge to the global solution trajectory. We study the Jacobian of the dynamical system along a local minimum trajectory and show how its eigenvalues are manipulated by the natural data variation in the problem, which may consequently trigger escaping poor local minima over time.

Recommendations

• Time-Variation in Online Nonconvex Optimization Enables Escaping From Spurious Local Minima
• Nonasymptotic estimates for stochastic gradient Langevin dynamics under local conditions in nonconvex optimization
• Absence of local minima for a class of nonconvex optimization problems
• Local convexification of the Lagrangian function in nonconvex optimization
• Local convexification of the Lagrangian function for nonlinear nonconvex optimization
• Gradient-only approaches to avoid spurious local minima in unconstrained optimization
• On the local convergence of a stochastic semismooth Newton method for nonsmooth nonconvex optimization
• Local saddle points and convexification for nonconvex optimization problems
• Local minima of nonconvex problems
• Local saddle point and a class of convexification methods for nonconvex optimization problems

Cited in

(1)

• Time-Variation in Online Nonconvex Optimization Enables Escaping From Spurious Local Minima

This page was built for publication: On the Absence of Spurious Local Trajectories in Time-Varying Nonconvex Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6137487)