Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes

2025/04/05 by Ruiqi Zhang, Zhang, Ruiqi, Jingfeng Wu +5 · 1 citation
Computer Science · Mathematics · #Stochastic Gradient Optimization Techniques #Privacy-Preserving Technologies in Data #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2504.04105

Abstract

We study gradient descent (GD) for logistic regression on linearly separable data with stepsizes that adapt to the current risk, scaled by a constant hyperparameter η. We show that after at most 1/γ² burn-in steps, GD achieves a risk upper bounded by exp(-Θ(η)), where γ is the margin of the dataset. As η can be arbitrarily large, GD attains an arbitrarily small risk immediately after the burn-in steps, though the risk evolution may be non-monotonic. We further construct hard datasets with margin γ, where any batch (or online) first-order method requires Ω(1/γ²) steps to find a linear separator. Thus, GD with large, adaptive stepsizes is minimax optimal among first-order batch methods. Notably, the classical Perceptron (Novikoff, 1962), a first-order online method, also achieves a step complexity of 1/γ², matching GD even in constants. Finally, our GD analysis extends to a broad class of loss functions and certain two-layer networks.

Cited by

• Gradient Descent with Provably Tuned Learning-rate Schedules

Related

• Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes
• Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency
• Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression
• Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes
• Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?