A geometric integration approach to smooth optimisation: Foundations of the discrete gradient method

Matthias J. Ehrhardt, Erlend S. Riis, Torbjørn Ringholm, Carola‐Bibiane Schönlieb

Abstract

Discrete gradient methods are geometric integration techniques designed to preserve the dissipative structure of gradient flows. By ensuring a monotonic decay of function values, these methods are uniquely suited for both convex and nonconvex optimisation problems. This paper provides a rigorous theoretical foundation for the discrete gradient method, establishing its well-posedness through proofs of existence and uniqueness of iterates for any positive time step. We introduce an efficient relaxed fixed-point method for solving the associated implicit equations and establish convergence rates of $O(1/k)$ for convex objectives and linear convergence for functions satisfying the Polyak–Lojasiewicz (PL) inequality. Our analysis covers several discrete gradients, including the Gonzalez, mean value, and Itoh–Abe gradients, as well as a randomised variant. Numerical experiments demonstrate that these methods are exceptionally robust with respect to stiffness and ill-conditioning.

Introduction

In classical gradient descent, the choice of step size (learning rate) presents a fundamental trade-off: a step size that is too large leads to divergence, while one that is too small results in glacial convergence. This challenge is exacerbated in "stiff" problems, where the objective function exhibits rapid variations in certain directions, forcing explicit methods to adopt infinitesimal steps to maintain stability.

This paper bridges the gap between geometric numerical integration and mathematical programming by formalising the Discrete Gradient Method. While geometric integration has historically used these methods to preserve physical properties like energy dissipation in differential equations, their application as general-purpose optimisation tools has lacked a comprehensive theoretical framework—until now.

The Discrete Gradient Framework

The discrete gradient method is an implicit iterative scheme defined by: $$x^{k+1} = x^k - au_k \overline{\nabla}V(x^k, x^{k+1})$$ where $\tau_k > 0$ is the step size and $\overline{\nabla}V$ is a discrete gradient. To qualify as a discrete gradient, the operator must satisfy the mean value property: $$V(y) - V(x) = \langle \overline{\nabla}V(x, y), y - x \rangle$$ and a consistency condition where $\overline{\nabla}V(x, x) = \nabla V(x)$. This structure ensures that the objective function $V(x)$ decreases at every iteration, regardless of the step size $\tau$, a property known as unconditional stability.

Discrete Gradient Variants

The paper analyses four primary discrete gradients:

  1. Gonzalez Discrete Gradient: A first-order method that requires gradient information.
  2. Mean Value Discrete Gradient: Defined by the integral of the gradient along the segment connecting $x$ and $y$.
  3. Itoh–Abe Discrete Gradient: A derivative-free method that uses coordinate-wise difference quotients. This is particularly valuable for "black-box" optimisation where gradients are unavailable.
  4. Randomised Itoh–Abe Method: An extension that applies the Itoh–Abe logic along random directions rather than fixed coordinates.

Theoretical Contributions

Well-Posedness and Solvability

A significant hurdle for implicit methods is ensuring that the update equation actually has a solution. Using Brouwer’s fixed-point theorem, we prove that a solution for $x^{k+1}$ exists for any positive time step $\tau > 0$. Furthermore, we propose a Relaxed Fixed Point Method to solve the implicit update efficiently, proving its convergence to a unique solution under mild conditions.

Convergence Rates

We establish rigorous convergence bounds that place discrete gradient methods on par with, or ahead of, standard first-order methods:

  • Convex Functions: We prove an $O(1/k)$ convergence rate.
  • PL-type Functions: For functions satisfying the Polyak–Lojasiewicz inequality (a generalization of strong convexity that includes some nonconvex functions), we prove linear convergence.
  • Coordinate Descent Comparison: For the Itoh–Abe method, our proven convergence rates are stronger than existing theoretical bounds for standard cyclic coordinate descent.

Numerical Experiments and Robustness

The methods were evaluated across several challenging scenarios:

  • Stiff Linear Systems: Testing sensitivity to ill-conditioning in high-dimensional spaces ($n=500$).
  • Logistic Regression: Applying $l_2$-regularized problems to synthetic data.
  • Nonconvex Optimization: Validating linear convergence on functions satisfying the PL inequality.
  • Image Denoising: Using Total Variation (TV) denoising on MRI imagery.

The results confirm that discrete gradient methods are remarkably resilient to stiffness. In TV denoising, where gradients change abruptly and explicit methods often struggle or require manual step-size tuning, the discrete gradient method maintains steady, stable convergence.

Discussion and Future Directions

While the discrete gradient method offers superior stability and robustness, it introduces a higher computational cost per iteration due to its implicit nature. However, the ability to take much larger steps without risking divergence often offsets this cost in stiff or ill-conditioned problems.

Future research will focus on:

  • Acceleration: Incorporating Nesterov-style momentum to achieve $O(1/k^2)$ convergence.
  • Inexact Updates: Quantifying how the convergence rate is affected when the implicit equation is solved only approximately.
  • Non-Euclidean Geometry: Extending the framework to manifold-constrained optimization and Bregman distances.

Conclusion

By providing the first thorough analysis of well-posedness and convergence rates for the discrete gradient method, this work establishes a solid foundation for a new class of optimization algorithms. These methods offer a mathematically principled alternative to standard gradient descent, particularly for complex, stiff, or derivative-free optimization tasks.

Summary updated

Abstract

Discrete gradient methods are geometric integration techniques that can preserve the dissipative structure of gradient flows. Due to the monotonic decay of the function values, they are well suited for general convex and nonconvex optimisation problems. Both zero- and first-order algorithms can be derived from the discrete gradient method by selecting different discrete gradients. In this paper, we present a thorough analysis of the discrete gradient method for optimisation which provides a solid theoretical foundation. We show that the discrete gradient method is well-posed by proving the existence of iterates for any positive time step, as well as uniqueness in some cases, and propose an efficient method for solving the associated discrete gradient equation. Moreover, we establish an $O(1/k)$ convergence rate for convex objectives and prove linear convergence if instead the Polyak-Lojasiewicz inequality is satisfied. The analysis is carried out for three discrete gradients-the Gonzalez discrete gradient, the mean value discrete gradient, and the Itoh-Abe discrete gradient, as well as for a randomised Itoh-Abe method. Our theoretical results are illustrated with a variety of numerical experiments, and we furthermore demonstrate that the methods are robust with respect to stiffness.
BibTeX
@inproceedings{ehrhardt2024geometric,
  author = {Matthias J. Ehrhardt and Erlend S. Riis and Torbjørn Ringholm and Carola‐Bibiane Schönlieb},
  title = {{A geometric integration approach to smooth optimisation: Foundations of the discrete gradient method}},
  booktitle = {IMA},
  year = {2024},
  doi = {10.1093/imanum/drae037},
}
Figure