# Any-stepsize Gradient Descent for Separable Data under Fenchel-Young Losses

arXiv: https://arxiv.org/abs/2502.04889 · HTML: https://mlsanity.com/paper/2502.04889/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 70 references that are in the map.
- First posted on arXiv 7 Feb 2025.

## Builds on (most cited first, 30 of 37)

- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016)
- [Mitigating Neural Network Overconfidence with Logit Normalization](https://mlsanity.com/paper/2205.09310/) (2022)
- [The large learning rate phase of deep learning: the catapult mechanism](https://mlsanity.com/paper/2003.02218/) (2020)
- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Sparse Sequence-to-Sequence Models](https://mlsanity.com/paper/1905.05702/) (2019)
- [Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2209.15594/) (2022)
- [Understanding Gradient Descent on Edge of Stability in Deep Learning](https://mlsanity.com/paper/2205.09745/) (2022)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [Hessian-based Analysis of Large Batch Training and Robustness to Adversaries](https://mlsanity.com/paper/1802.08241/) (2018)
- [Understanding the unstable convergence of gradient descent](https://mlsanity.com/paper/2204.01050/) (2022)
- [Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction](https://mlsanity.com/paper/2206.07085/) (2022)
- [A Walk with SGD](https://mlsanity.com/paper/1802.08770/) (2018)
- [SparseMAP: Differentiable Sparse Structured Inference](https://mlsanity.com/paper/1802.04223/) (2018)
- [Normalized Flat Minima: Exploring Scale Invariant Definition of Flat Minima for Neural Networks using PAC-Bayesian Analysis](https://mlsanity.com/paper/1901.04653/) (2019)
- [Gradient descent follows the regularization path for general losses](https://mlsanity.com/paper/2006.11226/) (2020)
- [Understanding Edge-of-Stability Training Dynamics with a Minimalist Example](https://mlsanity.com/paper/2210.03294/) (2022)
- [Learning threshold neurons via the "edge of stability"](https://mlsanity.com/paper/2212.07469/) (2022)
- [Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect](https://mlsanity.com/paper/2110.03677/) (2021)
- [Beyond the Quadratic Approximation: the Multiscale Structure of Neural Network Loss Landscapes](https://mlsanity.com/paper/2204.11326/) (2022)
- [Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability](https://mlsanity.com/paper/2305.11788/) (2023)
- [Beyond the Edge of Stability via Two-step Gradient Updates](https://mlsanity.com/paper/2206.04172/) (2022)
- [Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency](https://mlsanity.com/paper/2402.15926/) (2024)
- [Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function](https://mlsanity.com/paper/2002.06189/) (2020)
- [Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks](https://mlsanity.com/paper/2410.22069/) (2024)
- [Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization](https://mlsanity.com/paper/2406.08654/) (2024)
- [A Closer Look at Prototype Classifier for Few-shot Image Classification](https://mlsanity.com/paper/2110.05076/) (2021)
- [Surrogate Regret Bounds for Polyhedral Losses](https://mlsanity.com/paper/2110.14031/) (2021)
- [Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes](https://mlsanity.com/paper/2406.05033/) (2024)

## Built on by (most cited first, 1 of 1)

- [Non-asymptotic implicit bias of logistic regression at early-stage gradient descent dynamics](https://mlsanity.com/paper/2608.04382/) (2026)

## Abstract (arXiv)

The gradient descent (GD) has been one of the most common optimizer in machine learning. In particular, the loss landscape of a neural network is typically sharpened during the initial phase of training, making the training dynamics hover on the edge of stability. This is beyond our standard understanding of GD convergence in the stable regime where arbitrarily chosen stepsize is sufficiently smaller than the edge of stability. Recently, Wu et al. (COLT2024) have showed that GD converges with arbitrary stepsize under linearly separable logistic regression. Although their analysis hinges on the self-bounding property of the logistic loss, which seems to be a cornerstone to establish a modified descent lemma, our pilot study shows that other loss functions without the self-bounding property can make GD converge with arbitrary stepsize. To further understand what property of a loss function matters in GD, we aim to show arbitrary-stepsize GD convergence for a general loss function based on the framework of Fenchel--Young losses. We essentially leverage the classical perceptron argument to derive the convergence rate for achieving ε-optimal loss, which is possible for a majority of Fenchel--Young losses. Among typical loss functions, the Tsallis entropy achieves the GD convergence rate T=Omega(ε-1/2), and the R'enyi entropy achieves the far better rate T=Omega(ε-1/3). We argue that these better rate is possible because of separation margin of loss functions, instead of the self-bounding property.