Proof. \(\:\)
a) Since \(f'(x)=ax+b\) the iterates of GD are given by \[x_{n+1}=x_{n}-\eta(ax_{n}+b),\quad n\ge0\tag{3.7}\] (see lines 2 and 3 of Algorithm [algo:GD]). The unique local and global minimizer of \(f\) is \(x_{*}=-\frac{b}{2a}.\) Let \[y_{n}=x_{n}-x_{*}\] be the distance to this minimizer of the \(n\)-th iterate. Substituting \(y_{n}+x_{*}\) for \(x_{n}\) in (3.7) and using that \(ax_{*}+b=f'(x_{*})=0\) we obtain \[y_{n+1}=y_{n}-a\eta y_{n},\quad n\ge0.\] This can be rewritten as \(y_{n+1}=y_{n}(1-a\eta),\) from which it is obvious that \[y_{n}=(1-a\eta)^{n}y_{0}=\theta^{n}y_{0}\quad n\ge0,\tag{3.8}\] where \[\theta=1-a\eta.\]

We have \(\theta^{n}y_{0}\to0\) iff \(\theta\in(-1,1),\) and \(\theta\in(-1,1)\) iff \(\eta\in(0,2a^{-1}).\) Since \(y_{n}\to0\) iff \(x_{n}\to x_{*},\) this proves a).

We have \[|x_{n}-x_{*}|=|y_{n}|=|\theta|^{n}|y_{0}|=|\theta|^{n}|x_{0}-x_{*}|\quad n\ge0.\] The claim then follows since if \(\eta\ne a^{-1}\) then \(|\theta|^{n}=\exp(\log|\theta|n)=\exp(-\kappa n),\) and if in addition \(\eta<2a^{-1}\) then \(\log|\theta|=\log|1-2a\eta|>0.\)

Similar to b).

Exercise.

If \(\eta\le a^{-1}\) then \(\theta\in(0,1],\) and then \(\theta^{n}y_{0}\) is a monotone sequence, so \(x_{n}=\theta^{n}y_{0}+x_{*}\) is also monotone.

If \(\eta>a^{-1}\) then \(\theta<0,\) and so \[{\rm sign}(y_{n})={\rm sign}(\theta)^{n}{\rm sign}(y_{0})=(-1)^{n}{\rm sign}(y_{0}).\]

