# Tight Lower Bounds under Asymmetric High-Order H"older Smoothness and Uniform Convexity

arXiv: https://arxiv.org/abs/2409.10773 · HTML: https://mlsanity.com/paper/2409.10773/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 16 Sep 2024.

## Builds on (most cited first, 14 of 14)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization](https://mlsanity.com/paper/1307.5001/) (2013)
- [Oracle Complexity of Second-Order Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1705.07260/) (2017)
- [The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization](https://mlsanity.com/paper/2205.09647/) (2022)
- [Near-optimal method for highly smooth convex optimization](https://mlsanity.com/paper/1812.08026/) (2018)
- [Lower Bounds for Higher-Order Convex Optimization](https://mlsanity.com/paper/1710.10329/) (2017)
- [An Optimal High-Order Tensor Method for Convex Optimization](https://mlsanity.com/paper/1812.06557/) (2018)
- [Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method](https://mlsanity.com/paper/1905.02671/) (2019)
- [Primal-dual subgradient methods for minimizing uniformly convex functions](https://mlsanity.com/paper/1401.1792/) (2014)
- [The global rate of convergence for optimal tensor methods in smooth convex optimization](https://mlsanity.com/paper/1809.00382/) (2018)
- [Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness](https://mlsanity.com/paper/2112.01118/) (2021)
- [High-Order Oracle Complexity of Smooth and Strongly Convex Optimization](https://mlsanity.com/paper/2010.06642/) (2020)
- [Lower Complexity Bounds for Minimizing Regularized Functions](https://mlsanity.com/paper/2202.04545/) (2022)
- [Complexity of Minimizing Regularized Convex Quadratic Functions](https://mlsanity.com/paper/2404.17543/) (2024)

## Built on by (most cited first, 3 of 3)

- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [Stacey: Promoting Stochastic Steepest Descent via Accelerated ℓp-Smooth Nonconvex Optimization](https://mlsanity.com/paper/2506.06606/) (2025)
- [Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm](https://mlsanity.com/paper/2603.00027/) (2026)

## Abstract (arXiv)

In this paper, we provide tight lower bounds for the oracle complexity of minimizing high-order H"older smooth and uniformly convex functions. Specifically, for a function whose pth-order derivatives are H"older continuous with degree nu and parameter H, and that is uniformly convex with degree q and parameter σ, we focus on two asymmetric cases: (1) q > p + nu, and (2) q < p+nu. Given up to pth-order oracle access, we establish worst-case oracle complexities of Omegaleft( left( fracHσright)^frac23(p+nu)-2left( fracσεright)^frac2(q-p-nu)q(3(p+nu)-2)right) in the first case with an ℓ_∞-ball-truncated-Gaussian smoothed hard function and Omegaleft(left(fracHσright)^frac23(p+nu)-2+ loglogleft(left(fracσp+nuHqright)^frac1p+nu-qfrac1εright)right) 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.