Stochastic Line Search under Nonuniform Smoothness beyond Interpolation

Selecting step sizes for stochastic gradient methods is challenging because effective choices depend on unknown curvature and stochastic noise. Recent work has shown that stochastic line search can address this challenge under interpolation and, more recently, beyond interpolation under global smoothness. However, global smoothness can be restrictive for Machine Learning (ML) objectives. This motivates generalized conditions such as $(L_0,L_1)$-nonuniform smoothness (NUS), under which local curvature can vary with the gradient norm. Although line search naturally adapts to this varying curvature, its analysis beyond interpolation is challenging because both the sampled curvature information and the search direction are noisy. We study stochastic line search under sample-wise symmetric NUS without interpolation. We propose STORM with Vanishing-margin Line Search (STORMVLS), combining stochastic line search with recursive STORM gradient tracking. Assuming each component function is lower bounded, we prove that STORMVLS returns a point $x_R$ satisfying $\mathbb E ||\nabla f(x_R)||^2\leq\varepsilon$ within $\widetilde O(\varepsilon^{-3})$ stochastic gradient evaluations. The result requires neither a uniform global smoothness bound nor a separate variance assumption. Experiments suggest that a practical variant is stable and competitive with existing stochastic line search methods.