Known-Gap Generalized Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Known-Gap Generalized Smooth Convex Minimization
We consider minimizing a differentiable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Parameter regime and dimension). The
parameters satisfy
Assumption 2 (Convexity and generalized smoothness).
The function
Assumption 3 (Initial distance and objective gap).
There exists a global minimizer
Queries may be made at any point of
Results
- Known Gap Generalized Smooth Lower Bound · Lean proof
- Known Gap Generalized Smooth Upper Bound · Lean proof
Convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) KnownGapGeneralizedSmoothLowerBound
(Ours) |
|||
| (2) KnownGapGeneralizedSmoothUpperBound (Ours) (review) | |||
| (3) (Rudomanov et al. 2026), Thm. B.3 | (1): randomized
expected-gap hardness; stronger |
(1): gradient-only
hardness; stated large- |
|
| (4) (LongTails, n.d.-b), radius-only lower bound | (1): adds |
(1): stronger dimension restriction. Rates are not comparable without a common gap restriction on hard instances. |
Abbr:
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (5) (Rudomanov et al. 2026), Thm. B.7(b) | (2): removes |
(2): gap branch can lose
|
|
| (6) (Rudomanov et al. 2026), Thm. 3.7 | (2): matches
radius-branch rate; smaller total order if |
(2): selection
additionally uses |
|
| (7) Derived bound (LongTails, n.d.-a, n.d.-c) | (2): matches known rate; formal upper-bound companion to (1). | (2): narrower
finite-dimensional regime; selection uses |
Abbr: