Theorem 4.1 — ε-accuracy for D-optimal design
ProvedRelSmoothFOM.DOptimal.theorem_4_1d-optimal-designfirst-order-methodslog-barrierp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1relative-smoothness
Let have rank , with . Run the primal gradient scheme on the positive simplex for , using the log barrier, relative-smoothness constant , and . Let attain the minimum among feasible simplex points where the information matrix is positive definite, and write . If and
then .
This gives the paper's explicit iteration count for reaching a prescribed optimality gap in D-optimal design.
Formalization Note Positive makes the division and logarithm meaningful. The optimum is represented by an attained on the positive-definiteness domain; the run is over the positive simplex because the log barrier is infinite at the boundary in the paper. Iterates start at index zero.
Preamble
import Mathlib import Definitions.Def_RelSmoothFOM_DOptimal_Setting
Formal statement
namespace RelSmoothFOM.DOptimal
/-- Theorem 4.1: iteration complexity for D-optimal design. -/
theorem theorem_4_1 {m n : ℕ} (H : Matrix (Fin m) (Fin n) ℝ)
(hH : H.rank = m) (hmn : m + 1 ≤ n)
(x : ℕ → Fin n → ℝ) (hx0 : x 0 = fun _ => 1 / (n : ℝ))
(hrun : RelSmoothFOM.PrimalGrad.IsPrimalGradientRun (posSimplex n) (dOptObj H) logBarrier 1 x)
(xstar : Fin n → ℝ) (hxs : xstar ∈ stdSimplex ℝ (Fin n))
(hxspd : (H * Matrix.diagonal xstar * H.transpose).PosDef)
(hopt : ∀ y ∈ stdSimplex ℝ (Fin n),
(H * Matrix.diagonal y * H.transpose).PosDef →
dOptObj H xstar ≤ dOptObj H y)
(ε : ℝ) (hε : 0 < ε)
(hεle : ε ≤ dOptObj H (x 0) - dOptObj H xstar)
(k : ℕ)
(hk : 2 * (n : ℝ) *
Real.log (2 * (dOptObj H (x 0) - dOptObj H xstar) / ε) / ε ≤ (k : ℝ)) :
dOptObj H (x k) - dOptObj H xstar ≤ ε := by sorry
end RelSmoothFOM.DOptimal
Source
Lu, Freund & Nesterov, Relatively smooth convex optimization by first-order methods, and applications, SIAM J. Optim. 28 (2018), p. 349, Theorem 4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.