{"id":"arxiv/2610.21461","url":"https://arxiv.org/abs/2610.21461","tags":["math.OC"],"score":0,"title":"Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under $(L_0,L_1)$-Smoothness","domain":"math.OC","source":"arxiv","authors":["Mikhail Rudomanov","Ivan Fomin","Alexander V. Gasnikov","Fedor S. Stonyakin"],"reviews":0,"subject":"math.OC","summary":"For convex $(L_0,L_1)$-smooth functions, the curvature may grow together with the gradient norm. Therefore, even when $\\|x^0-x^*\\|\\le R$, the gradient and the optimality gap at the starting point may be exponentially large in $L_1R$, and the bound $\\sqrt{L_0R^2/\\varepsilon}$, known for the accelerated method on functions with Lipschitz gradient, no longer describes the complexity of the problem. We determine the oracle complexity of this class for arbitrary deterministic first-order methods: for $L_0R^2/\\varepsilon\\ge1$, the optimal number of oracle calls $N$ satisfies…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-15","reactions":{}}