Research map / Optimization / Nonconvex and smooth optimization
Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives tight oracle-complexity lower bounds for minimizing p-th order Hölder smooth, uniformly convex functions in both asymmetric regimes (q > p+ν via ℓ∞-ball truncated Gaussian smoothing; q < p+ν via Nesterov's hard function), matching known upper bounds.
Problem
Oracle complexity of minimizing functions that are p-th order Hölder smooth (degree ν, parameter H) and uniformly convex (degree q, modulus σ) in the asymmetric regimes q > p+ν and q < p+ν; prior lower bounds did not cover this general setting.
Approach
Uses a truncated Gaussian smoothing operator restricted to an ℓ∞ ball, which has dimension-free smoothness and is local and p-th order smooth with constant scaling as (2/ρ)^p, to build a Nemirovski-style hard function for q > p+ν; for q < p+ν, adapts Nesterov's hard function with orthogonal basis vectors and a uniformly convex regularizer.
Key results
- For q > p+ν, the paper proves an Ω((H/σ)^{2/(3(p+ν)-2)} (σ/ε)^{2(q-p-ν)/(q(3(p+ν)-2))}) oracle complexity lower bound via ℓ∞-truncated Gaussian smoothing.
- For q < p+ν, the paper proves an Ω((H/σ)^{2/(3(p+ν)-2)} + log log(...)) lower bound adapting Nesterov's construction.
- The lower bounds match the existing upper bounds of the unified acceleration framework in the general setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ℓ∞-ball-truncated Gaussian smoothing instead of uniform randomized smoothing within an ℓ2 ball (ablation) | High-order smooth convex optimization lower-bound construction · High-order smooth convex optimization lower-bound construction | convergence rate: \mc{O}\big(T^{-\frac{2}{5p+1}}\big) -> \mc{O}\big(T^{-\frac{2}{3p+1}}\big) | Helped |
| Establish the q > p + ν lower bound using ℓ∞-ball-truncated Gaussian smoothing | High-order Hölder smooth, uniformly convex optimization · q > p + ν | oracle complexity | Helped |
| Generalize Nesterov's hard-function construction to Hölder smoothness and uniform convexity | High-order Hölder smooth, uniformly convex optimization · q < p + ν | oracle complexity | Helped |
Surprising findings
- Gaussian and softmax smoothing and Moreau smoothing are not local or do not raise smoothness constant to the p-th power, motivating the ℓ∞-truncated design.
- Uniform randomized smoothing over an ℓ2 ball gives a sub-optimal rate due to a dimension factor in smoothness constant.
Limitations
- The q > p+ν lower bound holds for deterministic algorithms only in the zero-chain sense; randomized extension is not established in this paper.
- The q = p+ν case is not covered.
- The hard function for q > p+ν is only p-th order smooth on a bounded domain.
Experimental setup
Metrics: oracle complexity (iteration count lower bound)
Baselines: Nemirovski-Yudin / Nesterov lower bounds uniform randomized smoothing lower bound (Lemma 2.3 based) Nesterov hard function lower bound for p=2, q=2
Builds on: Nesterov's hard function randomized smoothing lower bounds (Woodworth & Srebro style) unified acceleration framework for Hölder smooth uniformly convex functions
Closest papers by meaning
- Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness (NeurIPS 2021 · similarity 0.90)
- The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization (NeurIPS 2022 · similarity 0.90)
- On the Complexity of Finite-Sum Smooth Optimization under the Polyak–Łojasiewicz Condition (ICML 2024 · similarity 0.84)
- Frank-Wolfe Beyond 1/t Convergence (NeurIPS 2026 · similarity 0.84)
- On The Complexity of First-Order Methods in Stochastic Bilevel Optimization (ICML 2024 · similarity 0.84)
- Second-Order Min-Max Optimization with Lazy Hessians (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.