\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
  \else
    \usepackage{fontspec}
  \fi
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\PassOptionsToPackage{hyphens}{url} % url is loaded by hyperref
\usepackage[unicode=true]{hyperref}
\hypersetup{
            pdftitle={COMS 6998-4 F17 Homework 0 (due Wednesday September 13)},
            pdfauthor={Daniel Hsu (djh2164)},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\usepackage[margin=1in]{geometry}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi

% set default figure placement to htbp
\makeatletter
\def\fps@figure{htbp}
\makeatother


\title{COMS 6998-4 F17 Homework 0 (due Wednesday September 13)}
\author{Daniel Hsu (djh2164)}
\date{}

\begin{document}
\maketitle

\newcommand\E{\mathbb{E}}
\renewcommand\P{\mathbb{P}}
\newcommand\R{\mathbb{R}}
\newcommand\Var{\operatorname{Var}}

\section{Instructions}\label{instructions}

Create an account on Gradescope \url{https://gradescope.com} (if you
don't have one already), and add this course using the Entry Code
\textbf{M8662E}. Submit the write-up on Gradescope as a PDF document by
11:59 PM of the due date.

Make sure the following appears at the top of the first page of your
write-up:

\begin{itemize}
\tightlist
\item
  your name,
\item
  your UNI, and
\item
  the names and UNIs of any students with whom you discussed the
  assignment.
\end{itemize}

You are welcome to use the Markdown or LaTeX source for the assignment
as a template for your write-up. I use Pandoc \url{http://pandoc.org} to
translate the Markdown to \LaTeX~and ultimately to PDF.

\newpage

\section{Problem 1}\label{problem-1}

Name one or two of your own personal, academic, or career values.
Briefly explain how you hope CS/ML theory can be of service to those
values.

\emph{Your solution}:

\newpage

\section{Problem 2}\label{problem-2}

The course website \url{http://www.cs.columbia.edu/~djhsu/coms6998-f17}
has information about the course prerequisites, course requirements,
academic rules of conduct, and other information. You are required to
understand this information and abide by the rules of conduct,
regardless of whether or not you can correctly solve this problem.

\begin{enumerate}
\def\labelenumi{(\alph{enumi})}
\item
  True or false: I may look at the homework write-up of another student
  as long as their write-up only contains solutions for at most half of
  the problems, and we list each other as discussion partners on the
  submitted write-up.
\item
  True or false: I may use any outside reference material to help me
  solve the homework problems as long as I acknowledge these materials
  in the submitted write-up.
\end{enumerate}

\bigskip

\emph{Your solution}:

\newpage

\section{Problem 3}\label{problem-3}

The \(l^p\) norm for vectors in \(\R^n\) is defined by \[
  \|x\|_p := \left( \sum_{i=1}^n |x_i|^p \right)^{1/p} , \quad x = (x_1,\dotsc,x_n) \in \R^n .
\]

Prove that \(\|x\|_1 \leq \sqrt{n} \|x\|_2\) for every \(x \in \R^n\).

\emph{Hint}: Use the Cauchy-Schwarz inequality.

\bigskip

\emph{Your solution}:

\newpage

\section{Problem 4}\label{problem-4}

Prove that if \(X\) is a non-negative integer-valued random variable,
then \(\P(X \neq 0) \leq \E X\) and \[
  \P(X = 0) \leq \frac{\Var(X)}{\E(X^2)} .
\]

\emph{Hint}: For the second part, use the Cauchy-Schwarz inequality.

\bigskip

\emph{Your solution}:

\newpage

\section{Problem 5}\label{problem-5}

Let vectors \(v_1,\dotsc,v_d \in \R^n\) and a positive integer \(k\) be
given. Prove that for any vector \(u\) in the convex hull of
\(v_1,\dotsc,v_d\), there exist non-negative integers \(k_1,\dotsc,k_d\)
with \(\sum_{i=1}^d k_i = k\) and \[
  \left\| u - \frac1k \sum_{i=1}^d k_i v_i \right\|_2^2
  \leq \frac{\max_i \|v_i\|_2^2 - \|u\|_2^2}{k} .
\]

\emph{Hint}: Recall that a vector \(u\) is in the convex hull of
\(v_1,\dotsc,v_d\) if there exist non-negative real numbers
\(\alpha_1,\dotsc,\alpha_d \geq 0\) with \(\sum_{i=1}^d \alpha_i = 1\)
such that \[
  u = \sum_{i=1}^d \alpha_i v_i .
\] This suggest a natural proof via the probabilistic method.

\bigskip

\emph{Your solution}:

\end{document}