← Visual companionIn-app Blueprint viewLean 4 source indexPDFDependency graph

Erratum: Deep Equilibrium Models for Poisson Imaging Inverse Problems via Mirror Descent

5 Monotone Backtracking Mirror Descent — Algorithm 1

Definition 30 Backtracking threshold \(\hat{\tau }\), acceptance criterion, and Algorithm 1 sequence
✓

For \(\gamma \in (0, 1)\), \(\eta \in (0, 1)\), \(\tau _0 {\gt} 0\), and \(x^0 \in L_0(x^0)\), set

\[ \hat{\tau } := \min \! \left\{ \frac{1}{(a + \xi ) G},\; \frac{1 - \gamma }{L_{\beta _1}}\right\} \in (0, \bar{\tau }]. \]

A step size \(\tau {\gt} 0\) is accepted at \(x \in L_0(x^0)\) if \(1 + \tau (x_j + \xi ) \partial _j F(x) {\gt} 0\) for all \(j\), \(T_\tau (x) \in \mathrm{dom}(\Psi )\), and

\[ \Psi (x) - \Psi (T_\tau (x)) \ge \frac{\gamma }{\tau } D_{h_\xi }(T_\tau (x), x). \]

Starting from \((x^0, \tau _{-1}) := (x^0, \tau _0)\), Algorithm 1 sets \(\tau _k := \eta ^{m_k} \tau _{k-1}\) where \(m_k \in \mathbb {N}\) is the smallest nonnegative integer for which \(\tau _k\) is accepted at \(x^k\), and \(x^{k+1} := T_{\tau _k}(x^k)\).

Lemma 31 Acceptance below \(\hat{\tau }\) and finite inner termination
✓

Every \(\tau \in (0, \hat{\tau })\) is accepted at any \(x \in L_0(x^0)\). Consequently, for any \(\tau _{\mathrm{prev}} {\gt} 0\), there exists \(m \in \mathbb {N}\) accepting \(\eta ^m \tau _{\mathrm{prev}}\), and the resulting monotone step sizes satisfy \(\min \{ \tau _0, \eta \hat{\tau }\} \le \tau _k \le \tau _0\) for all \(k \in \mathbb {N}\).

Proof ▶

For \(\tau \in (0, \hat{\tau }) \subseteq (0, \bar{\tau })\), \(\tau L_{\beta _1} \le 1 - \gamma \) gives \(1/\tau - L_{\beta _1} \ge \gamma / \tau \), so Theorem 27 yields acceptance. Since \(\eta ^m \tau _{\mathrm{prev}} \to 0\), backtracking terminates finitely, and if \(m_k \ge 1\) then failure at \(m_k - 1\) implies \(\eta ^{m_k - 1}\tau _{k-1} \ge \hat{\tau }\), hence \(\tau _k \ge \eta \hat{\tau }\).

Theorem 32 Finite stabilization of the backtracking step size
✓
#

The step-size sequence \((\tau _k)_{k \in \mathbb {N}}\) is monotonically nonincreasing and stabilizes in finitely many outer iterations: there exist \(k_{\mathrm{stab}} \in \mathbb {N}\) and \(\tau _\infty {\gt} 0\) such that \(\tau _k = \tau _\infty \) for all \(k \ge k_{\mathrm{stab}}\).

Proof ▶

Every strict decrease multiplies \(\tau _k\) by at most \(\eta {\lt} 1\), whereas \(\tau _k \ge \tau _{\min } := \min \{ \tau _0, \eta \hat{\tau }\} {\gt} 0\) uniformly by Lemma 31. Thus at most \(N_{\max }\) strict drops can occur, forcing eventual constancy.

Theorem 33 Global convergence of Algorithm 1
✓

Assume \(\Psi \) satisfies \(\mathrm{HasKL}(\Psi )\). Then the iterates \((x^k)_{k \in \mathbb {N}}\) and step sizes \((\tau _k)_{k \in \mathbb {N}}\) generated by Algorithm 1 satisfy:

  1. \(\tau _k \downarrow \tau _\infty {\gt} 0\) in finitely many steps, with \(\min \{ \tau _0, \eta \hat{\tau }\} \le \tau _k \le \tau _0\);

  2. \(\sum _{k=0}^\infty \| x^{k+1} - x^k\| {\lt} +\infty \);

  3. \(x^k \to x^\infty \in \mathrm{crit}(\Psi ) \cap L_0(x^0)\), and \(x^\infty = T_{\tau _\infty }(x^\infty )\).

Proof ▶

Acceptance gives \(\Psi (x^{k+1}) \le \Psi (x^k) \le \Psi (x^0)\), keeping \(x^k \in L_0(x^0) \subseteq K_{\beta _0} \subseteq K_{\beta _1}\) for all \(k\). Using \(\tau _k \le \tau _0\) and Lemma 16 yields (H1) with uniform constant \(c_1 = \frac{\gamma / \tau _0}{2(a+\xi )^2} {\gt} 0\). Using the positivity of the accepted denominators together with Theorem 18, Lemma 4, and \(\tau _k \ge \tau _{\min } {\gt} 0\) yields (H2) with \(b = M_{\beta _1} + \frac{1}{\tau _{\min } \xi ^2} {\gt} 0\). Verification of (H3) and Theorem 11 give finite length and \(x^k \to x^\infty \in \mathrm{crit}(\Psi ) \cap L_0(x^0)\), while joint continuity of \((\tau , x) \mapsto T_\tau (x)\) and \(\tau _k \to \tau _\infty \) yield \(x^\infty = T_{\tau _\infty }(x^\infty )\).