Fast Initial Convergence Under (L₀,L₁) - Smoothness: Gradient and Coordinate Methods

Abstract

We study gradient descent (GD) and its variants for convex objectives satisfying <inline-formula> <tex-math notation="LaTeX">$(L_{0},L_{1})$ </tex-math></inline-formula>-smoothness. Our analysis reveals a fast initial regime that is hidden by worst-case sublinear bounds: while <inline-formula> <tex-math notation="LaTeX">$\|\nabla f(x^{k})\|\geq L_{0}/L_{1}$ </tex-math></inline-formula>, the objective residual decreases geometrically, and after the trajectory crosses this threshold the method retains the standard <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(1/N)$ </tex-math></inline-formula> guarantee. We establish this trajectory-level behavior for <inline-formula> <tex-math notation="LaTeX">$(L_{0},L_{1})$ </tex-math></inline-formula>-GD, whose step adapts to the gradient norm, and for clipped GD with an arbitrary clipping threshold; we also characterize the corresponding geometric regime of normalized GD. We then develop, to the best of our knowledge, the first convergence guarantees under coordinate-wise <inline-formula> <tex-math notation="LaTeX">$(L_{0},L_{1})$ </tex-math></inline-formula>-smoothness for random coordinate descent and its order-oracle counterpart, which uses only <inline-formula> <tex-math notation="LaTeX">$\mathrm {sign}(f(y)-f(x))$ </tex-math></inline-formula>; for the latter, we also quantify the comparison complexity of the one-dimensional search. Strong convexity yields three explicit contraction factors across the trajectory. Numerical examples verify the predicted transition and illustrate the advantage of adapting the step to generalized smoothness.