Chaotic Regularization and Heavy-Tailed Limits for Deterministic Gradient Descent
Recent studies have shown that gradient descent (GD) can achieve improved
generalization when its dynamics exhibits a chaotic behavior. However, to
obtain the desired effect, the step-size should be chosen sufficiently large, a
task which is problem dependent and can be difficult in practice. In this
study, we incorporate a chaotic component to GD in a controlled manner, and
introduce multiscale perturbed GD (MPGD), a novel optimization framework where
the GD recursion is augmented with chaotic perturbations that evolve via an
independent dynamical system. We analyze MPGD from three different angles: (i)
By building up on recent advances in rough paths theory, we show that, under
appropriate assumptions, as the step-size decreases, the MPGD recursion
converges weakly to a stochastic differential equation (SDE) driven by a
heavy-tailed L\'evy-stable process. (ii) By making connections to recently
developed generalization bounds for heavy-tailed processes, we derive a
generalization bound for the limiting SDE and relate the worst-case
generalization error over the trajectories of the process to the parameters of
MPGD. (iii) We analyze the implicit regularization effect brought by the
dynamical regularization and show that, in the weak perturbation regime, MPGD
introduces terms that penalize the Hessian of the loss function. Empirical
results are provided to demonstrate the advantages of MPGD.