In a new paper from DeepMind and the University of Oxford, researchers Brendan O’Donoghue and Chris J. Maddison bridge the gap between classical mechanics and convex optimization. By treating the "duality gap" of an optimization problem as the "energy" of a physical system, they derive a new class of algorithms that are remarkably robust to poorly conditioned data.
The Challenge of Conditioning and Composite Objectives
Most first-order optimization methods, like Gradient Descent (GD), are highly sensitive to the "conditioning" of a problem. If an optimization landscape resembles a long, narrow, winding canyon rather than a neat circular bowl, gradient descent tends to bounce back and forth between the walls, making agonizingly slow progress toward the minimum.
While researchers have recently used ordinary differential equations (ODEs) to model and understand optimization, most of these continuous-time models do not naturally handle composite objectives—problems where the goal is to minimize the sum of two different functions, such as a data-fitting term combined with a regularization term. This paper seeks a principled, physical way to design algorithms for these composite problems that remain agnostic to the "shape" or scaling of the data.
Hamiltonian Mechanics as an Optimization Framework
To solve this, the authors look to Hamiltonian mechanics, a formulation of classical mechanics that describes how systems evolve over time while conserving total energy.
The core insight of the paper is identifying the duality gap—a measure of how far a point is from the optimum in optimization—as the "energy" of their physical system. In this framework, the "potential energy" corresponds to one part of the objective function, and the "kinetic energy" corresponds to the other (the dual).
In a standard physical system, energy is conserved, meaning a pendulum would swing forever. To transform this into an optimizer that settles at a minimum, the authors introduce forced dissipation. They add a "contractive term" to the equations of motion, forcing the energy (the duality gap) to leak out at a constant linear rate.
This formulation results in a continuous-time ODE whose solutions are mathematically proven to converge to the optimal point at a linear (geometric) rate. Furthermore, the continuous version of Hamiltonian descent is perfectly affine-invariant. This means if you stretch, rotate, or rescale your data, the path the optimizer takes remains identical—a highly desirable property that standard gradient descent lacks.
To implement this on a computer, the continuous ODE must be discretized into steps. The authors demonstrate that different ways of "stepping" through this physical flow lead to different algorithms. Remarkably, they show that widely used algorithms like the Alternating Direction Method of Multipliers (ADMM) and Primal-Dual Hybrid Gradient (PDHG) are actually specific discretizations of this Hamiltonian flow, providing a unified physical explanation for why these methods work so well in practice.
Experimental Results: Robustness and Speed
The paper evaluates this approach on synthetic regularized least-squares problems designed with varying condition numbers (from $10^3$ to $10^{14}$) and Elastic Net Regularized Logistic Regression.
The results highlight a stark contrast in robustness. As the least-squares problem became more "difficult" (higher condition number), Gradient Descent slowed down significantly. In contrast, the Hamiltonian Descent (HD) traces were completely unaffected.
On a poorly conditioned logistic regression problem, Hamiltonian Descent reached a primal objective error of $10^{-10}$ in the same number of iterations it took Gradient Descent to reach only $10^{-2}$. The empirical results perfectly mirror the theoretical guarantee: the Hamiltonian (the duality gap) converges to zero linearly, regardless of the specific properties of the convex functions.
Limitations and Future Directions
While the theoretical properties of Hamiltonian Descent are striking, practical challenges remain:
- Discretization Loss: The continuous ODE is perfectly affine-invariant, but the discrete algorithms run on computers lose some of this property. Finding a discretization scheme that perfectly preserves invariance is an open challenge.
- Step-Size Sensitivity: The current convergence analysis for the discrete version requires step sizes that depend on the smoothness ($L$) and strong convexity ($\mu$) of the functions. The authors suspect a tighter analysis is possible that better reflects the algorithm's empirical robustness.
- Scaling to Deep Learning: The paper focuses strictly on convex problems. Extending these Hamiltonian "energy-leaking" concepts to the highly non-convex landscapes of deep neural networks represents a promising, unexplored frontier.
Summary updated