Skip to main content
Back

UCLA Closes a Years-Long Math Gap With ChatGPT's Help

A new paper closes a years-long gap in optimization theory, proving that certain accelerated gradient methods are provably optimal — with an AI-assisted proof construction

Paper, Full Access
  • A new paper by Dongruo Zhou closes a years-long open problem in optimization theory by proving tight lower bounds for first-order methods under higher-order smoothness.
  • The Ω(ε⁻⁷/⁴) lower bound for Hessian-Lipschitz functions and Ω(ε⁻⁵/³) for third-order-smooth functions now exactly match the best known upper bounds.
  • The core construction uses a novel "block-chain mechanism" that enforces blockwise information revelation while preserving smoothness structure.
  • The lower-bound construction was discovered with the assistance of ChatGPT 5.5 Pro and subsequently verified by the authors — a notable example of AI-assisted mathematical proof discovery.
  • The bounds are dimension-free and valid for every finite smoothness order, completing the complexity picture for the full smoothness hierarchy.
  • No code is released; this is a pure theory result confirming that existing accelerated gradient methods are provably optimal under these assumptions.

For anyone training large models or designing optimization algorithms, a fundamental question lurks in the background: how fast can you possibly go? Complexity theory gives us lower bounds , mathematical certificates that say no algorithm, no matter how clever, can do better than X. For nonconvex optimization, these bounds have been partially open for years. A new paper by Dongruo Zhou at UCLA now closes that gap, proving sharp lower bounds that exactly match the best known upper bounds under higher-order smoothness assumptions. And in a notable twist, the core construction was discovered with the help of ChatGPT.

The open problem that's been nagging theorists

In nonconvex optimization, the goal is to find an ε-stationary point , a point where the gradient norm is at most ε, meaning you're near a local flat region. For smooth functions, gradient descent finds such a point in O(ε⁻²) gradient evaluations, which matches known lower bounds. That rate is tight. You cannot do better if you only know the gradient is Lipschitz.

But what if the function is extra smooth? In practice, many loss landscapes satisfy stronger conditions: their Hessians (second derivatives) or even third derivatives are also Lipschitz continuous. Researchers have known for years that you can exploit this. Carmon, Duchi, Hinder, and Sidford presented an accelerated gradient method for nonconvex problems with Lipschitz first and second derivatives that finds an ε-stationary point in O(ε⁻⁷/⁴ log(1/ε)) time , and crucially, the method is Hessian-free, meaning it only requires gradient computations. More recently, an O(ε⁻⁵/³ log(1/ε)) complexity was established using the nonconvex AGD algorithm under Lipschitz third derivatives.

These are impressive upper bounds. But upper bounds alone don't tell you whether an algorithm is optimal. For that, you need a matching lower bound , a proof that no algorithm can beat that rate. While higher-order smoothness leads to these accelerated upper bounds, the matching lower bounds had remained open. That's the gap this paper closes.

Why lower bounds are hard to prove

Proving a lower bound in optimization means constructing a "hard instance" , a specific function that is provably difficult for any first-order algorithm. The classical technique, going back to Nesterov, uses what's called a