Spectral Analysis of the Dynamics of Gradients and Updates

Let $G_T=\{g_1,\dots ,g_T\}$ and $U_T=\{u_1,\dots ,u_T\}$ denote the sequences of gradient and update vectors. Each pair $(g_i,u_i)$ is recorded at the $i$-th iteration of an optimization algorithm. For a deep neural network (DNN), these vectors may instead represent the full optimizer-visible state at the $i$-th training step on input-label pair $(x_i,y_i)$, including the gradients produced by backpropagating the prediction error. We study the spectral properties of $G_T$ and $U_T$ across a collection of convex optimization problems and DNNs, including convolutional neural networks (CNNs) and residual networks (ResNets). Our experiments show that the spectral energy of these histories is sharply concentrated in a small number of directions. Now, focusing only on optimization algorithms, for a given choice of descent such as Nesterov accelerated gradient descent (NAG), we define a corresponding Nesterov-Ramanujan descent in which vectors from the gradient and update histories are transformed according to $v⟼Mv.$ Here, $M$ is a sparse mixing operator supported on a randomly directed, two-colored Ramanujan graph designed to be ergodic, rapidly mixing, and large-girth. Ordinary NAG corresponds to $M=I$. At iteration $t$, our update rule uses the histories $G_t$ and $U_t$ to determine a step size ${\Delta }_t$ and then computes $(g_{t+1},u_{t+1}).$ The intervention broadens the spectrum of at least one of the two histories. We use this spectral change to increase the step size through a safeguarded adaptive rule, which typically enables faster convergence in our experiments. Surprisingly, the update history $U_T$ is often more informative than the gradient history $G_T$, even though classical momentum methods are usually formulated primarily in terms of gradients.