Skip to yearly menu bar Skip to main content


Poster

Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity

Cedar Site Bai · Brian Bullins

Hall 3 + Hall 2B #430
[ ]
Sat 26 Apr midnight PDT — 2:30 a.m. PDT
 
Oral presentation: Oral Session 5D
Fri 25 Apr 7:30 p.m. PDT — 9 p.m. PDT

Abstract: 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 pthpth-order derivatives are Hölder continuous with degree νν and parameter HH, and that is uniformly convex with degree qq and parameter σσ, we focus on two asymmetric cases: (1) q>p+νq>p+ν, and (2) q<p+νq<p+ν. Given up to pthpth-order oracle access, we establish worst-case oracle complexities of Ω((Hσ)23(p+ν)2(σϵ)2(qpν)q(3(p+ν)2))Ω((Hσ)23(p+ν)2(σϵ)2(qpν)q(3(p+ν)2)) in the first case with an -ball-truncated-Gaussian smoothed hard function and Ω((Hσ)23(p+ν)2+loglog((σp+νHq)1p+νq1ϵ))Ω((Hσ)23(p+ν)2+loglog((σp+νHq)1p+νq1ϵ)) 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.

Live content is unavailable. Log in and register to view live content