Descriptions may be stale. Consult the linked Lean sources.
Strongly Convex
Minimization with Comparisons
We minimize a continuously differentiable function over the
closed Euclidean unit ball in
dimension . On ,
is strongly convex and Lipschitz with Lipschitz gradient. For each query
, the oracle uses a fresh
independent sample to return a sign in with mean , where is an unknown odd, nondecreasing
function with local derivative bounds. Given , the goal is a feasible
output with ,
where minimizes on and the expectation includes algorithm
and oracle randomness.
With denoting the
Euclidean norm, the constrained problem is The algorithm receives the
dimension , the objective
constants , the
transfer parameters and
, and the
tolerance .
Our assumptions:
Assumption 1 (Objective regularity and strong
convexity). The function is
continuously differentiable on . For every , it satisfies
Assumption 2 (Comparison transfer). The transfer
function
is continuously differentiable, odd, and nondecreasing. Its derivative
satisfies where for every .
Assumption 3 (Pairwise comparison oracle). Let be independent random
variables with common law on a
measurable space ,
independent of the algorithm’s randomness. On call with ordered pair , the oracle returns
the bit encoded as a
sign, where is jointly measurable. For every
,
After the allotted comparisons, the output must be a measurable -valued random variable. For a minimizer
, the gap must be integrable
under the joint law of the algorithm’s randomness and the oracle samples
and satisfy