where we have used the fact that the last inequality holds when
$\alpha_{k}\leq 10^{-1}$ and $c_{0}=26/25$. If $e^{t_{k-1}}<2$, we have
$e^{t_{k}}<2e^{\alpha_{k}}$ and

$\displaystyle\frac{e^{\alpha_{k+1}}-1}{e^{\alpha_{k}/2}-1}$
$\displaystyle\geq(e^{\alpha_{k}/2}+1)\frac{(e^{t_{k-1}}-1)^{\min(1-\gamma_{1},\,-\gamma_{2}/2)}}{e^{\alpha_{k}}(e^{t_{k}}-1)^{\max(1-\gamma_{1},\,-\gamma_{2}/2)}}\frac{1-(c_{0}-1)^{1/2}}{1+(c_{0}-1)^{1/2}}$
$\displaystyle\geq(e^{\alpha_{k}/2}+1)\frac{(2e^{-\alpha_{k}}-1)}{e^{\alpha_{k}}(2e^{\alpha_{k}}-1)}\frac{1-(c_{0}-1)^{1/2}}{1+(c_{0}-1)^{1/2}}\geq
1\,,$

where we have used the fact that the last inequality holds when
$\alpha_{k}\leq 10^{-1}$ and $c_{0}=26/25$. This completes the proof of
$\alpha_{k+1}\geq\alpha_{k}/2$.

Next, we show that the algorithm terminates after a finite number of steps. We
first show that $t_{k}$ diverges. To this end, using (60) and (82), we have

$\displaystyle\frac{e^{t_{k}/2}(e^{\alpha_{1}}-1)\|\nabla
L_{n}(\bm{0})\|_{2}(1-e^{-t_{k}})}{\|\theta_{k}\|_{2}}\geq\frac{e^{t_{k}/2}(e^{\alpha_{1}}-1)\|\nabla
L_{n}(\bm{0})\|_{2}(1-e^{-t_{k}})}{\|\theta(t_{k})\|_{2}/(1-(c_{0}-1)^{1/2})}$
$\displaystyle\geq\frac{e^{t_{k}/2}(e^{\alpha_{1}}-1)\|\nabla
L_{n}(\bm{0})\|_{2}(1-e^{-t_{k}})(1-(c_{0}-1)^{1/2})}{(e^{t_{k}}-1)\|\nabla
L_{n}(\bm{0})\|_{2}}\geq 2^{-1}(e^{\alpha_{1}}-1)e^{-t_{k}/2}\,,$

which implies that

$A_{k}\geq\ln(1+2^{-1}(e^{\alpha_{1}}-1)e^{-t_{k}/2})\geq\frac{(e^{\alpha_{1}}-1)e^{-t_{k}/2}}{2+(e^{\alpha_{1}}-1)e^{-t_{k}/2}}=\frac{(e^{\alpha_{1}}-1)}{2e^{t_{k}/2}+(e^{\alpha_{1}}-1)}\,.$
(89)

Moreover, $B_{k}\geq A_{k}$ when $e^{t_{k}}<2$, and when $e^{t_{k}}\geq 2$, we
have

$\displaystyle
e^{t_{k}}\max\left((e^{t_{k}}-1)^{-\gamma_{1}},(e^{t_{k}}-1)^{-1-\gamma_{2}/2}\right)\|\theta_{k}\|_{2}$
$\displaystyle\leq
2e^{t_{k}}\max\left((e^{t_{k}}-1)^{1-\gamma_{1}},(e^{t_{k}}-1)^{-\gamma_{2}/2}\right)\|\nabla
L_{n}(\bm{0})\|_{2}$ $\displaystyle\leq 2e^{2t_{k}}\|\nabla
L_{n}(\bm{0})\|_{2}\,,$

which implies that when $e^{t_{k}}\geq 2$

$\displaystyle B_{k}$ $\displaystyle\geq\ln(1+(C_{1}\beta e^{2t_{k}}\|\nabla
L_{n}(\bm{0})\|_{2})^{-1})\geq\frac{(2C_{1}\beta e^{2t_{k}}\|\nabla
L_{n}(\bm{0})\|_{2})^{-1}}{1+(2C_{1}\beta e^{2t_{k}}\|\nabla
L_{n}(\bm{0})\|_{2})^{-1}}$ $\displaystyle=\frac{1}{1+(2C_{1}\beta
e^{2t_{k}}\|\nabla L_{n}(\bm{0})\|_{2})}\,.$

Thus,

$\displaystyle B_{k}$
$\displaystyle\geq\min\left\\{\frac{(e^{\alpha_{1}}-1)}{2e^{t_{k}/2}+(e^{\alpha_{1}}-1)},\,\frac{1}{1+(2C_{1}\beta
e^{2t_{k}}\|\nabla L_{n}(\bm{0})\|_{2})}\right\\}\,.$

Combining we have that

$\alpha_{k+1}\geq\min\left(\alpha_{\max},2\alpha_{k},\frac{(e^{\alpha_{1}}-1)}{2e^{t_{k}/2}+(e^{\alpha_{1}}-1)}\,,\frac{1}{1+2C_{1}\beta
e^{2t_{k}}\|\nabla L_{n}(\bm{0})\|_{2}}\right)\,.$ (90)

Now we prove the divergence of $t_{k}$ by contradiction. Suppose that $t_{k}$
does not diverge. Then there must exist a constant $T$ such that $t_{k}<T$ for
all $k$. However, now we have

$\alpha_{k+1}\geq\min\left(\alpha_{\max},2\alpha_{k},\frac{(e^{\alpha_{1}}-1)}{2e^{T/2}+(e^{\alpha_{1}}-1)}\,,\frac{1}{1+2C_{1}\beta
e^{2T}\|\nabla L_{n}(\bm{0})\|_{2}}\right)\,,$

which implies that $\alpha_{k}$ is lower bounded by a positive constant when
$k$ is large enough, implying that $t_{k}$ should diverge. This is a
contradiction. Hence, $t_{k}$ diverges.

Now we are ready to show that the algorithm must terminate after a finite
number of iterations. If $t_{\max}<\infty$, then $t_{k}\geq t_{\max}$ must
hold for large enough $k$ as $t_{k}$ diverges. If $t_{\max}=\infty$, then we
have that $\theta(t_{\max})=\theta^{\star}$ is finite by assumption.
Therefore, the termination criterion in (25) should also be met when $N$ is
large enough, because $t_{N}$ diverges and

$\displaystyle\frac{\max(\|\theta(t_{\max})\|_{2}^{2},\|\theta_{N}\|_{2}^{2})}{(e^{t_{N}}-1)}\leq\frac{2\max(\|\theta(t_{\max})\|_{2}^{2},\|\theta(t_{N})\|_{2}^{2})}{(e^{t_{N}}-1)}\leq\frac{2\|\theta^{\star}\|_{2}^{2}}{(e^{t_{N}}-1)}\rightarrow
0\text{ as }N\rightarrow\infty\,.$

Finally, we are ready to prove (29) after the algorithm is terminated. Upon
termination when $k+1=N$, we have one of the two conditions in (25) must hold.
If $t_{N}>t_{\max}$, it is easy to see that the step sizes defined in (27) and
(28) satisfy all the assumptions in Theorem 4, by using (21) in Theorem 4 and
the definition of $\alpha_{k}$, we have that

$\displaystyle\sup_{0\leq t\leq t_{\max}}$
$\displaystyle\left\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\right\\}\lesssim(e^{\alpha_{1}}-1)^{2}\|\nabla
L_{n}(\bm{0})\|_{2}^{2}\leq\epsilon\,.$

If the second inequality in (25) holds, then

$\displaystyle\frac{2\max(\|\theta(t_{\max})\|_{2}^{2},\|\theta_{N}\|_{2}^{2})}{(e^{t_{N}}-1)}$
$\displaystyle\leq\frac{2\|\theta(t_{\max})\|_{2}^{2}}{(e^{t_{N}}-1)}\leq\frac{2\|\theta_{N}\|_{2}^{2}}{(e^{t_{N}}-1)}\frac{\|\theta(t_{\max})\|_{2}^{2}}{\|\theta_{N}\|_{2}^{2}}$
$\displaystyle\leq\frac{2\|\theta(t_{\max})\|_{2}^{2}}{\|\theta(t_{N})\|_{2}^{2}}(e^{\alpha_{1}}-1)^{2}\|\nabla
L_{n}(\bm{0})\|_{2}^{2}\,.$

Combining this with (22) in Theorem 4, we obtain that

$\displaystyle\sup_{0\leq t\leq t_{\max}}$
$\displaystyle\left\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\right\\}\lesssim\frac{\|\theta(t_{\max})\|_{2}^{2}}{\|\theta(t_{N})\|_{2}^{2}}(e^{\alpha_{1}}-1)^{2}\|\nabla
L_{n}(\bm{0})\|_{2}^{2}\leq\epsilon\,.$

This completes the proof of Theorem 5.

We next present a supporting lemma for the proof of Theorem 6 and 10.

###### Lemma 3

For any $\epsilon\in(0,1]$, let $(e^{\alpha_{1}}-1)^{2}=c_{1}^{2}\epsilon$ and
$\alpha_{k+1}=\ln(1+c_{2}e^{t_{k}/2}(e^{\alpha_{1}}-1))$, where
$c_{1},c_{2}>0$ are constants and $t_{k}=\sum_{i=1}^{k}\alpha_{i}$. Define
$k^{\star}:=\max\\{k:t_{k}\leq\ln(\epsilon^{-1})\\}$. Then,

$k^{\star}<\frac{1+c_{1}c_{2}+\sqrt{1+c_{1}c_{2}}}{c_{1}c_{2}\sqrt{\epsilon}\sqrt{1+c_{1}\sqrt{\epsilon}}},\,\sum_{k=1}^{k^{\star}}e^{t_{k}}(t_{k}+1)\leq\frac{(1+2c_{1}c_{2}+\sqrt{1+c_{1}c_{2}})(1+\ln(\epsilon^{-1}))}{c_{1}c_{2}\epsilon}\,.$
(91)

Proof of Lemma 3.  It is easy to see that $\alpha_{k}$ is strictly increasing
for $k\geq 2$ and by definition of $k^{\star}$, we have that

$\alpha_{k+1}\leq\ln(1+c_{1}c_{2})\text{ for any }1\leq k\leq k^{\star}\,,$
(92)

which implies that $e^{\alpha_{k+1}/2}\leq(1+c_{1}c_{2})^{1/2}$ for any $1\leq
k\leq k^{\star}$. Moreover, since
$e^{\alpha_{k+1}}=1+c_{1}c_{2}\sqrt{\epsilon}e^{t_{k}/2}$, we have that

$\displaystyle e^{-t_{k}/2}-e^{-t_{k+1}/2}$
$\displaystyle=\frac{e^{\alpha_{k+1}/2}-1}{e^{t_{k+1}/2}}\
=\frac{e^{-t_{k+1}/2}(e^{\alpha_{k+1}}-1)}{e^{\alpha_{k+1}/2}+1}=\frac{e^{-\alpha_{k+1}/2}c_{1}c_{2}\sqrt{\epsilon}}{e^{\alpha_{k+1}/2}+1}=\frac{c_{1}c_{2}\sqrt{\epsilon}}{e^{\alpha_{k+1}}+e^{\alpha_{k+1}/2}}$

for any $k\geq 1$. Therefore, for any $1\leq k\leq k^{\star}$,

