In the world of mathematical optimization, researchers are constantly hunting for the "speed limit"—the absolute minimum number of steps (or "oracle calls") an algorithm must take to find the minimum of a function. For decades, Nesterov’s lower bound for smooth, strongly convex functions has been the gold standard. However, as we move into the realm of "high-order" optimization—where algorithms can "see" not just gradients but also Hessians and even higher-order derivatives—the landscape becomes much more complex.
A new paper by Cedar Site Bai from Purdue University, titled "Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity," finally completes a major missing piece of this puzzle.
TL;DR
This paper establishes the first tight lower bound for minimizing functions where the degree of smoothness and the degree of convexity "match." It proves that for these functions, the best possible algorithms must still scale logarithmically with the desired accuracy, providing a high-order equivalent to Nesterov’s classical results.
What Problem Does This Paper Address?
To understand the contribution, we need to define two key properties of functions:
- Hölder Smoothness ($p, \nu, H$): This describes how much the $p^{th}$ derivative of a function can change. It’s a measure of how "wiggly" the function is at a high level.
- Uniform Convexity ($q, \sigma$): This describes the "curvature" of the function. A higher $q$ means the function is flatter near its minimum, making it harder to pinpoint the exact bottom.
The "matched regime" occurs when $q = p + \nu$. This is a special sweet spot. In first-order optimization ($p=1, \nu=1$), this corresponds to the well-known class of smooth and strongly convex functions ($q=2$). While researchers had already figured out the limits for cases where smoothness and convexity were mismatched (either very flat or very wiggly), the matched case for high-order derivatives remained an open question.
The challenge lies in the fact that high-order oracles (which provide derivatives up to order $p$) are incredibly powerful. A single Hessian evaluation can reveal an entire quadratic function, so the "hard functions" used to prove lower bounds for simple gradient descent don't work here.
Methods
The author proves the lower bound by constructing a "hard function"—a mathematical obstacle course designed to be as difficult as possible for any deterministic algorithm.
The core innovation is a multiscale phase-wise construction. Instead of a single long chain of variables (the classical approach), the author builds the function in "phases."
- Multi-center Base: The author creates a base function with multiple "centers." As the algorithm gets closer to the minimum, it moves from one center to the next, with each center representing a smaller scale of accuracy.
- Separation of Geometry and Hardness: One of the biggest hurdles in previous attempts was "norm mismatch"—the difficulty of making a function that is hard to optimize in the Euclidean norm while maintaining specific convexity properties. Bai solves this by using a base function to handle the convexity and adding "short power chains" to provide the hardness.
- Smooth Maximums: To glue these different phases and centers together without creating "kinks" that would violate the smoothness requirements, the author uses a sophisticated "smooth maximum" function.
Datasets
Not discussed in the paper. As a theoretical work in optimization, the "evaluation" consists of rigorous mathematical proofs rather than experiments on datasets.
Key Insights and Ideas
- The Logarithmic Barrier: The paper confirms that in the matched regime, the complexity is always logarithmic in terms of accuracy ($\log \Delta_0/\epsilon$). This means that even with high-order information, you eventually hit a point of diminishing returns where you must "restart" your search at a finer scale.
- The High-Order Condition Number: The bound depends on a high-order condition number $\kappa = H/\sigma$. The specific exponent $\frac{2}{3q-2}$ shows exactly how much "power" you gain by using higher-order derivatives.
- Preserving Oracle Responses: A key part of the proof is ensuring that the "hard function" doesn't change its behavior in a way that would tip off the algorithm about the location of the minimum based on previous guesses.
Key Results
The paper proves that for any deterministic algorithm using $p^{th}$-order derivatives, the number of oracle calls $T$ required to reach an accuracy $\epsilon$ is:
$$T \in \Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3q-2}} \log \frac{\Delta_0}{\epsilon}\right)$$
This result is "tight," meaning it exactly matches the best-known upper bounds (the performance of the best existing algorithms). This completes the complexity landscape for uniformly convex functions, as shown in the table below:
Limitations and Future Work
- Deterministic Algorithms: The current proof applies to deterministic algorithms. While many optimization methods are deterministic, randomized algorithms (like those used in machine learning) might have different lower bounds.
- Euclidean Geometry: The construction relies heavily on the properties of the Euclidean norm. The author notes that lower bounds in other "norm geometries" (like $\ell_1$ or $\ell_\infty$) remain an open question.
- Dimension Requirements: To make the "hard function" work, the problem must have a sufficiently high dimension. Exploring the limits in low-dimensional spaces is a potential area for future study.
Summary updated