Research map / Optimization / Implicit bias and generalization
From Logistic Regression to the Perceptron Algorithm: Exploring Gradient Descent with Large Step Sizes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that logistic regression with gradient descent on separable data reduces to a batch perceptron as the step size goes to infinity, argues logistic loss is an unreliable convergence metric, and proposes Normalized LR+GD with an improved iteration bound.
Problem
Understanding why logistic regression with gradient descent solves linearly separable classification with arbitrarily large step sizes, where the logistic loss is non-monotone, and whether its iteration complexity is good.
Approach
As the step size goes to infinity, LR+GD iterates (scaled by the step size) converge to a batch perceptron update, giving a simple explanation for large-step convergence. Because of this, the loss can be high while convergence is fast, so iteration complexity should be measured instead. A normalized variant (LR+GD scaled by an adaptive factor beta_t) removes the linear dependence on n and matches
Key results
- On the constructed worst-case dataset, Normalized LR+GD with step 100 solves the problem in 2 iterations versus 308 for LR+GD with step 100.
- On imbalanced Fashion MNIST, Normalized LR+GD with step 100 needs 311 iterations versus 538 for LR+GD with step 100.
- LR+GD with large step sizes tracks the batch perceptron on CIFAR-10, FashionMNIST, EuroSAT and MNIST subsets, and larger steps give higher loss but faster accuracy 1.0.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Normalize LR+GD using the adaptive factor β_t | LR+GD · Worst-case dataset from theorem | iterations to solve: 308 -> 2 | Helped |
| Normalize LR+GD using the adaptive factor β_t | LR+GD · Imbalanced FashionMNIST | iterations to solve: 538 -> 311 | Helped |
| Normalize LR+GD using the adaptive factor β_t | LR+GD · FashionMNIST | iterations to solve: 2928 -> 3160 | Hurt |
| Increase the step size from 0.1 to 100.0 | Normalized LR+GD · Worst-case dataset from theorem | iterations to solve: 157 -> 2 | Helped |
| Increase the step size from 0.1 to 100.0 | Normalized LR+GD · Imbalanced FashionMNIST | iterations to solve: 504 -> 311 | Helped |
| Increase the step size from 10.0 to 100.0 | LR+GD · FashionMNIST | iterations to solve: 2778 -> 2928 | Hurt |
| Use the normalized batch perceptron update, dividing by |S_t| instead of n | Batch Perceptron · Separable classification | iteration complexity: n R^2/μ^2 -> R^2/μ^2 | Helped |
| Use larger LR+GD step sizes | LR+GD · CIFAR-10, FashionMNIST, EuroSAT, and MNIST | iterations to reach accuracy 1.0 | Helped |
| Use larger LR+GD step sizes | LR+GD · CIFAR-10 and FashionMNIST | logistic loss | Hurt |
| Use the normalized batch perceptron update | Batch Perceptron · Default experimental setup | iterations to reach accuracy 1.0 | Hurt |
| Use the normalized batch perceptron update | Batch Perceptron · Imbalanced data | iterations to reach accuracy 1.0 | Helped |
| Use Normalized LR+GD with step 100.0 instead of LR+GD with step 100.0 | LR+GD · Imbalanced FashionMNIST | iterations to solve: 538 -> 311 | Helped |
Surprising findings
- Higher logistic loss values can accompany faster convergence to a separator with large step sizes.
- Standard batch perceptron converges slightly better than normalized batch perceptron on balanced data despite worse theoretical bounds.
Limitations
- Theory covers only linear models and separable data; extension to neural networks is open.
- Batch perceptron iteration bound scales linearly with n, and the lower bound is for a specific constructed dataset.
- Experiments are limited to 5,000-sample binary subsets of four image datasets.
Experimental setup
Datasets: CIFAR-10 FashionMNIST EuroSAT MNIST
Benchmarks: CIFAR-10 subset FashionMNIST subset EuroSAT subset MNIST subset
Metrics: iterations to accuracy 1.0 logistic loss gradient norm
Baselines: LR+GD Batch Perceptron Perceptron
Builds on: perceptron algorithm edge of stability Soudry et al. implicit bias of gradient descent on logistic regression
Closest papers by meaning
- Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes (ICML 2025 · similarity 0.91)
- Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression (NeurIPS 2025 · similarity 0.89)
- Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization (NeurIPS 2024 · similarity 0.87)
- Any-stepsize Gradient Descent for Separable Data under Fenchel–Young Losses (NeurIPS 2025 · similarity 0.87)
- Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design (NeurIPS 2026 · similarity 0.87)
- Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.