Davis and Drusvyatskiy's Algorithm Beats Gradient Descent 4x on Quartic Loss Problems
A new Lyapunov-based proof replaces an intricate manifold argument, yielding a simpler adaptive gradient-Polyak hybrid that converges 2 to 5x faster in benchmarks.
PRO- New paper gives a short Lyapunov proof of nearly-linear convergence for adaptive gradient descent under fourth-order growth and convexity.
- The proof replaces the earlier ravine-manifold argument with a direct contraction of the squared projected gradient.
- Convexity kills a cubic Taylor term that made the general case geometrically messy.
- The algorithm switches from gradient to Polyak steps when R(x) = f(x)/||∇f(x)||^(4/3) exceeds a threshold.
- Beats tuned GDPolyak by 2-4x on Rosenbrock, quadratic sensing, and single-neuron benchmarks.
- Practical target: rank-overparameterized matrix sensing and overparameterized shallow network training.
Gradient descent has a well-known blind spot. When a loss function grows only like a fourth power of the distance to its minimum rather than a quadratic, constant-stepsize gradient descent slows to a crawl and converges only sublinearly. That regime is not a mathematical curiosity: it is exactly what happens in rank-overparameterized matrix sensing, matrix factorization, and overparameterized single-neuron training, where the Hessian at the optimum is singular in some directions.
A prior result from Davis, Drusvyatskiy, and Jiang showed you can recover a nearly-linear rate by adaptively switching between gradient steps and Polyak steps, but the proof was notoriously intricate. A new paper by Damek Davis and Dmitriy Drusvyatskiy delivers a much shorter argument under a mild extra assumption, and as a side effect produces a cleaner, more adaptive algorithm that beats the original on every benchmark they tried.
Why fourth-order growth breaks gradient descent
Classical results establish that gradient descent converges linearly for smooth functions satisfying quadratic growth. The story falls apart when the Hessian at the minimizer is singular. In that case the function still curves upward, but only very gently, like a quartic bowl instead of a quadratic one, along the directions in the Hessian's null space.
The geometric picture the earlier proof leaned on is called the ravine: a smooth manifold containing the minimizer along which f behaves like a pure fourth power of the distance. The Hessian splits the space so that along its range f is locally quadratic, while along its null space growth is only quartic. Constant length gradient steps quickly drive the iterates toward the ravine by shrinking the quadratic part of f. Once the iterates sit sufficiently close to the ravine, a single Polyak step contracts the distance to the minimizer. Tracking that manifold explicitly is where the original argument gets ugly, because the ravine can be a curved, nonlinear object even when the function itself is convex.
This story is for Pro members
You've reached the end of the free preview. Upgrade to AlphaSignal Pro to read the full article - and everything else behind the paywall.
Comments
