betaFeedback

WorksMathematics

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 pthp^{th}-order derivatives are Hölder continuous with degree νν and parameter HH, and that are uniformly convex with degree qq and parameter σσ. When these orders match, namely, q=p+νq = p + ν, we show that any deterministic algorithm with access to derivatives up to order pp requires Ω((Hσ)23(p+ν)−2log⁡Δ0ε)Ω\left(\left(\frac{H}σ\right)^{\frac{2}{3(p+ν)-2}}\log\frac{Δ_0}ε\right) oracle calls to reduce an initial optimality gap of Δ0Δ_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.

Introduction

Determining the optimal complexity of minimizing uniformly convex functions is a fundamental problem in optimization. Uniform convexity generalizes strong convexity through curvature bounds involving higher powers of the distance between points, with applications in high-order optimization [26, 8] and machine learning [30, 8, 4]. The optimal complexity depends jointly on the order of derivative oracle access, the smoothness of the function, and its uniform-convexity degree.

We study this problem in a general setting, with pthp^{\mathrm{th}}-order derivative oracle access to functions F(x)F(x) whose pthp^{\mathrm{th}}-order derivatives ∇pF(x)\nabla^p F(x) are Hölder continuous with exponent ν\nu and parameter HH, and that are uniformly convex with degree qq and modulus σ\sigma. We focus on the matched regime q=p+νq=p+\nu, which includes the classical smooth strongly convex case when p=1,ν=1,q=2p=1,\nu=1,q=2, in which Hσ\frac{H}{\sigma} is the condition number. In this case, Nesterov’s accelerated gradient method [24] converges linearly, attaining an optimality gap F(xT)−F(x∗)≤ϵF(x_T)-F(x^*)\leq\epsilon in T∈O((Hσ)12log⁡(Δ0ϵ))T\in\mathcal{O}\left(\left(\frac{H}{\sigma}\right)^{\frac{1}{2}}\log\left(\frac{\Delta_0}{\epsilon}\right)\right) gradient oracle calls [25, 7], where x∗x^* is the minimizer and Δ0:=F(x0)−F(x∗)\Delta_0:=F(x_0)-F(x^*) denotes the initial optimality gap.

On the upper-bound side, [29] establishes linear convergence in the matched higher-order regime q=p+ν>2q=p+\nu>2, with iteration complexity Op,ν((Hσ)23q−2log⁡(Δ0ϵ))\mathcal{O}_{p,\nu}\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3q-2}}\log\left(\frac{\Delta_0}{\epsilon}\right)\right). These methods use derivatives through order pp, and Hσ\frac{H}{\sigma} is the high-order condition number [17, 8, 16]. The logarithmic accuracy dependence follows from a restarting mechanism that reapplies an accelerated convex method at smaller accuracy scales, reducing the optimality gap by a constant factor at each stage [17, 29].

On the lower-bound side, Nesterov’s classical first-order construction [25] establishes the optimality of the first-order rate above, while a tight characterization for the matched higher-order setting has remained open.

For general combinations of p,q,νp,q,\nu, [4] establishes tight deterministic lower bounds for both asymmetric regimes, with polynomial dependence on 1ϵ\frac{1}{\epsilon} when q>p+νq>p+\nu and doubly logarithmic dependence on 1ϵ\frac{1}{\epsilon} when q<p+νq<p+\nu, matching the corresponding upper bounds [29]. These complementary results leave q=p+νq=p+\nu as the only missing case in the general complexity characterization, as summarized in Table 1, under the respective function-class assumptions.

