1. Convex conjugates [30 points]

Consider $f : \mathbb{R}^n \to \mathbb{R} \cup \{\pm \infty\}$. Its convex conjugate is the function $f^* : \mathbb{R}^n \to \mathbb{R} \cup \{\pm \infty\}$ given by

$$f^*(y) = \sup \left\{ \langle y,x\rangle - f(x) : x \in \mathbb{R}^n \right\}.$$

1. [5 points] Compute $f^*$ when $f(x) = e^{x_1} + e^{x_2} + \cdots + e^{x_n}$.

2. [5 points] Compute $f^*$ when $f(x) = \frac{1}{p} \|x\|_p^p$ for $p > 1$.

3. [5 points] Prove that for all $x,y \in \mathbb{R}^n$,

   $$\langle x,y\rangle \leq f(x) + f^*(y).$$

4. [15 points] Assume that $f$ is a convex $\mathcal{C}^2$ function. Show that $f$ has $L$-Lipschitz gradients if and only if $f^*$ is $1/L$-strongly convex.

2. Logconcave and isotropic distributions [25 points]

Given a probability distribution $\mu$ on $\mathbb{R}^n$, its covariance matrix is defined by

$$\mathrm{cov}(\mu) = \mathbb{E}_{X \sim \mu} \left[(X-\mathbb{E}[X])(X-\mathbb{E}[X])^{\top}\right],$$

where $X$ is a random vector sampled from $\mu$.

Recall that a probability density on $\mathbb{R}^n$ is an integrable function $p : \mathbb{R}^n \to [0,\infty)$ such that

$$\int_{\mathbb{R}^n} p(x)\,dx = 1.$$

And the associated probability measure is defined on measurable subsets $S \subseteq \mathbb{R}^n$ by

$$\mu(S) = \int_S p(x)\,dx.$$

Recall also the Minkowski sum $A+B$ of two sets $A,B \subseteq \mathbb{R}^n$:

$$A+B = \{ a + b : a \in A, b \in B \}.$$

1. [5 points] For a function $F : \mathbb{R}^n \to \mathbb{R}^n$ and a distribution $\mu$, we define the pushforward measure $F \# \mu$ by

   $$F \# \mu(S) = \mu(F^{-1}(S)).$$

   For a given measure $\mu$, define an affine function $F$ such that $F \# \mu$ is isotropic. Recall that an affine function $F : \mathbb{R}^n \to \mathbb{R}^n$ is of the form $F(x) = Ax + b$ for $A \in \mathbb{R}^{n \times n}, b\in \mathbb{R}^n$.

   (You may assume that the covariance matrix $A = \mathrm{cov}(\mu)$ is invertible.)

2. [EXTRA CREDIT, 10 points] Recall that $p : \mathbb{R}^n \to \mathbb{R}$ is log-concave if the function $\log p(x)$ is concave. Say that a distribution $\mu$ is log-concave if it holds that for all measurable subsets $A,B \subseteq \mathbb{R}^n$,

   $$\mu(\lambda A + (1-\lambda)B) \geq \mu(A)^{\lambda} \mu(B)^{1-\lambda} \qquad (*)$$

   The Brunn-Minkowski inequality asserts that the volume measure $\mathrm{vol}(S)$ on $S \subseteq \mathbb{R}^n$ is log-concave.

   Show that if $p$ is a log-concave density, then the associated probability measure $\mu$ is log-concave in the sense of $(*)$.

3. [10 points] (You may assume that part (B) is true for this part!)

   Suppose that the distribution $\mu$ is given by the density $p : \mathbb{R}^n \to \mathbb{R}$

   $$p(x) = \frac{\mathbf{1}_K(x)}{\mathrm{vol}(K)},$$

   where $K \subseteq \mathbb{R}^n$ is a closed, bounded, convex set.

   Show that if $F : \mathbb{R}^n \to \mathbb{R}^n$ is an affine function, then $\nu = F \# \mu$ is log-concave in the sense of $(*)$.

3. A different measure of progress [25 points]

Suppose that $f : \mathbb{R}^n \to \mathbb{R}$ is convex and $\mathcal{C}^2$. Assume also that for some $\mu,L > 0$,

$$L \mathbf{I} \succeq \nabla^2 f(x) \succeq \mu \mathbf{I},\quad \forall x \in \mathbb{R}^n.$$

In class we showed that if we define the gradient desent steps by

$$x^{(k+1)} = x^{(k)} - \frac{1}{L} \nabla f(x^{(k)}),$$

then we have the rate of convergence

$$f(x^{(k)}) - f(x^*) \leq \left(1-\frac{1}{\kappa}\right)^k \left(f(x^{(0)})-f(x^*)\right),$$

where $\kappa = L/\mu$. We also showed that $\|x^{(k)}-x^*\|_2$ is decreasing as $k$ increases. In this problem, you will try to obtain an exponential rate of decrease for $\|x^{(k)}-x^*\|_2$.

1. [10 points] Show that

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

2. [15 points] Using the mirror-descent analysis for inspiration, prove that

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

   Partial credit will be given for proving the slightly weaker bound with a decrease of $1-\frac{1}{\kappa}$ at every iteration.