Proof of Lemma 3.9 a). We have \(f'(x)=a|x|^{k-1}{\rm sign}(x).\) Thus the iterates of GD are given by \[x_{n+1}=x_{n}-\eta a|x_{n}|^{k-1}{\rm sign}(x_{n})=x_{n}(1-\eta a|x_{n}|^{s}),\quad n\ge0,\tag{3.12}\] where \(s=k-2.\) By assumption we have \[|x_{1}|=|x_{0}||1-\eta a|x|_{0}^{s}|\le|x_{0}|,\] and \[\eta a|x_{1}|^{2}=\eta a|x|_{0}^{s}(1-\eta a|x|_{0}^{s})^{s}\in(0,\eta a|x_{0}|^{s})\subset(0,1).\] Also if for some \(n\ge1\) \[|x_{n}|\le|x_{n-1}|\quad\text{and}\quad\eta a|x_{n}|^{s}\in(0,1),\] then \[|x_{n+1}|=|x_{n}|(1-\eta a|x_{n}|^{s})\le|x_{n}|,\] and \[\eta a|x_{n+1}|^{s}=\eta a|x_{n}|^{s}(1-\eta a|x_{n}|^{s})^{s}\le\eta a|x_{n}|^{s}\in(0,1).\] Thus by induction \[|x_{n}|\le|x_{n-1}|\quad\forall n\ge1.\] Since the sequence \(|x_{n}|\) is monotone decreasing and bounded blow, the limit \[x_{*}:=\lim_{n\to\infty}|x_{n}|\in[0,\infty)\] exists, and satisfies \[\eta a|x_{*}|^{s}\in(0,1).\] Assume for contradiction that \(x_{*}>0.\) Then \(|x_{n}|\ge x_{*}>0\) for all \(n,\) and \[|x_{n+1}|\le|x_{n}||1-\eta a|x_{n}|^{s}|\le x_{n}(1-\eta ax_{*}^{s}).\] But this implies that \[|x_{n}|\le|x_{0}|(1-\eta ax_{*}^{s})^{n}\quad\forall n\ge0,\] which implies that \(\lim_{n\to\infty}x_{n}=0,\) which is a contradiction. Thus indeed \(x_{*}=0.\)

Sketch of proof of Lemma 3.9 b). This is a heuristic argument for the rate \(n^{-1/s}\) of convergence, without rigorous proofs. Assume for simplicity that \(x_{0}>0.\) To investigate the speed of convergence we note that (3.12) implies that \[x_{n}=x_{0}(1-\eta ax_{0}^{s})(1-\eta ax_{1}^{s})\ldots(1-\eta ax_{n-1}^{s}),\quad\text{ for all }n\ge0,\] (where \(s=k-2\)).The product invites the application of a \(\log\) to both sides, yielding \[\log x_{n}=\log x_{k}+\sum_{m=k}^{n}\log(1-\eta ax_{m}^{s}),\quad\text{for all }n\ge k,\tag{3.13}\] provided \(1-\eta ax_{m}^{s}>-1\) for all \(m\ge k,\) which will certainly hold if \(x_{n}\) converges to \(x_{*}=0.\) In that case we can furthermore use the approximation \(\log(1-x)\approx-x\) for \(k\) large enough to heuristically obtain \[\log x_{n}\approx\log x_{k}-\eta a\sum_{m=k}^{n}x_{m}^{s}.\tag{3.14}\] We expect the convergence to be slower than in Lemma 3.3, where it was exponential, and therefore make the ansatz “\(x_{n}\approx n^{-\alpha}\)” for some \(\alpha>0.\) Under this ansatz we would have \[\log x_{n}\approx-\alpha\log n,\tag{3.15}\] and \[\eta a\sum_{m=k}^{n}x_{m}^{s}\approx\eta a\sum_{m=k}^{n}m^{-\alpha s}.\tag{3.16}\] Recall that \[\sum_{m=k}^{n}m^{-\beta}<\sum_{m=k}^{\infty}m^{-\beta}<\infty\quad\text{if}\quad\beta>1,\] and \[\sum_{m=k}^{n}m^{-\beta}\approx\int_{k}^{n}m^{-\beta}dm\propto n^{1-\beta}\quad\text{if}\quad\beta>1.\] Thus (3.14), (3.15) and (3.16) are inconsistent if \(\alpha s\ne1,\) since they would imply that \(-\alpha\log n\approx\log x_{k}+O(1)\) resp. \(-\alpha\log n\approx\log x_{k}+n^{1-\beta}.\) This indicates that the ansatz \(x_{n}\approx n^{-\alpha}\) is incorrect if \(\alpha\ne\frac{1}{s}.\) If \(\alpha=\frac{1}{s}\) on the other hand, the ansatz amounts to \(x_{m}^{s}\approx m^{-1},\) and since \(\sum_{m=k}^{n}m^{-1}\approx\log n\) this means that (3.14), (3.15) and (3.16) are more consistent in that all terms depending on \(n\) are of order \(\log n.\) This suggests that \(x_{n}\) is proportional to \(n^{-1/s},\) and the iterates of GD converge at rate \(n^{-1/s}.\) The constant of proportionality can be guessed by making the ansatz \(x_{n}\approx hn^{-1/s}\) for \(h>0,\) under which (3.14), (3.15) and (3.16) combine to \[-\frac{1}{s}\log n+\log h\approx\log x_{k}-\eta ah^{s}\log n.\] This is consistent if \(\eta ah^{s}=\frac{1}{s},\) so we expect that if convergent, the iterates of GD converge as \[|x_{n}-x_{*}|\approx|x_{0}-x_{*}|\frac{1}{(s\eta a)^{1/s}}n^{-1/s}.\]

Proof. Since \(\nabla f(x)=Ax+b\) the iterates of gradient descent are given by \[x_{n+1}=x_{n}-\eta(Ax_{n}+b),n\ge0.\tag{3.20}\] Let \(y_{n}=x_{n}-x_{*}\) be the difference between iterate and minimizer. Substituting \(y_{n}+x_{*}\) for \(x_{n}\) in (3.20) and using that \(Ax_{*}+b=\nabla f(x_{*})=0\) we obtain \[y_{n+1}=y_{n}-\eta Ay_{n},\quad n\ge0.\] Let \(e_{1},\ldots,e_{d}\) be an orthonormal eigenbasis with corresponding eigenvalues \(\lambda_{\min}=\lambda_{1}\le\lambda_{2}\le\ldots\le\lambda_{d}=\lambda_{\max}.\) Letting \(z_{n}\) denote \(y_{n}\) written in this basis (i.e. \(z_{n,i}=y_{n}\cdot e_{i}\)), this turns into \[z_{n+1,i}=z_{n,i}-\eta\lambda_{i}z_{n,i},\quad i=1,\ldots,d,n\ge0.\] This puts us back in the setting of Lemma 3.3. As in the proof of that lemma, we obtain that \[z_{n,i}=(1-\eta\lambda_{i})^{n}z_{0,i},\quad i=1,\ldots,d,n\ge0.\] a) The sequence \(z_{n,i}\) converges to zero iff \(|1-\eta\lambda_{i}|<1.\) We have \[1-\eta\lambda_{\max}\le1-\eta\lambda_{i}\le1-\eta\lambda_{1},\] and thus \[|1-\eta\lambda_{i}|\le\max(1-\eta\lambda_{1},\eta\lambda_{\max}-1)=\theta.\] Thus all the sequences \(z_{n,i}\) converge to zero if \(\theta<1.\) If \(\eta<\frac{2}{\lambda_{\max}},\) then \(|1-\lambda_{\max}|<1,\) so indeed \(\theta<1,\) and \(z_{n,i}\to0\) for all \(i=1,\ldots,d.\) Furthermore \[\begin{array}{ccccccl} |x_{n}-x_{*}|^{2} & = & |y_{n}|^{2} & = & |z_{n}|^{2} & = & \sum_{i=1}^{d}|1-\eta\lambda_{i}|^{2n}z_{0,i}^{2}\\ & & & & & \le & \sum_{i=1}^{d}\theta^{2n}z_{0,i}^{2}\\ & & & & & = & \theta^{2n}|z_{0}|^{2}\\ & & & & & = & e^{-2\kappa n}|z_{0}|^{2}\\ & & & & & = & e^{-2\kappa n}|x_{0}-x_{*}|^{2}. \end{array}\] Taking the square root of both sides we obtain (3.18).

b) If \(\eta\lambda_{\max}>2,\) then \(\theta=|1-\eta\lambda_{\max}|>1,\) so \[\begin{array}{cccclcl} |x_{n}-x_{*}|^{2} & = & |y_{n}|^{2} & = & |z_{n}|^{2} & = & \sum_{i=1}^{d}|1-\eta\lambda_{i}|^{2n}z_{0,i}^{2}\\ & & & & & \ge & \sum_{i:\lambda_{i}=\lambda_{\max}}|1-\eta\lambda_{\max}|^{2n}z_{0,i}^{2}\\ & & & & & = & \theta^{2n}\sum_{i:\lambda_{i}=\lambda_{\max}}z_{0,i}^{2}\\ & & & & & = & e^{2\kappa n}|\tilde{x}_{0}-x_{*}|^{2}. \end{array}\] Taking the square root of both sides we obtain (3.19).

Proof. Since \(f\) is differentiable \[\begin{array}{ccl} f(x+p) & = & \int_{0}^{1}\partial_{t}\{f(x+tp)\}dt\\ & = & \int_{0}^{1}\nabla f(x+tp)\cdot pdt\\ & = & \nabla f(x)\cdot p+p\cdot\int_{0}^{1}(\nabla f(x+tp)-\nabla f(x))dt. \end{array}\] Since \(\nabla f\) is \(L\)-Lipschitz. \[|\nabla f(x+tp)-\nabla f(x)|\le L|tp|\le Lt|p|.\] Thus \[\left|p\cdot\int_{0}^{1}(\nabla f(x+tp)-\nabla f(x))dt\right|\le L|p|^{2}\int_{0}^{1}tdt=\frac{L}{2}|p|^{2}.\]

Proof. Let \(x_{0}=x\) and \(x_{1}=x-\eta\nabla f(x),\) for arbitrary \(\eta>0.\) By Lemma 3.21 \[\begin{array}{ccl} f(x_{1}) & \le & f(x_{0})-\eta\nabla f(x)^{T}\nabla f(x)+\frac{L}{2}\eta^{2}|\nabla f(x)|^{2}\\ & = & f(x_{0})+\left(\frac{L}{2}\eta^{2}-\eta\right)|\nabla f(x)|^{2}. \end{array}\] Optimizing over \(\eta\) leads to the choice \(\eta=\frac{1}{L},\) giving \[f(x_{1})\le f(x_{0})-\frac{1}{2L}|\nabla f(x)|^{2},\tag{3.23}\] or equivalently \[f(x_{0})-f(x_{1})\ge\frac{1}{2L}|\nabla f(x)|^{2}.\] Since \(x_{*}\) is a global minimizer \(f(x_{0})-f(x_{*})\ge f(x_{0})-f(x_{1}),\) so the claim follows.

Proof. We prove that \[|x_{n+1}-x_{*}|^{2}\le(1-\eta u)^{2}|x_{n}-x_{*}|^{2}\quad\text{ for all }\quad n\ge0.\tag{3.25}\] The claim then follows by induction. To prove (3.25), note that \[\begin{array}{ccl} |x_{n+1}-x_{*}|^{2} & = & |x_{n}-\eta\nabla f(x_{n})-x_{*}|^{2}\\ & = & |x_{n}-x_{*}|^{2}-2\eta\nabla f(x_{n})^{T}(x_{n}-x_{*})+\eta^{2}|\nabla f(x_{n})|^{2}. \end{array}\tag{3.26}\] Consider \(\nabla f(x_{n})^{T}(x_{n}-x_{*}).\) By the strong convexity of \(f\) \[f(x_{n})\ge f(x_{*})-(x_{n}-x_{*})^{T}\nabla f(x_{n})+\frac{\mu}{2}|x_{n}-x_{*}|^{2},\] which can be rearranged to \[f(x_{*})-f(x_{n})-\frac{\mu}{2}|x_{n}-x_{*}|^{2}\ge-(x_{n}-x_{*})^{T}\nabla f(x_{n}).\] Thus (3.26) is at most \[\begin{array}{l} |x_{n}-x_{*}|^{2}+2\eta(f(x_{*})-f(x_{n}))-\mu\eta|x_{n}-x_{*}|^{2}+\eta^{2}|\nabla f(x_{n})|^{2}\\ =(1-\mu\eta)|x_{n}-x_{*}|^{2}+2\eta(f(x_{*})-f(x_{n}))+\eta^{2}|\nabla f(x_{n})|^{2}. \end{array}\] Using Lemma 3.22 to bound the final term we get that the last line is at most \[\begin{array}{l} (1-\mu\eta)|x_{n}-x_{*}|^{2}+2\eta(f(x_{*})-f(x_{n}))+2L\eta^{2}(f(x_{n})-f(x_{*}))\\ =(1-\mu\eta)|x_{n}-x_{*}|^{2}-2\eta(1-\eta L)(f(x_{n})-f(x_{*})). \end{array}\] Since the last term is positive for \(\eta\le\frac{1}{L},\) this proves (3.25).

Proof. We have \(f'(x)=ax+b\) and \(f''(x)=a,\) so \[\frac{f'(x)}{f''(x)}=x+\frac{b}{a}=x-x_{*}\] Thus the iterates satisfy \[x_{n+1}=x_{n}-\eta(x-x_{*}),\quad n\ge0.\] This can be written as \[x_{n+1}-x_{*}=(x_{n}-x_{*})(1-\eta),\quad n\ge0.\] Thus \[|x_{n+1}-x_{*}|=|x_{0}-x_{*}||1-\eta|^{n},\quad n\ge0.\] For \(\eta\in(0,1)\cup(1,2)\) we have \[\kappa=-\log|1-\eta|>0\] and \[|1-\eta|^{n}=e^{-\kappa n},\] giving the claim.

Proof of Lemma 3.32. We have \(\nabla f(x)=Ax+b\) and \(\nabla^{2}f(x)=A.\) The iterates of damped Newton-Raphson are \[x_{n+1}=x_{n}-\eta A^{-1}(Ax_{n}+b)=x_{n}(1-\eta)+\eta x_{*},\quad n\ge0.\] This can be rewritten as \[x_{n+1}-x_{*}=(x_{n}-x_{*})(1-\eta),\quad n\ge0,\] from which it follows that for \(\eta\in(0,1)\cup(1,2)\) \[|x_{n}-x_{*}|\le|x_{0}-x_{*}||1-\eta|^{n}=|x_{0}-x_{*}|e^{-\kappa n},\quad n\ge0.\]

Proof. We have \(f'(x)=a|x|^{k-1}{\rm sign}(x)\) and \(f''(x)=a|x|^{k-2},\) so the iterates of Newton-Raphson read \[x_{n+1}=x_{n}-\eta\frac{a|x_{n}|^{k-1}{\rm sign}(x_{n})}{a|x_{n}|^{k-2}}=x_{n}-\eta x_{n}=(1-\eta)x_{n}.\] Thus \[|x_{n}-x_{*}|=|1-\eta|^{n}|x_{0}-x_{*}|=e^{-\kappa n}|x_{0}-x_{*}|.\]

Proof. The equation (3.36) is a linear difference equation, as encountered in the course M12 about ODEs. To find the general family of solutions of such an equation, we consider its characteristic equation (3.37). If its roots \(r_{1},r_{2}\) satisfy \(r_{1}\ne r_{2},\) then the sequence \(z_{n}\) must satisfy \[z_{n}=ar_{1}^{n}+br_{2}^{n},\quad n\ge0\tag{3.40}\] for some \(a,b\in\mathbb{C}.\) Even without assuming any results from M12, this can easily be proved using induction. From the cases \(n=0\) and \(n=1\) of (3.40) we derive the equations \[\begin{cases} a+b=z_{0},\\ ar_{1}+br_{2}=z_{1}, \end{cases}\] whose unique solution is \[a=\frac{r_{2}z_{0}-z_{1}}{r_{2}-r_{1}},\qquad b=\frac{-r_{1}z_{0}+z_{1}}{r_{2}-r_{1}}.\] This proves (3.40).

Similarly, if \(r_{1}=r_{2}\) then the sequence \(z_{n}\) must satisfy \[z_{n}=ar+bnr^{n},\quad n\ge0.\tag{3.41}\] for some \(a,b\in\mathbb{C},\) which similarly implies that (3.39) must hold.

Proof. We have \(f'(x)=ax+b,\) so the iterates satisfy \[x_{n+1}=x_{n}-\eta(ax_{n}+b)+\beta(x_{n}-x_{n-1}),\quad n\ge0.\] Letting \(y_{n}=x_{n}-x_{*}\) this turns into \[y_{n+1}=(1-a\eta)y_{n}+\beta(y_{n}-y_{n-1}),\quad n\ge0,\] where \(y_{0}=y_{-1},\) which in turn can be rewritten as \[y_{n+1}=\theta y_{n}-\beta y_{n-1},\quad n\ge0,\] for \[\theta:=1-a\eta+\beta.\] Let \[r_{1}=\frac{1}{2}(\theta-\sqrt{\theta^{2}-4\beta}),\quad r_{2}=\frac{1}{2}(\theta+\sqrt{\theta^{2}-4\beta}),\tag{3.44}\] denote the roots of the quadratic \(r^{2}=\theta r-\beta.\)

We have \[r_{1}=r_{2}\iff\theta^{2}=4\beta\iff\eta a=(1-\sqrt{\beta})^{2}.\] Thus if \(\eta a\ne(1-\sqrt{\beta})^{2},\) then using Lemma 3.19 a) for \(z_{n}=y_{n+1},n\ge0,\) (so that \(z_{0}=z_{1}=y_{0}\)) proves that \[y_{n}=y_{0}\left(\frac{1-r_{1}}{r_{2}-r_{1}}r_{2}^{n+1}-\frac{1-r_{2}}{r_{2}-r_{1}}r_{1}^{n+1}\right),\quad\forall n\ge0.\tag{3.45}\] From (3.45) we obtain \[|y_{n}|\le|y_{0}|\left(\frac{|1-r_{1}|}{|r_{2}-r_{1}|}|r_{2}|^{n+1}+\frac{|1-r_{2}|}{|r_{2}-r_{1}|}|r_{1}|^{n+1}\right)\le c\max(|r_{1}|,|r_{2}|)^{n}|y_{0}|,\] for the constant \(c=\frac{|1-r_{1}|+|1-r_{2}|}{|r_{2}-r_{1}|}\max(|r_{1}|,|r_{2}|).\) Thus (3.42) holds for \[\kappa=-\log\max(|r_{1}|,|r_{2}|).\] To show that \(\kappa>-\log|1-\eta a|>0\) for \(\eta a<(1-\sqrt{\beta})^{2},\) note that for such \(\eta a\) the roots \(r_{1},r_{2}\) are both real and \(0<r_{1}<r_{2},\) so \[\max(|r_{1}|,|r_{2}|)=|r_{2}|.\] Also \[|r_{2}|<\frac{1}{2}(\theta+\sqrt{\theta^{2}-4(1-\eta a)\beta})=\frac{1}{2}(1-\eta a+\beta+\sqrt{(1-\eta a-\beta)^{2}}).\] Furthermore \[1-\eta a-\beta\ge1-(1-\sqrt{\beta})^{2}-\beta=2\sqrt{\beta}-2\beta=2\sqrt{\beta}(1-\sqrt{\beta})>0,\] so \[\frac{1}{2}(1-\eta a+\beta+\sqrt{(1-\eta a-\beta)^{2}})=\frac{1}{2}(1-\eta a+\beta+1-\eta a-\beta)=1-\eta a.\] Thus \[|r_{2}|<|1-\eta a|<1.\] This proves (3.43) and that \(\kappa>0\) for \(\eta a\in(0,(1-\sqrt{\beta})^{2}).\)

If \(\eta a\in((1-\sqrt{\beta})^{2},(1+\sqrt{\beta})^{2}),\) then \(r_{1}\) and \(r_{2}\) are both complex and in fact \[r_{1}=\frac{1}{2}(\theta-i\sqrt{4\beta-\theta^{2}}),\quad r_{2}=\frac{1}{2}(\theta+i\sqrt{4\beta-\theta^{2}}).\] Then \[|r_{1}|=|r_{2}|=\frac{1}{2}\sqrt{\theta^{2}+(4\beta-\theta^{2})}=\beta\in(0,1).\] Since \(-\log\beta>0\) this proves that \(\kappa>0\) when \(a\eta\in((1-\sqrt{\beta})^{2},(1+\sqrt{\beta})^{2}).\)

If \(\eta a=(1-\sqrt{\beta})^{2},\) then \[r_{1}=r_{2}=r:=\frac{\theta}{2}=\frac{1-\eta a+\beta}{2}=\frac{1-(1-\sqrt{\beta})^{2}+\beta}{2}=\beta,\] and by Lemma 3.19 b) we have \[y_{n}=y_{0}(\beta^{n+1}+(\beta^{-1}-1)(n+1)\beta^{n+1}),\quad\forall n\ge0.\] Thus \[|y_{n}|\le|y_{0}|(|r|^{n+1}+|\beta^{-1}(n+1)|r|^{n+1})\le c_{1}(n+1)\beta^{n},\] where \(c_{1}=\beta+1.\) Since \(\beta<\sqrt{\beta},\) there exists a constant \(c_{2}>0\) (depending on \(\beta\)) s.t. \((n+1)\beta^{n}\le c_{2}(\sqrt{\beta})^{n}\) for all \(n\ge0.\) Thus \[|y_{n}|\le c(\sqrt{\beta})^{n}\quad\forall n\ge0,\] for \(c=c_{1}c_{2},\) so (3.42) holds with \(\kappa=-\log\sqrt{\beta}>0\) when \(\eta a=(1-\sqrt{\beta})^{2}\)

Proof. We have \(\nabla f(x)=Ax+b,\) so the iterates of GD with momentum are \[x_{n+1}=x_{n}-\eta(Ax_{n}+b)+\beta(x_{n}-x_{n-1}),\quad n\ge0,\] which in terms of \(y_{n}=x_{n}-x_{*}\) reads \[y_{n+1}=y-\eta Ay_{n}+\beta(y_{n}-y_{n-1}),\quad n\ge0.\tag{3.49}\] As in Lemma 3.32 and Lemma 3.17 , we can diagonalize \(A\) with eigenvalues \(0<\lambda_{\min}\le\lambda_{1}\le\ldots\le\lambda_{n}\le\lambda_{\max}\) and express (3.49) in the diagonalizing basis. This yields \[y_{n+1.i}=y_{i}-\eta\lambda_{i}y_{n,i}+\beta(y_{n,i}-y_{n-1,i}),\quad,i=1,\ldots,d,n\ge0,\] where the update in each dimension is decoupled. The updates in each dimension are described precisely as in Lemma 3.20 with \(a=\lambda_{i}.\) Thus if \(\eta<\lambda_{\max}^{-1}(1+\sqrt{\beta})^{2},\) so that \(\eta<\lambda_{i}^{-1}(1+\sqrt{\beta})^{2}\) for all \(i=1,\ldots,d,\) then constants \(c_{1,}\kappa_{1},c_{2},\kappa_{2},\ldots,c_{d},\kappa_{d}>0\) exist such that \[|y_{n,i}|\le c_{d}e^{-\kappa_{i}n}\quad\forall n\ge0,i=1,\ldots,d.\] Thus \[|y_{n}|^{2}=\sum_{i=1}^{d}y_{n,i}^{2}\le ce^{-2\kappa n}\quad\forall n\ge0,\] where \(c=c_{1}+\ldots+c_{d},\) and \[\kappa=\min(\kappa_{1},\ldots,\kappa_{d})>0.\] If in addition \(\eta<\lambda_{\max}^{-1}(1-\sqrt{\beta})^{2},\) so that \(\eta<\lambda_{i}^{-1}(1-\sqrt{\beta})^{2}\) for all \(i,\) then \(\kappa_{i}>-\log|1-\lambda_{i}\eta|\ge-\log|1-\lambda_{\min}\eta|\) for all \(i,\) so indeed (3.48) holds.

Proof sketch. We have \(f'(x)=|x|^{k-1}{\rm sign}(x),\) so the iterates of GD with momentum are \[x_{n+1}=x_{n}-\eta(|x|^{k-1}{\rm sign}(x)+b)+\beta(x_{n}-x_{n-1}),\quad n\ge0.\] As in the sketch of the proof of Lemma 3.9, let us assume that \(x_{n}\) converges to \(x_{*},\) and heuristically guess the convergence rate. Like in (3.13) we have under the convergence assumption that \[\log x_{n}=\log x_{k}+\sum_{m=k}^{n}\log\left(1-\eta ax_{m}^{s}+\beta\left(1-\frac{x_{m-1}}{x_{m}}\right)\right),\quad\text{for all }n\ge k,\] for \(k\) large enough, where \(s=k-2.\) This leads to the approximation \[\log x_{n}\approx\log x_{k}-\sum_{m=k}^{n}\eta ax_{m}^{s}+\beta\sum_{m=k}^{n}\left(1-\frac{x_{m-1}}{x_{m}}\right),\quad\text{for all }n\ge k.\] With the ansatz \(x_{n}=hn^{-1/s}\) for some constant \(h>0,\) which we argued was the correct rate of \(x_{n}\downarrow0\) for GD without momentum in Example 3.9 for \(h=(s\eta a)^{-1/s},\) we have in this case \[1-\frac{x_{m-1}}{x_{m}}=1-\left(1-\frac{1}{m}\right)^{-1/s}=-\frac{1}{s}\frac{1}{m}+O(m^{-2}).\] This gives \[-\frac{1}{s}\log n\approx-\left(h^{s}\eta a+\frac{\beta}{s}\right)\log n\] after neglecting terms that are \(O(1).\) This is consistent provided \(\frac{1}{s}=h^{s}\eta a+\frac{\beta}{s}\iff h=\left(\frac{1-\beta}{s\eta a}\right)^{1/s}.\) Thus we expect the rate of convergence to be proportional to \(n^{-1/s},\) as for GD without momentum, but with an improved constant of proportionality, so that \(x_{n}\sim\left(\frac{1-\beta}{s\eta a}\right)^{1/s}n^{-1/s}.\)