大步长自适应梯度下降让逻辑回归快速收敛到最优解。
Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes
- 用随风险自适应的大步长进行梯度下降
- 烧结后风险指数级下降，仅需1/γ²步
- 适合追求最优收敛速度的理论研究者
我们研究在可线性分离数据上，对逻辑回归使用自适应步长的梯度下降（GD），步长由常数超参数η缩放。我们证明，在最多1/γ²次预热步骤后，GD的风险上界为exp(−Θ(η))，其中γ是数据集的间隔。由于η可任意大，GD在预热后能立即达到任意小的风险，尽管风险演化可能非单调。我们进一步构造了间隔为γ的困难数据集，表明任何批量或在线一阶方法至少需要Ω(1/γ²)步才能找到线性分类器。因此，采用大且自适应步长的GD在所有一阶批量方法中具有最小最大最优性。值得注意的是，经典感知机（Novikoff, 1962）作为一阶在线方法，也达到了1/γ²的步复杂度，甚至在常数上与GD匹配。最后，我们的GD分析可推广至一大类损失函数及某些两层网络。
原文摘要 · Abstract (English)
We study $\textit{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/γ^2$ 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 $\textit{immediately after the burn-in steps}$, though the risk evolution may be $\textit{non-monotonic}$. We further construct hard datasets with margin $γ$, where any batch (or online) first-order method requires $Ω(1/γ^2)$ steps to find a linear separator. Thus, GD with large, adaptive stepsizes is $\textit{minimax optimal}$ among first-order batch methods. Notably, the classical $\textit{Perceptron}$ (Novikoff, 1962), a first-order online method, also achieves a step complexity of $1/γ^2$, matching GD even in constants. Finally, our GD analysis extends to a broad class of loss functions and certain two-layer networks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。