SGT

1

$${\nabla }_{x}f(x)=\frac{\partial f(x)}{\partial x}={\left[\begin{array}{c}\frac{\partial f}{\partial x_1},\frac{\partial f}{\partial x_2},\dots ,\frac{\partial f}{\partial x_n}\end{array}\right]}^T$$ $$\begin{array}{rl}\frac{1}{2}||Ax-b|{|}^2& =\frac{1}{2}[(Ax-b{)}^T(Ax-b)]\\ & =\frac{1}{2}[A^T{x}^{T}Ax-A^T{x}^{T}b-b^{T}Ax+b^{T}b]\\ & =\frac{1}{2}[A^T{x}^{T}Ax-2A^T{x}^{T}b+b^{T}b]\end{array}$$

We want to find $\frac{\partial A^T{x}^{T}Ax-2A^T{x}^{T}b+b^{T}b}{\partial x}$.

Rule we want to use:

$$\frac{\partial x^{T}x}{\partial x}=2x$$

Find the derivatives: $\frac{\partial (A^T{x}^{T}xA)}{\partial (x)}=2x{A}^{T}A$ $\frac{\partial (2A^T{x}^{T}b)}{\partial (x)}=2A^{T}b$ $\frac{\partial b^{T}b}{\partial (x)}=0$

Since $b^{T}Ax$ is scalar, it is equal to its own transpose: $b^{T}Ax=(x^T{A}^{T}b{)}^T$.

$$\begin{array}{rl}\frac{\partial A^T{x}^{T}Ax-2A^T{x}^{T}b+b^{T}b}{\partial x}& =2x{A}^{T}A-2A^{T}b+0\\ & =2A^T(Ax-b)\\ & \\ \therefore \frac{1}{2}\frac{\partial A^T{x}^{T}Ax-2A^T{x}^{T}b+b^{T}b}{\partial x}& =A^T(Ax-b)\text{ as required}\\ & \therefore \text{ answer is }C\end{array}$$

2

By definition of convexity, $f$ is convex since $H$ is symmetric positive semi-definite matrix and it admits a global minimum $x^{\ast }$ since it is a convex function.

3

Closed-form expression for this minimum $x^{\ast }$:

$$\begin{array}{r}f(x):=\frac{1}{2}{x}^{T}Hx-q^{T}x\\ \nabla f(x)=Hx-q\\ H{x}^{\ast }-q=0\\ x^{\ast }=\frac{q}{H}\end{array}$$

Closed-form expression for excess cost function $f(x)-f(x^{\ast })$:

$$\begin{array}{rl}f(x)-f(x^{\ast })& =\frac{1}{2}{x}^{T}Hx-q^{T}x-\left(\begin{array}{c}\frac{1}{2}{x}^{\ast T}Hx-q^T{x}^{\ast }\end{array}\right)\\ & =\frac{1}{2}{x}^{T}Hx-q^{T}x-\frac{1}{2}{x}^{\ast T}Hx+q^T{x}^{\ast }\\ & =\frac{1}{2}{x}^{T}Hx-\frac{1}{2}{x}^{\ast T}Hx+q^T(x^{\ast }-x)\\ & =\frac{1}{2}{x}^{T}Hx-\frac{1}{2}{x}^{\ast T}Hx+(H{x}^{\ast }{)}^T(x^{\ast }-x)\\ & =\frac{1}{2}{x}^{T}Hx-\frac{1}{2}{x}^{\ast T}Hx+x^{\ast T}H(x^{\ast }-x)\\ & =\frac{1}{2}{x}^{T}Hx+\frac{1}{2}{x}^{\ast T}Hx+x^{\ast T}H(x)\\ & =\frac{1}{2}(x-x^{\ast }{)}^{T}H(x-x^{\ast })\end{array}$$

4

Expression of gradient of $f$ (as required):

$$\begin{array}{rl}\nabla f(x)& =Hx-q\\ H{x}^{\ast }& =q\\ \nabla f(x)& =Hx-H{x}^{\ast }\\ & =H(x-x^{\ast })\end{array}$$

5

Gradient descent iteration formula with step-size $\gamma$ and gradient $g$: $x_{t+1}=x_t-g_t$

$$\begin{array}{rl}{g}_t& =\nabla f(x_t)\\ & =H(x_t-x^{\ast })\text{ from last question}\end{array}$$

We are given that the error term is ${\alpha }_t=x_t-x^{\ast }$ (where $x^{\ast }$ is the optimal solution). Given this we can state the recursion satisfied by ${\alpha }_t$:

Substitute $x_t={\alpha }_t+x^{\ast }$ and use $g_t=Hx-q$.

$$\begin{array}{rl}{x}_t& =x_{t-1}-\gamma (H{x}_{t-1}-q)\\ x_t-x^{\ast }& =x_{t-1}-x^{\ast }-\gamma (H{x}_{t-1}-q)\\ {\alpha }_t& ={\alpha }_{t-1}-\gamma H(a_{t-1}+x^{\ast })+\gamma q\end{array}$$

Assume that $H{x}^{\ast }-q=0$, we have:

$${\alpha }_t={\alpha }_{t-1}-\gamma H{\alpha }_{t-1}$$