Gap-Constrained Generalized Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Gap-Constrained Generalized Smooth Convex Minimization
We consider minimizing a convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity). For every
Assumption 2 (Generalized smoothness). The function
Assumption 3 (Initial distance and objective gap).
There exists
Queries may be made at any point of
Results
Convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) GapGeneralizedSmoothConvexLowerBound
(Ours) |
Necessary: |
||
| (2) (Rudomanov et al. 2026), Thm. B.3 | (1): Randomized hardness
with gap dependence. For fixed |
(1): gradients only;
larger dimension instead of |
|
| (3) (Rudomanov et al. 2026), Thm. 4.10 | (1): Scope covers
prescribed |
On that common large-gap regime,
(1) has |
|
| (4) (LongTails, n.d.-a) | (1): Scope establishes
bounded-gap hardness for every |
(1) requires dimension
exponent |
|
| (5) (LongTails, n.d.-b) | (1): Adds
generalized-smooth bounded-gap hardness: |
(1) requires larger dimension. |
Abbr: