Answer history of a run with
DefinitionBinaryQueryLB_Supplement_strongHistoryconvex-optimizationlower-boundsoracle-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1
For an algorithm with , a chart and a function , the run of on is the sequence of queries and answers it produces when every answer is computed from and . The history after steps is the list of answer pairs received so far: at each step , applied to the current history, either asks a query , whose answer is appended, or stops, after which the history no longer changes.
Formalization Note Steps are counted from ; while has not stopped, the history after steps has length .
Definition code
import Mathlib
import Definitions.Def_BinaryQueryLB_Supplement_StrongAlgorithm
import Definitions.Def_BinaryQueryLB_Supplement_strongAnswer
namespace BinaryQueryLB.Supplement
/-- **Answer history of a run with O\*.** Shen–Zhong, *Near-Quadratic Lower Bounds for Convex Optimization with Binary First-Order Queries* (manuscript, sha256 9502d824…), §2.2, p.12: "For a function `f` and a chart `G`, the run of the algorithm on `(f, G)` is the sequence of
queries and answers that it produces when every answer is computed from `f` and `G`"; with `O∗` the
answers are the exact pairs `(f(y), ⟨v, g_f(y)⟩)`.
`strongHistory A G f t` is the list of answer pairs after `t` steps of the run of `A` on `(f, G)`:
at each step the algorithm, applied to the current history, either asks a query `(y, v)`, whose
answer `strongAnswer G f (y, v)` is appended, or stops, after which the history no longer changes.
**Formalization Note.** Steps are counted from `0`; while the algorithm has not stopped,
`strongHistory A G f t` has length `t`. -/
noncomputable def strongHistory {d : ℕ} (A : StrongAlgorithm d) (G : BinaryQueryLB.Chart d)
(f : EuclideanSpace ℝ (Fin d) → ℝ) : ℕ → List (ℝ × ℝ)
| 0 => []
| t + 1 =>
match A (strongHistory A G f t) with
| Sum.inl q => strongHistory A G f t ++ [strongAnswer G f q]
| Sum.inr _ => strongHistory A G f t
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