Comparison Orth Convex — Comparison-Based Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Comparison-Based Smooth Convex Minimization · Lean proof
Comparison-Based Smooth
Convex Minimization
We consider minimizing a differentiable convex function , where is an integer. Its gradient is
-Lipschitz in the Euclidean norm,
with , and a given starting
point lies
within distance of a global
minimizer . At a queried
pair , the oracle returns the
Boolean value of . For
a tolerance , the
goal is an output satisfying
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is
Throughout, denotes the
Euclidean norm. The algorithm receives , , , , and .
Our assumptions:
Assumption 1 (Convexity). For every and ,
Assumption 2 (Smoothness). The function is differentiable everywhere on , and its gradient satisfies
Assumption 3 (Initial distance). There exists such that
Queries may use any pair .
Comparisons are exact: the reply is true precisely when , including equality, and
false otherwise.
After the allotted comparison calls, the output must satisfy The minimizer is fixed independently of the
algorithm’s randomness; all global minimizers have the same objective
value.
Proved result
OracleTemplate.Convergence LongTails.Setups.ComparisonSmoothConvex.spec OracleTemplate.ComparisonOrth.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.