2024/09/16 by Site Bai, Brian Bullins, Bai, Cedar Site +1 · 2 citations
Computer Science · Decision Sciences · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Mathematical Approximation and Integration #Optimization and Control (math.OC) #Optimization and Variational Analysis #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.2409.10773
openalex publication_date 2024/09/16 · openalex created_date 2024/10/29 · openalex updated_date 2026/07/28
In this paper, we provide tight lower bounds for the oracle complexity of minimizing high-order Hölder smooth and uniformly convex functions. Specifically, for a function whose pth-order derivatives are Hölder continuous with degree ν and parameter H, and that is uniformly convex with degree q and parameter σ, we focus on two asymmetric cases: (1) q > p + ν, and (2) q < p+ν. Given up to pth-order oracle access, we establish worst-case oracle complexities of Ω( ( \fracHσ)^(2)/(3(p+ν)-2)( \fracσε)^(2(q-p-ν))/(q(3(p+ν)-2))) in the first case with an ℓ_∞-ball-truncated-Gaussian smoothed hard function and Ω((\fracHσ)^(2)/(3(p+ν)-2)+ loglog((\fracσp+νHq)^(1)/(p+ν-q)\frac1ε)) in the second case, for reaching an ε-approximate solution in terms of the optimality gap. Our analysis generalizes previous lower bounds for functions under first- and second-order smoothness as well as those for uniformly convex functions, and furthermore our results match the corresponding upper bounds in this general setting.