Tight lower bounds for optimizing smooth convex functions with matching orders

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

Machine Learning

Summary

Finding the best solution quickly in math often depends on how smooth and curved the function you're working with is. This paper shows the exact minimum number of steps any method needs to find a good answer when certain smoothness and curvature conditions match. The authors developed a new, careful approach to prove this limit, improving over previous methods. Their result completes the picture for this specific situation where previous knowledge was incomplete.

What this means in practice

  • For optimization algorithm designers: Determine fundamental limits when developing algorithms for minimizing high-order smooth and convex functions with matching smoothness and convexity degrees.
  • For machine learning engineers: Understand the step complexity lower bounds when tuning advanced optimization methods for uniformly convex loss functions with high-order smoothness.

A theory result. No direct application yet.

Authors

Cedar Site Bai

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 $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 $Ω\left(\left(\frac{H}σ\right)^{\frac{2}{3(p+ν)-2}}\log\frac{Δ_0}ε\right)$ 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.