- Boxes
- definitions
- Ellipses
- theorems and lemmas
- Blue border
- the statement of this result is ready to be formalized; all prerequisites are done
- Orange border
- the statement of this result is not ready to be formalized; the blueprint needs more work
- Blue background
- the proof of this result is ready to be formalized; all prerequisites are done
- Green border
- the statement of this result is formalized
- Green background
- the proof of this result is formalized
- Dark green background
- the proof of this result and all its ancestors are formalized
- Dark green border
- this is in Mathlib
For \(\gamma \in (0, 1)\), \(\eta \in (0, 1)\), \(\tau _0 {\gt} 0\), and \(x^0 \in L_0(x^0)\), set
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
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)\).
For \(\eta {\gt} 0\), a function \(\varphi : \mathbb {R}\to \mathbb {R}\) is a desingularizing function in \(\Phi _\eta \) if \(\varphi (0) = 0\), \(\varphi \) is continuous on \([0, \eta )\), \(C^1\) and concave on \((0, \eta )\), and satisfies \(\varphi '(s) {\gt} 0\) on \((0, \eta )\).
For \(f : \mathcal{E}_n \to (-\infty , +\infty ]\), the effective domain is
The function \(f\) is proper if \(\mathrm{dom}(f) \ne \emptyset \) and \(f(x) \ne -\infty \) for all \(x \in \mathcal{E}_n\).
A proper extended-real function \(f\) satisfies the KŁ property at \(\bar{x} \in \mathrm{dom}(\partial f)\) if there exist \(\eta {\gt} 0\), a neighborhood \(U\) of \(\bar{x}\), and \(\varphi \in \Phi _\eta \) such that for every \(x \in U\) with \(f(\bar{x}) {\lt} f(x) {\lt} f(\bar{x}) + \eta \),
We say \(f\) satisfies the KŁ property (\(\mathrm{HasKL}(f)\)) if it has the KŁ property at every \(\bar{x} \in \mathrm{dom}(\partial f)\).
For \(\beta \in \mathbb {R}\), define
The \(\omega \)-limit set \(\omega (x^0)\) of a sequence \((x_k)_{k \in \mathbb {N}}\) in \(\mathcal{E}_n\) is the set of all cluster points \(\bar{x}\) for which there exists a strictly increasing extraction \(\psi : \mathbb {N}\to \mathbb {N}\) with \(x_{\psi (j)} \to \bar{x}\).
Let \(a {\gt} 0\), \(\xi {\gt} 0\), \(y \in \mathbb {R}^m_{\ge 0}\) (zero counts allowed), \(A \in \mathbb {R}^{m \times n}_{\ge 0}\) with every row nonzero, and \(R_\theta : \mathcal{E}_n \to \mathbb {R}\) of class \(C^2\) on an open neighborhood \(U_R \supseteq [0, a]^n\). Set \(C := [0, a]^n\),
with \(0 \log (0/u) := 0\) (even for \(u = 0\)), and \(\Psi (x) := \mathrm{KL}(y, Ax) + R_\theta (x) + \iota _{[0, a]^n}(x)\). Define the open positive-observation set \(U_+ := \{ x \in \mathcal{E}_n \mid \forall i,\; y_i {\gt} 0 \implies (Ax)_i {\gt} 0\} \) and the boundary singular set
The classical Burg entropy on \(\mathcal{E}_n\) is \(h(x) := -\sum _{j=1}^n \log x_j\) on \(\mathbb {R}^n_{{\gt}0}\) (and \(+\infty \) otherwise), with \((\nabla h(x))_j = -1/x_j\). For shift \(\xi {\gt} 0\), the shifted Burg entropy and Bregman divergence are
Let \(f : \mathcal{E}_n \to (-\infty , +\infty ]\) and \(x \in \mathrm{dom}(f)\). A vector \(v \in \mathcal{E}_n\) belongs to the Fréchet subdifferential \(\widehat{\partial } f(x)\) if
The limiting (Mordukhovich) subdifferential \(\partial f(x)\) is the set of \(v \in \mathcal{E}_n\) for which there exist sequences \(x_k \to x\) and \(v_k \in \widehat{\partial } f(x_k)\) with \(f(x_k) \to f(x)\) and \(v_k \to v\). Critical points are defined by \(\mathrm{crit}(f) := \{ x \in \mathcal{E}_n \mid 0 \in \partial f(x)\} \). For a subset \(C \subseteq \mathcal{E}_n\) and \(x \in C\), the convex normal cone is
Given an initial point \(x^0 \in [0, a]^n\) with \(\Psi (x^0) {\lt} +\infty \), define
and for \(\beta \in \mathbb {R}\),
For step size \(\tau {\gt} 0\) and \(x \in [0, a]^n\), the shifted-Burg Mirror Descent subproblem objective is
We define the operator \(T_\tau \) coordinatewise by
Set \(G := \sup _{x \in K_{\beta _0}} \| \nabla F(x)\| _\infty \ge 0\) and
(taking \(\bar{\tau } := 1 / L_{\beta _1}\) if \(G = 0\)).
With \(A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\), \(R_\theta \equiv 0\), \(a \ge 1\), \(y \in \mathbb {R}^2_{{\gt}0}\), and \(x^0 = (0, 1)\), we have \(\Psi (x^0) {\lt} +\infty \) and every \(x_t := (t, 1)\) for \(t \in (0, 1]\) lies in \(L_0(x^0) \cap (0, a]^n\) with \(t \mapsto \Psi (x_t)\) bounded above on \((0, 1]\). Yet \(\| \nabla h(x_t) - \nabla h(x_1)\| = |1 - 1/t| \to +\infty \) while \(\| x_t - x_1\| = 1 - t \le 1\), so \(\nabla h\) is not Lipschitz continuous on \(\mathrm{dom}(h) \cap L_0(x^0)\).
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}\).
We have \(\mathrm{dom}(\Psi ) = [0, a]^n \cap U_+\), \(\overline{\mathrm{dom}(\Psi )} = [0, a]^n\), and \(\overline{\mathrm{dom}(\Psi )} \setminus \mathrm{dom}(\Psi ) = \mathcal{S}\).
\(F\) is \(C^2\) on the open set \(U_+ \cap U_R \supseteq K_\beta \), and \(\nabla F\) is \(M_\beta \)-Lipschitz on the compact convex set \(K_\beta \):
For every \(\beta \in \mathbb {R}\), \(K_\beta \) is convex, closed, and compact, and \(L_0(x^0) \subseteq K_{\beta _0}\).
For every \(\beta \in \mathbb {R}\), there exists \(c_\beta {\gt} 0\) such that \((Ax)_i \ge c_\beta \) for all \(x \in K_\beta \) and every \(i\) with \(y_i {\gt} 0\). Consequently, \(K_\beta \subseteq U_+ \cap U_R\) and \(K_\beta \cap \mathcal{S} = \emptyset \).
If \((x_k)_{k \in \mathbb {N}}\) is bounded, then \(\omega (x^0)\) is nonempty, closed, and compact, and \(\operatorname {dist}(x_k, \omega (x^0)) \to 0\) as \(k \to \infty \).
\(\Psi \) is proper, lower semicontinuous on \(\mathcal{E}_n\), and bounded below on \(\mathcal{E}_n\) by \(\inf _{z \in [0, a]^n} R_\theta (z)\).
For all \(u, x \in [0, a]^n\),
Suppose \(U \subseteq \mathcal{E}_n\) is open, \(x \in U\), \(g : \mathcal{E}_n \to \mathbb {R}\) is \(C^1\) on \(U\), \(h : \mathcal{E}_n \to (-\infty , +\infty ]\) is proper, and \(f = g + h\) on \(U\). Then
Let \(f : \mathcal{E}_n \to (-\infty , +\infty ]\) be proper, lower semicontinuous, bounded below, and satisfy the KŁ property. Let \((x_k)_{k \in \mathbb {N}}\) be a bounded sequence starting at \(x_0 \in \mathrm{dom}(f)\) satisfying for constants \(c_1, b {\gt} 0\):
\(f(x_{k+1}) + c_1 \| x_{k+1} - x_k\| ^2 \le f(x_k)\) for all \(k \in \mathbb {N}\);
there exists \(\omega _{k+1} \in \partial f(x_{k+1})\) with \(\| \omega _{k+1}\| \le b \| x_{k+1} - x_k\| \) for all \(k \in \mathbb {N}\);
whenever \(x_{\psi (j)} \to \bar{x}\), we have \(f(x_{\psi (j)}) \to f(\bar{x})\).
Then \(\sum _{k=0}^\infty \| x_{k+1} - x_k\| {\lt} +\infty \), and \((x_k)\) converges to a critical point \(x_\infty \in \mathrm{crit}(f)\).
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:
\(\tau _k \downarrow \tau _\infty {\gt} 0\) in finitely many steps, with \(\min \{ \tau _0, \eta \hat{\tau }\} \le \tau _k \le \tau _0\);
\(\sum _{k=0}^\infty \| x^{k+1} - x^k\| {\lt} +\infty \);
\(x^k \to x^\infty \in \mathrm{crit}(\Psi ) \cap L_0(x^0)\), and \(x^\infty = T_{\tau _\infty }(x^\infty )\).
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}}\).
For every \(\beta \in \mathbb {R}\), the function \(L_\beta h_\xi - F\) is convex on \(K_\beta \), and hence for all \(x, u \in K_\beta \),
Let \(x^0 \in [0, a]^n\) with \(\Psi (x^0) {\lt} +\infty \). For every \(x \in L_0(x^0)\) and every \(\tau \in (0, \bar{\tau })\):
\(1 + \tau (x_j + \xi ) \partial _j F(x) {\gt} 0\) for every coordinate \(j \in \{ 1, \dots , n\} \);
\(T_\tau (x) \in K_{\beta _1} \cap L_0(x^0)\);
Bregman sufficient decrease (6) holds:
\[ \Psi (x) - \Psi (T_\tau (x)) \ge \left(\frac{1}{\tau } - L_{\beta _1}\right) D_{h_\xi }(T_\tau (x), x); \]setting \(\omega := \nabla F(T_\tau (x)) - \nabla F(x) + \frac{1}{\tau }(\nabla h_\xi (x) - \nabla h_\xi (T_\tau (x)))\), we have \(\omega \in \partial \Psi (T_\tau (x))\) and the relative error bound (7):
\[ \| \omega \| \le \left(M_{\beta _1} + \frac{1}{\tau \xi ^2}\right) \| T_\tau (x) - x\| . \]
For any \(\tau {\gt} 0\) and \(x \in [0, a]^n\) satisfying \(1 + \tau (x_j + \xi ) \partial _j F(x) {\gt} 0\) for all \(j\):
\(T_\tau (x)\) satisfies the optimality inclusion (5):
\[ -\nabla F(x) - \frac{1}{\tau }\bigl(\nabla h_\xi (T_\tau (x)) - \nabla h_\xi (x)\bigr) \in \partial \iota _{[0, a]^n}(T_\tau (x)) = N_{[0, a]^n}(T_\tau (x)); \]\(T_\tau (x)\) is the unique global minimizer (1) of \(\Phi _{x, \tau }\) over \(\mathcal{E}_n\), and conversely any global minimizer of \(\Phi _{x, \tau }\) coincides with \(T_\tau (x)\) (4).
Furthermore, for every \(\tau \in \mathbb {R}\), \(T_\tau \) is continuous on \([0, a]^n \cap U_+\).
Let \(x^0 \in [0, a]^n\) with \(\Psi (x^0) {\lt} +\infty \), let \(\tau \in (0, \bar{\tau })\), and assume \(\Psi \) satisfies the KŁ property (\(\mathrm{HasKL}(\Psi )\)). Then the sequence \((x^k)_{k \in \mathbb {N}}\) satisfies
and converges to a critical point \(x^\infty \in \mathrm{crit}(\Psi ) \cap L_0(x^0)\) which is a fixed point of \(T_\tau \), i.e., \(x^\infty = T_\tau (x^\infty )\).
Let \(\Omega \subseteq \mathcal{E}_n\) be nonempty and compact, and suppose \(f\) is constant on \(\Omega \) with finite value \(f_\star \) and satisfies the KŁ property at every \(z \in \Omega \). Then there exist \(\varepsilon {\gt} 0\), \(\eta {\gt} 0\), and a common desingularizing function \(\varphi \in \Phi _\eta \) such that for all \(x \in \mathcal{E}_n\) with \(\operatorname {dist}(x, \Omega ) {\lt} \varepsilon \) and \(f_\star {\lt} f(x) {\lt} f_\star + \eta \),