$\displaystyle e^{-t_{1}/2}-e^{-t_{k^{\star}+1}/2}$
$\displaystyle=\sum_{i=1}^{k^{\star}}\left(e^{-t_{i}/2}-e^{-t_{i+1}/2}\right)=\sum_{i=1}^{k^{\star}}\frac{c_{1}c_{2}\sqrt{\epsilon}}{e^{\alpha_{i+1}}+e^{\alpha_{i+1}/2}}\geq\frac{k^{\star}c_{1}c_{2}\sqrt{\epsilon}}{1+c_{1}c_{2}+\sqrt{1+c_{1}c_{2}}},$
$\displaystyle e^{-t_{k}/2}-e^{-t_{k^{\star}}/2}$
$\displaystyle=\sum_{i=k}^{k^{\star}-1}\left(e^{-t_{i}/2}-e^{-t_{i+1}/2}\right)=\sum_{i=k}^{k^{\star}-1}\frac{c_{1}c_{2}\sqrt{\epsilon}}{e^{\alpha_{i+1}}+e^{\alpha_{i+1}/2}}\geq\frac{(k^{\star}-k)c_{1}c_{2}\sqrt{\epsilon}}{1+c_{1}c_{2}+\sqrt{1+c_{1}c_{2}}},$

which implies the first inequality in (91) and

$e^{-t_{k}/2}\geq
e^{-t_{k^{\star}}/2}+\frac{(k^{\star}-k)c_{1}c_{2}\sqrt{\epsilon}}{1+c_{1}c_{2}+\sqrt{1+c_{1}c_{2}}}\geq\sqrt{\epsilon}+\frac{c_{1}c_{2}\sqrt{\epsilon}}{1+c_{1}c_{2}+\sqrt{1+c_{1}c_{2}}}(k^{\star}-k)$
(93)

by using the fact that $t_{k^{\star}}\leq\ln(\epsilon^{-1})$. Therefore, for
any $1\leq k\leq k^{\star}$,

$e^{t_{k}}\leq\frac{\epsilon^{-1}}{(1+C(k^{\star}-k))^{2}}\,,$ (94)

where $C=\frac{c_{1}c_{2}}{1+c_{1}c_{2}+\sqrt{1+c_{1}c_{2}}}<1$. Now we are
ready to prove the second inequality in (91). By (94) and the fact that
$t_{k^{\star}}\leq\ln(\epsilon^{-1})$, it follows that

$\displaystyle\sum_{k=1}^{k^{\star}}e^{t_{k}}t_{k}$ $\displaystyle\leq$
$\displaystyle
e^{t_{k^{\star}}}t_{k^{\star}}+\sum_{k=1}^{k^{\star}-1}\epsilon^{-1}\frac{1}{(1+C(k^{\star}-k))^{2}}\ln\left(\epsilon^{-1}\frac{1}{(1+C(k^{\star}-k))^{2}}\right)$
$\displaystyle\leq$
$\displaystyle\epsilon^{-1}\ln(\epsilon^{-1})+\int_{1}^{k^{\star}}\epsilon^{-1}\frac{1}{(1+C(k^{\star}-x))^{2}}\ln\left(\epsilon^{-1}\frac{1}{(1+C(k^{\star}-x))^{2}}\right)dx$
$\displaystyle=$
$\displaystyle\epsilon^{-1}\ln(\epsilon^{-1})+\frac{1}{2C\sqrt{\epsilon}}\int_{a}^{b}te^{t/2}dt=\epsilon^{-1}\ln(\epsilon^{-1})+\frac{1}{C\sqrt{\epsilon}}((b-2)e^{b/2}-(a-2)e^{a/2})$

where $a=\ln(\epsilon^{-1})-2\ln(1+C(k^{\star}-1))$ and
$b=\ln(\epsilon^{-1})$. Using (94) with $k=1$ and the fact that function
$(t-2)e^{t/2}$ is increasing over $t\geq 0$, we have that

$\displaystyle a=\ln(\epsilon^{-1})-2\ln(1+C(k^{\star}-1))\geq t_{1}>0\text{
and }(a-2)e^{a/2}\geq-2\,.$

Hence,

$\displaystyle\frac{(b-2)e^{b/2}-(a-2)e^{a/2}}{C\sqrt{\epsilon}}\leq\frac{(b-2)e^{b/2}}{C\sqrt{\epsilon}}+\frac{2}{C\sqrt{\epsilon}}=\frac{\epsilon^{-1}(\ln(\epsilon^{-1})-2)}{C}+\frac{2}{C\sqrt{\epsilon}}\leq\frac{\epsilon^{-1}\ln(\epsilon^{-1})}{C}\,,$

provided that $\epsilon<1$. Combining, we obtain that

$\sum_{k=1}^{k^{\star}}e^{t_{k}}t_{k}\leq\epsilon^{-1}\ln(\epsilon^{-1})+\frac{\epsilon^{-1}\ln(\epsilon^{-1})}{C}=\frac{(C+1)\epsilon^{-1}\ln(\epsilon^{-1})}{C}\,.$

Similarly, by using (94), we have that

$\displaystyle\sum_{k=1}^{k^{\star}}e^{t_{k}}$ $\displaystyle\leq$
$\displaystyle\epsilon^{-1}+\sum_{k=1}^{k^{\star}-1}\epsilon^{-1}\frac{1}{(1+C(k^{\star}-k))^{2}}\leq\epsilon^{-1}+\int_{1}^{k^{\star}}\frac{\epsilon^{-1}}{(1+C(k^{\star}-x))^{2}}\,dx$
$\displaystyle=$
$\displaystyle\epsilon^{-1}+\frac{\epsilon^{-1}}{C}\left(1-\frac{1}{1+C(k^{\star}-1)}\right)\leq\frac{(C+1)\epsilon^{-1}}{C}\,.$

Consequently, we have that

$\sum_{k=1}^{k^{\star}}e^{t_{k}}(t_{k}+1)\leq\frac{(C+1)\epsilon^{-1}(1+\ln(\epsilon^{-1}))}{C}=\frac{(1+2c_{1}c_{2}+\sqrt{1+c_{1}c_{2}})\epsilon^{-1}(1+\ln(\epsilon^{-1}))}{c_{1}c_{2}}\,.$

This completes the proof of Lemma 3.

Proof of Theorem 6.  We first consider the case where $t_{\max}=\infty$ and
$\gamma_{1}\geq 1$. In view of the termination criterion (25), the algorithm
will be terminated when $t_{k}=\mathcal{O}(\ln(\epsilon^{-1}))$. We define
$N=\max\\{k:t_{k}\leq\ln(\epsilon^{-1})\\}$. By applying Lemma 1 and 2 with
$c_{0}=26/25$, we have

$\frac{\|\theta_{k}\|_{2}}{1-e^{-t_{k}}}\leq\frac{5}{4}\frac{\|\theta(t_{k})\|_{2}}{1-e^{-t_{k}}}\leq\frac{5}{4}\left(\|\theta(t_{\max})\|_{2}+\|\nabla
L_{n}(\bm{0})\|_{2}\right)\,.$ (95)

Therefore,

$\displaystyle e^{A_{k}}-1$
$\displaystyle=\frac{e^{t_{k}/2}(e^{\alpha_{1}}-1)\|\nabla
L_{n}(\bm{0})\|_{2}(1-e^{-t_{k}})}{\|\theta_{k}\|_{2}}\geq\frac{4e^{t_{k}/2}(e^{\alpha_{1}}-1)\|\nabla
L_{n}(\bm{0})\|_{2}}{5(\|\theta(t_{\max})\|_{2}+\|\nabla
L_{n}(\bm{0})\|_{2})}\,,$ $\displaystyle e^{B_{k}}-1$
$\displaystyle=\left(C_{2}\beta
e^{t_{k}}\max\left((e^{t_{k}}-1)^{-\gamma_{1}},(e^{t_{k}}-1)^{-1-\gamma_{2}/2}\right)\|\theta_{k}\|_{2}\right)^{-1}$
$\displaystyle\geq\left(C_{2}\beta\max\left((e^{t_{k}}-1)^{1-\gamma_{1}},(e^{t_{k}}-1)^{-\gamma_{2}/2}\right)(\|\theta(t_{\max})\|_{2}+\|\nabla
L_{n}(\bm{0})\|_{2})\right)^{-1}$
$\displaystyle\geq\left(C_{2}\beta(\|\theta(t_{\max})\|_{2}+\|\nabla
L_{n}(\bm{0})\|_{2})\right)^{-1}\,,$

which implies that,

$\alpha_{k+1}\geq\ln(1+\nu_{1}e^{t_{k}/2}(e^{\alpha_{1}}-1))$

when $\alpha_{k+1}\leq\min(\alpha_{\max},\,\ln(1+\nu_{2}))$, where we treat

$\nu_{1}=\frac{4\|\nabla
L_{n}(\bm{0})\|_{2}}{5(\|\theta(t_{\max})\|_{2}+\|\nabla
L_{n}(\bm{0})\|_{2})}\text{ and
}\nu_{2}=\left(C_{2}\beta(\|\theta(t_{\max})\|_{2}+\|\nabla
L_{n}(\bm{0})\|_{2})\right)^{-1}$

as problem-dependent constants. Then, applying Lemma 3, we have that

$N\leq\mathcal{O}\left(\epsilon^{-1/2}+\ln(\epsilon^{-1})/\min(\alpha_{\max},\ln(1+\nu_{2}))\right)=\mathcal{O}\left(\epsilon^{-1/2}\right)\,,$

if we treat $\beta$, $\|\theta(t_{\max})\|_{2}$, and $\|\nabla
L_{n}(\bm{0})\|_{2}$ as constants. When $t_{\max}<\infty$ and $\gamma_{1}\geq
1$, the algorithm terminates at $N$ if $t_{N}>t_{\max}$. Since $\alpha_{k}$ is
increasing, it follows that $N\leq
t_{\max}/\alpha_{1}=\mathcal{O}\left(\epsilon^{-1/2}\right)$. This completes
the proof of Theorem 6.

Proof of Theorem 7.  It is easy to verify that $f_{t_{k}}(\theta)$ is
$m_{k}$-strongly convex with $L_{k}$-Lipschitz gradient, where
$m_{k}=m(1-e^{-t_{k}})+e^{-t_{k}}$ and $L_{k}=L(1-e^{-t_{k}})+e^{-t_{k}}$. By
standard analysis of gradient descent for strongly convex and smooth functions
(see, e.g., Theorem 2.1.14 of Nesterov, 1998), we have that

$\displaystyle\|\theta_{k+1}-\theta(t_{k+1})\|_{2}$ $\displaystyle\leq$
$\displaystyle\left(1-\frac{2m_{k+1}L_{k+1}}{m_{k+1}+L_{k+1}}\eta_{k+1}\right)^{n_{k+1}}\|\theta_{k}-\theta(t_{k+1})\|_{2}\,,$
(96)

where $\eta_{k+1}\leq\frac{2}{m_{k+1}+L_{k+1}}$. Similar to the derivation of
(48), we obtain that

$\|\theta(t^{\prime})-\theta(t)\|_{2}\leq\frac{|C(t^{\prime})-C(t)|}{C(t)+mC(t)C(t^{\prime})}\|\theta(t)\|_{2}\,,$
(97)

for any $t^{\prime}<t$, because
$C(t^{\prime})L_{n}(\theta)+\frac{1}{2}\|\theta\|_{2}^{2}$ is
$(1+C(t^{\prime})m)$-strongly convex. Using this with
$t^{\prime}=t_{k},t=t_{k+1}$, and applying the triangular inequality, we
obtain that

$\displaystyle\|\theta_{k}-\theta(t_{k+1})\|_{2}\leq\|\theta_{k}-\theta(t_{k})\|_{2}+\|\theta(t_{k})-\theta(t_{k+1})\|_{2}$
$\displaystyle=$
$\displaystyle\|\theta_{k}-\theta(t_{k})\|_{2}+\frac{(e^{t_{k+1}}-e^{t_{k}})}{(e^{t_{k+1}}-1)(1+m(e^{t_{k}}-1))}\|\theta(t_{k+1})\|_{2}$
$\displaystyle\leq$
$\displaystyle\|\theta_{k}-\theta(t_{k})\|_{2}+\frac{(e^{\alpha_{k+1}}-1)}{(e^{t_{k+1}}-1)m_{k}}\|\theta(t_{k+1})\|_{2}\,.$

Combining this with (96), we get

$\displaystyle\|\theta_{k+1}-\theta(t_{k+1})\|_{2}$
$\displaystyle\leq\left(1-\frac{2m_{k+1}L_{k+1}}{m_{k+1}+L_{k+1}}\eta_{k+1}\right)^{n_{k+1}}$
$\displaystyle\quad\quad\quad\left(\|\theta_{k}-\theta(t_{k})\|_{2}+\frac{(e^{\alpha_{k+1}}-1)\|\theta(t_{k+1})\|_{2}}{(e^{t_{k+1}}-1)m_{k}}\right)\,.$
(98)

Next we use induction to show that

$\|\theta_{k}-\theta(t_{k})\|_{2}\leq
2\left(1-\frac{2m_{k}L_{k}}{m_{k}+L_{k}}\eta_{k}\right)^{n_{k}}\frac{(e^{\alpha_{k}}-1)\|\theta(t_{k})\|_{2}}{(e^{t_{k}}-1)m_{k-1}}\,.$
(99)

Suppose that (99) holds for $\theta_{k}$, then using (98) and (99), it follows
that (99) holds for $\theta_{k+1}$ if

$2\left(1-\frac{2m_{k}L_{k}}{m_{k}+L_{k}}\eta_{k}\right)^{n_{k}}\frac{(e^{\alpha_{k}}-1)\|\theta(t_{k})\|_{2}}{(e^{t_{k}}-1)m_{k-1}}\leq\frac{(e^{\alpha_{k+1}}-1)\|\theta(t_{k+1})\|_{2}}{(e^{t_{k+1}}-1)m_{k}}$
(100)

for any $k\geq 1$. Next we show that (100) can be ensured by the conditions in
(32). First, using the fact that

$\frac{m_{k}}{m_{k-1}}=\frac{m(1-e^{-t_{k}})+e^{-t_{k}}}{m(1-e^{-t_{k-1}})+e^{-t_{k-1}}}\leq\begin{cases}m_{1}&\text{
when }k=1\\\ \frac{1-e^{-t_{k}}}{1-e^{-t_{k-1}}}&\text{ for any }k\geq
2\,,\end{cases}$ (101)

and

$\displaystyle\frac{(e^{t_{k+1}}-1)(e^{\alpha_{k}}-1)(1-e^{-t_{k}})}{(e^{t_{k}}-1)(e^{\alpha_{k+1}}-1)(1-e^{-t_{k-1}})}\leq
12\text{ for any }k\geq
2,\,\frac{(e^{t_{2}}-1)(e^{\alpha_{1}}-1)}{(e^{t_{1}}-1)(e^{\alpha_{2}}-1)}\leq
5\,,$

when $\alpha_{k}\leq 2\alpha_{k-1}$, $\alpha_{k+1}\geq\alpha_{k}/2$, and
$\alpha_{k}\leq\ln(2)$ for $k\geq 1$, it follows that a sufficient condition
for (100) is

$n_{1}\geq\frac{\log(10m_{1})}{-\log\left(1-\frac{2m_{1}L_{1}}{m_{1}+L_{1}}\eta_{1}\right)}\text{
and
}n_{k}\geq\frac{\log(24)}{-\log\left(1-\frac{2m_{k}L_{k}}{m_{k}+L_{k}}\eta_{k}\right)}$

for any $k\geq 2$.

Next, using the fact that $f_{t_{k}}(\cdot)$ has $L_{k}$-Lipschitz gradient,
we have

$\|g_{k}\|_{2}\leq L_{k}\|\theta_{k}-\theta(t_{k})\|_{2}\leq
2L_{k}\left(1-\frac{2m_{k}L_{k}}{m_{k}+L_{k}}\eta_{k}\right)^{n_{k}}\frac{(e^{\alpha_{k}}-1)\|\theta(t_{k})\|_{2}}{(e^{t_{k}}-1)m_{k-1}}\,.$

This completes the proof of Theorem 7.

Proof of Theorem 8.  Since $C(t)L_{n}(\theta)+\frac{1}{2}\|\theta\|_{2}^{2}$
is $(1+C(t)m)$-strongly convex, using (45), we have that

$\|\theta(t)-\bm{0}\|_{2}\leq\frac{\|C(t)\nabla
L_{n}(\bm{0})\|_{2}}{1+C(t)m}\,,$ (102)

which implies that,

$\|\theta(t_{k})\|_{2}\leq\frac{1-e^{-t_{k}}}{m_{k}}\|\nabla
L_{n}(\bm{0})\|_{2}\,.$ (103)

By Theorem 7, since

$n_{k}\geq\frac{\log(24)+\max(0,\log(L_{k}/m_{k-1}))}{-\log\left(1-\frac{2m_{k}L_{k}}{m_{k}+L_{k}}\eta_{k}\right)}\,,$
(104)

it follows that

$\|g_{k}\|_{2}\leq
2\left(1-\frac{2m_{k}L_{k}}{m_{k}+L_{k}}\eta_{k}\right)^{n_{k}}\frac{(e^{\alpha_{k}}-1)\|\theta(t_{k})\|_{2}}{(e^{t_{k}}-1)m_{k-1}}\leq(12)^{-1}\frac{(e^{\alpha_{k}}-1)\|\theta(t_{k})\|_{2}}{(e^{t_{k}}-1)}\,.$
(105)

Similar to (82), we can show that

$\frac{1}{1+(12)^{-1}}\leq\frac{\|\theta_{k}\|_{2}}{\|\theta(t_{k})\|_{2}}\leq\frac{1}{1-(12)^{-1}}\,.$
(106)

Using this, Lemma 1, and (13), we have that

$\displaystyle\sup_{t\in[0,t_{1}]}$
$\displaystyle\left\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\right\\}\leq\max\left(e^{t_{1}}\|g_{1}\|_{2}^{2},\,\|\theta_{1}\|_{2}^{2}\right)+\frac{e^{t_{1}}(1-e^{-t_{1}})^{2}}{2}\|\nabla
L_{n}(\bm{0})\|_{2}^{2}$
$\displaystyle\leq\frac{e^{t_{1}}(1-e^{-t_{1}})^{2}}{2}\|\nabla
L_{n}(\bm{0})\|_{2}^{2}+(3/2)\|\theta(t_{1})\|_{2}^{2}\leq
2(e^{\alpha_{1}}-1)^{2}\|\nabla L_{n}(\bm{0})\|_{2}^{2}\,.$

Moreover, using (105), (106), and Corollary 1, we obtain that

$\displaystyle
e^{t_{k+1}}\left(\frac{1-e^{-t_{k+1}}}{1-e^{-t_{k}}}\right)^{2}\|g_{k}\|_{2}^{2}\leq\frac{e^{t_{k+1}}}{144}\left(\frac{1-e^{-t_{k+1}}}{1-e^{-t_{k}}}\right)^{2}\left(\frac{(e^{\alpha_{k}}-1)\|\theta(t_{k})\|_{2}}{(e^{t_{k}}-1)}\right)^{2}$
$\displaystyle\leq\frac{e^{\alpha_{k+1}}}{144}\frac{(e^{\alpha_{k}}-1)^{2}(1-e^{-t_{k+1}})^{2}}{(e^{\alpha_{k+1}}-1)^{2}(1-e^{-t_{k}})^{2}}e^{-t_{k}}\left(\frac{e^{\alpha_{k+1}}-1}{1-e^{-t_{k}}}\right)^{2}\|\theta(t_{k})\|_{2}^{2}\leq(20)^{-1}e^{-t_{k}}\left(\frac{e^{\alpha_{k+1}}-1}{1-e^{-t_{k}}}\right)^{2}\|\theta_{k}\|_{2}^{2}$
$\displaystyle
e^{t_{k+1}}\|g_{k+1}\|_{2}^{2}\leq\frac{e^{t_{k+1}}}{144}\left(\frac{(e^{\alpha_{k+1}}-1)\|\theta(t_{k+1})\|_{2}}{(e^{t_{k+1}}-1)}\right)^{2}\leq\frac{e^{\alpha_{k+1}}}{144}e^{-t_{k}}\left(\frac{e^{\alpha_{k+1}}-1}{1-e^{-t_{k}}}\right)^{2}\|\theta(t_{k})\|_{2}^{2}$
$\displaystyle\quad\quad\quad\leq(50)^{-1}e^{-t_{k}}\left(\frac{e^{\alpha_{k+1}}-1}{1-e^{-t_{k}}}\right)^{2}\|\theta_{k}\|_{2}^{2}\,,$

and

$\displaystyle(e^{-t_{k}}-e^{-t_{k+1}})^{2}\max\left\\{\frac{e^{t_{k+1}}\|\theta_{k}\|_{2}^{2}}{(1-e^{-t_{k}})^{2}},\,\frac{e^{t_{k}}\|\theta_{k+1}\|_{2}^{2}}{(1-e^{-t_{k+1}})^{2}}\right\\}$
$\displaystyle\leq\left(1-(12)^{-1}\right)^{-2}(e^{-t_{k}}-e^{-t_{k+1}})^{2}\max\left\\{\frac{e^{t_{k+1}}\|\theta(t_{k})\|_{2}^{2}}{(1-e^{-t_{k}})^{2}},\,\frac{e^{t_{k}}\|\theta(t_{k+1})\|_{2}^{2}}{(1-e^{-t_{k+1}})^{2}}\right\\}$
$\displaystyle\leq\left(1-(12)^{-1}\right)^{-2}e^{-t_{k}}\left(\frac{e^{\alpha_{k+1}}-1}{1-e^{-t_{k}}}\right)^{2}\|\theta(t_{k})\|_{2}^{2}$
$\displaystyle\leq\left(1-(12)^{-1}\right)^{-2}\left(1+(12)^{-1}\right)^{2}e^{-t_{k}}\left(\frac{e^{\alpha_{k+1}}-1}{1-e^{-t_{k}}}\right)^{2}\|\theta_{k}\|_{2}^{2}\,,$

where we have used the fact that
$e^{\alpha_{k+1}}(e^{\alpha_{k}}-1)(1-e^{-t_{k+1}})/(e^{\alpha_{k+1}}-1)(1-e^{-t_{k}})\leq(\sqrt{2}+1)^{2}$.
Combining these with (14), we have that

