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

Junren Chen; Arya Mazumdar

stat.MLJun 19, 2026

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

Authors: Junren Chen, Arya Mazumdar

Abstract

We consider the parameter estimation problem in logistic regression with Gaussian design: the estimation of a fixed unknown parameter $θ^*\in \mathbb{R}^d$ ( $\|θ^*\|_2\ge 1$ ) from $n$ i.i.d. samples $\{(x_i,y_i)\}_{i=1}^n$ , where $x_i\sim N(0,I_d)$ and $y_i|x_i \sim {\rm Bernoulli}(1/(1+\exp(-x_i^\top θ^*)))$ . Our main aim is to characterize the finite-sample estimation performance and convergence behavior of gradient descent (GD) on the maximum likelihood objective (i.e., the logistic loss). Under small $O(1)$ stepsize and $0$ initialization, we show that GD linearly converges to a small neighborhood of $θ^*$ achieving an $\ell_2$ error of order $O(\sqrt{\|θ^*\|_2^5d/n})$ . This substantially goes beyond existing theoretical results that lack non-asymptotic estimation error rate and exhibit much slower parameter convergence. We also establish a faster local linear convergence to the same statistical error under a large $Θ(\|θ^*\|_2)$ stepsize. The main technical component is to show that the gradient of the logistic loss satisfies a certain approximate invertibility condition (AIC). To that end, we uniformly control the deviation of the gradient from its population counterpart by covering and peeling arguments, and then show that the population GD is a contraction by a delicate analysis based on the eigenvalues of population Hessian matrices. Finally, we build upon the recent work Matsumoto and Mazumdar (2025) and devise a novel efficient estimator that attains a sharper rate in high dimensions. This indicates that the existing non-asymptotic guarantees exhibit sub-optimal dependence on $\|θ^*\|_2$ , and that in many regimes $Θ(\sqrt{\|θ^*\|_2d/n})$ is the tight estimation error rate. Numerical examples are provided to corroborate our theoretical results.

Explore similar work

Jun 7, 2024cs.LG

Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes

We study gradient descent (GD) dynamics on logistic regression problems with large, constant step sizes. For linearly-separable data, it is known that GD converges to the minimizer with arbitrarily large step sizes, a property which no longer holds when the problem is not separable. In fact, the behaviour can be much more complex -- a sequence of period-doubling bifurcations begins at the critical step size

2/λ

, where

λ

is the largest eigenvalue of the Hessian at the solution. Using a smaller-than-critical step size guarantees convergence if initialized nearby the solution: but does this suffice globally? In one dimension, we show that a step size less than

1/λ

suffices for global convergence. However, for all step sizes between

1/λ

and the critical step size

2/λ

, one can construct a dataset such that GD converges to a stable cycle. In higher dimensions, this is actually possible even for step sizes less than

1/λ

. Our results show that although local convergence is guaranteed for all step sizes less than the critical step size, global convergence is not, and GD may instead converge to a cycle depending on the initialization.

Si Yi Meng, Antonio Orvieto, Daniel Yiming Cao +1

Large Step Sizes Gradient Descent Bifurcation Separability Logistic Regression Largest Eigenvalue

Ask PDF

Aug 3, 2026math.ST

Beyond Modern Asymptotics for Log-Likelihood Ratios in Logistic Regression

We characterize the finite sample behavior of the log-likelihood ratio statistic in binary logistic regression, uniformly over both the design and the target parameter. For

n\geq d\geq 3

, we determine, up to universal constants, its worst case

(1-δ)

quantile over all fixed collections of design vectors and all target parameters:

d\log\left(\frac{e n}{d}\right)+\log\left(\frac{1}δ\right).

This is a nonasymptotic analogue of the Wilks

χ^2_d

phenomenon and requires no regularity assumptions on the design. The low dimensional cases exhibit unusual behavior. The worst case quantile in dimension

d=2

is sharply of order

\log\log\log n+\log\left(\frac{1}δ\right).

The worst case quantile in dimension

d=1

is of order

\log(1/δ)

, with no dependence on

n

. Finally, i.i.d. Gaussian design vectors recover the classical Wilks scale. In the regime

n\gtrsim d+\log(1/δ)

, we prove the sharp bound

d+\log\left(\frac{1}δ\right).

Unlike existing asymptotic results, our bounds are uniform over the target parameter, which may depend on

n

d

, and

δ

Hugo Chardon, Reese Pathak, Nikita Zhivotovskiy

Finite-Sample Asymptotics Likelihood Logistic Regression 3D Gaussian Splatting

Ask PDF

Date pendingcs.LG

Generalization Guarantees on Data-Driven Tuning of Gradient Descent with Langevin Updates

We study learning to learn through the lens of hyperparameter tuning. We propose the Langevin Gradient Descent Algorithm (LGD), which approximates the mean of the posterior distribution defined by the loss function and regularizer of a regression task with convex objective. For classification tasks, the LGD algorithm estimates the posterior probabilities of each class on the test set. We prove the existence of an optimal hyperparameter configuration for which the LGD algorithm achieves the Bayes' optimal solution for squared loss on regression tasks, and for which LGD closely approximates the posterior probabilities for well-specified classification tasks. Subsequently, we study generalization guarantees on meta learning optimal hyperparameters for the LGD algorithm from a given set of tasks in the data-driven setting. For a number of parameters

d

and hyperparameter dimension

h

, we show a pseudo-dimension bound of

O(dh)

, up to logarithmic terms under mild assumptions on LGD. This matches the dependence of the bounds on number of parameters obtained in prior work for linear regression using the elastic net, which only allows for

h=2

hyperparameters, and extends their bounds to regression on convex loss. Compared to bounds on regularized logistic regression that allow for only

h=1

hyperparameter, our bounds improve greatly on the dependence on samples per task at the cost of worse dependence on the number of parameters by accounting for hardware-aware procedures. Finally, we show empirical evidence of the success of LGD and the meta learning procedure for few-shot learning on linear and logistic regression using synthetically created datasets.

Saumya Goyal, Rohith Rongali, Ritabrata Ray +1

Gradient Descent Hyperparameter Optimization Empirical Risk Minimization Lasso Regularization Techniques Langevin Dynamics

Ask PDF