Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity
Abstract
In this paper, we provide tight lower bounds for minimizing high-order Hölder-smooth and uniformly convex functions when their orders match. Specifically, we consider functions whose pth-order derivatives are Hölder continuous with degree ν and parameter H, and that are uniformly convex with degree q and parameter σ. When these orders match, namely, q = p + ν, we show that any deterministic algorithm with access to derivatives up to order p requires Ω((H/σ)2/(3(p+ν)−2)logΔ0/ε) oracle calls to reduce an initial optimality gap of Δ0 to ε. This matches the corresponding upper bound and establishes a higher-order uniformly convex counterpart to Nesterov's classical first-order lower bound for strongly convex functions. Rather than directly generalizing Nesterov's classical quadratic-chain construction, we develop a multiscale phase-wise construction that preserves previous oracle responses while maintaining global Hölder smoothness and uniform convexity. Our result resolves the matched case left open by existing lower bounds for the two asymmetric regimes.
Related
- An Optimal Second-Order Algorithm for Finite-Sum Optimization under Average Smoothness and Convexity
- Last-Iterate Convergence Rate of Normalized Gradient Descent under Hölder Smoothness
- Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness
- From qualitative smoothness to uniform estimates for fully nonlinear elliptic equations
- Hölder Selections under Stieltjes Clocks: Uniform Disconnectedness and Jump Dominance
BibTeX
@misc{bai2026tight,
title = {{Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity}},
author = {Cedar Site Bai},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05527},
eprint = {2611.05527},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05527},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity
AU - Cedar Site Bai
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05527
UR - https://arxiv.org/abs/2611.05527
AB - In this paper, we provide tight lower bounds for minimizing high-order Hölder-smooth and uniformly convex functions when their orders match. Specifically, we consider functions whose p^th-order derivatives are Hölder continuous with degree ν and parameter H, and that are uniformly convex with degree q and parameter σ. When these orders match, namely, q = p + ν, we show that any deterministic algorithm with access to derivatives up to order p requires Ω((H/σ)^2/(3(p+ν)−2)logΔ_0/ε) oracle calls to reduce an initial optimality gap of Δ_0 to ε. This matches the corresponding upper bound and establishes a higher-order uniformly convex counterpart to Nesterov's classical first-order lower bound for strongly convex functions. Rather than directly generalizing Nesterov's classical quadratic-chain construction, we develop a multiscale phase-wise construction that preserves previous oracle responses while maintaining global Hölder smoothness and uniform convexity. Our result resolves the matched case left open by existing lower bounds for the two asymmetric regimes.
ER -