Appendix B.3, pp. 14–15 — explicit minimizer and minimum of F^t
ProvedCompositeLB.DetSmooth.xstar_closed_formconvex-optimizationfinite-sumlower-boundoracle-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1prox-oracle
For , , and orthonormal , let . This point minimizes over the entire Euclidean space, and
This is the value comparison used to obtain the explicit optimization gap. The quadratic ignores directions orthogonal to its displayed span, so the theorem asserts that is a minimizer, without claiming uniqueness.
Preamble
import Mathlib import Definitions.Def_CompositeLB_DetSmooth_Construction
Formal statement
namespace CompositeLB.DetSmooth
/-- Appendix B.3, pp. 14–15: `xstarT` minimizes the quadratic `F^t` and has
the displayed minimum value. Orthogonal directions make minimizers nonunique. -/
theorem xstar_closed_form {m d k : ℕ} (a : ℝ) (v : ℕ → CompositeLB.DetLip.E d)
(t : ℕ) (hm : 2 ≤ m) (ht : 1 ≤ t) (htk : t ≤ k + 1)
(hv : Orthonormal ℝ (fun r : Fin (k + 1) => v (r : ℕ))) :
(∀ y : CompositeLB.DetLip.E d, Fsum m a v t (xstarT a v t) ≤ Fsum m a v t y) ∧
Fsum m a v t (xstarT a v t) =
-(a ^ 2 * ((m / 2 : ℕ) : ℝ) / (8 * (m : ℝ))) *
(1 - 1 / ((t : ℝ) + 1)) := by sorry
end CompositeLB.DetSmooth
Source
Woodworth & Srebro, arXiv:1605.08003v3, Appendix B.3, p. 14, final display, and p. 15, first two displays
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.