import DeqMdErratum.Defs

/-!
# Shifted Burg Properties, Mirror Descent Operator `T_τ`, and Variational Equivalence (1) ⟺ (4) ⟺ (5)

This module proves:
* Eq. (3) consequences on `[0, a]^n`: strong convexity of `h_ξ` with modulus `(a + ξ)^{-2}`
  (`bregmanShiftedBurg_ge_norm_sq`) and `ξ^{-2}`-Lipschitz continuity of `∇h_ξ`
  (`shiftedBurgGrad_lipschitzOn_box`).
* Continuity of the closed-form Mirror Descent layer `T_τ` on `[0, a]^n ∩ UPos` (`T_tau_continuousOn`).
* Normal-cone / limiting-subdifferential optimality condition Eq. (5) (`T_tau_optimality_cond`).
* Exact variational equivalence between the Mirror Descent subproblem (1) and the closed-form
  operator `T_τ` in (4) (`T_tau_unique_argmin`, `argmin_eq_T_tau`).
-/

open Filter Topology
open scoped BigOperators InnerProductSpace

namespace DeqMdErratum

section ShiftedBurgBounds

variable {n : ℕ}

/-- Scalar Bregman divergence of `-log (t + ξ)` for `u, x > -ξ`. -/
noncomputable def breg1D (ξ u x : ℝ) : ℝ :=
  (-Real.log (u + ξ)) - (-Real.log (x + ξ)) - (-(x + ξ)⁻¹) * (u - x)

lemma bregmanShiftedBurg_eq_sum_breg1D (ξ : ℝ) (u x : E n) :
    bregmanShiftedBurg ξ u x = ∑ j : Fin n, breg1D ξ (u j) (x j) := by
  unfold bregmanShiftedBurg shiftedBurgReal shiftedBurgGrad breg1D
  rw [E_inner_eq]
  simp only [PiLp.sub_apply]
  have h1 : (-∑ j : Fin n, Real.log (u j + ξ)) - (-∑ j : Fin n, Real.log (x j + ξ)) =
      ∑ j : Fin n, (-Real.log (u j + ξ) - -Real.log (x j + ξ)) := by
    rw [← Finset.sum_neg_distrib, ← Finset.sum_neg_distrib, ← Finset.sum_sub_distrib]
  rw [h1, ← Finset.sum_sub_distrib]

lemma breg1D_nonneg {ξ u x : ℝ} (hu : 0 < u + ξ) (hx : 0 < x + ξ) :
    0 ≤ breg1D ξ u x := by
  unfold breg1D
  have hdiv : 0 < (u + ξ) / (x + ξ) := div_pos hu hx
  have hlog : Real.log ((u + ξ) / (x + ξ)) ≤ (u + ξ) / (x + ξ) - 1 :=
    Real.log_le_sub_one_of_pos hdiv
  rw [Real.log_div hu.ne' hx.ne'] at hlog
  have hsub : (u + ξ) / (x + ξ) - 1 = (u - x) * (x + ξ)⁻¹ := by
    field_simp
    ring
  rw [hsub] at hlog
  linarith

lemma bregmanShiftedBurg_nonneg {ξ : ℝ} {u x : E n}
    (hu : ∀ j : Fin n, -ξ < u j) (hx : ∀ j : Fin n, -ξ < x j) :
    0 ≤ bregmanShiftedBurg ξ u x := by
  rw [bregmanShiftedBurg_eq_sum_breg1D]
  exact Finset.sum_nonneg fun j _ => breg1D_nonneg (by linarith [hu j]) (by linarith [hx j])

lemma breg1D_ge_sq_on_Icc {a ξ u x : ℝ} (hξ : 0 < ξ)
    (hu : u ∈ Set.Icc 0 a) (hx : x ∈ Set.Icc 0 a) :
    1 / (2 * (a + ξ) ^ 2) * (u - x) ^ 2 ≤ breg1D ξ u x := by
  have ha_nonneg : 0 ≤ a := hu.1.trans hu.2
  have haξ : 0 < a + ξ := by linarith
  set c : ℝ := 1 / (2 * (a + ξ) ^ 2)
  let g : ℝ → ℝ := fun t => -Real.log (t + ξ) - c * t ^ 2
  let g' : ℝ → ℝ := fun t => -(t + ξ)⁻¹ - 2 * c * t
  have hg_deriv : ∀ t ∈ Set.Icc 0 a, HasDerivAt g (g' t) t := by
    intro t ht
    have htξ : t + ξ ≠ 0 := by linarith [ht.1]
    have h1 : HasDerivAt (fun s => -Real.log (s + ξ)) (-(t + ξ)⁻¹) t := by
      simpa using ((hasDerivAt_id t).add_const ξ).log htξ |>.neg
    have h2 : HasDerivAt (fun s => c * s ^ 2) (2 * c * t) t := by
      simpa [mul_assoc, mul_comm, mul_left_comm] using (hasDerivAt_pow 2 t).const_mul c
    exact h1.sub h2
  have hg'_mono : MonotoneOn g' (Set.Icc 0 a) := by
    intro t₁ ht₁ t₂ ht₂ h12
    have h_diff : g' t₂ - g' t₁ =
        (t₂ - t₁) * (1 / ((t₁ + ξ) * (t₂ + ξ)) - 1 / (a + ξ) ^ 2) := by
      dsimp [g', c]
      have hne1 : t₁ + ξ ≠ 0 := by linarith [ht₁.1]
      have hne2 : t₂ + ξ ≠ 0 := by linarith [ht₂.1]
      have hne3 : a + ξ ≠ 0 := haξ.ne'
      field_simp
      ring
    have ht₁ξ : 0 < t₁ + ξ := by linarith [ht₁.1]
    have ht₂ξ : 0 < t₂ + ξ := by linarith [ht₂.1]
    have hprod_le : (t₁ + ξ) * (t₂ + ξ) ≤ (a + ξ) ^ 2 := by
      have h1 : t₁ + ξ ≤ a + ξ := by linarith [ht₁.2]
      have h2 : t₂ + ξ ≤ a + ξ := by linarith [ht₂.2]
      nlinarith
    have hinv_ge : 1 / (a + ξ) ^ 2 ≤ 1 / ((t₁ + ξ) * (t₂ + ξ)) :=
      one_div_le_one_div_of_le (mul_pos ht₁ξ ht₂ξ) hprod_le
    have hnn : 0 ≤ (t₂ - t₁) * (1 / ((t₁ + ξ) * (t₂ + ξ)) - 1 / (a + ξ) ^ 2) :=
      mul_nonneg (sub_nonneg.mpr h12) (sub_nonneg.mpr hinv_ge)
    linarith
  have hg_breg : g' x * (u - x) ≤ g u - g x := by
    rcases lt_trichotomy x u with hxu | rfl | hux
    · have hIcc : Set.Icc x u ⊆ Set.Icc 0 a := fun t ht => ⟨hx.1.trans ht.1, ht.2.trans hu.2⟩
      have hcont : ContinuousOn g (Set.Icc x u) := fun t ht =>
        (hg_deriv t (hIcc ht)).continuousAt.continuousWithinAt
      have hdiff : DifferentiableOn ℝ g (Set.Ioo x u) := fun t ht =>
        (hg_deriv t (hIcc ⟨ht.1.le, ht.2.le⟩)).differentiableAt.differentiableWithinAt
      obtain ⟨z, hz, hz_eq⟩ := exists_deriv_eq_slope g hxu hcont hdiff
      have hz_deriv : deriv g z = g' z := (hg_deriv z (hIcc ⟨hz.1.le, hz.2.le⟩)).deriv
      rw [hz_deriv] at hz_eq
      have hmono := hg'_mono hx (hIcc ⟨hz.1.le, hz.2.le⟩) hz.1.le
      rw [hz_eq] at hmono
      exact (le_div_iff₀ (sub_pos.mpr hxu)).mp hmono
    · simp
    · have hIcc : Set.Icc u x ⊆ Set.Icc 0 a := fun t ht => ⟨hu.1.trans ht.1, ht.2.trans hx.2⟩
      have hcont : ContinuousOn g (Set.Icc u x) := fun t ht =>
        (hg_deriv t (hIcc ht)).continuousAt.continuousWithinAt
      have hdiff : DifferentiableOn ℝ g (Set.Ioo u x) := fun t ht =>
        (hg_deriv t (hIcc ⟨ht.1.le, ht.2.le⟩)).differentiableAt.differentiableWithinAt
      obtain ⟨z, hz, hz_eq⟩ := exists_deriv_eq_slope g hux hcont hdiff
      have hz_deriv : deriv g z = g' z := (hg_deriv z (hIcc ⟨hz.1.le, hz.2.le⟩)).deriv
      rw [hz_deriv] at hz_eq
      have hmono := hg'_mono (hIcc ⟨hz.1.le, hz.2.le⟩) hx hz.2.le
      rw [hz_eq] at hmono
      have hmul := mul_le_mul_of_nonpos_right hmono (sub_nonpos.mpr hux.le)
      have heq1 : (g x - g u) / (x - u) * (u - x) = -(g x - g u) := by
        have hne : x - u ≠ 0 := (sub_pos.mpr hux).ne'
        field_simp
        ring
      rw [heq1] at hmul
      linarith
  have hid : g u - g x - g' x * (u - x) = breg1D ξ u x - c * (u - x) ^ 2 := by
    dsimp [g, g', breg1D]
    ring
  linarith

/-- Strong convexity Bregman lower bound (from (3)) on `[0, a]^n`:
`1 / (2 * (a + ξ)^2) * ‖u - x‖^2 ≤ D_{h_ξ}(u, x)`. -/
theorem bregmanShiftedBurg_ge_norm_sq {a ξ : ℝ} (hξ : 0 < ξ) {u x : E n}
    (hu : u ∈ boxSet n a) (hx : x ∈ boxSet n a) :
    1 / (2 * (a + ξ) ^ 2) * ‖u - x‖ ^ 2 ≤ bregmanShiftedBurg ξ u x := by
  rw [bregmanShiftedBurg_eq_sum_breg1D, E_norm_sq_sub_eq, Finset.mul_sum]
  exact Finset.sum_le_sum fun j _ => breg1D_ge_sq_on_Icc hξ (hu j) (hx j)

/-- Lipschitz bound on `∇h_ξ` over `[0, a]^n` from (3): `‖∇h_ξ(u) - ∇h_ξ(x)‖ ≤ ξ^{-2} ‖u - x‖`. -/
theorem shiftedBurgGrad_lipschitzOn_box {a ξ : ℝ} (hξ : 0 < ξ) {u x : E n}
    (hu : u ∈ boxSet n a) (hx : x ∈ boxSet n a) :
    ‖shiftedBurgGrad ξ u - shiftedBurgGrad ξ x‖ ≤ (1 / ξ ^ 2) * ‖u - x‖ := by
  have hsq : ‖shiftedBurgGrad ξ u - shiftedBurgGrad ξ x‖ ^ 2 ≤ ((1 / ξ ^ 2) * ‖u - x‖) ^ 2 := by
    rw [E_norm_sq_sub_eq, mul_pow, E_norm_sq_sub_eq, Finset.mul_sum]
    refine Finset.sum_le_sum fun j _ => ?_
    have huξ : ξ ≤ u j + ξ := by linarith [(hu j).1]
    have hxξ : ξ ≤ x j + ξ := by linarith [(hx j).1]
    have huξ_pos : 0 < u j + ξ := by linarith
    have hxξ_pos : 0 < x j + ξ := by linarith
    have hdiff : (shiftedBurgGrad ξ u j - shiftedBurgGrad ξ x j) ^ 2 =
        (u j - x j) ^ 2 / ((u j + ξ) * (x j + ξ)) ^ 2 := by
      simp only [shiftedBurgGrad]
      have hne1 : u j + ξ ≠ 0 := huξ_pos.ne'
      have hne2 : x j + ξ ≠ 0 := hxξ_pos.ne'
      field_simp
      ring
    rw [hdiff]
    have hprod : ξ ^ 2 ≤ (u j + ξ) * (x j + ξ) := by nlinarith
    have hprod_sq : (ξ ^ 2) ^ 2 ≤ ((u j + ξ) * (x j + ξ)) ^ 2 := by nlinarith
    have hdiv_le : 1 / ((u j + ξ) * (x j + ξ)) ^ 2 ≤ 1 / (ξ ^ 2) ^ 2 :=
      one_div_le_one_div_of_le (by positivity) hprod_sq
    calc
      (u j - x j) ^ 2 / ((u j + ξ) * (x j + ξ)) ^ 2
          = (1 / ((u j + ξ) * (x j + ξ)) ^ 2) * (u j - x j) ^ 2 := by ring
      _ ≤ (1 / (ξ ^ 2) ^ 2) * (u j - x j) ^ 2 :=
        mul_le_mul_of_nonneg_right hdiv_le (sq_nonneg _)
      _ = (1 / ξ ^ 2) ^ 2 * (u j - x j) ^ 2 := by ring
  have hsqrt := Real.sqrt_le_sqrt hsq
  rw [Real.sqrt_sq (norm_nonneg _), Real.sqrt_sq (by positivity)] at hsqrt
  exact hsqrt

lemma bregmanShiftedBurg_three_point (ξ : ℝ) (z y x : E n) :
    bregmanShiftedBurg ξ z x - bregmanShiftedBurg ξ y x =
      bregmanShiftedBurg ξ z y + ⟪shiftedBurgGrad ξ y - shiftedBurgGrad ξ x, z - y⟫_ℝ := by
  unfold bregmanShiftedBurg
  have hsub : z - x = (z - y) + (y - x) := by abel
  rw [hsub, inner_add_right, inner_sub_left]
  ring

end ShiftedBurgBounds

section MirrorDescentStep

variable {m n : ℕ}

/-- Scalar update formula for the shifted-Burg Mirror Descent layer `T_τ(x)`. When the
denominator `d := 1 + τ * (xj + ξ) * gj` is positive, this equals
`Π_{[0,a]}((xj + ξ) / d - ξ)`; when `d ≤ 0`, the variational solution saturates at `a`,
which matches the `0 < d ≤ ξ / (a + ξ)` regime continuously. -/
noncomputable def T_tauCoord (a ξ τ xj gj : ℝ) : ℝ :=
  let d := 1 + τ * (xj + ξ) * gj
  if 0 < d then max 0 (min a ((xj + ξ) / d - ξ)) else a

/-- Total Mirror Descent operator `T_τ(x)` from (4), defined componentwise. -/
noncomputable def T_tau (P : ProblemData m n) (τ : ℝ) (x : E n) : E n :=
  WithLp.toLp 2 (fun j => T_tauCoord P.a P.ξ τ (x j) (gradient (FSmooth P) x j))

lemma T_tauCoord_mem_Icc {a ξ τ xj gj : ℝ} (ha : 0 ≤ a) :
    T_tauCoord a ξ τ xj gj ∈ Set.Icc 0 a := by
  dsimp only [T_tauCoord]
  split_ifs
  · refine ⟨le_max_left _ _, max_le ha (min_le_left _ _)⟩
  · exact ⟨ha, le_rfl⟩

lemma T_tau_mem_box (P : ProblemData m n) (τ : ℝ) (x : E n) :
    T_tau P τ x ∈ boxSet n P.a := fun j => by
  simpa [T_tau] using T_tauCoord_mem_Icc P.ha.le

lemma T_tau_eq_closed_form (P : ProblemData m n) {τ : ℝ} {x : E n}
    (hden : ∀ j : Fin n, 0 < 1 + τ * (x j + P.ξ) * gradient (FSmooth P) x j) :
    T_tau P τ x = WithLp.toLp 2 (fun j =>
      max 0 (min P.a ((x j + P.ξ) / (1 + τ * (x j + P.ξ) * gradient (FSmooth P) x j) - P.ξ))) := by
  apply E_ext
  intro j
  simp [T_tau, T_tauCoord, hden j]

/-- Continuous clamped representation of `T_tauCoord` on `[0, a] × ℝ` for `a > 0, ξ > 0`. -/
lemma T_tauCoord_eq_clamped {a ξ τ xj gj : ℝ} (ha : 0 < a) (hξ : 0 < ξ)
    (hxj : xj ∈ Set.Icc 0 a) :
    T_tauCoord a ξ τ xj gj =
      max 0 (min a ((xj + ξ) / max (ξ / (2 * (a + ξ))) (1 + τ * (xj + ξ) * gj) - ξ)) := by
  set d := 1 + τ * (xj + ξ) * gj
  set δ := ξ / (2 * (a + ξ))
  have hδ_pos : 0 < δ := by positivity
  have hxξ_ge : ξ ≤ xj + ξ := by linarith [hxj.1]
  have haξ_pos : 0 < a + ξ := by linarith
  by_cases hd_ge : ξ / (a + ξ) ≤ d
  · have hδ_lt : δ < ξ / (a + ξ) := by
      dsimp [δ]
      have : ξ / (2 * (a + ξ)) = (1 / 2) * (ξ / (a + ξ)) := by field_simp
      rw [this]
      linarith [show 0 < ξ / (a + ξ) from div_pos hξ haξ_pos]
    have hd_pos : 0 < d := (hδ_pos.trans hδ_lt).trans_le hd_ge
    have hmax : max δ d = d := max_eq_right (hδ_lt.le.trans hd_ge)
    dsimp only [T_tauCoord]
    rw [if_pos hd_pos, hmax]
  · push_neg at hd_ge
    have hmax_pos : 0 < max δ d := lt_max_of_lt_left hδ_pos
    have hmax_le : max δ d ≤ ξ / (a + ξ) := by
      refine max_le ?_ hd_ge.le
      dsimp [δ]
      have : 0 < ξ / (a + ξ) := div_pos hξ haξ_pos
      linarith [show ξ / (2 * (a + ξ)) = (1 / 2) * (ξ / (a + ξ)) by field_simp]
    have ha_le_right : a ≤ (xj + ξ) / max δ d - ξ := by
      have hdiv : (a + ξ) ≤ (xj + ξ) / max δ d := by
        rw [le_div_iff₀ hmax_pos]
        calc
          (a + ξ) * max δ d ≤ (a + ξ) * (ξ / (a + ξ)) :=
            mul_le_mul_of_nonneg_left hmax_le haξ_pos.le
          _ = ξ := mul_div_cancel₀ ξ haξ_pos.ne'
          _ ≤ xj + ξ := hxξ_ge
      linarith
    rw [min_eq_left ha_le_right, max_eq_right ha.le]
    dsimp only [T_tauCoord]
    split_ifs with hd_pos
    · have ha_le_d : a ≤ (xj + ξ) / d - ξ := by
        have hdiv : (a + ξ) ≤ (xj + ξ) / d := by
          rw [le_div_iff₀ hd_pos]
          calc
            (a + ξ) * d ≤ (a + ξ) * (ξ / (a + ξ)) :=
              mul_le_mul_of_nonneg_left hd_ge.le haξ_pos.le
            _ = ξ := mul_div_cancel₀ ξ haξ_pos.ne'
            _ ≤ xj + ξ := hxξ_ge
        linarith
      rw [min_eq_left ha_le_d, max_eq_right ha.le]
    · rfl

lemma FSmooth_contDiffOn_open (P : ProblemData m n) :
    ContDiffOn ℝ 2 (FSmooth P) (UPos P ∩ P.U_R) := by
  have hAx_contDiff : ∀ i : Fin m, ContDiff ℝ 2 (fun x : E n => Ax P x i) := by
    intro i
    unfold Ax
    refine ContDiff.sum fun j _ => ?_
    have hcoord : ContDiff ℝ 2 (fun x : E n => x j) :=
      ((ContinuousLinearMap.proj (R := ℝ) (ι := Fin n) (φ := fun _ => ℝ) j).comp
        (PiLp.continuousLinearEquiv 2 ℝ (fun _ : Fin n => ℝ)).toContinuousLinearMap).contDiff
    exact contDiff_const.mul hcoord
  have hsum : ContDiffOn ℝ 2 (fun x : E n => ∑ i : Fin m, klSmoothScalar (P.y i) (Ax P x i))
      (UPos P ∩ P.U_R) := by
    refine ContDiffOn.sum fun i _ => ?_
    by_cases hy0 : P.y i = 0
    · simp only [klSmoothScalar, hy0, ↓reduceIte]
      exact (hAx_contDiff i).contDiffOn
    · have hy_pos : 0 < P.y i := lt_of_le_of_ne (P.hy i) (Ne.symm hy0)
      have hterm_eq : Set.EqOn (fun x => klSmoothScalar (P.y i) (Ax P x i))
          (fun x => P.y i * (Real.log (P.y i) - Real.log (Ax P x i)) + Ax P x i - P.y i)
          (UPos P ∩ P.U_R) := by
        intro x hx
        have hAx_pos : 0 < Ax P x i := hx.1 i hy_pos
        simp only [klSmoothScalar, hy0, ↓reduceIte]
        rw [Real.log_div hy_pos.ne' hAx_pos.ne']
      refine ContDiffOn.congr ?_ hterm_eq
      have hlog : ContDiffOn ℝ 2 (fun x : E n => Real.log (Ax P x i)) (UPos P ∩ P.U_R) :=
        ContDiffOn.log ((hAx_contDiff i).contDiffOn) fun x hx => (hx.1 i hy_pos).ne'
      exact ((contDiffOn_const.mul (contDiffOn_const.sub hlog)).add
        (hAx_contDiff i).contDiffOn).sub contDiffOn_const
  exact hsum.add (P.hR_C2.mono Set.inter_subset_right)

lemma gradient_FSmooth_continuousOn (P : ProblemData m n) :
    ContinuousOn (gradient (FSmooth P)) (UPos P ∩ P.U_R) := by
  have hU_open : IsOpen (UPos P ∩ P.U_R) := (isOpen_UPos P).inter P.hU_R_open
  have hC1 : ContDiffOn ℝ 1 (FSmooth P) (UPos P ∩ P.U_R) :=
    (FSmooth_contDiffOn_open P).of_le (by norm_num)
  have hfd_cont : ContinuousOn (fderiv ℝ (FSmooth P)) (UPos P ∩ P.U_R) :=
    hC1.continuousOn_fderiv_of_isOpen hU_open le_rfl
  have hdual : Continuous (InnerProductSpace.toDual ℝ (E n)).symm :=
    (InnerProductSpace.toDual ℝ (E n)).symm.continuous
  refine (hdual.comp_continuousOn hfd_cont).congr fun x hx => ?_
  have hdiff : DifferentiableAt ℝ (FSmooth P) x :=
    (hC1.differentiableOn one_ne_zero x hx).differentiableAt (hU_open.mem_nhds hx)
  have hfd : fderiv ℝ (FSmooth P) x = (InnerProductSpace.toDual ℝ (E n)) (gradient (FSmooth P) x) :=
    (hasGradientAt_iff_hasFDerivAt.mp hdiff.hasGradientAt).fderiv
  dsimp only [Function.comp_def]
  rw [hfd, LinearIsometryEquiv.symm_apply_apply]

/-- Continuity of `T_τ` on `[0, a]^n ∩ UPos` for every `τ > 0` (even without assuming
positivity of denominators). -/
theorem T_tau_continuousOn (P : ProblemData m n) (τ : ℝ) :
    ContinuousOn (T_tau P τ) (boxSet n P.a ∩ UPos P) := by
  refine E_mk_continuousOn _ _ fun j => ?_
  have hsub : boxSet n P.a ∩ UPos P ⊆ UPos P ∩ P.U_R := fun x hx =>
    ⟨hx.2, P.hBox_sub_U_R hx.1⟩
  have hgrad_cont : ContinuousOn (fun x => gradient (FSmooth P) x j) (boxSet n P.a ∩ UPos P) :=
    (E_coord_continuous j).comp_continuousOn ((gradient_FSmooth_continuousOn P).mono hsub)
  have hx_cont : ContinuousOn (fun x : E n => x j) (boxSet n P.a ∩ UPos P) :=
    (E_coord_continuous j).continuousOn
  set δ : ℝ := P.ξ / (2 * (P.a + P.ξ))
  have hδ_pos : 0 < δ := div_pos P.hξ (by linarith [P.ha, P.hξ])
  let clamped : E n → ℝ := fun x =>
    max 0 (min P.a ((x j + P.ξ) / max δ (1 + τ * (x j + P.ξ) * gradient (FSmooth P) x j) - P.ξ))
  have hclamped_cont : ContinuousOn clamped (boxSet n P.a ∩ UPos P) := by
    have hnum : ContinuousOn (fun x : E n => x j + P.ξ) (boxSet n P.a ∩ UPos P) :=
      hx_cont.add continuousOn_const
    have hd : ContinuousOn (fun x : E n => 1 + τ * (x j + P.ξ) * gradient (FSmooth P) x j)
        (boxSet n P.a ∩ UPos P) :=
      continuousOn_const.add ((continuousOn_const.mul hnum).mul hgrad_cont)
    have hden : ContinuousOn (fun x : E n => max δ (1 + τ * (x j + P.ξ) * gradient (FSmooth P) x j))
        (boxSet n P.a ∩ UPos P) :=
      (continuous_const.max continuous_id).comp_continuousOn hd
    have hdiv : ContinuousOn (fun x : E n =>
        (x j + P.ξ) / max δ (1 + τ * (x j + P.ξ) * gradient (FSmooth P) x j))
        (boxSet n P.a ∩ UPos P) :=
      hnum.div hden fun x _ => (lt_max_of_lt_left hδ_pos).ne'
    have hmin : ContinuousOn (fun x : E n =>
        min P.a ((x j + P.ξ) / max δ (1 + τ * (x j + P.ξ) * gradient (FSmooth P) x j) - P.ξ))
        (boxSet n P.a ∩ UPos P) :=
      (continuous_const.min continuous_id).comp_continuousOn (hdiv.sub continuousOn_const)
    exact (continuous_const.max continuous_id).comp_continuousOn hmin
  refine hclamped_cont.congr fun x hx => ?_
  exact T_tauCoord_eq_clamped P.ha P.hξ (hx.1 j)

lemma T_tauCoord_scalar_normalCone {a ξ τ xj gj : ℝ} (ha : 0 < a) (hξ : 0 < ξ) (hτ : 0 < τ)
    (hxj : xj ∈ Set.Icc 0 a) (hd : 0 < 1 + τ * (xj + ξ) * gj) :
    let yj := T_tauCoord a ξ τ xj gj
    let wj := -gj - (1 / τ) * (-(yj + ξ)⁻¹ + (xj + ξ)⁻¹)
    ∀ zj ∈ Set.Icc 0 a, wj * (zj - yj) ≤ 0 := by
  intro yj wj zj hzj
  set d := 1 + τ * (xj + ξ) * gj
  have hxξ : 0 < xj + ξ := by linarith [hxj.1]
  have hy_eq : yj = max 0 (min a ((xj + ξ) / d - ξ)) := by simp [yj, T_tauCoord, hd, d]
  have hw_eq : wj = (1 / τ) * ((yj + ξ)⁻¹ - d / (xj + ξ)) := by
    dsimp [wj, d]
    field_simp [hτ.ne', hxξ.ne']
    ring
  rw [hw_eq]
  set raw := (xj + ξ) / d - ξ
  rcases le_or_gt raw 0 with hle0 | hgt0
  · have hy0 : yj = 0 := by
      rw [hy_eq, min_eq_right (hle0.trans ha.le), max_eq_left hle0]
    have hraw_le : (xj + ξ) / d ≤ ξ := by linarith
    have hinv_le : (0 + ξ)⁻¹ ≤ d / (xj + ξ) := by
      rw [zero_add]
      have h1 : xj + ξ ≤ ξ * d := (div_le_iff₀ hd).mp hraw_le
      rw [inv_eq_one_div, div_le_div_iff₀ hξ hxξ]
      linarith
    rw [hy0, sub_zero]
    have hw_nonpos : (1 / τ) * ((0 + ξ)⁻¹ - d / (xj + ξ)) ≤ 0 :=
      mul_nonpos_of_nonneg_of_nonpos (by positivity) (sub_nonpos.mpr hinv_le)
    exact mul_nonpos_of_nonpos_of_nonneg hw_nonpos hzj.1
  · rcases le_or_gt a raw with hgea | hlta
    · have hya : yj = a := by
        rw [hy_eq, min_eq_left hgea, max_eq_right ha.le]
      have hraw_ge : a + ξ ≤ (xj + ξ) / d := by linarith
      have haξ : 0 < a + ξ := by linarith
      have hinv_ge : d / (xj + ξ) ≤ (a + ξ)⁻¹ := by
        have h1 : (a + ξ) * d ≤ xj + ξ := (le_div_iff₀ hd).mp hraw_ge
        rw [inv_eq_one_div, div_le_div_iff₀ hxξ haξ]
        linarith
      rw [hya]
      have hw_nonneg : 0 ≤ (1 / τ) * ((a + ξ)⁻¹ - d / (xj + ξ)) :=
        mul_nonneg (by positivity) (sub_nonneg.mpr hinv_ge)
      exact mul_nonpos_of_nonneg_of_nonpos hw_nonneg (sub_nonpos.mpr hzj.2)
    · have hyraw : yj = raw := by
        rw [hy_eq, min_eq_right hlta.le, max_eq_right hgt0.le]
      have hyξ_eq : yj + ξ = (xj + ξ) / d := by
        rw [hyraw]
        dsimp [raw]
        ring
      have hinv_eq : (yj + ξ)⁻¹ = d / (xj + ξ) := by
        rw [hyξ_eq, inv_div]
      rw [hinv_eq, sub_self, mul_zero, zero_mul]

/-- Normal-cone optimality condition for `T_τ(x)`. -/
theorem T_tau_normalCone_opt (P : ProblemData m n) {τ : ℝ} {x : E n}
    (hτ : 0 < τ) (hx : x ∈ boxSet n P.a)
    (hden : ∀ j : Fin n, 0 < 1 + τ * (x j + P.ξ) * gradient (FSmooth P) x j) :
    -gradient (FSmooth P) x - (1 / τ) • (shiftedBurgGrad P.ξ (T_tau P τ x) - shiftedBurgGrad P.ξ x) ∈
      normalCone (boxSet n P.a) (T_tau P τ x) := by
  refine ⟨T_tau_mem_box P τ x, fun z hz => ?_⟩
  rw [E_inner_eq]
  refine Finset.sum_nonpos fun j _ => ?_
  have hcoord := T_tauCoord_scalar_normalCone P.ha P.hξ hτ (hx j) (hden j) (z j) (hz j)
  simpa [T_tau, shiftedBurgGrad] using hcoord

/-- Optimality condition (5) of the erratum:
`0 ∈ ∇F(x) + (1/τ)(∇h_ξ(T_τ(x)) - ∇h_ξ(x)) + ∂R(T_τ(x))`, written as
`-∇F(x) - (1/τ)(∇h_ξ(T_τ(x)) - ∇h_ξ(x)) ∈ ∂R(T_tau P τ x)`. -/
theorem T_tau_optimality_cond (P : ProblemData m n) {τ : ℝ} {x : E n}
    (hτ : 0 < τ) (hx : x ∈ boxSet n P.a)
    (hden : ∀ j : Fin n, 0 < 1 + τ * (x j + P.ξ) * gradient (FSmooth P) x j) :
    -gradient (FSmooth P) x - (1 / τ) • (shiftedBurgGrad P.ξ (T_tau P τ x) - shiftedBurgGrad P.ξ x) ∈
      limitingSubdiff (boxIndicator n P.a) (T_tau P τ x) := by
  rw [boxIndicator, limitingSubdiff_indicator_eq_normalCone_of_closed_convex
    (boxSet_isClosed n P.a) (boxSet_convex n P.a)]
  exact T_tau_normalCone_opt P hτ hx hden

/-- Objective of the Mirror Descent subproblem (1) with `h` replaced by `h_ξ` at iterate `x`. -/
noncomputable def mdSubproblemObj (P : ProblemData m n) (x : E n) (τ : ℝ) (z : E n) : EReal :=
  boxIndicator n P.a z +
    ((⟪z - x, gradient (FSmooth P) x⟫_ℝ + (1 / τ) * bregmanShiftedBurg P.ξ z x : ℝ) : EReal)

/-- Variational equivalence `(1) ⟺ (4)`: for `x ∈ [0, a]^n`, `τ > 0` with positive denominators,
`T_τ(x)` is the unique global minimizer of the shifted-Burg Mirror Descent subproblem (1). -/
theorem T_tau_unique_argmin (P : ProblemData m n) {τ : ℝ} {x : E n}
    (hτ : 0 < τ) (hx : x ∈ boxSet n P.a)
    (hden : ∀ j : Fin n, 0 < 1 + τ * (x j + P.ξ) * gradient (FSmooth P) x j) :
    ∀ z : E n, z ≠ T_tau P τ x → mdSubproblemObj P x τ (T_tau P τ x) < mdSubproblemObj P x τ z := by
  intro z hzne
  set ystar := T_tau P τ x
  have hystar_box : ystar ∈ boxSet n P.a := T_tau_mem_box P τ x
  by_cases hz_box : z ∈ boxSet n P.a
  · unfold mdSubproblemObj
    rw [boxIndicator_of_mem hystar_box, boxIndicator_of_mem hz_box, zero_add, zero_add,
      EReal.coe_lt_coe_iff]
    set g := gradient (FSmooth P) x
    set w := -g - (1 / τ) • (shiftedBurgGrad P.ξ ystar - shiftedBurgGrad P.ξ x)
    have hw_nc : w ∈ normalCone (boxSet n P.a) ystar := T_tau_normalCone_opt P hτ hx hden
    have hinner_nonneg : 0 ≤ -⟪w, z - ystar⟫_ℝ := neg_nonneg.mpr (hw_nc.2 z hz_box)
    have h3pt := bregmanShiftedBurg_three_point P.ξ z ystar x
    have hbreg_pos : 0 < bregmanShiftedBurg P.ξ z ystar := by
      have hge := bregmanShiftedBurg_ge_norm_sq P.hξ hz_box hystar_box
      have hnorm_pos : 0 < ‖z - ystar‖ := norm_pos_iff.mpr (sub_ne_zero.mpr hzne)
      have hcoef : 0 < 1 / (2 * (P.a + P.ξ) ^ 2) := by
        have : 0 < P.a + P.ξ := by linarith [P.ha, P.hξ]
        positivity
      exact (mul_pos hcoef (sq_pos_of_pos hnorm_pos)).trans_le hge
    have hid : (⟪z - x, g⟫_ℝ + (1 / τ) * bregmanShiftedBurg P.ξ z x) -
        (⟪ystar - x, g⟫_ℝ + (1 / τ) * bregmanShiftedBurg P.ξ ystar x) =
        (1 / τ) * bregmanShiftedBurg P.ξ z ystar - ⟪w, z - ystar⟫_ℝ := by
      have hz_split : z - x = (z - ystar) + (ystar - x) := by abel
      have hw_inner : ⟪w, z - ystar⟫_ℝ =
          -⟪z - ystar, g⟫_ℝ -
            (1 / τ) * ⟪shiftedBurgGrad P.ξ ystar - shiftedBurgGrad P.ξ x, z - ystar⟫_ℝ := by
        dsimp [w]
        rw [inner_sub_left, inner_neg_left, inner_smul_left, real_inner_comm (z - ystar) g]
        simp
      have h3 : (1 / τ) * (bregmanShiftedBurg P.ξ z x - bregmanShiftedBurg P.ξ ystar x) =
          (1 / τ) * bregmanShiftedBurg P.ξ z ystar +
            (1 / τ) * ⟪shiftedBurgGrad P.ξ ystar - shiftedBurgGrad P.ξ x, z - ystar⟫_ℝ := by
        rw [h3pt, mul_add]
      rw [hz_split, inner_add_left]
      linarith
    have hpos_diff : 0 < (1 / τ) * bregmanShiftedBurg P.ξ z ystar - ⟪w, z - ystar⟫_ℝ := by
      have h1 : 0 < (1 / τ) * bregmanShiftedBurg P.ξ z ystar := mul_pos (one_div_pos.mpr hτ) hbreg_pos
      linarith
    linarith
  · unfold mdSubproblemObj
    rw [boxIndicator_of_mem hystar_box, boxIndicator_of_notMem hz_box, zero_add,
      EReal.top_add_of_ne_bot (EReal.coe_ne_bot _)]
    exact EReal.coe_lt_top _

/-- Converse direction `(1) ⇒ (4)`: any global minimizer of `mdSubproblemObj P x τ` equals
`T_tau P τ x`. -/
theorem argmin_eq_T_tau (P : ProblemData m n) {τ : ℝ} {x z : E n}
    (hτ : 0 < τ) (hx : x ∈ boxSet n P.a)
    (hden : ∀ j : Fin n, 0 < 1 + τ * (x j + P.ξ) * gradient (FSmooth P) x j)
    (hmin : ∀ w : E n, mdSubproblemObj P x τ z ≤ mdSubproblemObj P x τ w) :
    z = T_tau P τ x := by
  by_contra hne
  have hlt := T_tau_unique_argmin P hτ hx hden z hne
  exact not_lt_of_ge (hmin (T_tau P τ x)) hlt

end MirrorDescentStep

end DeqMdErratum
