{"id":"arxiv/2611.04171","url":"https://arxiv.org/abs/2611.04171","tags":["math.OC","cs.LG","stat.ML"],"score":0,"title":"Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions","domain":"math.OC","source":"arxiv","authors":["Mikhail Rudomanov","Ivan Fomin","Alexander V. Gasnikov","Fedor S. Stonyakin"],"reviews":0,"subject":"math.OC","summary":"We study the minimization of the average of $n$ convex $(L_0,L_1)$-smooth functions: the Hessian norm of each function is bounded by an affine function of its gradient norm. We assume known upper bounds $R$ on the distance from the starting point to a minimizer and $δ$ on the difference between the minimum of the average and the average of the infima of the components. We derive upper and lower bounds on the oracle complexity of reaching accuracy $\\varepsilon$ in function value in expectation. Up to logarithmic factors, both bounds are of order $n(1+(L_1R)^{2/3})…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}