AI & ML
Tight Lower Bounds under Matched High-Order H\"older Smoothness and Uniform Convexity
arXiv stat.ML0 views
arXiv:2611.05527v1 Announce Type: cross Abstract: In this paper, we provide tight lower bounds for minimizing high-order H\"older-smooth and uniformly convex functions when their orders match. Specifically, we consider functions whose $p^{th}$-order derivatives are H\"older continuous with degree $\nu$ and parameter $H$, and that are uniformly convex with degree $q$ and parameter $\sigma$. When these orders match, namely, $q = p + \nu$, we show that any deterministic algorithm with access to derivatives up to order $p$ requires $\Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}\log\frac{\Delta_0}{\epsilon}\right)$ oracle calls to reduce an initial optimality gap of $\Delta_0$ to $\epsilon$. 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\"older smoothness and uniform convexity. Our result resolves the matched case left open by existing lower bounds for the two asymmetric regimes.
Source:https://arxiv.org/abs/2611.05527PreviousAlignment Myopia in Generative AINextTowards Efficient Whole Page Ranking with One-Pass Inference
Related posts
Uniform Race: Parameter-Free Approximate Rejection Sampling
0arXiv stat.ML
Efficient Robust Learning at the Information-Theoretic Limit
0arXiv stat.ML
Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning
0arXiv stat.ML
More Expressive Feedforward Layers: Part I. Token-Adaptive Mixing of Activations
0arXiv stat.ML
Fr\'echet Regression on the Bures-Wasserstein Manifold
0arXiv stat.ML
Decoupling Distance and Networks: Hybrid Graph Attention-Geostatistical Methods for Spatio-temporal Risk Mapping
0arXiv stat.ML