In the standard toolkit of optimization theory, we usually stop at the second derivative. We assume a function is "smooth" if its gradient doesn't change too quickly (Lipschitz gradients) or if its curvature is somewhat stable (Lipschitz Hessians). However, a growing body of research suggests that by looking one level deeper—at the third-order smoothness—we can unlock significantly faster convergence rates and explain why certain algorithms work better in practice than classical theory predicts.
Third-order smoothness is essentially the "curvature of the curvature." It measures how quickly the Hessian matrix changes as we move through the parameter space. When this rate of change is bounded, the local landscape becomes highly predictable, allowing algorithms to take bolder steps with higher confidence.
Escaping Saddle Points with Confidence
In non-convex optimization, the primary challenge isn't just finding a slope; it's escaping saddle points where the gradient vanishes but we haven't reached a minimum. Standard methods use "negative curvature" to slide away from these points.
As Pan Xu and Quanquan Gu demonstrate in Third-order Smoothness Helps: Faster Stochastic Optimization Algorithms for Finding Local Minima, knowing the third derivative is bounded allows an optimizer to take much larger steps along these negative directions. If the Hessian changes slowly, the direction that leads "downhill" from a saddle point remains valid for a longer distance. Their algorithm, FLASH, improves the theoretical complexity of finding local minima from $\tilde{O}(\epsilon^{-7/2})$ to $\tilde{O}(\epsilon^{-10/3})$ by exploiting this stability. Similarly, Dongruo Zhou and colleagues show in Finding Local Minima via Stochastic Nested Variance Reduction that this "Hessian-free" escape becomes significantly more efficient when the Hessian itself is Lipschitz continuous.
Why Federated Learning Works Better Than Expected
Federated Learning (or Local SGD) involves multiple machines performing local updates before synchronizing. A major theoretical mystery has been "iterate bias"—the tendency for local models to drift apart because they are optimizing slightly different local landscapes.
Recent work by Honglin Yuan and Tengyu Ma in Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective reveals that third-order smoothness is the "missing link" in explaining FedAvg's success. When the rate of change of the Hessian is bounded, the local curvature across different machines remains relatively aligned. This stability reduces the bias introduced by local updates, allowing for much faster convergence than standard second-order analysis would suggest. This insight led to the development of FEDAC (Federated Accelerated Stochastic Gradient Descent), which achieves a linear speedup with far fewer communication rounds by balancing momentum with this curvature stability.
Closing the Gap in Zeroth-Order Optimization
Zeroth-order (derivative-free) optimization is often seen as a "slow" cousin to gradient-based methods because it must estimate gradients from noisy function values. However, Francis Bach and Vianney Perchet proved in Highly-Smooth Zero-th Order Online Optimization that this performance gap is not inherent—it is a function of smoothness.
For "highly smooth" functions (those with many bounded derivatives), zeroth-order methods can actually match the convergence rates of first-order algorithms. The intuition is that if a function is extremely regular, a few function evaluations can provide an incredibly accurate picture of the local gradient and Hessian. Baihe Huang and Jason D. Lee recently established tight minimax bounds for this setting in Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian, showing that a Lipschitz Hessian allows these methods to surpass the limits of standard smooth optimization.
Simulating High-Order Tensors with Low-Order Oracles
If third-order information is so useful, why don't we use it everywhere? The bottleneck is usually the computational cost of calculating and storing third-order tensors (3D arrays of derivatives).
Alexander Gasnikov addresses this in Near-Optimal Hyperfast Second-Order Method. He demonstrates that for functions with Lipschitz third derivatives, it is possible to achieve "hyperfast" convergence rates (like $O(N^{-5})$) using only second-order oracles (Hessians). By cleverly solving third-order subproblems inexactly using Hessian information, these methods bypass the need for direct tensor computation while still reaping the theoretical benefits of higher-order smoothness.
The Limits of Smoothness
While higher-order regularity provides a powerful lever for acceleration, it is not a panacea. Yair Carmon and John Duchi have explored the fundamental "speed limits" of these approaches. In Lower bounds for finding stationary points II: first-order methods, they show that for first-order methods, the benefits of additional smoothness eventually plateau. There is a point where a gradient-based algorithm simply cannot "see" the extra regularity of the function, regardless of how many derivatives are bounded.
Furthermore, as Arya Akhavan and Massimiliano Pontil note in Exploiting Higher Order Smoothness in Derivative-free Optimization, these gains are often contingent on the function having sufficient underlying curvature (strong convexity). Without that base structure, increasing the smoothness of a function may fail to provide any practical speedup.