Randomization Beats Gradient Descent in the Plane

Abstract

We study the number of exact gradient queries required to find an ε-stationary point of an L-smooth, bounded-below function f: ℝ² → ℝ when function values are unavailable. If f(x₀) − inf f ≤ Δ and q = √(ΔL)/ε, gradient descent uses O(q²) queries. We give a randomized gradient-only algorithm that returns a queried point X with ‖∇f(X)‖ ≤ ε with probability at least 1 − ρ after O(q^(4/3) log^(1/3)(2/ρ)) queries. The argument has one central device: a single stratified line integral estimates every relative function value used on a planar cut. A maximal-prefix inequality avoids a union cost over the marked points, and a robust gradient-flow trap absorbs the remaining comparison error across geometrically shrinking scales. We also determine, up to universal constants, the complete accuracy–confidence law for the underlying Lipschitz integration problem; in particular, its 2/3 accuracy exponent is unimprovable even for one endpoint. Finally, the exact gradient at the output certifies success. Independent restarts therefore give a Las Vegas algorithm with zero error and expected O(q^(4/3)) queries. The optimal planar exponent remains between 1 and 4/3.