import DeqMdErratum.Theorem4

/-!
# Algorithm 1: Monotone Backtracking Shifted-Burg Mirror Descent

This module formalizes Algorithm 1 of the erratum (p. 4):
* Definition of the backtracking threshold `τ_hat := min{1 / ((a + ξ) G), (1 - γ) / L_{β₁}}`.
* Acceptance criterion: `0 < τ`, positive denominators `1 + τ (x_j + ξ) ∂_j F(x) > 0`,
  `T_τ(x) ∈ dom(Ψ)`, and Bregman sufficient decrease `Ψ(x) - Ψ(T_τ(x)) ≥ (γ / τ) D_{h_ξ}(T_τ(x), x)`.
* Proof that any `τ ∈ (0, τ_hat)` is accepted (`acceptStep_of_mem_Ioo_tauHat`), guaranteeing finite
  termination of inner backtracking at every outer iteration and uniform positive lower bound
  `btTau k ≥ min{τ₀, η τ_hat}`.
* Proof that the step size stabilizes in finitely many iterations (`btTau_eventually_const`),
  verifying `(H1)-(H3)` and concluding finite trajectory length and global convergence to
  `x^∞ ∈ crit(Ψ) ∩ L₀` with `x^∞ = T_{τ_∞}(x^∞)` (`algorithm1_backtracking_convergence`).
-/

open Filter Topology
open scoped BigOperators InnerProductSpace

namespace DeqMdErratum

section BacktrackingDefs

variable {m n : ℕ}

/-- Backtracking step-size threshold
`τ_hat := min{1 / ((a + ξ) G), (1 - γ) / L_{β₁}}` (handling `G = 0`). -/
noncomputable def tauHat (P : ProblemData m n) (γ : ℝ) (x0 : E n) : ℝ :=
  if G_const P x0 ≤ 0 then
    (1 - γ) / L_beta P (beta1 P x0)
  else
    min (1 / ((P.a + P.ξ) * G_const P x0)) ((1 - γ) / L_beta P (beta1 P x0))

lemma tauHat_pos (P : ProblemData m n) {γ : ℝ} (hγ : γ ∈ Set.Ioo 0 1) (x0 : E n) :
    0 < tauHat P γ x0 := by
  have h1γ_pos : 0 < 1 - γ := sub_pos.mpr hγ.2
  have hL_pos : 0 < L_beta P (beta1 P x0) := L_beta_pos P (beta1 P x0)
  unfold tauHat
  split_ifs with hG
  · exact div_pos h1γ_pos hL_pos
  · have hG_pos : 0 < G_const P x0 := lt_of_not_ge hG
    have haξ_pos : 0 < P.a + P.ξ := by linarith [P.ha, P.hξ]
    exact lt_min (one_div_pos.mpr (mul_pos haξ_pos hG_pos)) (div_pos h1γ_pos hL_pos)

lemma tauHat_le_tauBar (P : ProblemData m n) {γ : ℝ} (hγ : γ ∈ Set.Ioo 0 1) (x0 : E n) :
    tauHat P γ x0 ≤ tauBar P x0 := by
  have hL_pos : 0 < L_beta P (beta1 P x0) := L_beta_pos P (beta1 P x0)
  have hfrac_le : (1 - γ) / L_beta P (beta1 P x0) ≤ 1 / L_beta P (beta1 P x0) :=
    div_le_div_of_nonneg_right (by linarith [hγ.1]) hL_pos.le
  unfold tauHat tauBar
  split_ifs
  · exact hfrac_le
  · exact min_le_min le_rfl hfrac_le

lemma tauHat_le_one_sub_gamma_div_L (P : ProblemData m n) (γ : ℝ) (x0 : E n) :
    tauHat P γ x0 ≤ (1 - γ) / L_beta P (beta1 P x0) := by
  unfold tauHat
  split_ifs
  · exact le_rfl
  · exact min_le_right _ _

/-- Acceptance condition for a trial step size `τ` at iterate `x` in Algorithm 1. -/
def AcceptStep (P : ProblemData m n) (γ : ℝ) (x : E n) (τ : ℝ) : Prop :=
  0 < τ ∧
  (∀ j : Fin n, 0 < 1 + τ * (x j + P.ξ) * gradient (FSmooth P) x j) ∧
  T_tau P τ x ∈ effectiveDom (Psi P) ∧
  (γ / τ) * bregmanShiftedBurg P.ξ (T_tau P τ x) x ≤
    (Psi P x).toReal - (Psi P (T_tau P τ x)).toReal

/-- Every `τ ∈ (0, τ_hat)` satisfies the Algorithm 1 acceptance criterion for `x ∈ L₀`. -/
lemma acceptStep_of_mem_Ioo_tauHat (P : ProblemData m n) {x0 x : E n} {γ τ : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hγ : γ ∈ Set.Ioo 0 1) (hx : x ∈ L0 P x0) (hτ : τ ∈ Set.Ioo 0 (tauHat P γ x0)) :
    AcceptStep P γ x τ := by
  have hτ_bar : τ ∈ Set.Ioo 0 (tauBar P x0) :=
    ⟨hτ.1, hτ.2.trans_le (tauHat_le_tauBar P hγ x0)⟩
  have h3 := lemma_3 P hx0_box hx0_fin hx hτ_bar
  have hT_dom : T_tau P τ x ∈ effectiveDom (Psi P) := by
    rw [effectiveDom_Psi_eq]
    exact ⟨h3.2.1.1, K_beta_subset_UPos P (beta1 P x0) h3.2.1⟩
  have hL_pos : 0 < L_beta P (beta1 P x0) := L_beta_pos P (beta1 P x0)
  have hτ_le_frac : τ ≤ (1 - γ) / L_beta P (beta1 P x0) :=
    hτ.2.le.trans (tauHat_le_one_sub_gamma_div_L P γ x0)
  have hτL_le : τ * L_beta P (beta1 P x0) ≤ 1 - γ := (le_div_iff₀ hL_pos).mp hτ_le_frac
  have hcoef_le : γ / τ ≤ 1 / τ - L_beta P (beta1 P x0) := by
    have h1 : L_beta P (beta1 P x0) ≤ (1 - γ) / τ := (le_div_iff₀' hτ.1).mpr hτL_le
    have h2 : (1 - γ) / τ = 1 / τ - γ / τ := by ring
    linarith
  have hbreg_nn : 0 ≤ bregmanShiftedBurg P.ξ (T_tau P τ x) x :=
    bregmanShiftedBurg_nonneg (fun j => by linarith [(h3.2.1.1 j).1, P.hξ])
      (fun j => by linarith [(hx.1 j).1, P.hξ])
  have hmul : (γ / τ) * bregmanShiftedBurg P.ξ (T_tau P τ x) x ≤
      (1 / τ - L_beta P (beta1 P x0)) * bregmanShiftedBurg P.ξ (T_tau P τ x) x :=
    mul_le_mul_of_nonneg_right hcoef_le hbreg_nn
  exact ⟨hτ.1, h3.1, hT_dom, hmul.trans h3.2.2.1⟩

/-- Inner backtracking terminates in finitely many reductions `τ_prev ↦ η^m τ_prev`. -/
lemma exists_backtrack_pow (P : ProblemData m n) {x0 x : E n} {γ η τ_prev : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1)
    (hx : x ∈ L0 P x0) (hτ_prev : 0 < τ_prev) :
    ∃ k : ℕ, AcceptStep P γ x (η ^ k * τ_prev) := by
  have hlim : Tendsto (fun k : ℕ => η ^ k * τ_prev) atTop (𝓝 0) := by
    have h0 := tendsto_pow_atTop_nhds_zero_of_lt_one hη.1.le hη.2
    simpa using h0.mul_const τ_prev
  have hev : ∀ᶠ k in atTop, η ^ k * τ_prev < tauHat P γ x0 :=
    hlim.eventually (gt_mem_nhds (tauHat_pos P hγ x0))
  obtain ⟨k, hk⟩ := hev.exists
  have hk_pos : 0 < η ^ k * τ_prev := mul_pos (pow_pos hη.1 k) hτ_prev
  exact ⟨k, acceptStep_of_mem_Ioo_tauHat P hx0_box hx0_fin hγ hx ⟨hk_pos, hk⟩⟩

end BacktrackingDefs

section BacktrackingSequence

variable {m n : ℕ}

/-- State carried across iterations of Algorithm 1, packing the current iterate `x ∈ L₀` and
step size `τ_curr` together with their invariants. -/
structure BtState (P : ProblemData m n) (τ0 γ η : ℝ) (x0 : E n) where
  x : E n
  hx_L0 : x ∈ L0 P x0
  τ_curr : ℝ
  hτ_pos : 0 < τ_curr
  hτ_le : τ_curr ≤ τ0
  hτ_min : min τ0 (η * tauHat P γ x0) ≤ τ_curr

noncomputable def btInitState (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hτ0 : 0 < τ0) :
    BtState P τ0 γ η x0 where
  x := x0
  hx_L0 := ⟨hx0_box, le_rfl⟩
  τ_curr := τ0
  hτ_pos := hτ0
  hτ_le := le_rfl
  hτ_min := min_le_left _ _

noncomputable def btBacktrackCount (P : ProblemData m n) {x0 : E n} {γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1)
    {x : E n} (hx : x ∈ L0 P x0) {τ_prev : ℝ} (hτ_prev : 0 < τ_prev) : ℕ :=
  @Nat.find (fun k => AcceptStep P γ x (η ^ k * τ_prev)) (Classical.decPred _)
    (exists_backtrack_pow P hx0_box hx0_fin hγ hη hx hτ_prev)

lemma btBacktrackCount_spec (P : ProblemData m n) {x0 : E n} {γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1)
    {x : E n} (hx : x ∈ L0 P x0) {τ_prev : ℝ} (hτ_prev : 0 < τ_prev) :
    AcceptStep P γ x
      (η ^ btBacktrackCount P hx0_box hx0_fin hγ hη hx hτ_prev * τ_prev) :=
  @Nat.find_spec (fun k => AcceptStep P γ x (η ^ k * τ_prev)) (Classical.decPred _)
    (exists_backtrack_pow P hx0_box hx0_fin hγ hη hx hτ_prev)

lemma btBacktrackCount_min (P : ProblemData m n) {x0 : E n} {γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1)
    {x : E n} (hx : x ∈ L0 P x0) {τ_prev : ℝ} (hτ_prev : 0 < τ_prev)
    {m' : ℕ} (hm' : m' < btBacktrackCount P hx0_box hx0_fin hγ hη hx hτ_prev) :
    ¬ AcceptStep P γ x (η ^ m' * τ_prev) :=
  @Nat.find_min (fun k => AcceptStep P γ x (η ^ k * τ_prev)) (Classical.decPred _)
    (exists_backtrack_pow P hx0_box hx0_fin hγ hη hx hτ_prev) m' hm'

noncomputable def btNextState (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1)
    (s : BtState P τ0 γ η x0) : BtState P τ0 γ η x0 where
  x := T_tau P (η ^ btBacktrackCount P hx0_box hx0_fin hγ hη s.hx_L0 s.hτ_pos * s.τ_curr) s.x
  τ_curr := η ^ btBacktrackCount P hx0_box hx0_fin hγ hη s.hx_L0 s.hτ_pos * s.τ_curr
  hτ_pos := mul_pos (pow_pos hη.1 _) s.hτ_pos
  hτ_le := by
    have h1 : η ^ btBacktrackCount P hx0_box hx0_fin hγ hη s.hx_L0 s.hτ_pos * s.τ_curr ≤
        1 * s.τ_curr :=
      mul_le_mul_of_nonneg_right (pow_le_one₀ hη.1.le hη.2.le) s.hτ_pos.le
    linarith [s.hτ_le]
  hτ_min := by
    set k := btBacktrackCount P hx0_box hx0_fin hγ hη s.hx_L0 s.hτ_pos
    by_cases hk0 : k = 0
    · simpa [hk0] using s.hτ_min
    · obtain ⟨k', hk'⟩ := Nat.exists_eq_succ_of_ne_zero hk0
      have hfail : ¬ AcceptStep P γ s.x (η ^ k' * s.τ_curr) :=
        btBacktrackCount_min P hx0_box hx0_fin hγ hη s.hx_L0 s.hτ_pos (by omega)
      have hk'_pos : 0 < η ^ k' * s.τ_curr := mul_pos (pow_pos hη.1 k') s.hτ_pos
      have hge_hat : tauHat P γ x0 ≤ η ^ k' * s.τ_curr := by
        by_contra hlt
        push_neg at hlt
        exact hfail (acceptStep_of_mem_Ioo_tauHat P hx0_box hx0_fin hγ s.hx_L0 ⟨hk'_pos, hlt⟩)
      have hge_mul : η * tauHat P γ x0 ≤ η ^ (k' + 1) * s.τ_curr := by
        calc
          η * tauHat P γ x0 ≤ η * (η ^ k' * s.τ_curr) :=
            mul_le_mul_of_nonneg_left hge_hat hη.1.le
          _ = η ^ (k' + 1) * s.τ_curr := by rw [pow_succ']; ring
      show min τ0 (η * tauHat P γ x0) ≤ η ^ k * s.τ_curr
      rw [hk']
      exact (min_le_right _ _).trans hge_mul
  hx_L0 := by
    set τ_new := η ^ btBacktrackCount P hx0_box hx0_fin hγ hη s.hx_L0 s.hτ_pos * s.τ_curr
    set x_new := T_tau P τ_new s.x
    have haccept : AcceptStep P γ s.x τ_new :=
      btBacktrackCount_spec P hx0_box hx0_fin hγ hη s.hx_L0 s.hτ_pos
    have hτ_new_pos : 0 < τ_new := mul_pos (pow_pos hη.1 _) s.hτ_pos
    have hx_dom : s.x ∈ effectiveDom (Psi P) := by
      rw [effectiveDom_Psi_eq]
      exact ⟨s.hx_L0.1, K_beta_subset_UPos P (beta0 P x0)
        (L0_subset_K_beta0 P hx0_box hx0_fin s.hx_L0)⟩
    have hx_new_dom : x_new ∈ effectiveDom (Psi P) := haccept.2.2.1
    have hx_new_box : x_new ∈ boxSet n P.a := (effectiveDom_Psi_eq P ▸ hx_new_dom).1
    have hbreg_nn : 0 ≤ bregmanShiftedBurg P.ξ x_new s.x :=
      bregmanShiftedBurg_nonneg (fun j => by linarith [(hx_new_box j).1, P.hξ])
        (fun j => by linarith [(s.hx_L0.1 j).1, P.hξ])
    have hcoef_nn : 0 ≤ γ / τ_new := div_nonneg hγ.1.le hτ_new_pos.le
    have hreal_le : (Psi P x_new).toReal ≤ (Psi P s.x).toReal := by
      linarith [haccept.2.2.2, mul_nonneg hcoef_nn hbreg_nn]
    have hPsi_le : Psi P x_new ≤ Psi P s.x := by
      rw [← EReal.coe_toReal_of_mem_effectiveDom hx_new_dom,
        ← EReal.coe_toReal_of_mem_effectiveDom hx_dom, EReal.coe_le_coe_iff]
      exact hreal_le
    exact ⟨hx_new_box, hPsi_le.trans s.hx_L0.2⟩

/-- Sequence of Algorithm 1 states. -/
noncomputable def btStateSeq (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ0 : 0 < τ0) (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1) :
    ℕ → BtState P τ0 γ η x0
  | 0 => btInitState P hx0_box hτ0
  | k + 1 => btNextState P hx0_box hx0_fin hγ hη (btStateSeq P hx0_box hx0_fin hτ0 hγ hη k)

/-- Outer iterates `x^k` of Algorithm 1. -/
noncomputable def btIter (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ0 : 0 < τ0) (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1) (k : ℕ) : E n :=
  (btStateSeq P hx0_box hx0_fin hτ0 hγ hη k).x

/-- Step sizes `τ_k` accepted at outer iteration `k` (`x^{k+1} = T_{τ_k}(x^k)`). -/
noncomputable def btTau (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ0 : 0 < τ0) (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1) (k : ℕ) : ℝ :=
  (btStateSeq P hx0_box hx0_fin hτ0 hγ hη (k + 1)).τ_curr

lemma btIter_mem_L0 (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ0 : 0 < τ0) (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1) (k : ℕ) :
    btIter P hx0_box hx0_fin hτ0 hγ hη k ∈ L0 P x0 :=
  (btStateSeq P hx0_box hx0_fin hτ0 hγ hη k).hx_L0

lemma btIter_succ_eq (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ0 : 0 < τ0) (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1) (k : ℕ) :
    btIter P hx0_box hx0_fin hτ0 hγ hη (k + 1) =
      T_tau P (btTau P hx0_box hx0_fin hτ0 hγ hη k) (btIter P hx0_box hx0_fin hτ0 hγ hη k) :=
  rfl

lemma btTau_accept (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ0 : 0 < τ0) (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1) (k : ℕ) :
    AcceptStep P γ (btIter P hx0_box hx0_fin hτ0 hγ hη k)
      (btTau P hx0_box hx0_fin hτ0 hγ hη k) :=
  btBacktrackCount_spec P hx0_box hx0_fin hγ hη
    (btStateSeq P hx0_box hx0_fin hτ0 hγ hη k).hx_L0
    (btStateSeq P hx0_box hx0_fin hτ0 hγ hη k).hτ_pos

lemma btTau_bounds (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ0 : 0 < τ0) (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1) (k : ℕ) :
    min τ0 (η * tauHat P γ x0) ≤ btTau P hx0_box hx0_fin hτ0 hγ hη k ∧
      btTau P hx0_box hx0_fin hτ0 hγ hη k ≤ τ0 := by
  let s := btStateSeq P hx0_box hx0_fin hτ0 hγ hη (k + 1)
  exact ⟨s.hτ_min, s.hτ_le⟩

lemma btTau_succ_cases (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ0 : 0 < τ0) (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1) (k : ℕ) :
    btTau P hx0_box hx0_fin hτ0 hγ hη (k + 1) ≤ btTau P hx0_box hx0_fin hτ0 hγ hη k ∧
      (btTau P hx0_box hx0_fin hτ0 hγ hη (k + 1) = btTau P hx0_box hx0_fin hτ0 hγ hη k ∨
        btTau P hx0_box hx0_fin hτ0 hγ hη (k + 1) ≤ η * btTau P hx0_box hx0_fin hτ0 hγ hη k) := by
  let s := btStateSeq P hx0_box hx0_fin hτ0 hγ hη (k + 1)
  let m_bt := btBacktrackCount P hx0_box hx0_fin hγ hη s.hx_L0 s.hτ_pos
  have hτ_eq : btTau P hx0_box hx0_fin hτ0 hγ hη (k + 1) = η ^ m_bt * s.τ_curr := rfl
  have hsτ_eq : s.τ_curr = btTau P hx0_box hx0_fin hτ0 hγ hη k := rfl
  have hle : btTau P hx0_box hx0_fin hτ0 hγ hη (k + 1) ≤ btTau P hx0_box hx0_fin hτ0 hγ hη k := by
    rw [hτ_eq, hsτ_eq]
    have h1 := mul_le_mul_of_nonneg_right (pow_le_one₀ (n := m_bt) hη.1.le hη.2.le) s.hτ_pos.le
    simpa [hsτ_eq] using h1
  refine ⟨hle, ?_⟩
  by_cases hm0 : m_bt = 0
  · left; simp [hτ_eq, hm0, hsτ_eq]
  · right
    obtain ⟨m', hm'⟩ := Nat.exists_eq_succ_of_ne_zero hm0
    have hpow_le : η ^ m_bt ≤ η := by
      rw [hm', pow_succ']
      calc
        η * η ^ m' ≤ η * 1 := mul_le_mul_of_nonneg_left (pow_le_one₀ hη.1.le hη.2.le) hη.1.le
        _ = η := mul_one η
    rw [hτ_eq, hsτ_eq]
    calc
      η ^ m_bt * btTau P hx0_box hx0_fin hτ0 hγ hη k
          ≤ η * btTau P hx0_box hx0_fin hτ0 hγ hη k :=
        mul_le_mul_of_nonneg_right hpow_le s.hτ_pos.le

lemma btTau_antitone (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ0 : 0 < τ0) (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1) :
    Antitone (btTau P hx0_box hx0_fin hτ0 hγ hη) :=
  antitone_nat_of_succ_le fun k =>
    (btTau_succ_cases P hx0_box hx0_fin hτ0 hγ hη k).1

/-- Any positive sequence bounded below by `τ_min > 0` whose strict decreases multiply by at most
`η ∈ (0, 1)` becomes constant after finitely many steps. -/
lemma eventually_const_of_geometric_drops {τ : ℕ → ℝ} {τ_min η : ℝ}
    (hτ_min : 0 < τ_min) (hη : η ∈ Set.Ioo 0 1)
    (hlb : ∀ k, τ_min ≤ τ k)
    (hstep : ∀ k, τ (k + 1) = τ k ∨ τ (k + 1) ≤ η * τ k) :
    ∃ k_stab : ℕ, ∀ k ≥ k_stab, τ k = τ k_stab := by
  classical
  let d : ℕ → ℕ := fun k => ((Finset.range k).filter (fun i => τ (i + 1) ≠ τ i)).card
  have hd_mono : Monotone d := by
    intro a b hab
    exact Finset.card_le_card (Finset.filter_subset_filter _ (Finset.range_mono hab))
  have hd_le_pow : ∀ k : ℕ, τ k ≤ η ^ d k * τ 0 := by
    intro k
    induction k with
    | zero => simp [d]
    | succ k ih =>
      by_cases heq : τ (k + 1) = τ k
      · have hd_eq : d (k + 1) = d k := by
          dsimp [d]
          rw [Finset.range_add_one, Finset.filter_insert, if_neg (not_not.mpr heq)]
        rw [heq, hd_eq]
        exact ih
      · have hd_eq : d (k + 1) = d k + 1 := by
          dsimp [d]
          rw [Finset.range_add_one, Finset.filter_insert, if_pos heq,
            Finset.card_insert_of_notMem (by simp)]
        have hdrop : τ (k + 1) ≤ η * τ k := (hstep k).resolve_left heq
        rw [hd_eq, pow_succ']
        calc
          τ (k + 1) ≤ η * τ k := hdrop
          _ ≤ η * (η ^ d k * τ 0) := mul_le_mul_of_nonneg_left ih hη.1.le
          _ = η * η ^ d k * τ 0 := by ring
  have hτ0_pos : 0 < τ 0 := lt_of_lt_of_le hτ_min (hlb 0)
  have hlim : Tendsto (fun N : ℕ => η ^ N * τ 0) atTop (𝓝 0) := by
    simpa using (tendsto_pow_atTop_nhds_zero_of_lt_one hη.1.le hη.2).mul_const (τ 0)
  obtain ⟨N_max, hN_max⟩ := (hlim.eventually (gt_mem_nhds hτ_min)).exists
  have hd_bdd : ∀ k : ℕ, d k < N_max := by
    intro k
    by_contra hge
    push_neg at hge
    have hpow : η ^ d k ≤ η ^ N_max := pow_le_pow_of_le_one hη.1.le hη.2.le hge
    have h1 : τ_min ≤ τ k := hlb k
    have h2 : τ k ≤ η ^ d k * τ 0 := hd_le_pow k
    have h3 : η ^ d k * τ 0 ≤ η ^ N_max * τ 0 := mul_le_mul_of_nonneg_right hpow hτ0_pos.le
    linarith
  have hne : (Set.range d).Nonempty := ⟨d 0, 0, rfl⟩
  have hBdd : BddAbove (Set.range d) := ⟨N_max, by rintro _ ⟨k, rfl⟩; exact (hd_bdd k).le⟩
  obtain ⟨k_stab, hk_stab⟩ := Nat.sSup_mem hne hBdd
  have hd_const : ∀ k ≥ k_stab, d k = d k_stab := by
    intro k hk
    exact le_antisymm (hk_stab ▸ le_csSup hBdd ⟨k, rfl⟩) (hd_mono hk)
  refine ⟨k_stab, fun k hk => ?_⟩
  induction k, hk using Nat.le_induction with
  | base => rfl
  | succ m hm ih =>
    have hdm : d (m + 1) = d m := by
      rw [hd_const (m + 1) (Nat.le_succ_of_le hm), hd_const m hm]
    by_contra hne_step
    have hne_m : τ (m + 1) ≠ τ m := by rwa [ih]
    have hdm' : d (m + 1) = d m + 1 := by
      dsimp [d]
      rw [Finset.range_add_one, Finset.filter_insert, if_pos hne_m,
        Finset.card_insert_of_notMem (by simp)]
    omega

/-- Finite stabilization of the step size in Algorithm 1: `∃ k_stab τ_inf, ...`. -/
theorem btTau_eventually_const (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ0 : 0 < τ0) (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1) :
    ∃ k_stab : ℕ, ∃ τ_inf : ℝ,
      min τ0 (η * tauHat P γ x0) ≤ τ_inf ∧ τ_inf ≤ τ0 ∧ 0 < τ_inf ∧
      ∀ k ≥ k_stab, btTau P hx0_box hx0_fin hτ0 hγ hη k = τ_inf := by
  set τ_min : ℝ := min τ0 (η * tauHat P γ x0)
  have hτ_min_pos : 0 < τ_min := lt_min hτ0 (mul_pos hη.1 (tauHat_pos P hγ x0))
  obtain ⟨k_stab, hk_stab⟩ := eventually_const_of_geometric_drops hτ_min_pos hη
    (fun k => (btTau_bounds P hx0_box hx0_fin hτ0 hγ hη k).1)
    (fun k => (btTau_succ_cases P hx0_box hx0_fin hτ0 hγ hη k).2)
  set τ_inf := btTau P hx0_box hx0_fin hτ0 hγ hη k_stab
  have hbounds := btTau_bounds P hx0_box hx0_fin hτ0 hγ hη k_stab
  exact ⟨k_stab, τ_inf, hbounds.1, hbounds.2, lt_of_lt_of_le hτ_min_pos hbounds.1, hk_stab⟩

/-- Main convergence theorem for Algorithm 1 (Monotone Backtracking Shifted-Burg Mirror Descent):
Assuming `HasKL (Psi P)`, the backtracking sequence stabilizes in step size after finitely many
iterations, satisfies Theorem A.8's `(H1)-(H3)`, has finite length `∑ ‖x^{k+1} - x^k‖ < ∞`, and
converges to a critical point `x^∞ ∈ crit(Ψ) ∩ L₀` which is a fixed point `x^∞ = T_{τ_∞}(x^∞)`. -/
theorem algorithm1_backtracking_convergence (P : ProblemData m n) {x0 : E n} {τ0 γ η : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ0 : 0 < τ0) (hγ : γ ∈ Set.Ioo 0 1) (hη : η ∈ Set.Ioo 0 1)
    (hKL : HasKL (Psi P)) :
    let x := btIter P hx0_box hx0_fin hτ0 hγ hη
    let τ := btTau P hx0_box hx0_fin hτ0 hγ hη
    Antitone τ ∧
      (∀ k, min τ0 (η * tauHat P γ x0) ≤ τ k ∧ τ k ≤ τ0) ∧
      (∃ k_stab : ℕ, ∃ τ_inf : ℝ, 0 < τ_inf ∧ ∀ k ≥ k_stab, τ k = τ_inf) ∧
      Summable (fun k => ‖x (k + 1) - x k‖) ∧
      ∃ x_inf : E n, Tendsto x atTop (𝓝 x_inf) ∧
        x_inf ∈ crit (Psi P) ∧ x_inf ∈ L0 P x0 ∧
        ∃ τ_inf : ℝ, 0 < τ_inf ∧ Tendsto τ atTop (𝓝 τ_inf) ∧ x_inf = T_tau P τ_inf x_inf := by
  dsimp only
  set x := btIter P hx0_box hx0_fin hτ0 hγ hη
  set τ := btTau P hx0_box hx0_fin hτ0 hγ hη
  have hx_L0 : ∀ k, x k ∈ L0 P x0 := btIter_mem_L0 P hx0_box hx0_fin hτ0 hγ hη
  have hx_dom : ∀ k, x k ∈ effectiveDom (Psi P) := by
    intro k
    rw [effectiveDom_Psi_eq]
    exact ⟨(hx_L0 k).1, K_beta_subset_UPos P (beta0 P x0)
      (L0_subset_K_beta0 P hx0_box hx0_fin (hx_L0 k))⟩
  set τ_min : ℝ := min τ0 (η * tauHat P γ x0)
  have hτ_min_pos : 0 < τ_min := lt_min hτ0 (mul_pos hη.1 (tauHat_pos P hγ x0))
  have haξ_pos : 0 < P.a + P.ξ := by linarith [P.ha, P.hξ]
  have hξ_pos : 0 < P.ξ := P.hξ
  set c₁ : ℝ := (γ / τ0) / (2 * (P.a + P.ξ) ^ 2)
  have hc₁_pos : 0 < c₁ :=
    div_pos (div_pos hγ.1 hτ0) (mul_pos zero_lt_two (sq_pos_of_pos haξ_pos))
  set b : ℝ := M_beta P (beta1 P x0) + 1 / (τ_min * P.ξ ^ 2)
  have hb_pos : 0 < b := add_pos (M_beta_pos P (beta1 P x0))
    (one_div_pos.mpr (mul_pos hτ_min_pos (sq_pos_of_pos hξ_pos)))
  have hH1 : ∀ k, Psi P (x (k + 1)) + ((c₁ * ‖x (k + 1) - x k‖ ^ 2 : ℝ) : EReal) ≤ Psi P (x k) := by
    intro k
    have hacc := btTau_accept P hx0_box hx0_fin hτ0 hγ hη k
    have hbounds := btTau_bounds P hx0_box hx0_fin hτ0 hγ hη k
    have hτk_pos : 0 < τ k := hacc.1
    have hdiv_ge : γ / τ0 ≤ γ / τ k := div_le_div_of_nonneg_left hγ.1.le hτk_pos hbounds.2
    have hbreg_ge : (1 / (2 * (P.a + P.ξ) ^ 2)) * ‖x (k + 1) - x k‖ ^ 2 ≤
        bregmanShiftedBurg P.ξ (x (k + 1)) (x k) :=
      bregmanShiftedBurg_ge_norm_sq P.hξ (hx_L0 (k + 1)).1 (hx_L0 k).1
    have hc₁_le : c₁ * ‖x (k + 1) - x k‖ ^ 2 ≤
        (γ / τ k) * bregmanShiftedBurg P.ξ (x (k + 1)) (x k) := by
      have h1 : (γ / τ0) * ((1 / (2 * (P.a + P.ξ) ^ 2)) * ‖x (k + 1) - x k‖ ^ 2) ≤
          (γ / τ k) * bregmanShiftedBurg P.ξ (x (k + 1)) (x k) :=
        mul_le_mul hdiv_ge hbreg_ge
          (mul_nonneg (by positivity) (sq_nonneg _)) (div_pos hγ.1 hτk_pos).le
      have heq : (γ / τ0) * ((1 / (2 * (P.a + P.ξ) ^ 2)) * ‖x (k + 1) - x k‖ ^ 2) =
          c₁ * ‖x (k + 1) - x k‖ ^ 2 := by
        dsimp [c₁]; ring
      linarith
    have hacc_desc : (γ / τ k) * bregmanShiftedBurg P.ξ (x (k + 1)) (x k) ≤
        (Psi P (x k)).toReal - (Psi P (x (k + 1))).toReal := hacc.2.2.2
    have hreal_le : (Psi P (x (k + 1))).toReal + c₁ * ‖x (k + 1) - x k‖ ^ 2 ≤
        (Psi P (x k)).toReal := by
      linarith [hacc_desc]
    rw [← EReal.coe_toReal_of_mem_effectiveDom (hx_dom (k + 1)),
      ← EReal.coe_toReal_of_mem_effectiveDom (hx_dom k), ← EReal.coe_add, EReal.coe_le_coe_iff]
    exact hreal_le
  have hH2 : ∀ k, ∃ ω ∈ limitingSubdiff (Psi P) (x (k + 1)), ‖ω‖ ≤ b * ‖x (k + 1) - x k‖ := by
    intro k
    have hacc := btTau_accept P hx0_box hx0_fin hτ0 hγ hη k
    have hbounds := btTau_bounds P hx0_box hx0_fin hτ0 hγ hη k
    have hτk_pos : 0 < τ k := hacc.1
    have hden := hacc.2.1
    set ω : E n := gradient (FSmooth P) (x (k + 1)) - gradient (FSmooth P) (x k) +
      (1 / τ k) • (shiftedBurgGrad P.ξ (x k) - shiftedBurgGrad P.ξ (x (k + 1)))
    have hx_K1 : x k ∈ K_beta P (beta1 P x0) :=
      K_beta_mono P (by dsimp [beta1]; linarith) (L0_subset_K_beta0 P hx0_box hx0_fin (hx_L0 k))
    have hx1_K1 : x (k + 1) ∈ K_beta P (beta1 P x0) :=
      K_beta_mono P (by dsimp [beta1]; linarith) (L0_subset_K_beta0 P hx0_box hx0_fin (hx_L0 (k + 1)))
    have hsub_mem : ω ∈ limitingSubdiff (Psi P) (x (k + 1)) := by
      have hV_open : IsOpen (UPos P ∩ P.U_R) := (isOpen_UPos P).inter P.hU_R_open
      have hx1_V : x (k + 1) ∈ UPos P ∩ P.U_R := K_beta_subset_open P (beta1 P x0) hx1_K1
      have hC1 : ContDiffOn ℝ 1 (FSmooth P) (UPos P ∩ P.U_R) :=
        (FSmooth_contDiffOn_open P).of_le (by norm_num)
      have hPsi_eq : ∀ y ∈ UPos P ∩ P.U_R, Psi P y = (FSmooth P y : EReal) + boxIndicator n P.a y :=
        fun y hy => Psi_eq_FSmooth_add_boxIndicator_on_UPos P hy.1
      rw [limitingSubdiff_add_smooth_on_nhds hV_open hx1_V hC1 (boxIndicator_isProper P.ha.le) hPsi_eq]
      have hω_sub_eq : ω - gradient (FSmooth P) (x (k + 1)) =
          -gradient (FSmooth P) (x k) -
            (1 / τ k) • (shiftedBurgGrad P.ξ (x (k + 1)) - shiftedBurgGrad P.ξ (x k)) := by
        dsimp [ω]
        rw [← neg_sub (shiftedBurgGrad P.ξ (x (k + 1))) (shiftedBurgGrad P.ξ (x k)), smul_neg]
        abel
      have hstep : x (k + 1) = T_tau P (τ k) (x k) :=
        btIter_succ_eq P hx0_box hx0_fin hτ0 hγ hη k
      rw [hω_sub_eq, hstep]
      exact T_tau_optimality_cond P hτk_pos (hx_L0 k).1 hden
    have hω_norm : ‖ω‖ ≤ b * ‖x (k + 1) - x k‖ := by
      have hF_lip := grad_FSmooth_norm_sub_le P (beta1 P x0) hx1_K1 hx_K1
      have hh_lip := shiftedBurgGrad_lipschitzOn_box P.hξ (hx_L0 k).1 (hx_L0 (k + 1)).1
      rw [norm_sub_rev (x k) (x (k + 1))] at hh_lip
      have htri : ‖ω‖ ≤ ‖gradient (FSmooth P) (x (k + 1)) - gradient (FSmooth P) (x k)‖ +
          ‖(1 / τ k) • (shiftedBurgGrad P.ξ (x k) - shiftedBurgGrad P.ξ (x (k + 1)))‖ :=
        norm_add_le _ _
      have hsmul : ‖(1 / τ k) • (shiftedBurgGrad P.ξ (x k) - shiftedBurgGrad P.ξ (x (k + 1)))‖ ≤
          (1 / (τ k * P.ξ ^ 2)) * ‖x (k + 1) - x k‖ := by
        rw [norm_smul, Real.norm_of_nonneg (one_div_nonneg.mpr hτk_pos.le)]
        calc
          1 / τ k * ‖shiftedBurgGrad P.ξ (x k) - shiftedBurgGrad P.ξ (x (k + 1))‖
              ≤ 1 / τ k * ((1 / P.ξ ^ 2) * ‖x (k + 1) - x k‖) :=
            mul_le_mul_of_nonneg_left hh_lip (one_div_nonneg.mpr hτk_pos.le)
          _ = (1 / (τ k * P.ξ ^ 2)) * ‖x (k + 1) - x k‖ := by ring
      have hinv_le : 1 / (τ k * P.ξ ^ 2) ≤ 1 / (τ_min * P.ξ ^ 2) := by
        refine one_div_le_one_div_of_le (mul_pos hτ_min_pos (sq_pos_of_pos hξ_pos)) ?_
        exact mul_le_mul_of_nonneg_right hbounds.1 (sq_nonneg _)
      have hmul_inv : (1 / (τ k * P.ξ ^ 2)) * ‖x (k + 1) - x k‖ ≤
          (1 / (τ_min * P.ξ ^ 2)) * ‖x (k + 1) - x k‖ :=
        mul_le_mul_of_nonneg_right hinv_le (norm_nonneg _)
      dsimp [b]
      linarith
    exact ⟨ω, hsub_mem, hω_norm⟩
  have hH3 : ∀ x_bar ψ, StrictMono ψ →
      Tendsto (x ∘ ψ) atTop (𝓝 x_bar) →
      Tendsto (fun j => Psi P (x (ψ j))) atTop (𝓝 (Psi P x_bar)) :=
    fun _x_bar _ψ hψ hlim => Psi_tendsto_of_mem_L0 P hx0_box hx0_fin hx_L0 hψ hlim
  obtain ⟨hsumm, x_inf, hlim, hcrit⟩ := theorem_A8 (Psi_isProper P) (Psi_lowerSemicontinuous P)
    (Psi_bddBelow P) hKL (hx_dom 0) (L0_isBounded P hx_L0) hc₁_pos hH1 hb_pos hH2 hH3
  have hx_inf_L0 : x_inf ∈ L0 P x0 :=
    (L0_isClosed P x0).mem_of_tendsto hlim (Eventually.of_forall hx_L0)
  obtain ⟨k_stab, τ_inf, _, _, hτ_inf_pos, hτ_stab⟩ :=
    btTau_eventually_const P hx0_box hx0_fin hτ0 hγ hη
  have hτ_tendsto : Tendsto τ atTop (𝓝 τ_inf) :=
    tendsto_atTop_of_eventually_const hτ_stab
  have hfix : x_inf = T_tau P τ_inf x_inf :=
    T_tau_fixed_point_of_tendsto P hx0_box hx0_fin hx_L0
      (btIter_succ_eq P hx0_box hx0_fin hτ0 hγ hη) hτ_tendsto hlim
  refine ⟨btTau_antitone P hx0_box hx0_fin hτ0 hγ hη,
    btTau_bounds P hx0_box hx0_fin hτ0 hγ hη,
    ⟨k_stab, τ_inf, hτ_inf_pos, hτ_stab⟩,
    hsumm, x_inf, hlim, hcrit, hx_inf_L0, τ_inf, hτ_inf_pos, hτ_tendsto, hfix⟩

end BacktrackingSequence

end DeqMdErratum
