Appendix B.3, p. 14 — the full and truncated averages agree at hidden-direction-orthogonal points
ProvedCompositeLB.DetSmooth.Fsum_eqconvex-optimizationfinite-sumlower-boundoracle-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1prox-oracle
Suppose , , are orthonormal, each is binary, and exactly components have for each . The average of the hard components equals everywhere. If and is orthogonal to , then
This equality transfers the minimum of an early truncated quadratic into a lower bound for the final objective at points that have not revealed later directions.
Formalization Note Orthogonality to expresses the paper's span condition. The indicator sum uses natural-number division .
Preamble
import Mathlib import Definitions.Def_CompositeLB_DetSmooth_Construction
Formal statement
namespace CompositeLB.DetSmooth
/-- Appendix B.3, p. 14: the aggregate hard function is `F^(k+1)`, and an
iterate orthogonal to all directions from round `q` onward sees `F^q`. -/
theorem Fsum_eq {m d k : ℕ} (a : ℝ) (v : ℕ → CompositeLB.DetLip.E d)
(δ : Fin m → ℕ → ℝ) (hm : 2 ≤ m) (hk : 1 ≤ k)
(hv : Orthonormal ℝ (fun r : Fin (k + 1) => v (r : ℕ)))
(hδ : ∀ i r, δ i r = 0 ∨ δ i r = 1)
(hsum : ∀ r ∈ Finset.Icc 1 k,
∑ i : Fin m, δ i r = ((m / 2 : ℕ) : ℝ)) :
(∀ x : CompositeLB.DetLip.E d, CompositeLB.DetLip.avgF (fun i => hardF a k v (δ i)) x = Fsum m a v (k + 1) x) ∧
(∀ q : ℕ, 1 ≤ q → q ≤ k → ∀ x : CompositeLB.DetLip.E d,
(∀ r : ℕ, q ≤ r → r ≤ k → inner ℝ x (v r) = 0) →
Fsum m a v q x = CompositeLB.DetLip.avgF (fun i => hardF a k v (δ i)) x) := by sorry
end CompositeLB.DetSmooth
Source
Woodworth & Srebro, arXiv:1605.08003v3, Appendix B.3, p. 14, display after the definition of F^t and paragraph beginning “Then if d”
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.