Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension

摘要

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 𝒪(1/(ηγ^2 T)), as long as T ≥Ω(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.