可分数据下的逻辑回归梯度下降收敛速率

Jun, 2023

Gradient Descent Converges Linearly for Logistic Regression on Separable Data

Kyriakos Axiotis, Maxim Sviridenko

TL;DR本文证明了在使用可变学习率运行梯度下降时，对于逻辑回归目标函数，损失 f(x) ≤ 1.1·f(x*) + ε，其中误差 ε 按迭代次数指数下降，并按任意固定解决方案 x* 条目大小的多项式下降。该文还将这些思想应用于稀疏逻辑回归，在那里它们导致了稀疏误差交换的指数改进。

Abstract

We show that running gradient descent with variable learning rate guarantees loss $f(x) \leq 1.1 \cdot f(x^*) + \epsilon$ for the logistic regres