$\displaystyle\sup_{t\in[t_{k},t_{k+1}]}\left\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\right\\}\leq
e^{t_{k+1}}\max\left\\{\left(\frac{1-e^{-t_{k+1}}}{1-e^{-t_{k}}}\right)^{2}\|g_{k}\|_{2}^{2},\,\|g_{k+1}\|_{2}^{2}\right\\}$
$\displaystyle\quad\quad\quad\quad+(e^{-t_{k}}-e^{-t_{k+1}})^{2}\max\left\\{\frac{e^{t_{k+1}}\|\theta_{k}\|_{2}^{2}}{(1-e^{-t_{k}})^{2}},\,\frac{e^{t_{k}}\|\theta_{k+1}\|_{2}^{2}}{(1-e^{-t_{k+1}})^{2}}\right\\}$
$\displaystyle\leq\left((20)^{-1}+(1-(12)^{-1})^{-2}(1+(12)^{-1})^{2}\right)e^{-t_{k}}\left(\frac{e^{\alpha_{k+1}}-1}{1-e^{-t_{k}}}\right)^{2}\|\theta_{k}\|_{2}^{2}$
$\displaystyle\leq
2e^{-t_{k}}\left(\frac{e^{t_{k+1}-t_{k}}-1}{1-e^{-t_{k}}}\right)^{2}\|\theta_{k}\|_{2}^{2}$

for any $k\geq 1$.

Lastly, using (15), (105), (80), and part (ii) of Corollary 1, we have

$\displaystyle\sup_{t_{N}<t\leq t_{\max}}$
$\displaystyle\left\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\right\\}\leq\frac{e^{t_{N}}(1-e^{-t_{\max}})}{1-e^{-t_{N}}}\|g_{N}\|_{2}^{2}+\frac{3}{2(e^{t_{N}}-1)}\|\theta(t_{\max})\|_{2}^{2}$
$\displaystyle\leq\frac{e^{t_{N}}(1-e^{-t_{\max}})}{144(1-e^{-t_{N}})}\left(\frac{e^{\alpha_{N}}-1}{e^{t_{N}}-1}\right)^{2}\|\theta(t_{N})\|_{2}^{2}+\frac{3}{2(e^{t_{N}}-1)}\|\theta(t_{\max})\|_{2}^{2}$
$\displaystyle\leq\frac{2\|\theta(t_{\max})\|_{2}^{2}}{e^{t_{N}}-1}\,.$

Combining the three bounds, we obtain that when $t_{N}\leq t_{\max}$,

$\displaystyle\sup_{0\leq t\leq t_{\max}}$
$\displaystyle\left\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\right\\}\leq
2\max\Bigg{(}(e^{\alpha_{1}}-1)^{2}\|\nabla L_{n}(\bm{0})\|_{2}^{2}\,,$
$\displaystyle\max_{1\leq k\leq
N-1}e^{-t_{k}}\frac{(e^{\alpha_{k+1}}-1)^{2}}{(1-e^{-t_{k}})^{2}}\|\theta_{k}\|_{2}^{2}\,,\frac{\|\theta(t_{\max})\|_{2}^{2}}{e^{t_{N}}-1}\Bigg{)}\,,$

and when $t_{N-1}\leq t_{\max}<t_{N}$ for some $N\geq 1$.

$\displaystyle\sup_{0\leq t\leq
t_{\max}}\left\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\right\\}\leq\sup_{0\leq
t\leq t_{N}}\left\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\right\\}$
$\displaystyle\leq 2\max\Bigg{(}(e^{\alpha_{1}}-1)^{2}\|\nabla
L_{n}(\bm{0})\|_{2}^{2}\,,\max_{1\leq k\leq
N-1}e^{-t_{k}}\frac{(e^{\alpha_{k+1}}-1)^{2}}{(1-e^{-t_{k}})^{2}}\|\theta_{k}\|_{2}^{2}\Bigg{)}\,.$

This completes the proof of Theorem 8.

Proof of Theorem 9.  We first show that $\alpha_{k+1}\geq\alpha_{k}/2$. If
$\alpha_{k+1}=5^{-1}$ or $2\alpha_{k}$, then trivially
$\alpha_{k+1}\geq\alpha_{k}/2$. Now we assume that $\alpha_{k+1}=A_{k}$, where

$\displaystyle A_{k}$
$\displaystyle:=\ln\left(1+\frac{\epsilon^{1/2}e^{t_{k}/2}(1-e^{-t_{k}})}{\|\theta_{k}\|_{2}}\right)\,.$

First, using (105), (106), and the fact that
$\|\theta_{k}-\theta(t_{k})\|_{2}\leq e^{t_{k}}\|g_{k}\|_{2}$, we obtain that

$\displaystyle\|\theta_{k}\|_{2}$
$\displaystyle\leq\|\theta(t_{k})\|_{2}+\|\theta(t_{k})-\theta_{k}\|_{2}\leq\|\theta(t_{k})\|_{2}+e^{t_{k}}\|g_{k}\|_{2}\leq\|\theta(t_{k})\|_{2}+e^{t_{k}}\frac{(e^{\alpha_{k}}-1)}{12(e^{t_{k}}-1)}\|\theta(t_{k})\|_{2}\,,$

which implies that

$\|\theta_{k}\|_{2}\leq\|\theta(t_{k})\|_{2}\left(1+\frac{(e^{\alpha_{k}}-1)}{12(1-e^{-t_{k}})}\right)\,.$
(107)

When $k=1$, using (107) and the fact that
$e^{\alpha_{1}}-1\leq\sqrt{\epsilon}/\|\nabla L_{n}(\bm{0})\|_{2}$, we obtain
that

$\displaystyle\frac{e^{\alpha_{2}}-1}{e^{\alpha_{1}/2}-1}$
$\displaystyle=(e^{\alpha_{1}/2}+1)\frac{e^{\alpha_{2}}-1}{e^{\alpha_{1}}-1}\geq(e^{\alpha_{1}/2}+1)\frac{e^{A_{1}}-1}{e^{\alpha_{1}}-1}=(e^{\alpha_{1}/2}+1)e^{\alpha_{1}/2}\frac{\sqrt{\epsilon}(1-e^{-t_{1}})}{\|\theta_{1}\|_{2}(e^{\alpha_{1}}-1)}$
$\displaystyle\geq(e^{\alpha_{1}/2}+1)e^{\alpha_{1}/2}\frac{\sqrt{\epsilon}(1-e^{-t_{1}})}{\|\theta(t_{1})\|_{2}(e^{\alpha_{1}}-1)}\left(1+\frac{(e^{\alpha_{1}}-1)}{12(1-e^{-t_{1}})}\right)^{-1}$
$\displaystyle\geq\frac{(e^{-\alpha_{1}/2}+1)\sqrt{\epsilon}}{\|\nabla
L_{n}(\bm{0})\|_{2}(e^{\alpha_{1}}-1)}\left(1+e^{\alpha_{1}}/12\right)^{-1}\geq\frac{3}{4}(e^{-\alpha_{1}/2}+1)(1+e^{\alpha_{1}}/12)^{-1}\geq
1\,,$

provided that $\alpha_{1}\leq\ln(2)$. This implies that
$\alpha_{2}\geq\alpha_{1}/2$.

When $k\geq 2$, note that $\alpha_{k}\leq A_{k-1}$ and

$\displaystyle\frac{e^{\alpha_{k+1}}-1}{e^{\alpha_{k}/2}-1}$
$\displaystyle=(e^{\alpha_{k}/2}+1)\frac{e^{\alpha_{k+1}}-1}{e^{\alpha_{k}}-1}\geq(e^{\alpha_{k}/2}+1)\frac{e^{A_{k}}-1}{e^{A_{k-1}}-1}$
$\displaystyle=(e^{\alpha_{k}/2}+1)e^{\alpha_{k}/2}\frac{\epsilon^{1/2}(1-e^{-t_{k}})}{\|\theta_{k}\|_{2}}\frac{\|\theta_{k-1}\|_{2}}{\epsilon^{1/2}(1-e^{-t_{k-1}})}$
$\displaystyle\geq(e^{-\alpha_{k}/2}+1)\frac{(e^{t_{k}}-1)\|\theta_{k-1}\|_{2}}{(e^{t_{k-1}}-1)\|\theta_{k}\|_{2}}\,.$
(108)

Now similar to (107), we obtain that

$\|\theta(t_{k})\|_{2}\leq\|\theta_{k}\|_{2}+\|\theta(t_{k})-\theta_{k}\|_{2}\leq\|\theta_{k}\|_{2}+e^{t_{k}}\|g_{k}\|_{2}\leq\|\theta_{k}\|_{2}+\frac{(e^{\alpha_{k}}-1)}{12(1-e^{-t_{k}})}\|\theta(t_{k})\|_{2}\,,$

we have that

$\left(1-\frac{(e^{\alpha_{k}}-1)}{12(1-e^{-t_{k}})}\right)\leq\frac{\|\theta_{k}\|_{2}}{\|\theta(t_{k})\|_{2}}\leq\left(1+\frac{(e^{\alpha_{k}}-1)}{12(1-e^{-t_{k}})}\right)\,.$
(109)

Hence,

$\frac{(e^{t_{k}}-1)\|\theta_{k-1}\|_{2}}{(e^{t_{k-1}}-1)\|\theta_{k}\|_{2}}\geq\frac{(e^{t_{k}}-1)\|\theta(t_{k-1})\|_{2}}{(e^{t_{k-1}}-1)\|\theta(t_{k})\|_{2}}\frac{1-\frac{(e^{\alpha_{k}}-1)}{12(1-e^{-t_{k}})}}{1+\frac{(e^{\alpha_{k}}-1)}{12(1-e^{-t_{k}})}}\geq\frac{1-\frac{(e^{\alpha_{k}}-1)}{12(1-e^{-t_{k}})}}{1+\frac{(e^{\alpha_{k}}-1)}{12(1-e^{-t_{k}})}}$

where the last inequality uses part (ii) of Corollary 1. Combining this with
(108), we obtain that

$\frac{e^{\alpha_{k+1}}-1}{e^{\alpha_{k}/2}-1}\geq(e^{-\alpha_{k}/2}+1)\frac{1-\frac{(e^{\alpha_{k}}-1)}{12(1-e^{-t_{k}})}}{1+\frac{(e^{\alpha_{k}}-1)}{12(1-e^{-t_{k}})}}\,.$
(110)

Therefore, to prove $\alpha_{k+1}\geq\alpha_{k}/2$, it suffices to show that
the RHS of the above inequality is no smaller than $1$. To this end, using the
fact that $\alpha_{k}\leq\ln(2)$ for all $k\geq 1$, we have

$\displaystyle\frac{(e^{\alpha_{k}}-1)}{(1-e^{-t_{k}})}$
$\displaystyle=\frac{e^{\alpha_{k}}(1-e^{-\alpha_{k}})}{1-e^{-t_{k}}}\leq
e^{\alpha_{k}}\leq 2$

for any $k\geq 1$. Combining this with (110), we have that

$\frac{e^{\alpha_{k+1}}-1}{e^{\alpha_{k}/2}-1}\geq(e^{-\alpha_{k}/2}+1)\frac{1-\frac{(e^{\alpha_{k}}-1)}{12(1-e^{-t_{k}})}}{1+\frac{(e^{\alpha_{k}}-1)}{12(1-e^{-t_{k}})}}\geq(1/\sqrt{2}+1)\frac{1-6^{-1}}{1+6^{-1}}>1\,,$

which proves that $\alpha_{k+1}\geq\alpha_{k}/2$. Hence, $\alpha_{k}$ satisfy
all the conditions in Theorem 8.

Next, we show that the algorithm will terminate in finite steps. We first show
that $t_{k}$ diverges. To this end, using (60) and (106), we have

$\displaystyle\frac{\epsilon^{1/2}e^{t_{k}/2}(1-e^{-t_{k}})}{\|\theta_{k}\|_{2}}\geq\frac{e^{t_{k}/2}(e^{\alpha_{1}}-1)\|\nabla
L_{n}(\bm{0})\|_{2}(1-e^{-t_{k}})}{\|\theta(t_{k})\|_{2}/(1-(12)^{-1})}$
$\displaystyle\geq\frac{e^{t_{k}/2}(e^{\alpha_{1}}-1)\|\nabla
L_{n}(\bm{0})\|_{2}(1-e^{-t_{k}})}{2(e^{t_{k}}-1)\|\nabla
L_{n}(\bm{0})\|_{2}}\geq 2^{-1}(e^{\alpha_{1}}-1)e^{-t_{k}/2}\,,$

which implies that

$A_{k}\geq\ln(1+2^{-1}(e^{\alpha_{1}}-1)e^{-t_{k}/2})\geq\frac{(e^{\alpha_{1}}-1)e^{-t_{k}/2}}{2+(e^{\alpha_{1}}-1)e^{-t_{k}/2}}=\frac{(e^{\alpha_{1}}-1)}{2e^{t_{k}/2}+(e^{\alpha_{1}}-1)}\,.$
(111)

Thus,

$\alpha_{k+1}\geq\min\left(\alpha_{\max},2\alpha_{k},\frac{(e^{\alpha_{1}}-1)}{2e^{t_{k}/2}+(e^{\alpha_{1}}-1)}\right)\,.$
(112)

Now we prove the divergence of $t_{k}$ by contradiction. Suppose that $t_{k}$
does not diverge. Then there must exist a constant $T$ such that $t_{k}<T$ for
all $k$. However, now we have

$\alpha_{k+1}\geq\min\left(\alpha_{\max},2\alpha_{k},\frac{(e^{\alpha_{1}}-1)}{2e^{T/2}+(e^{\alpha_{1}}-1)}\right)\,,$

which implies that $\alpha_{k}$ is lower bounded by a positive constant when
$k$ is large enough, implying that $t_{k}$ should diverge. This is a
contradiction. Hence, $t_{k}$ diverges.

Now we are ready to show that the algorithm must terminate after a finite
number of iterations. If $t_{\max}<\infty$, then $t_{k}\geq t_{\max}$ must
hold for large enough $k$ as $t_{k}$ diverges. If $t_{\max}=\infty$, then we
have that $\theta(t_{\max})=\theta^{\star}$ is finite by assumption.
Therefore, the termination criterion in (25) should also be met when $N$ is
large enough, because $t_{N}$ diverges and

$\displaystyle\frac{\max(\|\theta(t_{\max})\|_{2}^{2},\|\theta_{N}\|_{2}^{2})}{(e^{t_{N}}-1)}\leq\frac{2\max(\|\theta(t_{\max})\|_{2}^{2},\|\theta(t_{N})\|_{2}^{2})}{(e^{t_{N}}-1)}\leq\frac{2\|\theta^{\star}\|_{2}^{2}}{(e^{t_{N}}-1)}\rightarrow
0\text{ as }N\rightarrow\infty\,.$

Finally, we are ready to prove (40) upon termination. Using (35) and (36) in
Theorem 8, and the definition of $\alpha_{1}$ and $\alpha_{k+1}$, we have that

$\displaystyle
e^{-t_{k}}\left(\frac{e^{\alpha_{k+1}}-1}{1-e^{-t_{k}}}\right)^{2}\|\theta_{k}\|_{2}^{2}\leq(e^{\alpha_{1}}-1)^{2}\|\nabla
L_{n}(\bm{0})\|_{2}^{2}\leq\epsilon\text{ and }$
$\displaystyle\frac{\|\theta(t_{\max})\|_{2}^{2}}{(e^{t_{N}}-1)}\leq\frac{2\|\theta_{N}\|_{2}^{2}}{(e^{t_{N}}-1)}\frac{\|\theta(t_{\max})\|_{2}^{2}}{2\|\theta_{N}\|_{2}^{2}}\leq\epsilon\frac{\|\theta(t_{\max})\|_{2}^{2}}{\|\theta(t_{N})\|_{2}^{2}}\,.$

for any $k\geq 1$ when the algorithm is terminated, and after termination,

$\sup_{0\leq t\leq
t_{\max}}\left\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\right\\}\leq\begin{cases}\frac{2\|\theta(t_{\max})\|_{2}^{2}}{\|\theta(t_{N})\|_{2}^{2}}\epsilon&\text{
when }t_{\max}\geq t_{N}\\\ 2\epsilon&\text{ when
}t_{\max}<t_{N}\end{cases}\,,$

which implies (40). This completes the proof of Theorem 9.

Proof of Theorem 10.  We first bound the number of gradient steps at each
iteration. Since $m=0$, we have that $m_{k}=e^{-t_{k}}$. By assumption, we
have that $\eta_{k}=\eta=\mathcal{O}(\min(1,L^{-1}))$. Then the upper bounds
on $n_{1}$ and $n_{k+1}$ in (34) can be bounded further as follows

$\displaystyle\frac{\log(24)+\max(0,\log(L_{k+1}/m_{k}))}{-\log\left(1-\frac{2m_{k+1}L_{k+1}}{m_{k+1}+L_{k+1}}\eta_{k+1}\right)}\leq\frac{\log(24)+\max(0,\log(L_{k+1}/m_{k}))}{\frac{2m_{k+1}L_{k+1}}{m_{k+1}+L_{k+1}}\eta_{k+1}}$
$\displaystyle\leq\frac{\log(24)+\max(0,\log(L_{k+1}/m_{k}))}{m_{k+1}\eta}\leq\frac{\log(24)+t_{k}+\log(L_{k+1})}{m_{k+1}\eta}=\mathcal{O}\left(e^{t_{k+1}}(t_{k+1}+1)\right)\,,$

where we have used $L_{k}\geq m_{k}$ for any $k\geq 1$. Similarly, we also we
have

$\displaystyle\frac{\log(10m_{1}L_{1})}{-\log\left(1-\frac{2m_{1}L_{1}}{m_{1}+L_{1}}\eta_{1}\right)}\lesssim
e^{t_{1}}\,,$

where we have used the fact that $-\log(1-x)\geq x$, $L_{k}\leq\max(L,1)$, and
treated $L$ as a constant.

Next, By applying Lemma 1 and (109), we have

$\frac{\|\theta_{k}\|_{2}}{1-e^{-t_{k}}}\leq\frac{7}{6}\frac{\|\theta(t_{k})\|_{2}}{1-e^{-t_{k}}}\leq\frac{7}{6}\left(\|\theta(t_{\max})\|_{2}+\|\nabla
L_{n}(\bm{0})\|_{2}\right)\,.$ (113)

Therefore, when $\alpha_{k+1}\leq\ln(2)$, we have that

$\displaystyle e^{\alpha_{k+1}}-1$
$\displaystyle=\frac{e^{t_{k}/2}(e^{\alpha_{1}}-1)\|\nabla
L_{n}(\bm{0})\|_{2}(1-e^{-t_{k}})}{\|\theta_{k}\|_{2}}\geq\frac{6e^{t_{k}/2}(e^{\alpha_{1}}-1)\|\nabla
L_{n}(\bm{0})\|_{2}}{7(\|\theta(t_{\max})\|_{2}+\|\nabla
L_{n}(\bm{0})\|_{2})}\,,$

which implies that

$\alpha_{k+1}\geq\ln(1+\nu_{1}e^{t_{k}/2}(e^{\alpha_{1}}-1))$

when $\alpha_{k+1}\leq\ln(2)$, where we treat

$\nu_{1}=\frac{6\|\nabla
L_{n}(\bm{0})\|_{2}}{7(\|\theta(t_{\max})\|_{2}+\|\nabla
L_{n}(\bm{0})\|_{2})}$

as problem-dependent constants.

Now we are ready to derive the bound for the number of gradient steps. When
$t_{\max}=\infty$, in view of the termination criterion (39), the algorithm
will be terminated when $t_{k}=\mathcal{O}\left(\ln(\epsilon^{-1})\right)$.
Therefore, the total number of gradient steps can be bounded as

$\sum_{k=1}^{k^{\star}}n_{k}\lesssim\sum_{k=1}^{k^{\star}}e^{t_{k}}(t_{k}+1)\lesssim\epsilon^{-1}(1+\ln(\epsilon^{-1}))\,,$

where $k^{\star}=\max\\{k:t_{k}\leq\ln(\epsilon^{-1})\\}$ and we have used
Lemma 3. Hence, the total number of gradient steps is at most
$\mathcal{O}\left(\epsilon^{-1}\ln(\epsilon^{-1})\right)$.

When $t_{\max}<\infty$, then in view of the termination criterion (39), the
algorithm will be terminated when $t_{k}>t_{\max}$. Therefore, the total
number of gradient steps can be bounded as

$\displaystyle\sum_{k=1}^{k^{\star}}n_{k}+\max(0,t_{\max}-t_{k^{\star}})/\ln(1+\nu_{1})\lesssim\sum_{k=1}^{k^{\star}}e^{t_{k}}(t_{k}+1)+1/\ln(1+\nu_{1})\lesssim\epsilon^{-1}(1+\ln(\epsilon^{-1}))\,,$

where again we have used Lemma 3. In this case, the total number of gradient
steps is also at most
$\mathcal{O}\left(\epsilon^{-1}\ln(\epsilon^{-1})\right)$. This completes the
proof of Theorem 10.

Proof of Corollary 3.  We first show that the bounds in Theorem 8 continue to
hold. The proof is similar to that of Theorem 8 with some slight
modifications. In particular, upon termination of the gradient descent method
at $t_{k}$, we have (41). Replacing the bound (105) in the proof of Theorem 8
by (41), and following a similar argument, we obtain that

$\sup_{0\leq t\leq
t_{\max}}\left\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\right\\}\\\
\lesssim\max\Bigg{(}(e^{\alpha_{1}}-1)^{2}\|\nabla
L_{n}(\bm{0})\|_{2}^{2}\,,\max_{1\leq k\leq
N-1}e^{-t_{k}}\left(\frac{e^{\alpha_{k+1}}-1}{1-e^{-t_{k}}}\right)^{2}\|\theta_{k}\|_{2}^{2}\Bigg{)}\,.$

when $t_{N}\geq t_{\max}$ for some $N$; and

$\sup_{0\leq t\leq
t_{\max}}\left\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\right\\}\lesssim\max\Bigg{(}(e^{\alpha_{1}}-1)^{2}\|\nabla
L_{n}(\bm{0})\|_{2}^{2}\,,\\\ \max_{1\leq k\leq
N-1}e^{-t_{k}}\left(\frac{e^{\alpha_{k+1}}-1}{1-e^{-t_{k}}}\right)^{2}\|\theta_{k}\|_{2}^{2}\,,\frac{\|\theta(t_{\max})\|_{2}^{2}}{(e^{t_{N}}-1)}\Bigg{)}$

when $t_{N}\leq t_{\max}$ and $\|\theta(t_{\max})\|_{2}<\infty$. Then the
bound (42) follows from these bounds, following the proof of Theorem 9. This
completes the proof of Corollary 3.

Proof of Proposition 1.  We verify condition (16) for the functions in Table 1
separately.

