A run with stops after exactly queries with output
DefinitionBinaryQueryLB_Supplement_StrongStopsWithconvex-optimizationlower-boundsoracle-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1
The run of an algorithm with on stops after exactly queries with output if asks a query at each of the steps and, at step , stops and outputs . Then is the number of queries makes on and ; repeated queries count.
Definition code
import Mathlib
import Definitions.Def_BinaryQueryLB_Supplement_strongHistory
namespace BinaryQueryLB.Supplement
/-- **A run with O\* stops after exactly `T` queries with output `ŷ`.** Shen–Zhong, *Near-Quadratic Lower Bounds for Convex Optimization with Binary First-Order Queries* (manuscript, sha256 9502d824…), §2.2, pp.11–12: when the algorithm "stops after `T` queries, it outputs a point
`ŷ` … every query counts, including repeated ones"; with `O∗` each query and the output are
functions of the previous real answers.
`StrongStopsWith A G f T ŷ` says that on `(f, G)` the algorithm asks a query at each of the steps
`0, …, T − 1` and stops at step `T` with output `ŷ`; `T` is then the number of queries it makes on
`(f, G)`. -/
def StrongStopsWith {d : ℕ} (A : StrongAlgorithm d) (G : BinaryQueryLB.Chart d)
(f : EuclideanSpace ℝ (Fin d) → ℝ) (T : ℕ) (yh : EuclideanSpace ℝ (Fin d)) : Prop :=
(∀ t < T, ∃ q : EuclideanSpace ℝ (Fin d) × EuclideanSpace ℝ (Fin d),
A (strongHistory A G f t) = Sum.inl q) ∧
A (strongHistory A G f T) = Sum.inr yh
end BinaryQueryLB.Supplement
Source
Shen–Zhong, Near-Quadratic Lower Bounds for Convex Optimization with Binary First-Order Queries (manuscript, sha256 9502d824…), §2.2, pp.11–12