---
title: COMS 6998-4 F17 Homework 0 (due Wednesday September 13)
author: Daniel Hsu (djh2164) # your name and UNI goes here
geometry: margin=1in
---

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

# Instructions

Create an account on Gradescope <https://gradescope.com> (if you don't have one already), and add this course using the Entry Code **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:

  - your name,
  - your UNI, and
  - the names and UNIs of any students with whom you discussed the assignment.

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

\newpage

# 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.

_Your solution_:

\newpage

# Problem 2

The course website <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.

  (a) 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.

  (b) 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.

\bigskip

_Your solution_:

\newpage

# 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$.

_Hint_: Use the Cauchy-Schwarz inequality.

\bigskip

_Your solution_:

\newpage

# 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)} .
$$

_Hint_: For the second part, use the Cauchy-Schwarz inequality.

\bigskip

_Your solution_:

\newpage

# 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} .
$$

_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

_Your solution_: