Research map / Optimization / Implicit bias and generalization
Any-stepsize Gradient Descent for Separable Data under Fenchel–Young Losses
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 gradient descent with arbitrary constant stepsize converges on linearly separable data under Fenchel–Young losses without the self-bounding property, via a perceptron-style argument, with faster rates (Tsallis-2 ε^-1/2, Rényi-2 ε^-1/3) when the loss has separation margin.
Problem
Understanding why gradient descent with large (edge-of-stability) stepsizes still attains arbitrarily small loss, and which loss-function property (e.g., self-bounding) is needed for this convergence.
Approach
Analyze GD for binary Fenchel–Young losses via a perceptron argument (lower-bounding parameter alignment with the separator and upper-bounding the norm via split optimization) rather than the descent lemma; convergence rate exponent is determined by the potential's order parameter alpha, and separation margin bounds the parameter norm, giving faster rates.
Key results
- Under Fenchel–Young losses with separation margin, GD with arbitrary stepsize reaches epsilon-optimal loss in T=Omega(epsilon^-1/2) steps for Tsallis q>2 and T=Omega(epsilon^-1/3) for Rényi q=2.
- Losses without self-bounding property (e.g., Tsallis q>1) also converge with large stepsize, e.g., eta=2^4 in the pilot study, showing self-bounding is not necessary.
- Stated rate for Shannon/logistic loss is T~Omega(epsilon^-1) for arbitrary stepsize, matching standard stable-regime GD rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Tsallis q-loss with q>1 instead of the Shannon (logistic) loss | Gradient descent for a linear classifier · Linearly separable binary classification | iteration complexity: T=\widetilde\Omega(\varepsilon^{-1}); T=\Omega(\varepsilon^{-1/q}) for q\in(1,2); T=\Omega(\varepsilon^{-1/2}) for 2\le | Helped |
| Use Rényi 2-loss instead of the Shannon (logistic) loss | Gradient descent for a linear classifier · Linearly separable binary classification | iteration complexity: T=\widetilde\Omega(\varepsilon^{-1}); T=\Omega(\varepsilon^{-1/3}) | Helped |
| Use semi-circle loss instead of the classical convex-smooth GD setting | Gradient descent for a linear classifier · Linearly separable binary classification | iteration complexity: T=\Omega(\varepsilon^{-1}); T=\Omega(\varepsilon^{-4}) | Hurt |
| Use arbitrary constant stepsize under the stated Fenchel–Young loss and separability assumptions | Gradient descent for a linear classifier · Linearly separable binary classification | convergence to arbitrarily small loss | Helped |
| Use a loss with separation margin rather than one without separation margin | Gradient descent for a linear classifier · Linearly separable binary classification | iteration complexity | Helped |
Surprising findings
- The Rényi-2 entropy loss gives a rate of epsilon^-1/3, a 'leap' in order from epsilon^-1/q as q approaches 2, better than Shannon/logistic.
- Losses lacking self-bounding property (Tsallis q>1) can converge under large stepsize, contrary to the belief that self-bounding is essential.
Limitations
- Analysis restricted to linear models and linearly separable data with a dataset-dependent margin gamma.
- Rate has an extra factor n from worst-case analysis; the authors conjecture it is not essential.
- Finite-time convergence for twice-differentiable losses without separation margin is left open.
Experimental setup
Datasets: toy four-point linearly separable dataset
Metrics: iteration complexity T as a function of epsilon empirical loss and parameter norm trajectories
Baselines: logistic loss GD perceptron Wu et al. 2024 large-stepsize logistic regression
Builds on: Wu et al. large-stepsize GD logistic regression Fenchel-Young losses perceptron convergence split optimization
Closest papers by meaning
- Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes (ICML 2025 · similarity 0.90)
- Convergence Rates for Gradient Descent on the Edge of Stability for Overparametrised Least Squares (NeurIPS 2025 · similarity 0.88)
- Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression (NeurIPS 2025 · similarity 0.88)
- Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability (ICML 2025 · similarity 0.88)
- On the Unstable Convergence Regime of Gradient Descent (AAAI 2024 · similarity 0.88)
- Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification (NeurIPS 2025 · similarity 0.87)
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.