Contractivity of Runge-Kutta methods for convex gradient systems

Jesús María Sanz-Serna, Konstantinos C. Zygalakis

Introduction

In optimization and numerical analysis, we often rely on the assumption that taking smaller steps with a sophisticated algorithm will lead to better convergence. However, a fundamental property of continuous-time gradient systems—contractivity—is not always preserved when we discretize them using standard numerical integrators. This paper explores whether Runge-Kutta (RK) methods maintain this property for convex gradient systems.

The Problem: Preserving Contractivity

A gradient system is defined by the differential equation $\dot{x} = -\nabla V(x)$. When the potential function $V$ is convex, the system is contractive: the Euclidean distance between any two trajectories $x(t)$ and $\tilde{x}(t)$ is non-increasing over time. In practice, we solve these systems using discrete steps of size $h$ via Runge-Kutta methods. While the simple first-order Euler method is known to be contractive for sufficiently small $h$, the behavior of higher-order methods is more complex.

The "Euler is Best" Paradox

A surprising result of this research is that for preserving contractivity in convex systems, the simple Euler method is actually optimal among explicit methods. While higher-order methods are generally preferred for their accuracy, they can fail to be contractive regardless of how small the time step $h$ is chosen.

Geometric Failure of Higher-Order Methods

The authors demonstrate this failure by focusing on Runge's method, a standard second-order RK scheme. They prove that for any $h > 0$, there exists a smooth, convex potential $V$ such that the method is non-contractive.

Geometric representation of a two-stage Runge-Kutta method step where the distance between two trajectories increases.

As illustrated in the figure above, the failure occurs because the intermediate "stages" of the RK method (labeled $x_h$ and $\tilde{x}_h$) sample the gradient at points that can "trick" the algorithm. Even if the gradients at the starting points ($x_0, \tilde{x}_0$) suggest the trajectories should move closer, the gradients at the intermediate stages ($k_h, \tilde{k}_h$) can cause the final points ($x_1, \tilde{x}_1$) to be further apart than the initial ones.

Methodology: Adversarial Construction

To prove these results, the authors employed a combination of robust control theory and convex interpolation. They identified "worst-case" scenarios and constructed specific piecewise linear convex functions that cause contractivity to fail. These functions were then smoothed using convolution to ensure they met the standard $L$-smoothness requirements of optimization theory.

Key Results and Implications

  • Theorem 2.2: Formally establishes that the Euler method allows for the largest possible step size while maintaining contractivity among explicit RK methods.
  • Theorem 3.2: Proves that for common second-order methods, the distance between trajectories can grow by a factor of $1 + O(h^3)$ in a single step, even for arbitrarily small $h$.
  • Structural Property: The lack of contractivity is a structural feature of the algorithm's stages, not a simple discretization error that vanishes with smaller $h$.

Conclusion

This work highlights a significant trade-off in numerical optimization: higher-order accuracy does not guarantee the preservation of fundamental geometric properties like contractivity. While explicit methods are computationally efficient for large-scale machine learning, their potential to drift apart trajectories—even on convex landscapes—suggests that the choice of integrator must be made with care, especially when stability is paramount. Future research may explore whether these "adversarial" scenarios appear in practical applications like neural network training or if alternative norms offer better stability.

Summary updated

BibTeX
@article{sanzserna2020contractivity,
  author = {Jesús María Sanz-Serna and Konstantinos C. Zygalakis},
  title = {{Contractivity of Runge-Kutta methods for convex gradient systems}},
  journal = {SIAM J. Numer. Anal.},
  year = {2020},
  doi = {10.1137/19m1299256},
}
Figure