在二维数据下，大步长梯度下降可更快收敛到低损失点。
Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension
- 通过精细分析正交子空间的振荡行为，优化大步长下的收敛过程。
- 证明在 $T \geq \Omega(n/\gamma + 1/\gamma^2)$ 时损失小于 $\mathcal{O}(1/(\eta\gamma^2 T))$。
- 适用于理解低维分类中梯度下降的非单调性与加速机制。
研究在可分数据条件下，用梯度下降最小化逻辑损失以训练线性二分类模型的问题。已有研究表明，在 $T$ 次迭代预算下，采用 $\eta = \Theta(\gamma^2 T)$ 的大步长可实现 $1/T^2$ 的加速收敛率，尽管损失轨迹非单调。本文针对二维数据给出更紧的分析：当步长 $\eta$ 足够大且 $T \geq \Omega(n/\gamma + 1/\gamma^2)$ 时，梯度下降可找到损失低于 $\mathcal{O}(1/(\eta\gamma^2 T))$ 的点。该改进源于对梯度下降从不稳定（非单调）过渡到稳定（单调）所需时间 $\tau$ 的更精确刻画，基于对垂直于最大间隔分类器方向的振荡动态的细粒度分析。同时，我们给出了与上界仅差对数因子的 $\tau$ 下界，表明分析是紧的。
原文摘要 · Abstract (English)
We consider the optimization problem of minimizing the logistic loss with gradient descent to train a linear model for binary classification with separable data. With a budget of $T$ iterations, it was recently shown that an accelerated $1/T^2$ rate is possible by choosing a large stepsize $η= Θ(γ^2 T)$ (where $γ$ is the dataset's margin) despite the resulting non-monotonicity of the loss. In this paper, we provide a tighter analysis of gradient descent for this problem when the data is two-dimensional: we show that GD with a sufficiently large learning rate $η$ finds a point with loss smaller than $\mathcal{O}(1/(ηγ^2 T))$, as long as $T \geq Ω(n/γ+ 1/γ^2)$, where $n$ is the dataset size. Our improved rate comes from a tighter bound on the time $τ$ that it takes for GD to transition from unstable (non-monotonic loss) to stable (monotonic loss), via a fine-grained analysis of the oscillatory dynamics of GD in the subspace orthogonal to the max-margin classifier. We also provide a lower bound of $τ$ matching our upper bound up to logarithmic factors, showing that our analysis is tight.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。