The -algorithm is -accurate for every and every chart
DefinitionBinaryQueryLB_Supplement_StrongSolvesEveryChartconvex-optimizationlower-boundsoracle-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1
An algorithm with is -accurate for every function and every chart if, for every first-order chart (a selection for , ) and every , the run of on stops after finitely many queries with an output that is -optimal for , that is, and .
Requiring success under every chart, rather than one fixed chart, lets the hard chart in a lower bound depend on the algorithm.
Definition code
import Mathlib
import Definitions.Def_BinaryQueryLB_Supplement_StrongStopsWith
import Definitions.Def_BinaryQueryLB_IsChart
import Definitions.Def_BinaryQueryLB_IsEpsOptimal
import Definitions.Def_BinaryQueryLB_ProblemClass
namespace BinaryQueryLB.Supplement
/-- **The O\*-algorithm is ε-accurate for every function and every chart.** Shen–Zhong, *Near-Quadratic Lower Bounds for Convex Optimization with Binary First-Order Queries* (manuscript, sha256 9502d824…), Theorem 1.4, p.5: "outputs a `(c0MR/√d)`-optimal point for every
`f ∈ F(d, R, M)` and every first-order chart"; p.5: "In this theorem the algorithm has to succeed for
every chart, so the hard chart may depend on the algorithm".
`StrongSolvesEveryChart d R M ε A`: for every first-order chart `G` (`IsChart d R M G`,
Definition 2.2) and every `f ∈ F(d, R, M)`, the run of `A` on `(f, G)` stops after some number
`T` of queries with an output `ŷ` that is ε-optimal for `f` (in particular `ŷ ∈ X`). -/
def StrongSolvesEveryChart (d : ℕ) (R M ε : ℝ) (A : StrongAlgorithm d) : Prop :=
∀ G : BinaryQueryLB.Chart d, BinaryQueryLB.IsChart d R M G →
∀ f ∈ BinaryQueryLB.ProblemClass d R M, ∃ (T : ℕ) (yh : EuclideanSpace ℝ (Fin d)),
StrongStopsWith A G f T yh ∧ BinaryQueryLB.IsEpsOptimal d R f ε yh
end BinaryQueryLB.Supplement
Source
Shen–Zhong, Near-Quadratic Lower Bounds for Convex Optimization with Binary First-Order Queries (manuscript, sha256 9502d824…), Theorem 1.4 and the paragraph before it, p.5