Homec4science
Diffusion Nonlinear (master) Browse

R7172/tex/Paper/sections/appendix.tex
81cc86af58bemaster

Last Change
Raw File

appendix.tex
View Options

\section{Proof of Lemma \ref{lem:smoothness}\label{sec:proof of smoothness lemma}}
\textbf{We assume Hessian exists. We shouldn't assume that for a strictly correct proof!}
Note that
\begin{align}
\mathcal{L}_{\beta}(x,y) = f(x) + \sum_{i=1}^m y_i A_i (x) + \frac{\b}{2} \sum_{i=1}^m (A_i(x))^2,
\end{align}
which implies that
\begin{align}
\nabla_x \mathcal{L}_\beta(x,y) & = \nabla f(x) + \sum_{i=1}^m y_i \nabla A_i(x) + \frac{\b}{2} \sum_{i=1}^m A_i(x) \nabla A_i(x) \nonumber\\
& = \nabla f(x) + DA(x)^\top y + \b DA(x)^\top A(x),
\end{align}
where $DA(x)$ is the Jacobian of $A$ at $x$. By taking another derivative with respect to $x$, we reach
\begin{align}
\nabla^2_x \mathcal{L}_\beta(x,y) & = \nabla^2 f(x) + \sum_{i=1}^m \left( y_i + \b A_i(x) \right) \nabla^2 A_i(x) + \b \sum_{i=1}^m \nabla A_i(x) \nabla A_i(x)^\top.
\end{align}
It follows that
\begin{align}
\|\nabla_x^2 \mathcal{L}_\beta(x,y)\| & \le \| \nabla^2 f(x) \|+ \max_i \| \nabla^2 A_i(x)\| \left (\|y\|_1+\b \|A(x)\|_1 \right) + \beta\sum_{i=1}^m \|\nabla A_i(x)\|^2 \nonumber\\
& \le \lambda_h+ \sqrt{m} \lambda_A \left (\|y\|+\b \|A(x)\| \right) + \b \|DA(x)\|^2_F.
\end{align}
For every $x$ such that $\|A(x)\|\le \rho$ and $\|x\|\le \rho'$, we conclude that
\begin{align}
\|\nabla_x^2 \mathcal{L}_\beta(x,y)\|
& \le \lambda_f + \sqrt{m}\lambda_A \left(\|y\| + \b\rho \right) + \b \max_{\|x\|\le \rho'}\|DA(x)\|_F^2,
\end{align}
which completes the proof of Lemma \ref{lem:smoothness}.
\section{Proof of Lemma \ref{lem:11}\label{sec:proof of descent lemma}}
Throughout, let
\begin{align}
G = G_{\b,\g}(x,y) = \frac{x-x^+}{\g},
\end{align}
for short.
Suppose that $\|A(x)\|\le \rho$, $\|x\|\le \rho$, and similarly $\|A(x^+)\|\le \rho$, $\|x^+\|\le \rho'$. An application of Lemma \ref{lem:smoothness} yields that
\begin{align}
\L_\b(x^+,y)+g(x^+) & \le \L_\b(x,y)+ \langle x^+-x,\nabla_x \L_\b(x,y) \rangle
+ \frac{\lambda_\b}{2} \|x^+ - x\|^2 + g(x^+) \nonumber\\
& = \L_\b(x,y)-\g \langle G ,\nabla_x \L_\b(x,y) \rangle
+ \frac{\g^2 \lambda_\b }{2} \|G\|^2 + g(x^+)
\label{eq:descent pr 1}
\end{align}
Since $x^+ = P_g(x - \g \nabla_x \L_\b(x,y))$, we also have that
\begin{align}
G - \nabla_x \L_\b(x,y) = \xi \in \partial g(x^+).
\label{eq:opt of prox}
\end{align}
By combining (\ref{eq:descent pr 1},\ref{eq:opt of prox}), we find that
\begin{align}
\L_\b(x^+,y)+g(x^+) &
\le \L_\b(x,y) -\g \|G\|^2 + \g \langle G, \xi \rangle + \frac{\g^2 \lambda_\b}{2}\|G\|^2 + g(x^+) \nonumber\\
& = \L_\b(x,y) -\g \|G\|^2 + \langle x- x^+ , \xi \rangle + \frac{\g^2 \lambda_\b}{2}\|G\|^2 + g(x^+) \nonumber\\
& \le \L_\b(x,y) + g(x) - \g\left( 1-\frac{\g\lambda_\b}{2}\right) \|G\|^2,
\end{align}
where the last line above uses the convexity of $g$. Recalling that $\g\le 1/\lambda_\b$ completes the proof of Lemma \ref{lem:11}.
\section{Proof of Lemma \ref{lem:eval Lipsc cte}\label{sec:proof of linesearch}}
Recalling $x^+_{\gamma}$ in \eqref{eq:defn of gamma line search}, we note that
\begin{equation}
x^+_{\gamma} - x +\gamma \nabla_x \mathcal{L}_\beta(x,y) = - \g\xi \in -\partial g (x^+_{\gamma}).
\label{eq:optimality of uplus}
\end{equation}
Lastly, $\gamma$ by definition in \eqref{eq:defn of gamma line search} satisfies
\begin{align}
& \mathcal{L}_{\beta}(x^+_{\gamma},y) + g(x_\g^+) \nonumber\\
& \le \mathcal{L}_\beta(x,y) + \left\langle
x^+_{\gamma} - x , \nabla_x \mathcal{L}_\beta (x,y)
\right\rangle + \frac{1}{2\gamma}\|x^+_{\gamma} - x\|^2
+ g(x_\g^+)
\nonumber\\
& = \mathcal{L}_\beta(x,y) + \left\langle
x - x^+_{\gamma} ,\xi
\right\rangle
- \frac{1}{2\gamma}\|x^+_{\gamma} - x\|^2 + g(x_\g^+)\nonumber\\
& \le \mathcal{L}_\beta(x,y)
- \frac{1}{2\gamma}\|x^+_{\gamma} - x\|^2 + g(x) - g(x^+_\g)
\qquad (\text{convexity of } g) \nonumber\\
& = \mathcal{L}_\beta(x,y) - \frac{\gamma}{2} \|G_{\beta,\gamma}(x,y)\|^2 +g(x) - g(x^+_\g),
\qquad \text{(see Definition \ref{def:grad map})}
\end{align}
which completes the proof of Lemma \ref{lem:eval Lipsc cte}.
\section{Proof of Lemma \ref{lem:bnd bnd Ak} \label{sec:proof of bnd Ak}}
Throughout, we assume that
\begin{align}
\max_{k\in K} \|A(x_k)\| \le \rho,
\qquad \max_{k\in K} \| x_k\| \le \rho',
\qquad \max_{k\in K} \| x_{k+1}-x_k \| \le \rho''.
\label{eq:bndness in slater proof}
\end{align}
From the $x$ update in \eqref{eq:update uk recall}, it follows that
\begin{align}
x_{k+1}-x_k + \g_k \nabla f(x_k) + \g_k DA(x_k)^\top (y_k + \b_k A(x_k) ) =- \xi \in - \partial g(x_{k+1}),
\end{align}
which, after recalling \eqref{eq:grad map recall}, can be written as
\begin{align}
-\frac{ G_k}{\b_k} + \frac{ \nabla f(x_k)}{\b_k}
+ \frac{ DA(x_k)^\top y_k }{\b_k} + DA(x_k)^\top A(x_k) \in - \frac{\partial g(x_{k+1})}{\b_k \g_k}.
\label{eq:to be projected}
\end{align}
Let
\begin{align}
\cone(x_{k+1}) = \text{cone}(\partial g(x_{k+1}) )^*,
\end{align}
be the shorthand for the dual cone associated with
\begin{equation}
\cone(\partial g(x_{k+1})) = \bigcup_{\alpha \ge 0} \alpha \cdot \partial g(x_{k+1}) \subseteq \RR^d.
\label{eq:defn of dual cone}
\end{equation}
By projecting both sides \eqref{eq:to be projected} onto $\cone_{k+1}$, we find that
\begin{align}
& P_{\cone(x_{k+1})}\left( - \frac{G_k}{\b_k} + \frac{\nabla f(x_k)}{\b_k} + \frac{DA(x_k)^\top y_k}{\b_k} + DA(x_k)^\top A(x_k) \right) \nonumber\\
& \in P_{\cone(x_{k+1})}\left( - \frac{\partial g(x_{k+1}) }{\b_k \g_k} \right) = \{ 0\},
\label{eq:before Sk}
\end{align}
where the equality follows from the duality of $\cone(x_{k+1})$ and $\cone(\partial g(x_{k+1}))$, see \eqref{eq:defn of dual cone}.
Consider a subspace $S_K\subseteq \RR^d$ such that
\begin{align}
S _{K} \supseteq \bigcup_{k\in K} P_{\cone(x_{k+1})}\left( DA(x_{k+1})^\top A(x_{k+1}) \right),
\label{eq:defn of S}
\end{align}
and project both sides of \eqref{eq:before Sk} onto $S_K$ to reach
\begin{align}
& P_{S_K}P_{\cone(x_{k+1})}\left( - \frac{G_k}{\b_k} + \frac{\nabla f(x_k)}{\b_k} + \frac{DA(x_k)^\top y_k}{\b_k} + DA(x_k)^\top A(x_k) \right) = 0.
\label{eq:pre norm}
\end{align}
By taking the norm and then applying the triangle inequality, we argue that
\begin{align}
& \left\|
P_{S_K} P_{\cone(x_{k+1})} ( DA(x_k)^\top A(x_k) )
\right\| \nonumber\\
& \le
\left\| P_{S_K} P_{\cone(x_{k+1})} \left( - \frac{G_k}{\b_k} + \frac{\nabla f(x_k)}{\b_k} + \frac{DA(x_k)^\top y_k}{\b_k}
\right) \right\|
\qquad \text{(see \eqref{eq:pre norm})}.
\label{eq:post norm}
\end{align}
Because proximal map is non-expansive and $P_{S_K}P_{\cone_{k+1}}(0) = 0$, we may upper bound the last line above as
\begin{align}
& \left\|
P_{S_K} P_{\cone(x_{k+1})} ( DA(x_k)^\top A(x_k) )
\right\| \nonumber\\
& \le
\left\| - \frac{G_k}{\b_k} + \frac{\nabla f(x_k)}{\b_k} + \frac{DA(x_k)^\top y_k}{\b_k}
\right\| \nonumber\\
& \le \frac{1}{\b_k} \left( \|G_k\| + \|\nabla f(x_k) \| + \|DA(x_k)^\top y_k\| \right).
\qquad \text{(triangle inequality)} \nonumber\\
& \le \frac{1}{\b_k} \left( \|G_k\| +\lambda'_f+ \lambda'_A \|y_k\| \right) ,
\label{eq:slater proof 0}
\end{align}
where
\begin{align}
\lambda'_f := \max_{\|x\| \le \rho'} \| \nabla f(x)\|,
\qquad
\lambda'_A := \max_{\|x\| \le \rho'} \| DA(x)\|.
\end{align}
To lower bound the first line of \eqref{eq:slater proof 0}, we must impose a restricted injectivity as follows.
We let $S_{K}$ with orthonormal columns denote a basis for the subspace $S_K$ in \eqref{eq:defn of S}, to simplify the notation. We then assume that $ \nu_A>0$, where
\begin{align}
\nu_A :=
\begin{cases}
\min_{v,x} \, \frac{\left\| S_{K}^\top P_{\cone(x_{k+1})} ( DA(x)^\top v) \right\|}{\|v\|} \\
\|v\|\le \rho\\
\|x\|\le \rho'.
\end{cases}
\label{eq:new slater proof}
\end{align}
Recalling the first bound in \eqref{eq:bndness in slater proof}, for every $k\in K $, we may therefore write that
\begin{align}
& \left\|
P_{S_K} P_{\cone(x_{k+1})} ( DA(x_{k})^\top A(x_k))
\right\| \nonumber\\
& \ge \left\|
P_{S_K} P_{\cone(x_{k+1})} ( DA(x_{k+k})^\top A(x_{k}))
\right\|
- \left\|
(DA(x_{k+1}) - DA(x_{k})) ^\top A(x_{k})
\right\| \nonumber\\
& \ge \nu_A \|A(x_k)\| - \| DA(x_{k+1})-DA(x_k) \| \|A(x_k) \|,
\qquad \text{(see \eqref{eq:new slater proof})}
\label{eq:slater proof 1}
\end{align}
where the second line above again uses the non-expansiveness of $P_{S_K}$ and $P_{\cone_{k+1}}$. The remaining term in \eqref{eq:slater proof 1} is bounded as
\begin{align}
\| DA(x_{k+1})-DA(x_k) \| & \le \lambda_A \|x_{k+1}-x_k\| \le \lambda_A \rho''.
\qquad \text{(see (\ref{eq:smoothness basic},\ref{eq:bndness in slater proof}))}
\end{align}
Assuming that
\begin{align}
\lambda_A \rho'' \le \nu_A/2,
\end{align}
allows us to simplify the last line of \eqref{eq:slater proof 1} as
\begin{align}
\left\|
P_{S_K} P_{\cone(x_{k+1})} ( DA(x_{k})^\top A(x_k))
\right\| \ge \frac{\nu_A }{2} \|A(x_k)\|,
\end{align}
which, after substituting in \eqref{eq:slater proof 0}, yields that
\begin{align}
\|A(x_k)\|
& \le \frac{2}{\b_k\nu_A} \left( \|G_k\| + \lambda'_f + \lambda'_A \|y_k\| \right),
\end{align}
and completes the proof of Lemma \ref{lem:bnd bnd Ak}.
c4science · Help