Homec4science
Diffusion Nonlinear (master) Browse

R7172/Journal/sections/LinAL_theory.tex
e5e7c90cfa6bmaster

Last Change
Raw File

LinAL_theory.tex
View Options

\section{Proof of Theorem \ref{thm:main} \label{sec:proof-of-main}}
For the reader's convenience, let us recall the updates of the algorithm in iteration $k$:
\begin{align}
x_{k+1} & = P_g( x_k - \gamma_k \nabla_x \mathcal{L}_{\beta_k} (x_k,y_k) )
\nonumber\\
& = P_g\Big( x_k - \gamma_k \nabla f(x_k)\nonumber\\
& \qquad \qquad - \gamma_k DA(x_k) ^\top \left( y_k + \b_k A(x_k)
\right) \Big),
\qquad \text{(see \eqref{eq:Lagrangian})}
\label{eq:update uk recall}
\end{align}
\begin{align}
y_{k+1} =y_k + \s_{k+1} A(x_{k+1}).
\label{eq:y update recall}
\end{align}
Moreover, we will use the shorthand
\begin{equation}
G_k = G_{\beta_k,\gamma_k}(x_k,y_k) = \frac{x_k-x_{k+1}}{\gamma_k},
\qquad \text{(see \eqref{eq:grad map})}
\label{eq:grad map recall}
\end{equation}
throughout the proof.
For integers $k_0\le k_1$, consider the interval
\begin{equation}
K = [k_0:k_1]=\{k_0,\cdots,k_1\}.
\end{equation}
Since the primal step size $\gamma_k$ is determined by the line search subroutine in Lemma \ref{lem:eval Lipsc cte}, we may now apply Lemma \ref{lem:11} for every iteration in the interval $K$ to find that
\begin{align}
\frac{\gamma_k \|G_k\|^2}{2}
& \le \mathcal{L}_{\beta_k}(x_k,y_k) + g(x_k) - \mathcal{L}_{\beta_k}(x_{k+1},y_k) - g(x_{k+1})
\qquad \text{(see Lemma \ref{lem:11})} \nonumber\\
& = f(x_k) + g(x_k) - f(x_{k+1})- g(x_{k+1}) + \langle A(x_k)-A(x_{k+1}) , y_k \rangle
\nonumber\\
& \qquad + \frac{\b_k}{2}( \|A(x_k)\|^2 - \|A(x_{k+1})\|^2),
\qquad \text{(see \eqref{eq:Lagrangian})}
\label{eq:smoothness rep}
\end{align}
for every $k\in K$.
On the other hand, note that
\begin{align}
y_k = y_{k_0-1} + \sum_{i=k_0}^k \sigma_i A(x_i),
\qquad \text{(see \eqref{eq:y update recall})}
\label{eq:y update unfolded}
\end{align}
which, after substituting in \eqref{eq:smoothness rep}, yields that
\begin{align}
\frac{\gamma_k \|G_k\|^2}{2} & \le f(x_k) + g(x_k) - f(x_{k+1})-g(x_{k+1}) \nonumber\\
& \qquad + \left\langle A(x_k) - A(x_{k+1}) , y_{k_0} + \sum_{i=k_0+1}^k \s_i A(x_i) \right\rangle \nonumber\\
& \qquad + \frac{\b_k}{2}( \|A(x_k)\|^2-\|A(x_{k+1})\|^2) .
\label{eq:key ineq}
\end{align}
By summing up \eqref{eq:key ineq} over $k$ from $k_0$ to $k_1$, we argue that
\begin{align}
& \sum_{k=k_0}^{k_1} \frac{\gamma_k \|G_k\|^2}{2} \nonumber\\
& \le f(x_{k_0})+g(x_{k_0}) - f(x_{k_1+1})-g(x_{k_1+1}) + \langle A(x_{k_0}) - A(x_{k_1+1}) , y_{k_0}\rangle \nonumber\\
& \qquad + \sum_{k=k_0}^{k_1} \sum_{i=k_0+1}^k \sigma_i \left\langle A(x_k) - A(x_{k+1}) , A(x_i) \right\rangle
\nonumber\\
& \qquad + \sum_{k=k_0}^{k_1} \frac{\beta_k}{2} \|A(x_k)\|^2 - \sum_{k=k_0}^{k_1} \frac{\beta_k}{2} \|A(x_{k+1})\|^2
\qquad \text{(see \eqref{eq:key ineq})}
\nonumber\\
& = f(x_{k_0})+g(x_{k_0}) - f(x_{{k_1}+1}) - g(x_{k_1+1}) + \langle A(x_{k_0}) - A(x_{{k_1}+1}) , y_{k_0} \rangle \nonumber\\
& \qquad + \sum_{k=k_0}^{k_1} \sum_{i=k_0+1}^k \sigma_i \left\langle A(x_k) - A(x_{k+1}) , A(x_i) \right\rangle\nonumber\\
& \qquad + \sum_{k=k_0}^{k_1} \frac{\beta_k}{2}\|A(x_k)\|^2- \sum_{k=k_0+1}^{{k_1}+1} \frac{\beta_{k-1}}{2} \|A(x_{k})\|^2.
\end{align}
By manipulating the last line above, we find that
\begin{align}
& \sum_{k=k_0}^{k_1} \frac{\gamma_k \|G_k\|^2}{2} \nonumber\\
& \le f(x_{k_0})+g(x_{k_0}) - f(x_{{k_1}+1})-g(x_{k_1+1}) + \langle A(x_{k_0}) - A(x_{{k_1}+1}) , y_{k_0} \rangle \nonumber\\
& \qquad + \frac{\beta_{k_0}}{2}\|A(x_{k_0})\|^2 + \sum_{i=k_0+1}^{k_1} \sum_{k=i}^{k_1} \sigma_i \left\langle A(x_k) - A(x_{k+1}) , A(x_i) \right\rangle
\nonumber\\
& \qquad
+ \sum_{k=k_0+1}^{k_1} \frac{\beta_k - \beta_{k-1}}{2} \|A(x_k)\|^2 - \frac{\beta_{k_1}}{2} \| A(x_{k_1+1})\|^2
\nonumber\\
& \le \mu + \sum_{i=k_0+1}^{k_1} \sigma_i \left\langle A(x_i) - A(x_{{k_1}+1}), A(x_i)\right\rangle \nonumber\\
& \qquad + \sum_{k=k_0+1}^{k_1} \frac{\beta_k - \beta_{k-1}}{2} \|A(x_k)\|^2 - \frac{\beta_{k_1}}{2} \| A(x_{k_1+1})\|^2
\qquad \text{(see \eqref{eq:defn mu})}
\nonumber\\
& = \mu + \sum_{k=k_0+1}^{k_1} \left( \sigma_k +\frac{\beta_k - \beta_{k-1}}{2} \right) \|A(x_k)\|^2 \nonumber\\
& \qquad - \sum_{k=k_0+1}^{k_1} \sigma_k \left \langle A(x_{{k_1}+1}), A(x_k)\right\rangle - \frac{\beta_{k_1}}{2} \| A(x_{k_1+1})\|^2,
\label{eq:long chain broken}
\end{align}
where we assumed that
\begin{align}
\mu & := \max\Bigg( \sup_{k } \Big( f(x_{k_0})+g(x_{k_0}) - f(x_k) - g(x_k) + \langle A(x_{k_0})-A(x_k) ,y_{k_0}\rangle \nonumber\\
& \qquad \qquad + \frac{\beta_{k_0}}{2} \|A(x_{k_0})\|^2 \Big), 0 \Bigg) < \infty,
\label{eq:defn mu}
\end{align}
Given initial step sizes $\b_{k_0},\s_{k_0}>0$, recall that the penalty weights and the dual step sizes of Algorithm~\ref{Algo:2} are set to
\begin{align*}
\beta_k = \b_{k_0} \sqrt{\frac{k\log^2 (k+1)}{k_0 \log^2 (k_0+1)}},
\end{align*}
\begin{align}
\sigma_k = \s_{k_0} \min\left( \sqrt{\frac{k_0 }{k }}, \frac{ \|A(x_{k_0})\| k_0 \log^2(k_0+1)}{\|A(x_k)\| k \log^2(k+1)} \right),
\qquad \forall k \in K.
\label{eq:beta n sigma}
\end{align}
For future reference, \eqref{eq:beta n sigma} implies that
\begin{align}
\beta_k- \beta_{k-1}
& = \beta_{k-1} \left( \sqrt{\frac{k\log^{{2}}(k+1)}{(k-1)\log^{{2}}k}} -1 \right) \nonumber\\
& \le \beta_{k-1} \cdot \frac{k\log^{{2}}(k+1) - (k-1) \log^{{2}} k}{(k-1)\log^{{2}} k} \nonumber\\
& \le \b_{k-1} \left(
\frac{k\log^2(1+ \frac{1}{k})}{(k-1)\log^2k} + \frac{1}{k-1}
\right)
\nonumber\\
& \le \frac{2 \beta_{k-1}}{k-1}
\qquad ( k_0 \gg 1)
\nonumber\\
& \le \frac{{2}\beta_{k_0}}{k-1} \sqrt{\frac{(k-1)\log^{{2}}k}{k_0 \log^{{2}}(k_0+1)}} \nonumber\\
& = \frac{ 2\beta_{k_0} \log k}{\sqrt{(k-1)k_0} \log (k_0+1)},
\qquad \forall k \in K,
\label{eq:consequences}
\end{align}
when $k_0$ is sufficiently large.
We can therefore further simplify the last line of \eqref{eq:long chain broken} as
\begin{align}
& \sum_{k=k_0}^{k_1} \frac{\g_k \|G_k\|^2}{2} \nonumber\\
& \le\mu + \sum_{k=k_0}^{k_1} \left(\sigma_k+ \frac{\beta_k-\beta_{k-1}}{2} \right) \|A(x_k)\|^2
\nonumber\\
& \qquad +
\sum_{k=k_0}^{k_1} \sigma_k \|A(x_{{k_1}+1})\| \|A(x_k)\| - \frac{\beta_{k_1}}{2} \| A(x_{k_1+1})\|^2
\qquad \text{(see (\ref{eq:long chain broken}))} \nonumber\\
& \le \mu + \sum_{k=k_0}^{k_1} \left(\sigma_k+ \frac{\beta_k-\beta_{k-1}+1}{2} \right) \|A(x_k)\|^2
\nonumber\\
& \qquad +
\frac{1}{2} \left( \sum_{k=k_0}^{k_1} \sigma_k^2 -\beta_{k_1} \right) \| A(x_{k_1+1})\|^2
\qquad (2ab \le a^2+b^2) \nonumber\\
& \le \mu+ 2 \sum_{k=k_0}^{k_1} \|A(x_k)\|^2,
\qquad \text{(see (\ref{eq:beta n sigma},\ref{eq:consequences}))}
\label{eq:long chain broken 10}
\end{align}
for sufficiently large $k_0$. Indeed, the coefficient of $\|A(x_{k_1+1})\|$ in the second-to-last line of \eqref{eq:long chain broken 10} is negative because
\begin{align}
& \sum_{k=k_0}^{k_1} \s_k^2 - \b_{k_1} \nonumber\\
& \le \sum_{k=k_0}^{k_1} \frac{\s_{k_0}^2 k_0}{k} - \b_{k_0}\sqrt{\frac{k_1\log^2(k_1+1)}{k_0 \log^2(k_0+1)}} \nonumber\\
& \le 2\s_{k_0}^2 k_0 \int_{k_0}^{k_1} \frac{da}{a} - \b_{k_0}\sqrt{\frac{k_1\log^2(k_1+1)}{k_0 \log^2(k_0+1)}} \nonumber\\
& \le 0,
\end{align}
when $k_0$ is sufficiently large. Note that \eqref{eq:long chain broken 10} bounds the gradient mapping with the feasibility gap. A converse is given by Lemma \ref{lem:bnd bnd Ak}.
In order to apply this result, let us assume that the assumptions in Lemma~\ref{lem:bnd bnd Ak} are met. Lemma \ref{lem:bnd bnd Ak} is then in force and we may now substitute \eqref{eq:bnd on Ak final} back into \eqref{eq:long chain broken 10} to find that
\begin{align}
& \sum_{k=k_0}^{k_1} \gamma_k \|G_k\|^2 \nonumber\\
& \le 2\sum_{k=k_0}^{{k_1}}\|A(x_k)\|^2 +2 \mu
\qquad \text{(see \eqref{eq:long chain broken 10})}
\nonumber\\
& \le 2\sum_{k=k_0}^{k_1} \left(\frac{2}{\nu\b_k} \left( \|G_k\| + \lambda'_f + \lambda'_A \| y_k\| \right) \right)^2 + 2\mu
\qquad \text{(see \eqref{eq:bnd on Ak final})}
\nonumber\\
& \le\sum_{k=k_0}^{k_1} \frac{32\|G_k\|^2}{ \nu^2 \b_k^2}
+ \sum_{k=k_0}^{k_1} \frac{8 \lambda'^2_f}{ \nu^2 \b_k^2 }
+ \sum_{k=k_0}^{k_1} \frac{8\lambda_A'^2 \|y_k\|^2}{ \nu^2\b_k^2} + 2\mu,
\label{eq:to be used for feas pre}
\end{align}
where we used the shorthand $\nu = \nu(g,A,S,\rho,\rho')$ and the last line above uses the inequality
\begin{align}
\left(\sum_{i=1}^p a_i\right)^2 \le p \sum_{i=1}^p a_i^2,
\end{align}
for integer $p$ and scalars $\{a_i\}_i$. If we set
\begin{align}
B_K = \sum_{k=k_0}^{k_1} \frac{\|y_k\|^2}{k\log^2 (k+1)},
\qquad
c \ge \sum_{k=1}^{\infty} \frac{1}{k\log^2 (k+1)},
\label{eq:defn of BK}
\end{align}
and, after recalling the choice of $\{\b_k\}_k$ in \eqref{eq:beta n sigma}, the last line of \eqref{eq:to be used for feas pre} can be simplified as
\begin{align}
\sum_{k=k_0}^{k_1} \g_k \|G_k\|^2
& \le 2\sum_{k=k_0}^{k_1} \|A(x_k)\|^2 + 2\mu \nonumber\\
& \le \sum_{k=k_0}^{k_1} \frac{32\|G_k\|^2 k_0 \log^2(k_0+1)}{ \nu^2 \b_{k_0}^2 k\log^2 (k+1)} + \sum_{k=k_0}^{k_1} \frac{8\lambda'^2_f k_0 \log^2 (k_0+1) }{\nu^2 \b_{k_0}^2 k\log^2 (k+1) } +2\mu
\nonumber\\
& \qquad + \sum_{k=k_0}^{k_1} \frac{8\lambda'^2_A k_0 \log^2(k_0+1) \|y_k\|^2}{\nu^2 k \log^2(k+1)} +2\mu
\qquad \text{(see \eqref{eq:beta n sigma})}
\nonumber\\
& \le \sum_{k=k_0}^{k_1} \frac{32 \|G_k\|^2 k_0 \log^2(k_0+1)}{ \nu^2 \b_{k_0}^2 k\log^2 (k+1)} +
\frac{8k_0\log^2(k_0+1)}{\nu^2 \b_{k_0}^2} \left( c\lambda'^2_f+ \lambda'^2_A B_K \right)
% \frac{8c \lambda'^2_f k_0 \log^2(k_0+1)}{\nu^2 \b^2_{k_0}}
%\nonumber\\
%& \qquad + \frac{8\lambda'^2_A B_K k_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}^2}
\nonumber\\
& \qquad +2\mu.
\qquad \text{(see \eqref{eq:defn of BK})}
\label{eq:to be used for feas}
\end{align}
To simplify the above bound, let us assume that
\begin{equation}
\frac{32 k_0 \log^2(k_0+1) }{\nu^2 \b_{k_0}^2 k\log^2(k+1)} \le \frac{\gamma_k}{2},
\qquad \forall k\in K.
\label{eq:to be used later on}
\end{equation}
After rearranging \eqref{eq:to be used for feas} and applying \eqref{eq:to be used later on}, we arrive at
\begin{align}
& \sum_{k=k_0}^{k_1} \frac{\gamma_k}{2} \|G_k\|^2 \nonumber\\
& \le \sum_{k=k_0}^{k_1} \left( \gamma_k - \frac{32k_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}^2 k\log^2(k+1)} \right) \|G_k\|^2
\qquad \text{(see \eqref{eq:to be used later on})}
\nonumber\\
& \le
% \frac{8c \lambda'^2_f k_0 \log^2(k_0+1)}{\nu^2 \b^2_{k_0}} +
%\frac{8\lambda'^2_A B_K k_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}^2}
\frac{8k_0\log^2(k_0+1)}{\nu^2\b_{k_0}^2} \left( c\lambda'^2_f+\lambda'^2_A B_K \right)
+ 2\mu.
\qquad \text{(see \eqref{eq:final bnd on G})}
\label{eq:final bnd on G}
\end{align}
In turn, the bound above on the gradient mapping controls the feasibility gap, namely,
\begin{align}
\sum_{k=k_0}^{{k_1}} \|A(x_k)\|^2
& \le \sum_{k=k_0}^{k_1} \frac{\g_k \|G_k\|^2}{4 }
+ \frac{4k_0 \log^2(k_0+1)}{\nu^2\b_{k_0}^2} \left( c\lambda'^2_f+\lambda'^2_A B_K \right)
%+ \frac{4c \lambda'^2_f k_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}}
%\nonumber\\
%& \qquad + \frac{4\lambda'^2_A B_K k_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}^2}
\qquad \text{(see (\ref{eq:to be used for feas},\ref{eq:to be used later on}))}
\nonumber\\
& \le
%\frac{8c \lambda'^2_f k_0 \log^2(k_0+1)}{\nu^2 \b^2_{k_0}}
%\nonumber\\
%& \qquad + \frac{8\lambda'^2_A B_K k_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}^2}
\frac{8k_0 \log^2(k_0+1)}{\nu^2\b_{k_0}^2} \left( c\lambda'^2_f+\lambda'^2_A B_K \right) + \mu.
\qquad \text{(see (\ref{eq:final bnd on G}))}
\label{eq:final bnd on feas gap}
\end{align}
By adding (\ref{eq:final bnd on G},\ref{eq:final bnd on feas gap}), we find that
\begin{align}
\sum_{k=k_0}^{k_1} \g_k \|G_k\|^2 + \|A(x_k)\|^2
& \le
% \frac{24c \lambda'^2_f k_0 \log^2(k_0+1)}{\nu^2 \b^2_{k_0}} \nonumber\\
%& \qquad + \frac{24\lambda'^2_A B_K k_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}^2}
\frac{24k_0 \log^2(k_0+1)}{\nu^2\b_{k_0}^2} \left( c\lambda'^2_f+\lambda'^2_A B_K \right) + 5\mu.
\label{eq:overall bnd raw}
\end{align}
In order to interpret (\ref{eq:overall bnd raw}), we next estimate $B_{K}$, defined in \eqref{eq:defn of BK}. To that end, let us first control the growth of the dual sequence $\{y_k\}_k$. Recalling \eqref{eq:y update recall} and for every $k\in K$, we write that
\begin{align}
\|y_k\| & \le \|y_{k_0}\|+ \sum_{i=k_0+1}^k \s_i \|A(x_i)\|
\qquad \text{(see \eqref{eq:y update recall})}
\nonumber\\
& \le \|y_{k_0}\|+ \sum_{i=k_0+1}^k \frac{\rho \s_{k_0} k_0 \log^2(k_0+1)}{ k\log^2(k+1)}
\qquad \text{(see (\ref{eq:good neighb},\ref{eq:beta n sigma}))} \nonumber\\
& \le \|y_{k_0}\|+ c\rho \s_{k_0} k_0 \log^2(k_0+1) \nonumber\\
& =: y_{\max}.
\label{eq:dual growth}
\end{align}
With the growth of the dual sequence discovered above, we evaluate $B_{K}$ as
\begin{align}
B_{K} & = \sum_{k=k_0}^{k_1} \frac{\|y_k\|^2}{k\log^2 (k+1)}
\qquad \text{(see \eqref{eq:defn of BK})}
\nonumber\\
& \le \sum_{k=k_0}^{k_1} \frac{y_{\max}^2}{k\log^2 (k+1)}
\qquad \text{(see \eqref{eq:dual growth})} \nonumber\\
& \le cy_{\max}^2.
\qquad \text{(see \eqref{eq:defn of BK})}
\label{eq:Bk evaluated}
\end{align}
In order to interpret (\ref{eq:overall bnd raw}), it still remains to estimate the primal step sizes $\{\g_k\}_k$. To invoke \eqref{eq:moreover}, we in turn need to gauge how smooth the augmented Lagrangian $\mathcal{L}_{\beta_k}(\cdot,y_k)$ is. For every $k\in K$, note that
\begin{align}
\lambda_{\beta_k} & \le \lambda_f+ \sqrt{m}\lambda_A \left( \|y_k\| + \b_k \rho \right)+ \b_k d \lambda'^2_A
\qquad \text{(see \eqref{eq:smoothness of Lagrangian})} \nonumber\\
& \le (\lambda_f+ \sqrt{m}\lambda_A y_{\max} ) + \b_k \left( \sqrt{m}\lambda_A \rho + d \lambda'^2_A \right).
\qquad \text{(see \eqref{eq:dual growth})}
\label{eq:smoothness at k}
\end{align}
We are now in position to invoke \eqref{eq:moreover} by writing that
\begin{align}
\gamma_k & \ge \frac{\theta}{\lambda_{\beta_k}} \qquad \text{(see \eqref{eq:moreover})}\nonumber\\
& \ge \frac{\theta}{ (\lambda_h+ \sqrt{m}\lambda_A y_{\max} )+ \b_k \left( \sqrt{m}\lambda_A \rho + d \lambda'^2_A \right) } \qquad
\text{(see \eqref{eq:smoothness at k})} \nonumber\\
& \ge \frac{\theta}{ 2 \b_k \left( \sqrt{m}\lambda_A \rho + d \lambda'^2_A \right)}
\qquad ( \text{(\ref{eq:beta n sigma}) and } k_0 \gg 1 ) \nonumber\\
& \ge \frac{\theta }{ 2 \b_{k_0} \left( \sqrt{m}\lambda_A \rho + d \lambda'^2_A \right)}\sqrt{\frac{k_0 \log^2(k_0+1)}{k \log^2(k+1)}} \qquad \text{(see \eqref{eq:beta n sigma})} \nonumber\\
& =: \overline{\g} \sqrt{\frac{k_0 \log^2(k_0+1)}{k \log^2(k+1)}},
\label{eq:low bnd on gammas}
\end{align}
for every $k\in K$. The first consequence of \eqref{eq:low bnd on gammas} is that \eqref{eq:to be used later on} holds automatically when $k_0$ is sufficiently large. Having estimated $B_K$ and $\{\gamma_k\}_k$, we can also rewrite~(\ref{eq:overall bnd raw}). Indeed, (\ref{eq:overall bnd raw},\ref{eq:Bk evaluated},\ref{eq:low bnd on gammas}) together imply that
\begin{align}
& \sum_{k=k_0}^{k_1} \overline{\g} \|G_k\|^2 \sqrt{\frac{k_0 \log^2(k_0+1)}{k\log^2(k+1)}} + \|A(x_k)\|^2 \nonumber\\
& \le
% \frac{24c \lambda'^2_f k_0 \log^2(k_0+1)}{\nu^2 \b^2_{k_0}} + \frac{24c\lambda'^2_A y_{\max}^2 k_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}^2}
\frac{24c k_0 \log^2(k_0+1)}{\nu^2\b_{k_0}^2} \left( \lambda'^2_f+\lambda'^2_A y_{\max}^2 \right)
+ 5\mu,
\end{align}
and, consequently,
\begin{align}
& \min_{k\in K}\overline{\g} \|G_k\|^2 \sqrt{\frac{k_0 \log^2(k_0+1)}{k_1\log^2(k_1+1)}} + \|A(x_k)\|^2
\nonumber\\
& \le
\frac{24c k_0 \log^2(k_0+1)}{\nu^2\b_{k_0}^2 (k_1-k_0)} \left( \lambda'^2_f+\lambda'^2_A y_{\max}^2 \right)
+ \frac{5\mu}{k_1-k_0}.
%\frac{24c \lambda'^2_f k_0 \log^2(k_0+1)}{\nu^2 \b^2_{k_0}(k_1-k_0)} + \frac{24c\lambda'^2_A y_{\max}^2 k_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}^2(k_1-k_0)} + \frac{5\mu}{k_1-k_0}.
\label{eq:exact dependences}
\end{align}
%\notea{marker}
%Using (\ref{eq:Bk evaluated}), we also see that, for \eqref{eq:suff cnd on rho} to hold, it suffices to have that
%\begin{align}
% \frac{8c \lambda'^2_f k_0 \log^2(k_0+1)}{\nu_A^2 \b^2_{k_0}}
%+ \frac{8c\lambda'^2_A y_{\max}^2 k_0 \log^2(k_0+1)}{\nu_A^2 \b_{k_0}^2} + \mu \le \rho^2.
%\label{eq:suff cnd on rho final}
%\end{align}
When we applied Lemma \ref{lem:bnd bnd Ak} earlier, we did not check whether the assumptions on $\rho$ therein hold. Let us revisit this assumption.
We first derive a weaker but uniform bound on the feasibility gap. For every $k\in K$, it holds that
\begin{align}
\|A(x_k)\|^2 & \le \sum_{i=k_0}^{k_1} \|A(x_i)\|^2
\nonumber\\
& \le \frac{8k_0 \log^2(k_0+1)}{\nu^2\b_{k_0}^2} \left( c\lambda'^2_f+\lambda'^2_A B_K \right) + \mu
\qquad \text{(see \eqref{eq:final bnd on feas gap})}
\nonumber\\
& \le \frac{8ck_0 \log^2(k_0+1)}{\nu^2\b_{k_0}^2} \left( \lambda'^2_f+\lambda'^2_A y_{\max}^2 \right) + \mu.
\qquad \text{(see \eqref{eq:Bk evaluated})}
\label{eq:rate of feas gap}
\end{align}
Therefore, we may replace the assumption on $\rho$ in Lemma~\ref{lem:bnd bnd Ak} with the stronger assumption that
\begin{align}
\rho^2 \ge
\frac{8c k_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}^2} \left( \lambda_f'^2+ \lambda'^2_A y_{\max}^2 \right)+\mu,
\end{align}
which, after rearranging, can be presented as
\begin{align}
\nu^2 \ge \frac{8c k_0 \log^2(k_0+1) }{\b_{k_0}^2(\rho^2- \mu)} \left( \lambda_f'^2+ \lambda'^2_A y_{\max}^2 \right),
\qquad
\rho > \sqrt{\mu}.
\label{eq:suff cnd on nu-1}
\end{align}
Note that, for \eqref{eq:suff cnd on nu-1} to hold, it is in particular necessary that $\|A(x_{k_0})\| \le \rho \sqrt{2/\b_{k_0}}$, as seen in \eqref{eq:defn mu}. That is, for Algorithm~\ref{Algo:2} to success, it must be initialized close enough to the feasible set. Lastly, let us revisit the lower bound on $\nu$ in Lemma~\ref{lem:bnd bnd Ak}, namely, \eqref{eq:low-bnd-on-nu-lemma}. First we derive a weaker but uniform bound on the gradient mapping. For every $k\in K$, it holds that
\begin{align}
& \max_{k\in K} \g_k \| G_k\| \nonumber\\
& \le \max_{k\in K} \sqrt{\g_k} \cdot \sqrt{\max_{k\in K} \g_k \|G_k\|^2} \nonumber\\
& \le \max_{k\in K} \sqrt{\g_k} \cdot \sqrt{\sum_{k=k_0}^{k_1} \g_k \|G_k\|^2 } \nonumber\\
& \le \max_{k\in K} \sqrt{\g_k}
\cdot
\left(
\frac{16ck_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}^2 } \left( \lambda'^2_f+ \lambda'^2_A y_{\max}^2 \right)
% \frac{16c \lambda'^2_f k_0 \log^2(k_0+1)}{\nu^2 \b^2_{k_0}} + \frac{16c\lambda'^2_A y_{\max}^2 k_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}^2}
+ 4\mu \right)^{\frac{1}{2}} .
\qquad \text{(see (\ref{eq:final bnd on G},\ref{eq:Bk evaluated}))}
% & \le \max_{k\in K} \sqrt{\g_k}
%\cdot
% \left( \frac{4 \sqrt{c} \lambda'_f \sqrt{k_0} \log(k_0+1)}{\nu \b_{k_0}} + \frac{4\sqrt{c}\lambda'_A y_{\max} \sqrt{k_0} \log(k_0+1)}{\nu \b_{k_0}} + 2\sqrt{\mu} \right),
\end{align}
%where the last line uses the inequality $\sqrt{a+b+c}\le \sqrt{a}+\sqrt{b}+\sqrt{c}$ for nonnegative $a,b,c$.
Instead of \eqref{eq:low-bnd-on-nu-lemma}, it therefore suffices to make the stronger assumption that
\begin{align}
\nu \ge 2\lambda_A
\max_{k\in K} \sqrt{\g_k}
\cdot
\left( \frac{16ck_0 \log^2(k_0+1)}{\nu^2 \b_{k_0}^2}
\left( \lambda'^2_f+ \lambda'^2_A y_{\max}^2 \right)
+ 4\mu \right)^{\frac{1}{2}} ,
\end{align}
which can in turn be replaced with the stronger assumptions
\begin{align}
\nu \ge
\max\left(
4\sqrt{2}\lambda_A \max_{k\in K} \sqrt{\g_k \mu},
\frac{2\sqrt{ck_0} \log(k_0+1)}{\b_{k_0} \sqrt{\mu}} (\lambda'_f + \lambda'_A y_{\max} )
\right)
\label{eq:cnd-on-nu-proof}
\end{align}
This completes the proof of Theorem \ref{thm:main}.
c4science · Help