Poster
Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity
Cedar Site Bai · Brian Bullins
Hall 3 + Hall 2B #430
[
Abstract
]
Oral
presentation:
Oral Session 5D
Fri 25 Apr 7:30 p.m. PDT — 9 p.m. PDT
Sat 26 Apr midnight PDT
— 2:30 a.m. PDT
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(q−p−ν)q(3(p+ν)−2))Ω((Hσ)23(p+ν)−2(σϵ)2(q−p−ν)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