Research map / Optimization / Nonconvex and smooth optimization

Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Coordinate and Adam convergence analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that gradient descent on logistic loss with Gaussian design converges linearly to an O(sqrt(||θ*||^5 d/n)) neighborhood of θ*, with a faster large-stepsize local variant, and proposes a direction-norm sample-split estimator with sharper high-dimensional rate.

Problem

Finite-sample estimation error and convergence behavior of gradient descent on the logistic loss under Gaussian design, where prior results lacked non-asymptotic estimation rates and had slow parameter convergence; also whether MLE's rate in ||θ*|| is optimal.

Approach

Establishes an approximate invertibility condition (AIC) for the logistic gradient, uniformly controlling the deviation of the empirical gradient from the population gradient via covering and peeling, and shows population GD is a contraction via eigenvalue analysis of the population Hessian; also separates direction (via a ReLU-loss-based estimator) and norm (via averaged y_i x_i) estimation for a

Key results

• Small-stepsize GD (eta in [0.1,7.9]) linearly converges to an l2 error neighborhood of order O(sqrt(||θ*||^5 d/n)) with contraction 1-c/||θ*||^3.
• Large-stepsize GD with eta ~ 1/m(||θ*||) achieves local contraction 1-c/||θ*||^2 with the same statistical error.
• Proposed direction-plus-norm estimator achieves rate polylog(n)(||θ*||^3/sqrt(n)+sqrt(||θ*||d/n)+||θ*||^2 d/n), nearly tight at sqrt(||θ*||d/n) when n ≳ ||θ*||^3 d + ||θ*||^5.

Surprising findings

• The MLE rate sqrt(||θ*||^3 d/n) is shown to be sub-optimal in ||θ*|| dependence in high dimensions.
• Large stepsize GD (eta ~ ||θ*||) gives faster local convergence while being non-separable data regime.

Limitations

• Results rely on Gaussian design; extension to sub-Gaussian covariates is highly challenging.
• Sample complexity requires n ≳ ||θ*||^6 d log n, and the large-stepsize result needs an accurate initialization.
• Optimality of the rate is established only in the regime n ≳ ||θ*||^3 d + ||θ*||^5; the general minimax rate remains open.

Experimental setup

Datasets: synthetic Gaussian design logistic regression data

Metrics: l2 estimation error linear convergence rate

Baselines: MLE GD with logistic loss (bounded design analysis) GLM-tron Direction estimator of prior work

Builds on: GLM-tron MLE finite-sample analysis (Chardon et al.) Stein's identity

Closest papers by meaning

• Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes (ICML 2025 · similarity 0.90)
• Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression (NeurIPS 2025 · similarity 0.88)
• Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression (ICLR 2025 · similarity 0.87)
• From Logistic Regression to the Perceptron Algorithm: Exploring Gradient Descent with Large Step Sizes (AAAI 2025 · similarity 0.87)
• Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression (ICML 2025 · similarity 0.87)
• Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability (ICML 2025 · similarity 0.86)