First Order Online Optimisation Using Forward Gradients in Over-Parameterised Systems

Abstract

The success of deep learning over the past decade mainly relies on gradient-based optimisation and backpropagation. This paper focuses on analysing the performance of first-order gradient-based optimisation algorithms with time-varying non-convex cost function under Polyak-Lojasiewicz condition. Specifically, we focus on using the forward mode of automatic differentiation to compute directional derivatives of the cost function in fast-changing problems where calculating gradients using the backpropagation algorithm is either impossible or inefficient. Upper bounds for tracking and asymptotic errors are derived for various cases, showing the linear convergence to a solution or a neighbourhood of an optimal solution, where the convergence rate decreases with the increase in the dimension of the problem. We present numerical results demonstrating the method's correctness and performance. Show more