Log-barrier function.  Note that $L^{\prime}_{n}(\theta)=-\theta^{-1}$ and
$L_{n}^{\prime\prime}(\theta)=\theta^{-2}$. Consider $\gamma_{1}=3/2$,
$\gamma_{2}=1$ and $\beta\geq 2$. Then (17) reduces to
$|\delta|\leq\theta\beta^{-1}$. It is easy to see the right hand side of (16)
reduces to $\beta\delta^{2}\theta^{-3}$. Under the condition
$|\delta|\leq\theta\beta^{-1}$, the left hand side of (16) can be bounded as
follows

$\left|-\frac{1}{\theta+\delta}+\theta^{-1}-\frac{\delta}{\theta^{2}}\right|=\frac{\delta^{2}}{\theta^{2}}\left|\frac{1}{\theta+\delta}\right|=\frac{\delta^{2}}{\theta^{3}}\left|\frac{1}{1+\delta\theta^{-1}}\right|\leq\frac{\delta^{2}}{\theta^{3}}\frac{\beta}{\beta-1}\leq\beta\frac{\delta^{2}}{\theta^{3}}\,.$

Thus, $-\ln(\theta)$ satisfies the condition with $\gamma_{1}=\frac{3}{2}$ and
$\gamma_{2}=1$.

Entropy-barrier function.  Note that the first and second derivatives are
$L_{n}^{\prime}(\theta)=\ln(\theta)+1-\theta^{-1}$ and
$L_{n}^{\prime\prime}(\theta)=\theta^{-1}+\theta^{-2}$, respectively. Consider
$\gamma_{1}=\frac{3}{2}$, $\gamma_{2}=1$ and any $\beta$ satisfying
$\frac{\beta}{(\beta-1)^{2}}\leq 1$. Then (17) reduces to
$|\delta|\leq\theta\beta^{-1}$. The right hand side of (16) can be bounded as

$\beta\delta^{2}(\theta^{-1}+\theta^{-2})^{3/2}=\beta\frac{\delta^{2}}{\theta^{2}}\frac{(1+\theta)^{3/2}}{\theta}\geq\beta\frac{\delta^{2}}{\theta^{2}}(\theta^{-1}+3/2)\,.$

By Taylor’s expansion, there exists $s\in(0,1)$ such that

$\displaystyle\left|\ln(\theta+\delta)-\frac{1}{\theta+\delta}-\ln(\theta)+\theta^{-1}-(\theta^{-1}+\theta^{-2})\delta\right|$
$\displaystyle=$
$\displaystyle\left|\ln(1+\frac{\delta}{\theta})+\frac{\delta}{\theta(\theta+\delta)}-\frac{\delta}{\theta}(1+\theta^{-1})\right|=\left|-\frac{\delta^{2}}{2\theta^{2}(1+s\delta\theta^{-1})^{2}}-\frac{\delta}{\theta^{2}}+\frac{\delta}{\theta(\theta+\delta)}\right|$
$\displaystyle=$
$\displaystyle\frac{\delta^{2}}{\theta^{2}}\left(\frac{1}{\theta(1+\delta\theta^{-1})}+\frac{1}{2(1+s\delta\theta^{-1})^{2}}\right)\leq\frac{\delta^{2}}{\theta^{2}}\left(\theta^{-1}\frac{1}{1-\beta^{-1}}+\frac{1}{2(1-\beta^{-1})^{2}}\right)$
$\displaystyle=$
$\displaystyle\frac{\delta^{2}}{\theta^{2}}(\frac{\beta}{\beta-1})^{2}\left(\theta^{-1}(1-\frac{1}{\beta})+\frac{1}{2}\right)\leq\beta\frac{\delta^{2}}{\theta^{2}}(\theta^{-1}+3/2)\frac{\beta}{(\beta-1)^{2}}$
$\displaystyle\leq$
$\displaystyle\beta\frac{\delta^{2}}{\theta^{2}}(\theta^{-1}+3/2)\leq\beta\delta^{2}(\theta^{-1}+\theta^{-2})^{3/2}\,,$

which implies that $\theta\ln(\theta)-\ln(\theta)$ satisfies (16) with
$\gamma_{1}=3/2$ and $\gamma_{2}=1$.

Logistic function.  Note that $L_{n}^{\prime}(\theta)=-\frac{1}{1+e^{\theta}}$
and $L_{n}^{\prime\prime}(\theta)=\frac{e^{\theta}}{(1+e^{\theta})^{2}}$.
Consider $\gamma_{1}=1$, $\gamma_{2}=0$ and any $\beta$ satisfying
$e^{1/\beta}\leq 2\beta$ (e.g., $\beta=2$). Then (17) reduces to
$|\delta|\leq\beta^{-1}$. The right hand side of (16) is
$\beta\delta^{2}e^{\theta}(1+e^{\theta})^{-2}$. By Taylor’s expansion, there
exists $s\in(0,1)$ such that

$\left|-\frac{1}{1+e^{\theta+\delta}}+\frac{1}{1+e^{\theta}}-\frac{e^{\theta}}{(1+e^{\theta})^{2}}\delta\right|=\frac{\delta^{2}}{2}\left|\frac{e^{\theta+s\delta}-1}{e^{\theta+s\delta}+1}\right|\frac{e^{\theta+s\delta}}{(e^{\theta+s\delta}+1)^{2}}\leq\frac{\delta^{2}}{2}\frac{e^{\theta+s\delta}}{(e^{\theta+s\delta}+1)^{2}}\,.$

Let $q=e^{s\delta}$. Since $|\delta|\leq\beta^{-1}$, $s\in(0,1)$, we have
$q\in(e^{-\frac{1}{\beta}},e^{\frac{1}{\beta}})$. Therefore,

$\displaystyle\frac{qe^{\theta}}{(qe^{\theta}+1)^{2}}$ $\displaystyle=$
$\displaystyle
q\left(\frac{qe^{\theta}+1}{e^{\theta}+1}\right)^{-2}\frac{e^{\theta}}{(e^{\theta}+1)^{2}}=q\left(q+\frac{1-q}{e^{\theta}+1}\right)^{-2}\frac{e^{\theta}}{(e^{\theta}+1)^{2}}$
$\displaystyle\leq$
$\displaystyle\max(q,q^{-1})\frac{e^{\theta}}{(e^{\theta}+1)^{2}}\leq
e^{\frac{1}{\beta}}\frac{e^{\theta}}{(e^{\theta}+1)^{2}}\,.$

Consequently, for any $|\delta|\leq 1/\beta$ with $\beta$ satisfying
$e^{1/\beta}\leq 2\beta$, we have

$\frac{\delta^{2}}{2}\frac{e^{\theta+s\delta}}{(e^{\theta+s\delta}+1)^{2}}\leq\frac{\delta^{2}}{2}e^{\frac{1}{\beta}}\frac{e^{\theta}}{(e^{\theta}+1)^{2}}\leq\beta\delta^{2}\frac{e^{\theta}}{(1+e^{\theta})^{2}}\,,$

which implies that $\ln(1+e^{-\theta})$ satisfies (16) with $\gamma_{1}=1$ and
$\gamma_{2}=0$.

Exponential function.  Note that $L_{n}^{\prime}(\theta)=-e^{\theta}$ and
$L_{n}^{\prime\prime}(\theta)=e^{-\theta}$. Consider $\gamma_{1}=1$,
$\gamma_{2}=0$, and $\beta\geq\frac{1}{2}$. Then (17) reduces to
$|\delta|\leq\beta^{-1}$. It is easy to see the right hand side of inequality
(16) is $\beta e^{-\theta}\delta^{2}$. Note that $e^{x}\geq 1+x$ and
$e^{x}-1-x-\beta x^{2}\leq 0$ for any $\beta\geq 1/2$. Thus under the
condition that $|\delta|\leq\beta^{-1}$, the left hand side of inequality (16)
satisfies

$\left|-e^{-(\theta+\delta)}+e^{-\theta}-e^{-\theta}\delta\right|=e^{\theta}(e^{-\delta}-1+\delta)\leq
e^{\theta}\beta\delta^{2}\,,$

which implies that $e^{\theta}$ satisfies the condition with $\gamma_{1}=1$
and $\gamma_{2}=0$.

Square function.  Note that $L_{n}^{\prime}(\theta)=2\theta$ and
$L_{n}^{\prime\prime}(\theta)=2$. Since for any $\delta\in\mathbb{R}$, the
left hand side of inequality (16) satisfies

$\left|L_{n}^{\prime}(\theta+\delta)-L_{n}^{\prime}(\theta)-L_{n}^{\prime\prime}(\theta)\delta\right|=0$

we conclude that $\theta^{2}$ satisfies inequality (16) with any
$0\leq\gamma_{1}<2$, and $0\leq\gamma_{2}<2$. This completes of the proof of
Proposition 1.

Proof of Proposition 2.  We first prove two claims to be used later in the
proof.

###### Claim 1

Suppose that function $f:\mathbb{R}\mapsto\mathbb{R}$ satisfies Assumption 1
with $\gamma_{1}=1$, $\gamma_{2}=0$ and $\beta$. Then for any $p$-dimensional
vector $a$ and any scalar $b$, the function $g(x):=f(a^{\top}x+b)$ also
satisfies Assumption 1 with $\gamma_{1}=1$, $\gamma_{2}=0$, and
$\beta\|a\|_{2}$.

Proof of Claim 1.  Suppose that Assumption (A1) holds for $f(\cdot)$ with
$\gamma_{1}=1$, $\gamma_{2}=0$, and $\beta$. Then, for any
$d\in\mathbb{R}^{p}$ with $\|d\|_{2}\leq(\beta\|a\|_{2})^{-1}$, we have that
$|a^{\top}d|^{2}\leq\|a\|_{2}^{2}\|d\|_{2}^{2}\leq\beta^{-2}$. By Assumption
(A1), we have, for any $s\in\mathbb{R}$, that

$\left|f^{\prime}(s+a^{\top}d)-f^{\prime}(s)-f^{\prime\prime}(s)a^{\top}d\right|\leq\beta
f^{\prime\prime}(s)(a^{\top}d)^{2}\,.$

Moreover, note that $\nabla g(x)=f^{\prime}(a^{\top}x+b)a$ and
$\nabla^{2}g(x)=f^{\prime\prime}(a^{\top}x+b)aa^{\top}$. Consequently, for any
$x\in\mathbb{R}^{p}$, we have that

$\displaystyle\|\nabla g(x+d)-\nabla g(x)-\nabla^{2}g(x)d\|_{2}$
$\displaystyle=\|(f^{\prime}(a^{\top}x+b+a^{\top}d)-f^{\prime}(a^{\top}x+b)-f^{\prime\prime}(a^{\top}x+b)a^{\top}d)a\|_{2}$
$\displaystyle=\left|f^{\prime}(a^{\top}x+b+a^{\top}d)-f^{\prime}(a^{\top}x+b)-f^{\prime\prime}(a^{\top}x+b)a^{\top}d\right|\cdot\|a\|_{2}$
$\displaystyle\leq\beta
f^{\prime\prime}(a^{\top}x+b)(a^{\top}d)^{2}\|a\|_{2}=\beta\|a\|_{2}d^{\top}\nabla^{2}g(x)d\,,$

which implies that $g(\cdot)$ satisfies Assumption 1 with $\gamma_{1}=1$,
$\gamma_{2}=0$, and $\beta\|a\|_{2}$.

###### Claim 2

