Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under $(L_0,L_1)$-Smoothness

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 accelerat