Appendix B.3, p. 15 — squared norm of the explicit minimizer
ProvedCompositeLB.DetSmooth.xstar_norm_sq_leconvex-optimizationfinite-sumlower-boundoracle-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1prox-oracle
For and orthonormal , the explicit point satisfies
Choosing therefore places in the unit ball, as required for the bounded-domain lower bound. The paper's subsequent assertion that its norm equals one is a printed slip: the established conclusion is the inequality.
Preamble
import Mathlib import Definitions.Def_CompositeLB_DetSmooth_Construction
Formal statement
namespace CompositeLB.DetSmooth
/-- Appendix B.3, p. 15: the squared norm of the displayed minimizer, with
its finite-sum identity and its `a²t/3` bound. -/
theorem xstar_norm_sq_le {d k : ℕ} (a : ℝ) (v : ℕ → CompositeLB.DetLip.E d)
(t : ℕ) (ht : 1 ≤ t) (htk : t ≤ k + 1)
(hv : Orthonormal ℝ (fun r : Fin (k + 1) => v (r : ℕ))) :
(‖xstarT a v t‖ ^ 2 =
a ^ 2 * ∑ r ∈ Finset.range t,
(1 - ((r : ℝ) + 1) / ((t : ℝ) + 1)) ^ 2) ∧
‖xstarT a v t‖ ^ 2 ≤ a ^ 2 * (t : ℝ) / 3 := by sorry
end CompositeLB.DetSmooth
Source
Woodworth & Srebro, arXiv:1605.08003v3, Appendix B.3, p. 15, norm computation
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.