Escaping spurious local minimum trajectories in online time-varying nonconvex optimization

Abstract

A major limitation of online algorithms that track the optimizers of time-varying nonconvex optimization problems is that they focus on a specific local minimum trajectory, which may lead to poor spurious local solutions. In this paper, we show that the natural temporal variation may help simple online tracking methods find and track time-varying global minima. To this end, we investigate the properties of a time-varying projected gradient flow system with inertia, which can be regarded as the continuous-time limit of (1) the optimality conditions for a discretized sequential optimization problem with a proximal regularization and (2) the online tracking scheme. We introduce the notion of the dominant trajectory and show that the inherent temporal variation could re-shape the landscape of the Lagrange functional and help a proximal algorithm escape the spurious local minimum trajectories if the global minimum trajectory is dominant. For a problem with twice continuously differentiable objective function and constraints, 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 on a benchmark example with many local minima.

References in corpus (12)

• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• A Variational Perspective on Accelerated Methods in Optimization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• A Class of Prediction-Correction Methods for Time-Varying Convex Optimization
• Online Primal-Dual Methods with Measurement Feedback for Time-Varying Convex Optimization
• First-order Methods Almost Always Avoid Saddle Points
• Discrete and Continuous-time Soft-Thresholding with Dynamic Inputs
• Time-Varying Convex Optimization via Time-Varying Averaged Operators
• A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization
• Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis
• On-line Non-Convex Constrained Optimization