\documentclass[12pt]{article} \usepackage{graphicx} \usepackage{amsmath,amssymb,url} \usepackage{bbm} \usepackage{optidef} %\usepackage[boxruled,linesnumbered]{algorithm2e} \usepackage{courier} %\usepackage{minted} \usepackage{comment} \usepackage{algorithm} \usepackage{algpseudocode} \usepackage{listings} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \newfont{\bssdoz}{cmssbx10 scaled 1200} \newfont{\bssten}{cmssbx10} \oddsidemargin 0in \evensidemargin 0in \topmargin -0.5in \headheight 0.25in \headsep 0.25in \textwidth 6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt \parskip 1.5ex \parindent 0ex \footskip 20pt \begin{document} \parindent 0ex \thispagestyle{empty} \vspace*{-0.75in} {\bssdoz CME 323: Distributed Algorithms and Optimization} {\\ \bssten Instructor: Reza Zadeh (rezab@stanford.edu) } {\\ \bssten TA:Alex Yang (yangzj@stanford.edu) } {\\ \bssten HW\#2 -- Due Thursday May 9 11:59pm (on Gradescope)} \vspace{5pt} \begin{enumerate} \item \textbf{List Prefix Sums} As described in class, List Prefix Sums is the task of determining the sum of all the elements before each element in a list. Let us consider the following simple variation. \begin{itemize} \item Select each element from the list randomly and independently with probability $1 / \log n$ and add it to a set $S$. Add the head of the list to this set, and mark all these elements in the list. \item Start from each element $s \in S$, and in parallel traverse the lists until you find the next element in $S$ (by detecting the mark) or the end of the list. For $s \in S$, call this element found in this way $\texttt{next}(s)$. While traversing, calculate the sum from $s$ to $\texttt{next}(s)$ (inclusive of $s$ but exclusive of $\texttt{next}(s)$), and call this $\texttt{sum}(s)$. \item Create a list by linking each $s \in S$ to $\texttt{next}(s)$ and with each node having weight $\texttt{sum}(s)$. \item Compute the List Prefix Sums on this list using pointer jumping. Call the result $\texttt{prefixsum}(s)$. \item Go back to the original list, and again traverse from each $s$ to $\texttt{next}(s)$ starting with the value $\texttt{prefixsum}(s)$ and adding the value at each node to a running sum and writing this into the node. Now all elements in the list should have the correct prefix sum. \end{itemize} Analyze the work and depth of this algorithm. These should both be given with high probability bounds. \item \textbf{Shortest Path for Weighted Directed Graph} Consider a directed graph $G = (V, E)$ with non-negative weights $\omega: E \to \mathbb{R}^+$. The task is to develop an algorithm to efficiently find the shortest paths from the source $s \in V$ to any other vertex $v \in V$, i.e. $$p^*(v) = \text{argmin}_{p\, \text{valid}} \sum_{i = 1}^{n_{p}} \omega_{i}(u_i, u_{i+1}),$$ where a valid path from source $s$ to $v$ is a sequence $p = (u_0, u_1, \dots, u_{n_p})$ satisfying: %1. $u_0 = s$; 2. $u_{n_p} = v$; 3. $(u_i, u_{i+1}) \in E$ for any $i$. \begin{itemize} \item $u_0 = s$; \item $u_{n_p} = v$; \item $(u_i, u_{i+1}) \in E$ for $i = 0, \dots, n_p$. \end{itemize} Now assume that the operation of finding neighbors of a vertex can be performed in constant time and constant depth (both $O(1)$). Design an algorithm that achieves $O(nm)$ work and $O(n\, \text{log}\, n)$ depth. ($n = |V|$ and $m = |E|$.)\\ \item \textbf{Singular Value Decomposition for SPSD Matrices} Given a symmetric positive definite matrix $A \in \mathbb{R}^{n\times n}$, in this problem we explore how to efficiently compute its singular value decomposition $A = U^T S U$, where $U$ is orthogonal matrix, $S$ is diagonal. Here we assume the singular values satisfy $\lambda_1> \lambda_2 > \dots > \lambda_n$. \begin{enumerate} \item Instead of directly performing QR-iteration on $A$, we want to first convert matrix $A$ to a symmetric tridiagonal matrix using Householder reflection, i.e. constructing an orthogonal matrix $Q_0$, s.t. $T = Q_0^T A Q_0$ is symmetric tridiagonal. Give a parallel algorithm to solve this problem, and analyze its work and depth. (Hint: Householder reflection $H = I_n - 2\frac{(e_\alpha - e_\beta)(e_\alpha - e_\beta)^T}{(e_\alpha - e_\beta)^T(e_\alpha - e_\beta)}$ projects $e_\alpha$ to $e_\beta$ where $e_\alpha = \alpha/||\alpha||_2$ and $e_\beta = \beta/||\beta||_2$. ) \item Now we perform QR-iteration on symmetric tridiagonal matrix $T$ to achieve SVD for $T$ using Givens rotation. Obviously, if we get the SVD of T, i.e. $S = \tilde{Q}^T T \tilde{Q}$, then we have $S = (Q_0\tilde{Q})^T A Q_0\tilde{Q}$, which is the SVD of A. Now, let's explore the following algorithm: \begin{algorithmic}[0] \Function{QR-Iteration for symmetric tridiagonal matrix}{$\boldsymbol s[1 \dots n]$} \State Let $Q_0 \leftarrow I_n$, $T_0 \leftarrow T$ \For{$t = 1$ to $T$} \State Let $Q_t \leftarrow Q_{t-1}$, $T_t \leftarrow T_{t-1}$ \For{$k = 1$ to $n - 1$} \State Let $\alpha \leftarrow T_t[k : k+1, k]$, $(c, s)^T \leftarrow \alpha / ||\alpha||_2$ \State $G_k \leftarrow \text{Givens}(k, c, s)$ \State $T_t \leftarrow G_k * T_t * G_k^T$ \State $Q_t \leftarrow G_k * Q_t$ \EndFor \EndFor \State \Return $T_T$, $Q_T$ \EndFunction \end{algorithmic} Here, the matrix representation of Givens Rotation is $$\text{Givens}(k, c, s) =\begin{bmatrix} I_{k-1} & \mathbf{0} & \mathbf{0} \\ \mathbf{0} & \begin{bmatrix} c & s \\ -s & c \\ \end{bmatrix} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & I_{n - k - 1} \\ \end{bmatrix}.$$ Analyze the work and depth of this algorithm, then compare it with part (a). Write a few sentences about your findings. \end{enumerate} \item \textbf{Stochastic Gradient Descent} \begin{enumerate} \item In class we proved that gradient descent on $L$-smooth functions is guaranteed to decrease the function value at each iteration. Stochastic gradient descent, on the other hand, does not have the same guarantee. Provide an example where stochastic gradient descent does not produce a descent step. Specifically, find a function $f(x) = \sum_{i = 1}^m f_i(x)$, and an iterate $x_0$ such that for all step sizes, there exist $i$ such that $f(x_1) > f(x_0)$ (where $x+1 := x_0 - \alpha \nabla f_i(x)$). \item This exercise will guide you through the convergence proof of SGD. As a reminder, we are proving that if there exists a constant $G$ such that $\mathbb{E}[\norm{\nabla f_i(x)}^2]\leq G^2$ and $f(x)$ is $\mu$-strongly convex. Then, with step-sizes $\gamma_k = \frac{1}{\mu k}$, we have \[\mathbb{E}[\norm{x_k - x_*}^2] \leq \frac{\max \{\norm{x_1 - x_*}^2, \frac{G^2}{\mu^2} \}}{k}.\] \begin{itemize} \item Using strong convexity, prove that \[\langle \nabla f(x_k) - \nabla f(x_*), x_k - x_* \rangle = \langle \nabla f(x_k), x_k - x_*\rangle \geq \mu \norm{x_k - x*}^2\] \item Apply the previous step, to express $\mathbb{E}[\norm{x_{k+1} - x_*}^2]$ in terms of $\mathbb{E}[\norm{x_k - x_*}^2]$, $\gamma_k$, $G$, and $\mu$. \item Prove the convergence of SGD using induction. \end{itemize} \end{enumerate} \item \textbf{HOGWILD!} This exercise will provide examples applying the main theorem of HOGWILD!. Recall that in HOGWILD!, the objective function we want to minimize is : \[f(x) = \sum_{e \in E} f_e(x_e)\] where we define the hyperedge $e$ to be the subset of variables that $f_e$ depends on. Figure \ref{fig:conflict_graph} depicts such a graph. Then, if we denote the average degree of the conflict graph as $\overline{\Delta}_C$, convergence is still guaranteed if the core delay is less than $\tau \leq \frac{n}{2\overline{\Delta}_C}$ (i.e., no more than $\tau$ samples are being processed while a core is processing one). \begin{figure}[!h] \centering \includegraphics[width = 0.6 \textwidth]{conflict_graph.png} \caption{The function-variable and conflict graph for sparse functions.} \label{fig:conflict_graph} \end{figure} \begin{itemize} \begin{comment} \item \textbf{Sparse support vector machine} In sparse SVM, we are given a set of data pairs $E = \left{(z_1, y_1), \ldots (z_n, y_n)\right}$, where each $z_i \in \mathbb{R}^d$ and $y_i$ is a label for each $z_i$. We know \emph{a priori} that the $z_i$'s are sparse (i.e., mostly have zero entries). The cost function is give by \[ \min_{x} \sum_{e \in E} \max\{1- y_ex^Tz_e, 0\} + \lamba \norm{x}^2_2\] \item \textbf{Matrix Completion} In the matrix completion problem, we sample entries of a low-rank $d_1 \times d_2$ matrix, $M$. Precisely, let $E \subset [d_1] \times [d_2]$ and $|E| = n$ be our sample set. The goal is to estimate $M$ as a product $LR^T$, where $L\in \mathbb{R}^{d_1 \times r}$, and $R \in \mathbb{R}^{d_2 \times r}$ that minimizes \[\sum_{(u,v) \in E} \left(L_uR_v^2 - M_{uv}\right)^2 + \frac{\mu}{2}\norm{L}^2_F + \frac{\mu}{2} \norm{R}^2_F.\] Rewrite this as its sparse formulation, and prove that \[\frac{\overline{\Delta}_C}{n} = \mathcal{O}\left(\frac{d_2}{d_1}\right)\] \end{comment} \item \textbf{Graph Cuts} In graph cuts problems, we are given a sparse matrix $W$ which indexes similarity between node. We want to match each node to a list of $D$ classes i.e., we want assign a vector $x_i \in \{v \in \mathbb{R}^D| \sum_{j = 1}^D v_j = 1, v_j \geq 0\}$ that solve the following optimization problem. \begin{mini}|l| {x}{\sum_{(u,v) \in E} w_{uv} \norm{x_u - x_v}_1} {}{} \addConstraint{x_u \in \{v \in \mathbb{R}^D| \sum_{j = 1}^D v_j = 1, v_j \geq 0\}.} \end{mini} Prove that \[\frac{\overline{\Delta}_C}{n} = \mathcal{O}\left(\text{Avg. deg.}\right)\] \end{itemize} \item \textbf{Implement logistic regression using tensorflow.} Use the following code to generate train and test data. Note that we have set seed (using "random\_state=42"). Use cross-entropy loss and gradient descent optimizer with a learning rate of 0.01. Use batch\_size of 100, and run for 500 steps. Report the accuracy on test set. \begin{lstlisting}[language=Python] from sklearn.datasets import make_classification from sklearn.model_selection import train_test_split import matplotlib.pyplot as plt # Generate data X_data, y_data = make_classification(n_samples=200, n_features=2, n_redundant=0, random_state=42) # Split into train and test sets X_train, X_test, y_train, y_test = train_test_split(X_data, y_data, test_size=0.2, random_state=42) # Plot training data plt.scatter(X_train[:, 0], X_train[:, 1], c=y_train) plt.show() \end{lstlisting} \end{enumerate} \end{document}