分析梯度下降在逻辑回归中的有限样本表现，给出精确误差界。
Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design
- 用小步长和零初始化，梯度下降线性收敛到真实参数附近。
- 达到的l2误差为O(√(‖θ*‖²⁵d/n))，优于已有理论结果。
- 适用于高维数据下的参数估计，尤其关注非渐近性能。
研究高斯设计下逻辑回归的参数估计问题：从n个独立同分布样本{(x_i,y_i)}中估计固定未知参数θ*∈R^d（‖θ*‖₂≥1），其中x_i∼N(0,I_d)，y_i|x_i∼Bernoulli(1/(1+exp(-x_i^⊤θ*)))。本文重点刻画梯度下降（GD）在最大似然目标函数（即逻辑损失）上的有限样本估计性能与收敛行为。在小步长O(1)且零初始化条件下，证明GD线性收敛至θ*的小邻域，达到l2误差阶为O(√(‖θ*‖²⁵d/n))。该结果显著超越现有理论，后者缺乏非渐近误差率且收敛速度较慢。此外，在大步长Θ(‖θ*‖₂)下，建立更快的局部线性收敛至相同统计误差。核心技术在于证明逻辑损失梯度满足某种近似可逆性条件（AIC）。通过覆盖与剥削论证统一控制梯度与其总体对应的偏差，并基于总体Hessian矩阵的特征值进行精细分析，证明总体梯度下降为压缩映射。最后，借鉴最近工作Matsumoto and Mazumdar (2025)，提出一种新高效估计器，在高维情形下实现更优速率。这表明现有非渐近保证对‖θ*‖₂的依赖次优，许多情形下Θ(√(‖θ*‖₂d/n))才是紧致误差率。数值实验验证了理论结果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。