Appendix B.1, p. 12: the round and query thresholds imply m/(48ε)
ProvedCompositeLB.DetLip.query_countlower-boundoracle-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1query-count
For an integer and , the two query thresholds in Appendix B.1 obey
It converts the number of completed rounds into the explicit query lower bound for the normalized hard instance.
Formalization Note Floors and ceilings are natural numbers cast to real numbers. The main theorem itself retains an unspecified absolute Ω constant because the printed hard function is not 1-Lipschitz without rescaling.
Preamble
import Mathlib import Definitions.Def_CompositeLB_DetLip_Model
Formal statement
namespace CompositeLB.DetLip
/-- Appendix B.1, p. 12: the two stopping thresholds both give enough queries. -/
theorem query_count (m : ℕ) (ε : ℝ) (hm : 1 ≤ m)
(hε : 0 < ε) (hε_bound : ε ≤ 1 / 12) :
(m : ℝ) / (48 * ε) ≤
min ((m : ℝ) / ε)
(((⌊1 / (12 * ε)⌋₊ : ℕ) : ℝ) *
((⌈(m : ℝ) / 2⌉₊ : ℕ) : ℝ)) := by sorry
end CompositeLB.DetLip
Source
Woodworth & Srebro, arXiv:1605.08003v3, App. B.1, p. 12, query-count display before Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.