RegimeTight rate Θ(⋅)\Theta(\cdot)UpperSpecial casesLowerSpecial cases
q>p+νq > p + \nuκ23(p+ν)−2(σϵ)2(q−p−ν)q(3(p+ν)−2)\kappa^{\frac{2}{3(p+\nu)-2}}\left(\frac{\sigma}{\epsilon}\right)^{\frac{2(q-p-\nu)}{q(3(p+\nu)-2)}}[29][27] p=1,ν=1p = 1,\nu= 1[4][30] p=1,ν=1,q>2p = 1,\nu= 1,q > 2
q=p+νq = p + \nuκ23q−2log⁡(Δ0ϵ)\kappa^{\frac{2}{3q-2}}\log\left(\frac{\Delta_0}{\epsilon}\right)[29][17] p≥2,ν=1p \ge2,\nu= 1This work[25] p=1,ν=1,q=2p = 1,\nu= 1,q = 2
q<p+νq < p + \nuκ23(p+ν)−2+log⁡log⁡((σp+νHq)1p+ν−q1ϵ)\kappa^{\frac{2}{3(p+\nu)-2}}+\log\log\left(\left(\frac{\sigma^{p+\nu}}{H^q}\right)^{\frac{1}{p+\nu-q}}\frac{1}{\epsilon}\right)[29]O~\widetilde{O} [2] p=2,ν=1,q=2p = 2,\nu= 1,q = 2; O~\widetilde{O} [22] p≥2,ν=1,q=2p \ge2,\nu= 1,q = 2[4][2] p=2,ν=1,q=2p = 2,\nu= 1,q = 2; [22] p≥2,ν=1,q=2p \ge2,\nu= 1,q = 2

Table 1. Complexity overview. κ:=Hσ\kappa:= \frac{H}{\sigma}; Δ0\Delta_0: initial optimality gap; ϵ\epsilon: target accuracy.

Our Result

In this paper, we resolve this open problem by establishing a lower bound matching the upper bound for deterministic algorithms with oracle access to all derivatives up to order pp. Our result establishes a higher-order uniformly convex counterpart to Nesterov’s classical first-order lower bound [25] and complements the asymmetric results of [4].

Theorem 1.1 (Matched-order lower bound). *Fix an integer p≥2p\geq2, 0<ν≤10<\nu\leq1, and q=p+νq=p+\nu. There are constants cp,ν,Kp,ν>0c_{p,\nu},K_{p,\nu}>0 such that, for H,σ,Δ0>0H,\sigma,\Delta_0>0 with sufficiently large Hσ\frac{H}{\sigma} and 0<ϵ≤cp,νΔ00<\epsilon\leq c_{p,\nu}\Delta_0, and every dimension d≥Kp,ν(Hσ)23q−2log⁡(Δ0ϵ)d\geq K_{p,\nu}\left(\frac{H}{\sigma}\right)^{\frac{2}{3q-2}}\log\left(\frac{\Delta_0}{\epsilon}\right), every deterministic pthp^{\mathrm{th}}-order oracle algorithm initialized at x0∈Rdx_0\in\mathbb{R}^d admits a pp times continuously differentiable function F:Rd→RF:\mathbb{R}^d\to\mathbb{R} with minimizer x∗x^* and F(x0)−F(x∗)=Δ0F(x_0)-F(x^*)=\Delta_0, such that, for all x,y∈Rdx,y\in\mathbb{R}^d: (a) pthp^{\mathrm{th}}-order Hölder smoothness. ∥∇pF(y)−∇pF(x)∥≤H∥y−x∥ν\|\nabla^pF(y)-\nabla^pF(x)\|\leq H\|y-x\|^\nu. (b) Uniform convexity. F(y)≥F(x)+⟨∇F(x),y−x⟩+σq∥y−x∥qF(y)\geq F(x)+\langle\nabla F(x),y-x\rangle+\frac{\sigma}{q}\|y-x\|^q.

For a candidate x^T\widehat{x}_T after TT oracle calls, F(x^T)−F(x∗)≤ϵF(\widehat{x}_T)-F(x^*)\leq\epsilon requires T∈Ωp,ν((Hσ)23q−2log⁡(Δ0ϵ))T\in\Omega_{p,\nu}\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3q-2}}\log\left(\frac{\Delta_0}{\epsilon}\right)\right).*

