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:
- Gonzalez Discrete Gradient: A first-order method that requires gradient information.
- Mean Value Discrete Gradient: Defined by the integral of the gradient along the segment connecting $x$ and $y$.
- 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.
- 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