Suppose that functions $f_{i}$ with $f_{i}:\mathbb{R}^{p}\mapsto\mathbb{R}$
satisfies Assumption (A1) with $\gamma_{1}=1$, $\gamma_{2}=0$, and
$\beta=\beta_{i}$; $i=1,\ldots,n$. Then
$\alpha_{1}f_{1}+\alpha_{2}f_{2}\ldots+\alpha_{n}f_{n}$ also satisfies
Assumption (A1) with $\gamma_{1}=1$, $\gamma_{2}=0$, and $\beta=\max_{1\leq
i\leq n}\beta_{i}$, where $\alpha_{1},\ldots,\alpha_{n}\geq 0$.

Proof of Claim 2.  For any $d$ satisfying $\|d\|\leq 1/\beta$, we have
$\|d\|\leq 1/\beta_{i}$ for all $i=1,\ldots,n$. By Assumption (A1), this
implies

$\left\|\nabla f_{i}(s+d)-\nabla
f_{i}(s)-\nabla^{2}f_{i}(s)d\right\|_{2}\leq\beta_{i}d^{\top}\nabla^{2}f_{i}(s)d\leq\beta
d^{\top}\nabla^{2}f_{i}(s)d,$ (114)

for any vector $s\in\mathbb{R}^{p}$ and $i=1,\ldots,n$. Thus,

$\displaystyle\left\|\sum_{i=1}^{n}\alpha_{i}\nabla
f_{i}(s+d)-\sum_{i=1}^{n}\alpha_{i}\nabla
f_{i}(s)-\sum_{i=1}^{n}\alpha_{i}\nabla^{2}f_{i}(s)d\right\|_{2}$
$\displaystyle\leq\sum_{i=1}^{n}\alpha_{i}\left\|\nabla f_{i}(s+d)-\nabla
f_{i}(s)-\nabla^{2}f_{i}(s)d\right\|_{2}$
$\displaystyle\leq\sum_{i=1}^{n}\alpha_{i}\beta
d^{\top}\nabla^{2}f_{i}(s)d=\beta
d^{\top}\left(\sum_{i=1}^{n}\alpha_{i}\nabla^{2}f_{i}(s)\right)d\,.$

Consequently, the function $\sum_{i=1}^{n}\alpha_{i}f_{i}$ also satisfies
Assumption (A1) with $\gamma_{1}=1$, $\gamma_{2}=0$, and $\beta=\max_{1\leq
i\leq n}\beta_{i}$.

Now we are ready to prove the main result. It has been shown in Proposition 1
that the logistic regression loss function satisfies Assumption (A1) with
$\gamma_{1}=1$, $\gamma_{2}=0$ and $\beta=2$. By using Claim 1, it follows
that $\log(1+e^{-Y_{i}X_{i}^{\top}\theta})$ also satisfies Assumption (A1)
with $\gamma_{1}=1$, $\gamma_{2}=0$ and $\beta=2\max_{1\leq i\leq
n}\|X_{i}\|_{2}$ for $i=1,\ldots,n$. Moreover, it follows from Claim 2 that
the logistic regression empirical loss
$n^{-1}\sum_{i=1}^{n}\log(1+e^{-Y_{i}X_{i}^{\top}\theta})$ satisfies
Assumption (A1) with $\gamma_{1}=1$, $\gamma_{2}=0$, and $\beta=2\max_{1\leq
i\leq n}\|X_{i}\|_{2}$. This completes the proof of Proposition 2.

##  B Approximation-error bounds for the ODE methods

In this section, we follow the classical global approximation error analysis
of ordinary differential equation, which studies the ODE
$\theta^{\prime}(t)=F(t,\theta(t))$. In particular, we focus on Euler’s method
and second-order Runge-Kutta method, which have been studied extensively in
the numerical ODE literature (Hairer et al., 2008; Butcher, 2016). Both
methods belong to the more general class of the so-called one-step method
(Hairer et al., 2008), for which Lipschitz continuity of function
$F(t,\theta)$ plays an important role in quantifying the approximation error.
Here we present a result which is a direct application of Theorem 3.4 of
Hairer et al. (2008).

###### Theorem 11

(Theorem 3.4 of Hairer et al. (2008)) Assume that $L_{n}(\theta)$ is
$M$-Lipschitz continuous and $m$-strongly convex. Moreover, assume that the
gradient of $L_{n}(\theta)$ is $L$-Lipschitz continuous and the Hessian of
$L_{n}(\theta)$ is $S$-Lipschitz continuous. We have that

$\|\theta_{k}-\theta(t_{k})\|_{2}\leq\frac{C\alpha^{p}}{L^{\star}}(e^{L^{\star}t_{k}}-1)\,,$
(115)

where $\alpha$ is the step size, $t_{k}=k\alpha$, $C$ is an absolute constant,
and $L^{\star}=\frac{MS}{\min\\{m,1\\}^{2}}+\frac{L}{\min\\{m,1\\}}$.

Note that the approximation error is a power function of the step size
$\alpha$. The power $p$ is often referred to as the order the corresponding
approximation method. As we can see from the above Theorem, Euler’s method
defined in (11) and the special case of Runge-Kutta method defined in (12) are
first-order method and second-order method, respectively. In both cases, we
can control global error in finite interval by adjusting step size $\alpha$.

We also point out that the upper bound in (115) gets worse as
$k\rightarrow\infty$, which is less desirable compared with the approximation
error bounds derived for the other two path-following methods. This is likely
due to the generality of problem class considered in Theorem 3.4 of Hairer et
al. (2008). Indeed, some preliminary empirical studies suggest that the
second-order Runge-Kutta is practically comparable to the Newton method in
terms of approximation error. A more refined theoretical upper bound may hold
for the particular ODE we consider here, although we choose not to pursue this
due to space limit.

Proof of Theorem 11.  Applying Theorem 3.4 of Hairer et al. (2008), it
suffices to show that $F(t,\theta(t))$ is Lipschitz continuous with respect to
$\theta(t)$, based on which we could bound the global error directly. For any
$t>0$, $\theta_{1}$ and $\theta_{2}$, let $\Delta
F=F(t,\theta_{1})-F(t,\theta_{2})$. Note that

$\displaystyle\|\Delta F\|_{2}$ $\displaystyle=$
$\displaystyle\left\|[(1-e^{-t})\nabla^{2}L_{n}(\theta_{1})+e^{-t}I]^{-1}\nabla
L_{n}(\theta_{1})-[(1-e^{-t})\nabla^{2}L_{n}(\theta_{2})+e^{-t}I]^{-1}\nabla
L_{n}(\theta_{2})\right\|_{2}$ $\displaystyle\leq$
$\displaystyle\underbrace{\left\|\left[((1-e^{-t})\nabla^{2}L_{n}(\theta_{1})+e^{-t}I)^{-1}-((1-e^{-t})\nabla^{2}L_{n}(\theta_{2})+e^{-t}I)^{-1}\right]\nabla
L_{n}(\theta_{2})\right\|_{2}}_{\text{Part I}}+$
$\displaystyle\underbrace{\left\|((1-e^{-t})\nabla^{2}L_{n}(\theta_{1})+e^{-t}I)^{-1}(\nabla
L_{n}(\theta_{1})-\nabla L_{n}(\theta_{2}))\right\|_{2}}_{\text{Part II}}\,.$

Since $L_{n}(\theta)$ is $m$-strongly convex and $\nabla L_{n}(\theta)$ is
$L$-Lipschitz continuous, we have that for any $\theta$,
$\nabla^{2}f_{t}(\theta)=(1-e^{-t})\nabla^{2}L_{n}(\theta)+e^{-t}I$ satisfies
that

$[(1-e^{-t})\cdot
L+e^{-t}]^{-1}I\preceq[\nabla^{2}f_{t}(\theta)]^{-1}\preceq[(1-e^{-t})m+e^{-t}]^{-1}I\,.$

Therefore,

$\displaystyle\|(\nabla^{2}f_{t}(\theta_{1}))^{-1}-(\nabla^{2}f_{t}(\theta_{2}))^{-1}\|_{2}$
$\displaystyle=$
$\displaystyle\|(\nabla^{2}f_{t}(\theta_{1}))^{-1}(\nabla^{2}f_{t}(\theta_{2})-\nabla^{2}f_{t}(\theta_{1}))(\nabla^{2}f_{t}(\theta_{2}))^{-1}\|_{2}$
$\displaystyle\leq$
$\displaystyle\|(\nabla^{2}f_{t}(\theta_{1}))^{-1}\|_{2}\|\nabla^{2}f_{t}(\theta_{2})-\nabla^{2}f_{t}(\theta_{1})\|_{2}\|(\nabla^{2}f_{t}(\theta_{2}))^{-1}\|_{2}$
$\displaystyle\leq$
$\displaystyle[(1-e^{-t})m+e^{-t}]^{-2}(1-e^{-t})\|\nabla^{2}L_{n}(\theta_{1})-\nabla^{2}L_{n}(\theta_{1})\|_{2}$
$\displaystyle\leq$
$\displaystyle[(1-e^{-t})m+e^{-t}]^{-2}(1-e^{-t})S\|\theta_{1}-\theta_{2}\|_{2}\,.$

Moreover, since $L_{n}(\theta)$ is $M$-Lipschitz continuous and convex, we
have that

$\|\nabla L_{n}(\theta)\|_{2}^{2}\leq|L_{n}(\theta+\nabla
L_{n}(\theta))-L_{n}(\theta)|\leq M\|\nabla L_{n}(\theta)\|_{2}\,,$ (116)

which implies that $\|\nabla L_{n}(\theta)\|_{2}\leq M$. Consequently, we can
bound Part I as follows

Part I $\displaystyle\leq$
$\displaystyle\|[\nabla^{2}f_{t}(\theta_{1})]^{-1}-[\nabla^{2}f_{t}(\theta_{2})]^{-1}\|_{2}\|\nabla
L_{n}(\theta_{2})\|_{2}$ $\displaystyle\leq$ $\displaystyle
M\|[\nabla^{2}f_{t}(\theta_{1})]^{-1}-[\nabla^{2}f_{t}(\theta_{2})]^{-1}\|_{2}$
$\displaystyle\leq$ $\displaystyle
M[(1-e^{-t})m+e^{-t}]^{-2}(1-e^{-t})S\|\theta_{1}-\theta_{2}\|_{2}\,.$

For part II, we have that

Part II $\displaystyle\leq$
$\displaystyle\|[(1-e^{-t})\nabla^{2}L_{n}(\theta_{1})+e^{-t}I]^{-1}\|_{2}\|\nabla
L_{n}(\theta_{1})-\nabla L_{n}(\theta_{2})\|_{2}$ $\displaystyle\leq$
$\displaystyle[(1-e^{-t})m+e^{-t}]^{-1}L\|\theta_{1}-\theta_{2}\|_{2}\,.$

Combining the above two bounds, it follows that

$\|\Delta
F\|_{2}\leq\left(M[(1-e^{-t})m+e^{-t}]^{-2}(1-e^{-t})S+[(1-e^{-t})m+e^{-t}]^{-1}L\right)\|\theta_{1}-\theta_{2}\|_{2}\,.$

Let $S^{*}=M[(1-e^{-t})m+e^{-t}]^{-2}(1-e^{-t})S+[(1-e^{-t})m+e^{-t}]^{-1}L$.
It can be shown that

$\displaystyle S^{*}\leq
L^{\star}:=\frac{MS}{\min\\{m,1\\}^{2}}+\frac{L}{\min\\{m,1\\}}\,.$

Hence, we have that $\|\Delta F\|_{2}\leq
L^{\star}\|\theta_{1}-\theta_{2}\|_{2}$ for any $m>0$, which implies that
$F(t,\theta)$ is $L^{\star}$-Lipschitz continuous with respect to $\theta$.
This completes the proof of Theorem 11.

##  C Additional experiments

In this section, we provide some additional simulation results for ridge
regression. In particular, we compare the proposed methods based on Newton and
gradient descent updates against glmnet in terms of both runtime and
approximation error, under the setting of ridge regression. In our simulation,
the data $\\{(X_{i},Y_{i})\\}_{i=1}^{n}$ are generated from the usual linear
regression model $Y_{i}=X_{i}^{\top}\theta^{\star}+\tilde{\epsilon}$, where
$\tilde{\epsilon}\sim N(0,\sigma^{2})$,
$\theta^{\star}=(1/\sqrt{p},\ldots,1/\sqrt{p})^{\top}$, and
$X_{1},\ldots,X_{n}$ are IID samples from $N_{p}(0,I_{p\times p})$. We
consider two different scenarios with $\sigma^{2}=1/4$ and $\sigma^{2}=4$.
Moreover, for each scenario, we consider three different problem dimensions:
$(n,p)=(1000,500)$, $(n,p)=(1000,1000)$, and $(n,p)=(1000,2000)$.

Again, we use the global approximation error $\sup_{0\leq t\leq
t_{\max}}\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\\}$ to assess the
accuracy for the approximate solution path $\tilde{\theta}(t)$, where
$\tilde{\theta}(t)$ is the linear interpolation of the iterates $\theta_{k}$
generated by each method. Moreover, we sample $N$ points $s_{1},\ldots,s_{N}$
uniformly from $(0,t_{\max})$ and use $\max_{1\leq i\leq
N}\\{f_{s_{i}}(\tilde{\theta}({s_{i}}))-f_{s_{i}}(\theta({s_{i}}))\\}$ as an
approximation of $\sup_{0\leq t\leq
t_{\max}}\\{f_{t}(\tilde{\theta}(t))-f_{t}(\theta(t))\\}$. Here
$\theta({s_{i}})$ is the exact solution at $s_{i}$ and can be computed
explicitly. In our simulations, we use $N=100$ and $t_{\max}=10$.

Figure 7 plots runtime versus approximation error based on $100$ simulations.
Similar to Figure 3, we can see from Figure 7 that in all scenarios the
proposed Newton method runs the fastest when the required accuracy is high
(small suboptimality). Moreover, glmnet is no better than Newton method for
smaller problems ($p=500$ and $1000$); while glmnet outperforms both Newton
method and the gradient method when low accuracy solution is sufficient and
problem dimension is large ($p=2000$). Lastly, in all cases the gradient
method runs faster than Newton method when the desired accuracy is low.

Figure 7: Runtime v.s. suboptimality for the proposed Newton method, gradient
descent method, and glmnet under six different scenarios, when applied to
ridge regression.

## References

  * Ali et al. (2019) Alnur Ali, J Zico Kolter, and Ryan J Tibshirani.  A continuous-time view of early stopping for least squares.  In _International Conference on Artificial Intelligence and Statistics_ , volume 22, 2019.
  * Arnold and Tibshirani (2016) Taylor B. Arnold and Ryan J. Tibshirani.  Efficient implementations of the generalized lasso dual path algorithm.  _Journal of Computational and Graphical Statistics_ , 25(1):1–27, 2016.  doi: 10.1080/10618600.2015.1008638.
  * Bach et al. (2010) Francis Bach et al.  Self-concordant analysis for logistic regression.  _Electronic Journal of Statistics_ , 4:384–414, 2010.
  * Boyd and Vandenberghe (2004) Stephen Boyd and Lieven Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.
  * Butcher (2016) John Charles Butcher.  _Numerical methods for ordinary differential equations_.  John Wiley & Sons, 2016.
  * Conn et al. (2000) Andrew R Conn, Nicholas IM Gould, and Ph L Toint.  _Trust region methods_ , volume 1.  Siam, 2000.
  * Dobriban and Wager (2018) Edgar Dobriban and Stefan Wager.  High-dimensional asymptotics of prediction: Ridge regression and classification.  _Ann. Statist._ , 46(1):247–279, 02 2018.  doi: 10.1214/17-AOS1549.
  * Eddelbuettel (2013) Dirk Eddelbuettel.  _Seamless R and C++ integration with Rcpp_.  Springer, 2013.
  * Eddelbuettel et al. (2011) Dirk Eddelbuettel, Romain François, J Allaire, Kevin Ushey, Qiang Kou, N Russel, John Chambers, and D Bates.  Rcpp: Seamless r and c++ integration.  _Journal of Statistical Software_ , 40(8):1–18, 2011.
  * Efron et al. (2004) B. Efron, T. Hastie, I. Johnstone, and R. Tishirani.  Least angle regression.  _The Annals of Statistics_ , 32(2):407 – 499, 2004.
  * Fleming (1990) Henry E Fleming.  Equivalence of regularization and truncated iteration in the solution of ill-posed image reconstruction problems.  _Linear Algebra and its applications_ , 130:133–150, 1990\.
  * Frank and Friedman (1993) Ildiko E. Frank and Jerome H. Friedman.  A statistical view of some chemometrics regression tools.  _Technometrics_ , 35(2):109–135, 1993.  ISSN 00401706.
  * Friedman and Popescu (2004) Jerome Friedman and Bogdan Popescu.  Gradient directed regularization for linear regression and classiöcation.  _Technical Report_ , March 2004.
  * Friedman et al. (2007) Jerome Friedman, Trevor Hastie, Holger Hofling, and Robert Tibshirani.  Pathwise coordinate optimization.  _The Annals of Applied Statistics_ , 1(2):302–332, 2007.
  * Friedman et al. (2010) Jerome Friedman, Trevor Hastie, and Rob Tibshirani.  Regularization paths for generalized linear models via coordinate descent.  _Journal of statistical software_ , 33(1):1, 2010\.
  * Geyer (2009) Charles J. Geyer.  Likelihood inference in exponential families and directions of recession.  _Electron. J. Statist._ , 3:259–289, 2009.  doi: 10.1214/08-EJS349.
  * Grant and Boyd (2014) Michael Grant and Stephen Boyd.  Cvx: Matlab software for disciplined convex programming, version 2.1, 2014\.
  * Grant and Boyd (2008) Michael C Grant and Stephen P Boyd.  Graph implementations for nonsmooth convex programs.  In _Recent advances in learning and control_ , pages 95–110. Springer, 2008.
  * Gunasekar et al. (2017) Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro.  Implicit regularization in matrix factorization.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems 30_ , pages 6151–6159. Curran Associates, Inc., 2017.
  * Gunasekar et al. (2018) Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro.  Characterizing implicit bias in terms of optimization geometry.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 1832–1841, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
  * Hairer et al. (2008) Ernst Hairer, Syvert P Nørsett, and Gerhard Wanner.  _Solving ordinary differential equations I: nonstiff problems_ , volume 8.  Springer Science & Business Media, 2008.
  * Hastie et al. (2004) T. Hastie, S. Rosset, R. Tishirani, and J. Zhu.  The entire regularization path for the support vector machine.  _Journal of Machine Learning Research_ , 5:1391 – 1415, 2004.
  * Hastie et al. (2007) Trevor Hastie, Jonathan Taylor, Robert Tibshirani, Guenther Walther, et al.  Forward stagewise regression and the monotone lasso.  _Electronic Journal of Statistics_ , 1:1–29, 2007.
  * Hoefling (2010) Holger Hoefling.  A path algorithm for the fused lasso signal approximator.  _Journal of Computational and Graphical Statistics_ , 19(4):984–1006, 2010.  doi: 10.1198/jcgs.2010.09208.
  * Hoerl and Kennard (1970) Arthur E Hoerl and Robert W Kennard.  Ridge regression: Biased estimation for nonorthogonal problems.  _Technometrics_ , 12(1):55–67, 1970.
  * Levenberg (1944) K. Levenberg.  A method for the solution of certain non-linear problems in least squares.  _Quarterly of Applied Mathematics_ , pages 164–168, 1944.
  * M. Freund et al. (2017) Robert M. Freund, Paul Grigas, and Rahul Mazumder.  A new perspective on boosting in linear regression via subgradient optimization and relatives.  _Ann. Statist._ , 45(6):2328–2364, 2017.  doi: 10.1214/16-AOS1505.
  * Nesterov (1998) Yu. Nesterov.  _Introductory Lectures on Convex Programming Volume I: Basic course_.  1998\.
  * Nesterov and Nemirovskii (1993) Yu. E. Nesterov and A. S. Nemirovskii.  _Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms_.  SIAM Publications, 1993.
  * Neu and Rosasco (2018) Gergely Neu and Lorenzo Rosasco.  Iterate averaging as regularization for stochastic gradient descent.  In _COLT_ , 2018.
  * Osborne (1992) MR Osborne.  An effective method for computing regression quantiles.  _IMA Journal of Numerical Analysis_ , 12:151 – 166, 1992\.
  * Osborne et al. (2000) MR Osborne, B Presnell, and BA Turlach.  A new approach to variable selection in least squares problems.  _IMA Journal of Numerical Analysis_ , 20(3):389 – 403, 2000.
  * Raskutti et al. (2014) Garvesh Raskutti, Martin J Wainwright, and Bin Yu.  Early stopping and non-parametric regression: an optimal data-dependent stopping rule.  _The Journal of Machine Learning Research_ , 15(1):335–366, 2014.
  * Rosset (2004) Saharon Rosset.  Following curved regularized optimization solution paths.  _Advances in Neural Information Processing Systems_ , 17:1153–1160, 2004.
  * Rosset and Zhu (2007) Saharon Rosset and Ji Zhu.  Piecewise linear regularized solution paths.  _Ann. Statist._ , 35(3):1012–1030, 2007.  doi: 10.1214/009053606000001370.
  * Soudry et al. (2017) Daniel Soudry, Elad Hoffer, and Nathan Srebro.  The implicit bias of gradient descent on separable data.  _arXiv preprint arXiv:1710.10345_ , 2017.
  * Suggala et al. (2018) Arun Suggala, Adarsh Prasad, and Pradeep K Ravikumar.  Connecting optimization and regularization paths.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems 31_ , pages 10631–10641. Curran Associates, Inc., 2018.
  * Sun and Tran-Dinh (2017) Tianxiao Sun and Quoc Tran-Dinh.  Generalized self-concordant functions: a recipe for newton-type methods.  _Mathematical Programming_ , pages 1–69, 2017.
  * Tikhonov and Arsenin (1977) A. N. Tikhonov and V. Y. Arsenin.  _Solutions of ill-Posed Problems_.  Wiley, New York, 1977.
  * Wold et al. (1984) S. Wold, A. Ruhe, H. Wold, and W. J. Dunn, III.  The collinearity problem in linear regression. the partial least squares (pls) approach to generalized inverses.  _SIAM J. Sci. Stat. Comput._ , 5(3):735–743, September 1984.  ISSN 0196-5204.  doi: 10.1137/0905052.
  * Wu (2011) Yichao Wu.  An ordinary differential equation based solution path algorithm.  _Journal of Nonparametric Statistics_ , 23(1):185–199, 2011.
  * Yao et al. (2007) Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto.  On early stopping in gradient descent learning.  _Constructive Approximation_ , 26(2):289–315, 2007.  doi: 10.1007/s00365-006-0663-2.
  * Zhou and Wu (2014) Hua Zhou and Yichao Wu.  A generic path algorithm for regularized statistical estimation.  _Journal of the American Statistical Association_ , 109:686–699, 2014.