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

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 stepsize is chosen sufficiently smaller. Recently, Wu et al. [63] have shown that GD converges with much larger 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 selfbounding property can make GD attain arbitrarily small loss with large stepsize. To further understand what property of a loss function matters in GD, we aim to show large-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 iteration complexity for achieving ε-optimal loss, which is possible for a majority of Fenchel-Young losses. This convergence result highlights that the self-bounding property may not be necessary for GD to attain arbitrarily small loss. Moreover, when a loss function entails separation margin, a notion relevant to the margin in support vector machines, GD often yields faster convergence than typical GD rate T = Ω(ε -1 ) for convex smooth objectives. Specifically, GD with the Tsallis entropy attains ε-optimal loss with the rate T = Ω(ε -1/2 ), and the Rényi entropy achieves the far better rate T = Ω(ε -1/3 ).