The -algorithm queries only points of
DefinitionBinaryQueryLB_Supplement_StrongQueriesInBoxconvex-optimizationlower-boundsoracle-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1
An algorithm with queries only points of if every query it can ask, after any history of answers, has . The direction is unrestricted.
Definition code
import Mathlib
import Definitions.Def_BinaryQueryLB_Supplement_StrongAlgorithm
import Definitions.Def_BinaryQueryLB_Box
namespace BinaryQueryLB.Supplement
/-- **The O\*-algorithm queries only points of `X`.** Shen–Zhong, *Near-Quadratic Lower Bounds for Convex Optimization with Binary First-Order Queries* (manuscript, sha256 9502d824…), §2.2, p.12: "The oracle `O∗` answers a query `(y, v)` with `y ∈ X` and `v ∈ R^d`".
`StrongQueriesInBox d R A` says that every query `(y, v)` the algorithm can ask, after any answer
history, has its point `y` in the box `X = [−R, R]^d`; the direction `v ∈ ℝ^d` is unrestricted. -/
def StrongQueriesInBox (d : ℕ) (R : ℝ) (A : StrongAlgorithm d) : Prop :=
∀ (l : List (ℝ × ℝ)) (q : EuclideanSpace ℝ (Fin d) × EuclideanSpace ℝ (Fin d)),
A l = Sum.inl q → q.1 ∈ BinaryQueryLB.Box d R
end BinaryQueryLB.Supplement
Source
Shen–Zhong, Near-Quadratic Lower Bounds for Convex Optimization with Binary First-Order Queries (manuscript, sha256 9502d824…), §2.2, p.12