Strongly Convex Minimization with Flat Comparisons
Descriptions may be stale. Consult the linked Lean sources.
Strongly Convex Minimization with Flat Comparisons
We minimize a continuously differentiable function
Writing
Our assumptions:
Assumption 1 (Objective regularity and curvature).
The function
Assumption 2 (Transfer function). The function
Assumption 3 (Comparison oracle). Let
After the allotted comparisons, the algorithm must return a
measurable
Results
On the closed Euclidean unit ball
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) LocalReferenceDuelingLowerBound
(Ours) |
Lower bound |
||
| (2) (Kumagai 2017, Thm. 14) | Lower bound |
(1) proves fixed-ball
hardness even for |
(1) uses |
| (3) (Jamieson et al. 2012, Thm. 1, Lem. 1) | Lower bound |
(1) establishes hardness
on a fixed ball in every dimension. The query cube in
(3) shrinks with |
(1) fixes the local slope bounds and window. (3) allows any comparison oracle satisfying its reliability margin. |
Abbr: