Processing math: 100%

2409.10773

Total: 1

#1 Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity [PDF] [Copy] [Kimi] [REL]

Authors: Site Bai, Brian Bullins

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 Ω((Hσ)23(p+ν)2(σϵ)2(qpν)q(3(p+ν)2)) with a truncated-Gaussian smoothed hard function in the first case and Ω((Hσ)23(p+ν)2+log2(σp+νHq)1p+νq) 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 the general setting.

Subjects: Optimization and Control , Machine Learning

Publish: 2024-09-16 23:17:33 UTC