Motivation

To prove an oracle lower bound, we construct, for any given deterministic algorithm, a hard function for which reaching the target optimality gap requires the number of oracle calls stated in Theorem 1.1. The construction limits the information that each oracle output provides about the minimizer, so that fewer oracle calls cannot identify an accurate solution.

Classical Construction. Nesterov’s classical first-order lower-bound construction [25] uses a quadratic chain: a quadratic function whose terms couple neighboring coordinates, such as (xi−xi+1)2(x_i-x_{i+1})^2. The coordinate directions can be chosen so that gradient oracle outputs reveal the minimizer gradually. Its coordinates decay geometrically, so the unrevealed tail prevents the algorithm from reaching the target accuracy until sufficiently many directions have been determined. This construction does not directly extend to higher-order oracles, because one Hessian oracle call reveals the entire quadratic form.

References

  1. [1]Naman Agarwal and Elad Hazan. Lower bounds for higher-order convex optimization. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 774–792. PMLR, 06–09 Jul 2018. Cited on page 4.arxiv.org/abs/1710.10329
  2. [2]Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle Complexity of Second-Order Methods for Smooth Convex Optimization. Mathematical Programming, 178:327–360, 2019. Cited on pages 4 and 57.
  3. [3]Daniel Azagra. Global and fine approximation of convex functions. Proceedings of the London Mathematical Society, 107(4):799–824, 2013. Cited on pages 3, 4, 5, and 18.
  4. [4]Site Bai and Brian Bullins. Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity. In International Conference on Learning Representations, 2025. Cited on pages 1, 2, 4, and 57.arxiv.org/abs/2409.10773
  5. [5]Gábor Braun, Cristóbal Guzmán, and Sebastian Pokutta. Lower bounds on the oracle complexity of nonsmooth convex optimization via information theory. IEEE Transactions on Information Theory, 63(7):4709–4724, 2017. See the 2024 corrigendum, volume 70, number 7, pages 5408–5409, doi:10.1109/TIT.2024.3357200. Cited on page 2.
  6. [6]Youness Boutaib. On Lipschitz maps and the Hölder regularity of flows. Revue Roumaine de Mathématiques Pures et Appliquées, 65(2):131–177, 2020. Cited on pages 19 and 20.
  7. [7]Sébastien Bubeck. Convex Optimization: Algorithms and Complexity. Foundations and Trends in Machine Learning, 8(3–4):231–357, 2015. Cited on page 1.arxiv.org/abs/1405.4980
  8. [8]Brian Bullins. Highly Smooth Minimization of Non-smooth Problems. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 988–1030. PMLR, 2020. Cited on page 1.
  9. [9]Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Cited on pages 27, 69, and 77.
  10. [10]Jonathan M. Borwein and Jon D. Vanderwerff. Convex Functions: Constructions, Characterizations and Counterexamples. Cambridge University Press, 2010. Cited on pages 64 and 65.
  11. [11]Henri Cartan. Differential Calculus. Hermann, 1971. Cited on page 19.
  12. [12]Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 184(1–2):71–120, 2020. Cited on pages 58 and 61.arxiv.org/abs/1710.11606
  13. [13]Juan Pablo Contreras, Cristóbal Guzmán, and David Martínez-Rubio. Non-Euclidean high-order smooth convex optimization extended abstract. In Nika Haghtalab and Ankur Moitra, editors, Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, page 1330. PMLR, 2025. Cited on page 3.DOI
  14. [14]Brian Conrad. Higher derivatives and Taylor’s formula via multilinear maps. Math 396 course notes, Stanford University. Cited on page 18.
  15. [15]Yuriy Dorn, Darina Dvinskikh, Timofei Loginov, Osman Osmanov, Aleksandr Shestakov, Nazarii Tupitsa, and Alexander Gasnikov. Lower Bounds For Gradient-Free Convex Optimization And Convex-Concave Saddle-Point Problems, 2026. arXiv preprint arXiv:2610.00345. Cited on page 2.arxiv.org/abs/2610.00345
  16. [16]Nikita Doikov and Yurii Nesterov. Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method. Journal of Optimization Theory and Applications, 189(1):317–339, 2021. Cited on pages 1, 3, 24, and 43.DOI
  17. [17]Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, and César A. Uribe. Optimal tensor methods in smooth convex and uniformly convex optimization. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1374–1391. PMLR, 2019. Cited on pages 1, 2, 3, and 4.
  18. [18]Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. Near-optimal lower bounds for convex optimization for all orders of smoothness. In Advances in Neural Information Processing Systems, volume 34, pages 29874–29884. Curran Associates, Inc., 2021. Cited on page 4.arxiv.org/abs/2112.01118
  19. [19]Cristóbal Guzmán and Arkadi Nemirovski. On lower complexity bounds for large-scale smooth convex optimization. Journal of Complexity, 31(1):1–14, 2015. Cited on page 4.arxiv.org/abs/1307.5001
  20. [20]Geovani N. Grapiglia and Yurii Nesterov. Tensor methods for minimizing convex functions with Hölder continuous higher-order derivatives. SIAM Journal on Optimization, 30(4):2750–2779, 2020. Cited on pages 7, 8, 57, and 58.
  21. [21]Xu Kong, Jicheng Li, and Xiaolong Wang. New estimations on the upper bounds for the nuclear norm of a tensor. Journal of Inequalities and Applications, 2018(1):282, 2018. Cited on page 21.DOI
  22. [22]Guy Kornowski and Ohad Shamir. High-Order Oracle Complexity of Smooth and Strongly Convex Optimization, 2020. arXiv preprint arXiv:2010.06642. Cited on page 4.arxiv.org/abs/2010.06642
  23. [23]Arkadi Nemirovski. Information-Based Complexity of Convex Programming. Lecture notes, Technion – Israel Institute of Technology, 1994. Cited on page 2.
  24. [24]Yurii Nesterov. A Method of Solving a Convex Programming Problem with Convergence Rate O(1/k²). Doklady Akademii Nauk SSSR, 269(3):543–547, 1983. Cited on page 1.
  25. [25]Yurii Nesterov. Lectures on Convex Optimization, volume 137 of Springer Optimization and Its Applications. Springer International Publishing, 2nd edition, 2018. Cited on pages 1, 2, 4, and 57.DOI
  26. [26]Yurii Nesterov. Implementable tensor methods in unconstrained convex optimization. Mathematical Programming, 186(1–2):157–183, 2021. Cited on pages 1 and 57.
  27. [27]Vincent Roulet and Alexandre d’Aspremont. Sharpness, restart, and acceleration. SIAM Journal on Optimization, 30(1):262–289, 2020. Cited on page 4.arxiv.org/abs/1702.03828
  28. [28]Anton Rodomanov and Yurii Nesterov. Smoothness parameter of power of Euclidean norm. Journal of Optimization Theory and Applications, 185(2):303–326, 2020. Cited on pages 22 and 23.
  29. [29]Chaobing Song, Yong Jiang, and Yi Ma. Unified Acceleration of High-Order Algorithms under General Hölder Continuity. SIAM Journal on Optimization, 31(3):1797–1826, 2021. Cited on pages 1, 2, 3, and 4.DOI
  30. [30]Daniel Berg Thomsen and Nikita Doikov. Complexity of Minimizing Regularized Convex Quadratic Functions. SIAM Journal on Optimization, 36(3):1509–1536, 2026. Cited on pages 1 and 4.arxiv.org/abs/2404.17543

Paper details

vlnc:W_pwugz5j5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI Codex 6 Astra, 6.1 Sol

View statement
Looking for related papers…
Contents