\documentclass{article} \usepackage[left=1.25in,top=1.25in,right=1.25in,bottom=1.25in,head=1.25in]{geometry} \usepackage{amsmath,amssymb,amsthm} \usepackage{verbatim,float,url,enumerate} \usepackage{graphicx,subfigure,psfrag} \usepackage{natbib,xcolor,dsfont} \usepackage{microtype} \newtheorem{algorithm}{Algorithm} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \theoremstyle{remark} \newtheorem{remark}{Remark} \theoremstyle{definition} \newtheorem{definition}{Definition} \newcommand{\argmin}{\mathop{\mathrm{argmin}}} \newcommand{\argmax}{\mathop{\mathrm{argmax}}} \newcommand{\minimize}{\mathop{\mathrm{minimize}}} \newcommand{\maximize}{\mathop{\mathrm{maximize}}} \newcommand{\st}{\mathop{\mathrm{subject\,\,to}}} \def\R{\mathbb{R}} \def\E{\mathbb{E}} \def\P{\mathbb{P}} \def\S{\mathbb{S}} \def\Cov{\mathrm{Cov}} \def\Var{\mathrm{Var}} \def\half{\frac{1}{2}} \def\sign{\mathrm{sign}} \def\supp{\mathrm{supp}} \def\th{\mathrm{th}} \def\tr{\mathrm{tr}} \def\dim{\mathrm{dim}} \def\dom{\mathrm{dom}} \def\prox{\mathrm{prox}} \begin{document} \title{Homework 2} \author{\Large Convex Optimization 10-725} \date{{\bf Due Friday September 27 at 11:59pm} \\ \bigskip Submit your work as a single PDF on Gradescope. Make sure to prepare your solution to each problem on a separate page. (Gradescope will ask you select the pages which contain the solution to each problem.) \\ \bigskip Total: 80 points (+ 10 bonus points)} \maketitle \section{Gradient descent convergence analysis (18 points)} In this problem, we will analyze gradient descent under suitable assumptions. Consider minimizing a differentiable function $f$ with $\dom(f)=\R^n$, whose gradient is $L$-Lipschitz continuous for a constant $L>0$, meaning $$ \| \nabla f(x) - \nabla f(y)\|_2 \leq L \|x - y\|_2, \;\;\; \text{for all $x,y$}. $$ We will run gradient descent, starting from $x^{(0)}$, with the updates $$ x^{(k)} = x^{(k-1)} - t_k \cdot \nabla f(x^{(k-1)}), \;\;\; k=1,2,3,\ldots, $$ where each $t_k \leq 1/L$. As usual, we will write a generic update as $x^+ = x - t \nabla f(x)$, where $t \leq 1/L$. \subsection{Nonconvex case (8 points)} Here we will assume nothing about convexity of $f$. We will show that gradient descent reaches an $\epsilon$-substationary point $x$, such that $\|\nabla f(x)\|_2 \leq \epsilon$, in $O(1/\epsilon^2)$ iterations. Important note: you may use here that \begin{equation} \label{eq:quad_ub} f(y) \leq f(x) + \nabla f(x)^T (y-x) + \frac{L}{2} \|y-x\|_2^2, \;\;\; \text{for all $x,y$}. \end{equation} Recall that you assumed convexity and twice differentiability of $f$ on Homework 1 to show that the above is equivalent to the $L$-Lipschitz condition on $\nabla f$. But \eqref{eq:quad_ub} is in fact a consequence of $\nabla f$ being $L$-Lipschitz, and does not actually require convexity or twice differentiability of $f$. \bigskip \noindent (a, 2 pts) Plug in $y = x^+ = x - t \nabla f(x)$ to \eqref{eq:quad_ub} to show that $$ f(x^+) \leq f(x) - \Big (1-\frac{Lt}{2} \Big) t \|\nabla f(x)\|_2^2. $$ \bigskip \noindent (b, 2 pts) Use $t \leq 1/L$, and rearrange the previous result, to get $$ \|\nabla f(x)\|_2^2 \leq \frac{2}{t} ( f(x) - f(x^+) ). $$ \bigskip \noindent (c, 2 pts) Sum the previous result over all iterations from $1,\ldots,k+1$ to establish $$ \sum_{i=0}^k \|\nabla f(x^{(i)})\|_2^2 \leq \frac{2}{t} ( f(x^{(0)}) - f^\star). $$ \bigskip \noindent (d, 2 pts) Lower bound the sum in the previous result to get $$ \min_{i=0,\ldots,k} \|\nabla f(x^{(i)}) \|_2 \leq \sqrt{\frac{2}{t(k+1)} (f(x^{(0)}) - f^\star)}, $$ which establishes the desired $O(1/\epsilon^2)$ rate for achieving $\epsilon$-substationarity. \subsection{Convex case (10 points)} Now we will assume that $f$ is convex. We will show that gradient descent reaches an $\epsilon$-suboptimal point $x$, such that $f(x)-f^\star \leq \epsilon$, in $O(1/\epsilon)$ iterations. Going back to part (b) from the nonconvex case, we can rearrange this to get \begin{equation} \label{eq:desc_ineq} f(x^+) \leq f(x) - \frac{t}{2} \|\nabla f(x)\|_2^2. \end{equation} Note that, by this property, we see that gradient descent is indeed a descent method for $t \leq 1/L$ (it decreases the criterion at each iteration). \bigskip \noindent (a, 3 pts) Starting with \eqref{eq:desc_ineq}, apply the first-order condition for convexity of $f$, to show $$ f(x^+) \leq f^\star + \nabla f(x)^T (x-x^\star) - \frac{t}{2}\|\nabla f(x)\|_2^2. $$ \bigskip \noindent (b, 3 pts) From the previous result, show that $$ f(x^+) \leq f^\star + \frac{1}{2t} \big( \|x-x^\star\|_2^2 - \|x^+ - x^\star\|_2^2 \big). $$ \bigskip \noindent (c, 2 pts) Sum the previous result over all iterations $1,\ldots,k$ to get $$ \sum_{i=1}^k ( f(x^{(i)}) - f^\star ) \leq \frac{1}{2t} \|x^{(0)} - x^\star\|_2^2. $$ \bigskip \noindent (d, 2 pts) Use the fact that gradient descent is a descent method to lower bound the sum above, and conclude $$ f(x^{(k)}) - f^\star \leq \frac{\|x^{(0)} - x^\star\|_2^2}{2tk}, $$ which establishes the desired $O(1/\epsilon)$ rate for achieving $\epsilon$-suboptimality. \section{Properties and examples of subgradients (18 points)} We will inspect various properties and examples of subgradients. \bigskip \noindent (a, 2 pts) Show that $\partial f(x)$ is a closed and convex set for any function $f$ (not necessarily convex) and any point $x$ in its domain. \bigskip \noindent (b, 2 pts) Show that $g \in \partial f(x)$ if and only if $(g,-1)$ defines supporting hyperplane to epigraph of $f$ at $(x,f(x))$ (i.e., $(g,-1)$ is the normal vector to this hyperplane). \bigskip \noindent (c, 2 pts) For a convex function $f$, show that if $x \in U$ where $U$ is a open neighborhood in its domain, then $$ f(y) \geq f(x) + g^T (y-x), \;\;\; \text{for all $y \in U$} \;\; \Rightarrow \;\; g \in \partial f(x). $$ In other words, if the tangent line inequality holds in a local open neighborhood of $x$, then it holds globally. \bigskip \noindent (d, 1 pt) For a convex function $f$ and subgradients $g_x \in \partial f(x)$, $g_y \in \partial f(y)$, prove that $$ (g_x - g_y)^T (x-y) \geq 0. $$ This property is called {\it monotonicity} of the subdifferential $\partial f$. \bigskip \noindent (e, 2 pts) For $f(x) = \|x\|_2$, show that all subgradients $g \in \R^n$ at a point $x \in \R^n$ are of the form $$ g \in \begin{cases} \{ x/\|x\|_2 \} & x \not= 0 \\ \{ v : \|v\|_2 \leq 1 \} & x = 0. \end{cases} $$ \bigskip \noindent (f, 3 pts) For $f(x) = \max_{s \in S} f_s(x)$, where each $f_s$ is convex, show that $$ \partial f(x) \supseteq \mathrm{conv}\bigg( \bigcup_{s : f_s(x)=f(x)} \partial f_s(x) \bigg). $$ {\bf Bonus (4 pts):} when $S$ is a discrete set, prove the other direction. \bigskip \noindent (g, 6 pts): For $f(X) = \|X\|_{\tr}$, show that subgradients at $X=U \Sigma V^T$ (this is an SVD of $X$) satisfy $$ \partial f(X) \supseteq \{UV^T + W : \|W\|_{\mathrm{op}} \leq 1, \; U^T W = 0, \; WV = 0 \}. $$ Hint: you may use the fact that $\|\cdot\|_{\tr}$ and $\|\cdot\|_{\mathrm{op}}$ are dual norms, which implies $\langle A, B \rangle \leq \|A\|_{\tr} \|B\|_{\mathrm{op}}$ for any matrices $A,B$, where recall $\langle A,B \rangle = \tr(A^T B)$. {\bf Bonus (5 pts):} prove the other direction. \section{Properties and examples of proximal operators (22 points)} We will inspect various properties and examples of proximal operators. Unless otherwise specified, take $h$ to be a convex function with domain $\dom(h)=\R^n$, and $t>0$ be arbitrary, and consider its associated proximal operator $$ \prox_{h,t}(x) = \argmin_z \; \frac{1}{2t} \|x - z\|_2^2 + h(z). $$ \bigskip \noindent (a, 3 pts) Prove that $\prox_{h,t}$ is a well-defined function on $\R^n$, that is, each point $x \in \R^n$ gets mapped to a unique value $\prox_{h,t}(x)$. \bigskip \noindent (b, 2 pts) Prove that $\prox_{h,t}(x) = u$ if and only if $$ h(y) \geq h(u) + \frac{1}{t} (x-u)^T (y-u), \;\;\; \text{for all $y$}. $$ Hint: use subgradient optimality. \bigskip \noindent (c, 6 pts) Prove that $\prox_{h,t}$ is nonexpansive, meaning $$ \| \prox_{h,t}(x) - \prox_{h,t}(y) \|_2 \leq \|x-y\|_2, \;\;\; \text{for all $x,y$}. $$ Hint: use the previous question, and the monotonicity of subgradients from Q2(d). \bigskip \noindent (d, 3 pts) The proximal minimization algorithm (a special case of proximal gradient descent) repeats the updates: $$ x^{(k+1)} = \mathrm{prox}_{h,t} ( x^{(k)} ), \;\;\; k=1,2,3,\ldots. $$ Write out these updates when applied to $h(x) = \frac{1}{2} x^TAx - b^Tx$, where $A \in \S^n$. Show that this is equivalent to the {\it iterative refinement} algorithm for solving the linear system $Ax=b$: $$ x^{(k+1)} = x^{(k)} + (A + \epsilon I)^{-1} (b - A x^{(k)}), \;\;\; k=1,2,3,\ldots, $$ where $\epsilon > 0$ is some constant. {\bf Bonus (1 pt):} assuming that proximal minimization converges to the minimizer of $h(x)=\frac{1}{2} x^TAx - b^Tx$ (which is does, under suitable step sizes), what would the iterations of iterative refinement converge to in the case when $A$ is singular, $Ax=b$, and $x^{(0)}=0$? \bigskip \noindent (e, 8 pts) For a matrix-variate function $h$, we define its proximal operator as $$ \prox_{h,t}(X) = \argmin_Z \; \frac{1}{2t} \|X-Z\|_F^2 + h(Z), $$ For $h(X)=\|X\|_{\tr}$, show that the proximal operator evaluated at $X=U \Sigma V^T$ (this is an SVD of $X$) is so-called matrix soft-thresholding, $$ \prox_{h,t}(X) = U \Sigma_t V^T, \;\;\; \text{where $\Sigma_t = \mathrm{diag} \Big( (\Sigma_{11}- t)_+, \ldots, (\Sigma_{nn}- t)_+\Big)$}, $$ and $x_+ = \max\{x,0\}$ denotes the positive part of $x$. Hint: start with subgradient optimality as you developed in Q3(b), and use the subgradients of the trace norm from Q2(g). \section{Group lasso logistic regression (22 points)} Suppose we have features $X \in \R^{n \times (p+1)}$ that we divide into $J$ groups: $$ X = \Big[ \mathds{1} \; X_{(1)} \; X_{(2)} \; \cdots \; X_{(J)} \Big], $$ where $\mathds{1} = (1,\ldots,1) \in \R^n$ and each $X_{(j)} \in \R^{n \times p_j}$. To achieve sparsity over groups of features, rather than individual features, we can use a {\it group lasso} penalty. Write $\beta = (\beta_0, \beta_{(1)}, \dots, \beta_{(J)}) \in \R^{p+1}$, where $\beta_0$ is an intercept term and each $\beta_{(j)} \in \R^{p_j}$. Consider the problem \begin{equation} \label{eq:group_lasso} \min_\beta \; g(\beta) + \lambda \sum_{j=1}^J w_j \|\beta_{(j)}\|_2, \end{equation} where $g$ is a loss function and $\lambda \geq 0$ is a tuning parameter. The penalty $h(\beta) = \lambda \sum_{j=1}^J w_j \|\beta_{(j)}\|_2$ is called the group lasso penalty. A common choice for $w_j$ is $\sqrt{p_j}$ to adjust for the group size. \bigskip \noindent (a, 3 pts) Derive the proximal operator $\text{prox}_{h,t}(\beta)$ for the group lasso penalty defined above. \bigskip \noindent (b, 2 pts) Let $y \in \{0,1\}^n$ be a binary label, and let $g$ be the logistic loss $$ g(\beta) = -\sum_{i=1}^{n} y_i (X\beta)_i + \sum_{i=1}^{n}\log(1 + \exp\{(X\beta)_i\}), $$ Write out the steps for proximal gradient descent applied to the logistic group lasso problem \eqref{eq:group_lasso} in explicit detail. \bigskip \noindent (c, 5 pts) Now we'll use the logistic group lasso to classify a person's age group from his movie ratings. The movie ratings can be categorized into groups according to a movie's genre (e.g., all ratings for action movies can be grouped together). Load the training data in {\tt trainRatings.txt}, {\tt trainLabels.txt}; the features have already been arranged into groups and you can find information about this in {\tt groupTitles.txt}, {\tt groupLabelsPerRating.txt}. Solve the logistic group lasso problem \eqref{eq:group_lasso} with regularization parameter $\lambda = 5$ by running proximal gradient descent for 1000 iterations with fixed step size $t = 10^{-4}$. Plot $f^{(k)}-f^\star$ versus $k$, where $f^{(k)}$ denotes the objective value at iteration $k$, and use as an optimal objective value $f^\star = 336.207$. Make sure the plot is on a semi-log scale (where the y-axis is in log scale). \bigskip \noindent (d, 5 pts) Now implement Nesterov acceleration for the same problem. You should again run accelerated proximal gradient descent for 1000 iterations with fixed step size $t=10^{-4}$. As before, produce a plot $f^{(k)}-f^\star$ versus $k$. Describe any differences you see in the criterion convergence curve. \bigskip \noindent (e, 5 pts) Lastly, implement backtracking line search (rather than a fixed step size), and rerun proximal gradient for 400 iterations, without acceleration. (Note this means 400 outer iterations; the backtracking loop itself can take several inner iterations.) You should set $\beta=0.1$ and $\alpha=0.5$. Produce a plot of $f^{(k)}-f^\star$ versus $i(k)$, where $i(k)$ counts the {\it total} number of iterations performed at outer iteration $k$ (total, meaning the sum of the iterations in both the inner and outer loops). \bigskip \noindent Note: since it makes for an easier comparison, you can draw the convergence curves from (c), (d), (e) on the same plot. \bigskip \noindent (f, 2 pts) Finally, use the solution from accelerated proximal gradient descent in part (d) to make predictions on the test set, available in {\tt testRatings.txt}, {\tt testLabels.txt}. What is the classification error? What movie genre are important for classifying whether a viewer is under 40 years old? \end{document}