Deterministic algorithm with the strong oracle
DefinitionBinaryQueryLB_Supplement_StrongAlgorithmconvex-optimizationlower-boundsoracle-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1
The strong oracle answers a query , with and , by the exact pair of real numbers , where is the subgradient reported by the chart. A deterministic algorithm with chooses its -th query , decides whether to stop, and, when it stops, chooses its output , all as functions of the real answers received so far.
There is no bound on the number of queries and no restriction on the computation between queries; every query counts, including repeated ones.
Formalization Note An algorithm is a map from the history of answer pairs (a list of elements of , oldest first) to either a query or an output . That query points lie in is the separate predicate StrongQueriesInBox; that outputs lie in is part of -optimality.
Definition code
import Mathlib
namespace BinaryQueryLB.Supplement
/-- **Deterministic algorithm with the strong oracle O\*.** 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` by the
exact pair `(f(y), ⟨v, g_f(y)⟩)`, and a deterministic algorithm with `O∗` chooses each query and
its output as functions of the previous real answers."
**Formalization Note.** An algorithm is a map from the history of real answer pairs
`[(φ₁, ψ₁), …, (φ_{t−1}, ψ_{t−1})]` (a `List (ℝ × ℝ)`, oldest first) to either
`Sum.inl (y_t, v_t)` ("ask the query `(y_t, v_t)` next") or `Sum.inr ŷ` ("stop and output `ŷ`").
As in §2.2 there is no bound on the number of queries and no restriction on the computation between
queries; answers are exact reals, not discretized. That query points lie in `X` is the separate
predicate `StrongQueriesInBox`; that outputs lie in `X` is part of ε-optimality. ℝ^d is
`EuclideanSpace ℝ (Fin d)`. -/
abbrev StrongAlgorithm (d : ℕ) : Type :=
List (ℝ × ℝ) → (EuclideanSpace ℝ (Fin d) × EuclideanSpace ℝ (Fin d)) ⊕ EuclideanSpace ℝ (Fin d)
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