New proof shows gradient descent hits near-optimal error in logistic regression

Junren Chen and Arya Mazumdar have derived the first finite-sample performance bounds for gradient descent (GD) under the logistic regression model with isotropic Gaussian features. Their key innovation is an “approximate invertibility condition” (AIC) on the gradient of the logistic loss, which they establish using uniform concentration and covering arguments. Under small constant stepsize and zero initialization, GD converges linearly to a small neighborhood around the true parameter, achieving an ℓ2 error rate of O(√(‖θ*‖⁵ d/n)). This is a dramatic improvement over prior work that only provided asymptotic rates or much slower parameter convergence.

For the case of a larger Θ(‖θ*‖) stepsize, the authors prove even faster local linear convergence to the same statistical error. Building on recent work by Matsumoto and Mazumdar (2025), they also present an efficient estimator that attains the sharper rate O(√(‖θ*‖ d/n)) in high dimensions—matching information-theoretic lower bounds across many regimes. Numerical simulations confirm the theoretical findings. This work bridges the gap between optimization theory and statistical inference, offering precise, non-asymptotic guarantees for one of the most widely used classification algorithms.