1. Euclidean projections [30 points]

Recall the Euclidean projection of $y \in \mathbb{R}^n$ onto the set $Q \subseteq \mathbb{R}^n$:

$$\pi_Q(y) = \mathrm{argmin}_{x \in Q} \|x-x_0\|_2.$$

Compute an explicit formula for the projection in each of the following. (Please show any steps of your work that are not straightforward.)

1. [5 points] The positive orthant $Q = \{ x \in \mathbb{R}^n : x_i \geq 0, i=1,2,\ldots,n \}.$

2. [5 points] The box $Q = [a_1,b_1] \times [a_2,b_2] \times \cdots \times [a_n,b_n]$ with $a_i \leq b_i$ for each $i$.

3. [10 points] The simplex $Q = \{ x \in \mathbb{R}^n : x \geq 0 \textrm{ and } x_1+x_2+\cdots+x_n = 1 \}.$

   Calculate the projection for the following three values of $y$: $(1.1,-4.5,0.5), (0.3,0.7), (0.5,1.0,2.0,1.1)$.

4. [10 points] The polytope $Q = \{ x \in \mathbb{R}^n : Ax \leq b \}$

   Calculate the projection of $(3,-4)$ onto the triangle in the plane with vertices $\{(0,0), (0,1), (2,0)\}$.

2. Conservative gradient descent [25 points]

Suppose that $K \subseteq \mathbb{R}^n$ is closed and convex, and $f : K \to \mathbb{R}$ is a convex $\mathcal{C}^2$ function with $L$-Lipschitz gradients. Define the diameter $D = \max \{ \|x-y\|_2 : x,y \in K \}$.

Define the two step iterate:

$$y^{(k)} \leftarrow \mathrm{argmin}_{y \in K} \langle \nabla f(x^{(k)}), y\rangle \\ x^{(k+1)} \leftarrow \frac{k}{k+1} x^{(k)} + \frac{1}{k+1} y^{(k)}.$$

1. [10 points] Using the fact that $-L \mathbf{I} \preceq \nabla^2 f(x) \preceq L \mathbf{I}$ for all $x \in K$, show that

   $$f(x^{(k+1)}) \leq f(x^{(k)}) - \frac{1}{k+1} \left(f(x^{(k)})-f(x^*)\right) + \frac{L}{2} \frac{1}{(k+1)^2} \|y^{(k)}-x^{(k)}\|_2^2.$$

2. [10 points] Consider the potential function $\Psi_k = k \left[f(x^{(k)})-f(x^*)\right]$. Use the preceding part to show that for all $T \geq 1$,

   $$\Phi_T \leq \mathcal{O}(L D^2 \log(T+1)).$$

3. [5 points] Conclude an upper bound on $f(x^{(T)})-f(x^*)$ in terms of $L$, $D$, and $T$.

3. Faster convergence with mirror maps [45 points]

Say that a $\mathcal{C}^2$ convex function $f : \mathbb{R}^n \to \mathbb{R}$ is $L$-smooth and $\mu$-convex relative to a mirror map $\Phi : \mathbb{R}^n \to \mathbb{R}$ if it holds that

$$\mu \nabla^2 \Phi(x) \preceq \nabla^2 f(x) \preceq L \nabla^2 \Phi(x),\qquad \forall x \in \mathbb{R}^n.$$

Starting with $x^{(0)} \in \mathbb{R}^n$, for $k=0,1,\ldots,T$, define

$$x^{(k+1)} \leftarrow \mathrm{argmin}_{x \in \mathbb{R}^n} f(x^{(k)}) + \langle \nabla f(x^{(k)}), x-x^{(k)}\rangle + L\cdot D_{\Phi}(x;x^{(k)}),$$

where $D_{\Phi}$ is the Bregman divergence of $\Phi$.

1. [5 points] Prove that this algorithm is vanilla gradient descent if $\Phi(x) = \frac12 \|x\|_2^2$.

2. [5 points] Show that

   $$f(x^{(k+1)}) \leq f(x^{(k)}) + \langle \nabla f(x^{(k)}), x^{(k+1)}-x^{(k)}\rangle + L\cdot D_{\Phi}(x^{(k+1)};x^{(k)}).$$

3. [10 points] Show that for any $x \in \mathbb{R}^n$,

   $$f(x^{(k+1)}) \leq f(x^{(k)}) + \langle \nabla f(x^{(k)}), x-x^{(k)}\rangle + L \cdot D_{\Phi}(x;x^{(k)}) - L \cdot D_{\Phi}(x;x^{(k+1)}).$$

4. [5 points] Show that for any $x \in \mathbb{R}^n$,

   $$f(x^{(k+1)}) \leq f(x) + (L-\mu) D_{\Phi}(x;x^{(k)}) -L D_{\Phi}(x;x^{(k+1)}).$$

5. [10 points] Show that for any $k \geq 1$,

   $$f(x^{(k)}) - f(x^*) \leq L \left(1-\frac{\mu}{L}\right)^k D_{\Phi}(x^*; x^{(0)}).$$

6. [10 points] Define $f(x) = - \log \det(A D_x A^{\top})$ where $D_x$ is the diagonal matrix with $(D_x)_{ii} = x_i$ and $A$ is a (not necessarily square) matrix. Define $\Phi(x) = - \sum_{i=1}^n \ln x_i$. Show that $f$ is $1$-smooth relative to $\Phi$ for $x > 0$.

   [Hint: Show that $\nabla^2 f(x) = C \circ C$, where $C = A^{\top} (AD_x A^{\top})^{-1} A$ and $U \circ V$ is the Hadamard product given by $(U\circ V)_{ij} = U_{ij} V_{ij}$. You may use Schur’s Lemma which asserts that if $U,V \succeq 0$, then $U \circ V \succeq 0$ as well.]