Gradient Descent Converges Linearly for Logistic Regression on Separable Data

2023/06/26 by Kyriakos Axiotis, Axiotis, Kyriakos, Maxim Sviridenko +1 · 3 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2306.14381

openalex publication_date 2023/06/26 · openalex created_date 2023/06/28 · openalex updated_date 2026/07/28

Abstract

We show that running gradient descent with variable learning rate guarantees loss f(x) ≤ 1.1 ⋅ f(x^*) + ε for the logistic regression objective, where the error ε decays exponentially with the number of iterations and polynomially with the magnitude of the entries of an arbitrary fixed solution x^*. This is in contrast to the common intuition that the absence of strong convexity precludes linear convergence of first-order methods, and highlights the importance of variable learning rates for gradient descent. We also apply our ideas to sparse logistic regression, where they lead to an exponential improvement of the sparsity-error tradeoff.

Cited by

• Gradient-Normalized Smoothness for Optimization with Approximate Hessians
• AutoSGD: Automatic Learning Rate Selection for Stochastic Gradient Descent
• Adaptively Point-weighting Curriculum Learning

Related

• The Implicit Bias of Gradient Descent on Separable Data
• Risk and parameter convergence of logistic regression
• Convergence of Gradient Descent on Separable Data
• Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability
• Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency