Local Reference Dueling Lower Bound — Strongly Convex Minimization with Flat Comparisons
Descriptions may be stale. Consult the linked Lean sources.
Strongly Convex Minimization with Flat Comparisons · Lean proof
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
Proved result
OracleTemplate.NonConvergence LongTails.Setups.FlatTransferDueling.spec
LongTails.Theorems.LocalReferenceDuelingLowerBound.budgetRelevant previous results
- Wataru Kumagai. Regret
Analysis for Continuous Dueling Bandit. 2017. Complexity:
pairwise comparisons are necessary for expected objective gap at most , for , under a fixed budget and a Gaussian comparison link with variance .