Generalized Smoothness in Polynomial Dimension
Descriptions may be stale. Consult the linked Lean sources.
Generalized Smoothness in Polynomial Dimension
We consider minimizing a convex function
The optimization problem is
Our assumptions:
Assumption 1 (Parameter regime). The positive
parameters satisfy
Assumption 2 (Convexity). For every
Assumption 3 (Generalized smoothness). The function
Assumption 4 (Initial distance). There exists
Queries may be made at any point of
Results
Convex twice differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) PolynomialDimensionGeneralizedSmoothLowerBound
(Ours) |
Lower bound (necessary): |
||
| (2) (Rudomanov et al. 2026a), Thms. 4.8, 4.10 | Lower bound (necessary): |
(1): Scope: hardness extends from deterministic to arbitrary randomized algorithms, with expected-gap accuracy. | (1): Weaker |
| (3) (LongTails 2026), repository result, commit 0ed1e4a6 | Lower bound (necessary): |
(1): Scope: required
dimension decreases from |
|
| (4) (Rudomanov et al. 2026b), Thm. 7.1; different finite-sum class | Lower bound (necessary expected calls):
|
(1): Single-objective
hardness in polynomial dimension. Finite-sum classes are incomparable:
their average need not satisfy the single-function curvature bound.
Rates are not comparable; |
(1): Gradient-only, fixed-budget failure; (4) permits component values and gradients and bounds expected stopping cost. |
Abbr: