Strongly Convex Minimization with Comparisons
Descriptions may be stale. Consult the linked Lean sources.
Strongly Convex Minimization with Comparisons
We minimize a continuously differentiable function
With
Our assumptions:
Assumption 1 (Objective regularity and strong
convexity). The function
Assumption 2 (Comparison transfer). The transfer
function
Assumption 3 (Pairwise comparison oracle). Let
After the allotted comparisons, the output
Results
On the closed Euclidean unit ball
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) LocalReferenceDueling
(Ours) |
|||
| (2) Epoch-PDD (Saha et al. 2025, Thm. 4) | Derived bound on |
(1): For fixed |
(1): Weighted-average
expectation only. (2) gives a high-probability final
epoch point on general bounded domains containing a global minimizer,
with exterior queries allowed. (1) needs an odd |
| (3) NC-SMD (Kumagai 2017, Thms. 4, 13) | Derived bound on |
(1): Removes the accuracy
logarithm at fixed parameters. Allows |
(1): The |
| (4) Coordinate descent (Jamieson et al. 2012, Thm. 2) | (1): Covers constrained
minima with in-ball comparisons. Rates are not directly comparable:
(4) assumes unconstrained optimization on |
(1) needs a fixed link. (4) requires only a lower margin on the probability of a correct comparison. |
Abbr: