CSE 535: Homework #1

1. Convexity [14 points]

1. [9 points] Show that the following sets are convex:

   • The $n$-dimensional probability simplex $S_1 = \{ x \in \mathbb{R}^n : x \geq \mathbf{0}, \mathbf{1}^{\top} x = 1\}$.

   • The set $S_2 = \{x \in \mathbb{R}^n : (x-x_0)^{\top} A (x-x_0) \leq 1 \}$, where $x_0 \in \mathbb{R}^n$ and $A$ is an $n \times n$ positive semidefinite matrix.

     Describe what the set looks like for the case $A = \begin{pmatrix} 6 & 0 \\ 0 & 10 \end{pmatrix}$ and $x_0 = (1, 1)$.

   • Show that the following set is not convex:

     $$S_3 = \left\{ (x_1,x_2,\ldots,x_n) : x_i \in \mathbb{R}^n, i=1,\ldots,n, \textrm{ and } \sum_{i,j} \|x_i-x_j\|^2 \geq 1\right\}.$$

2. [8 points] Show that the following functions are convex, or give an example showing non-convexity.

   • $f_1(x) = \max(x,0)$

   • $f_2(x) = x \log x$ for $x > 0$

   • $f_3(X) = \mathrm{rank}(X)$ where $X$ is an $n \times n$ symmetric matrix.

   • $f_4(x) = \log\left(\sum_{i=1}^n e^{x_i}\right)$.

2. Regularized gradient descent steps [12 points]

In this problem, you should think (intuitively) of the direction $v$ as equal to $\nabla f(x)$ so that each of these computations offers a different “gradient descent step.”

1. Compute a closed form expression (and show your work!) for the minimizer of

   $$\min \left\{ v^{\top} (y-x) + \frac{1}{2\eta} \|x-y\|_2^2 : y \in \mathbb{R}^n \right\},$$

   where $x,v \in \mathbb{R}^n$ and $\eta > 0$.

2. Recall that $\mathbb{R}_{++}^n = \left\{ x \in \mathbb{R}^n : x_i > 0 \textrm{ for } i=1,\ldots,n\right\}$. Compute a closed form expression (and show your work!) for the minimizer of

   $$\min \left\{ v^{\top} (y-x) + \frac{1}{\eta} \mathsf{D}(y \ \|\ x) : y \in \mathbb{R}_{++}^n\right\},$$

   where $x \in \mathbb{R}_{++}^n$ and $\eta > 0$, and $\mathsf{D}(y \ \| \ x) = \sum_{i=1}^n \left(y_i \log \frac{y_i}{x_i} + (x_i-y_i) \right)$.

3. (*) Compute a closed form expression (and show your work!) for the minimizer of

   $$\min \left\{ v^{\top} (y-x) + \frac{1}{p\eta} \|x-y\|_p^p : y \in \mathbb{R}^n\right\},$$

   for every $p \geq 1$, where $x,v \in \mathbb{R}^n$ and $\eta > 0$.

3. Residual neural networks [30 points]

For this problem, recall that every matrix $A \in \mathbb{R}^{n \times n}$ admits a singular value decomposition $A = U \Sigma V^{\top}$, where $U$ and $V$ are orthogonal matrices and $\Sigma$ is a diagonal matrix with the singular values of $A$ on the diagonal. We use $\sigma_{\min}(A)$ to denote the smallest singular value of $A$, and $\sigma_{\max}(A)$ to denote the largest singular value of $A$. Also recall the Frobenius norm $\|A\|_F = \left(\sum_{i,j} |A_{ij}|^2\right)^{1/2}$.

1. [4 points] Given points $x_1,\ldots,x_n \in \mathbb{R}^n$ and a matrix $R \in \mathbb{R}^{n \times n}$, define the function

   $$f(A_1,A_2,A_3) = \frac12 \sum_{i=1}^n \left\|(I+A_3)(I+A_2)(I+A_1) x_i - R x_i\right\|_2^2,$$

   where $A_1,A_2,A_3 \in \mathbb{R}^{n \times n}$.

   Define $G = \sum_{i=1}^n x_i x_i^{\top}$ and show that

   $$f(A_1,A_2,A_3) = \frac12 \|E G^{1/2}\|_F^2,$$

   where $E = (I+A_3)(I+A_2)(I+A_1) - R$.

2. [6 points] Show that for any $H \in \mathbb{R}^{n \times n}$,

   $$\left.\frac{d}{dt}\right|_{t=0} f(A_1+t H, A_2,A_3) = \mathrm{Tr}\left(E^{\top} (I+A_3)(I+A_2) H G\right),$$

   where we used the notation $g'(0) = \left.\frac{d}{dt}\right|_{t=0} g(t)$

3. [4 points] Using part (B), show that

   $$\frac{\partial f}{\partial A_1} = (I+A_2)^{\top} (I+A_3)^{\top} E G.$$

4. [8 points] Assume now that $\sigma_{\max}(A_1),\sigma_{\max}(A_2),\sigma_{\max}(A_3) \leq \frac12$. Show that

   $$\left\|\frac{\partial f}{\partial A_1} \right\|_F \geq \frac{\sigma_{\min}(G)^{1/2}}{4} \|E G^{1/2}\|_F.$$

   You may use the fact that for matrices $A,B \in \mathbb{R}^{n \times n}$, it holds that $\|AB\|_F \geq \sigma_{\min}(A) \|B\|_F$.

5. [8 points] Show that any local minimum of $f$ within the domain $\mathcal{D} = \left\{(A_1,A_2,A_3) : \sigma_{\max}(A_1),\sigma_{\max}(A_2),\sigma_{\max}(A_3) \leq \frac12 \right\}$ is actually a global mininum of $f$ on $\mathcal{D}$.