\documentclass[11pt]{article}

\input{__includes}

\title{COMS 4995-004: Optimization for Machine Learning \\ Homework 4 {\bf (Corrected version)}}
\author{}
\date{}
\begin{document}
\maketitle
{\bf HW4 is due Wednesday, Nov 27 by 1:00 pm. No late assignments will be accepted\footnote{Unless you have an emergency; in that case please write to Satyen as soon as possible.}. Please refer to \url{https://www.satyenkale.com/optml-f19/} for instructions on how to submit homework assignments.}

\medskip
\noindent As discussed in class, projected gradient descent makes use of a projection oracle, whereas the Frank-Wolfe method uses a linear optimization oracle. A linear optimization oracle is easier to implement than a projection oracle, and in this exercise we will formalize this qualitative statement. Suppose that $K$ is a convex set in $\mathbb{R}^d$ in the unit $\ell_2$ ball, i.e. for all $x \in K$, we have $\|x\|_2 \leq 1$. A {\em linear optimization oracle} for $K$ is an algorithm that, given any vector $v \in \mathbb{R}^d$, computes $\arg\max_{x \in K} v\cdot x$. A {\em projection oracle} for $K$ is an algorithm that, given any point $y \in \mathbb{R}^d$, computes $\Pi_K(y) := \arg\min_{x \in K} \|y - x\|_2^2$. 
\begin{enumerate}
	\item {\bf (9 points)} Suppose we are given a projection oracle for $K$. We now want to implement an {\em $\epsilon$-approximate} linear optimization oracle for $K$ using the projection oracle, i.e. given a vector $v \in \mathbb{R}^d$, we want to find a point $x \in K$ such that $v \cdot x \geq \max_{x' \in K} v \cdot x' - \epsilon$. Show that we can find such a point $x$ by making {\em one} call to the projection oracle applied to a carefully chosen point $y$ (i.e. by computing $\Pi_K(y)$ for some point $y$). Give a precise formula for $y$ in terms of $v$ and $\epsilon$.\\
	{\em Hint: consider applying the projection oracle to a point $y = \alpha v$ for some scalar $\alpha$.}

	\item {\bf (16 points)} Suppose we are given a linear optimization oracle for $K$. We now want to implement an {\em $\epsilon$-approximate} projection  oracle for $K$ using the linear optimization oracle, i.e. given a point $y \in \mathbb{R}^d$, we want to find a point $x \in K$ such that $\|y - x\|_2^2 \leq \min_{x' \in K} \|y -  x'\|^2 + \epsilon$. Show that we can find such a point $x$ by making $O(\frac{1}{\epsilon})$ calls to the linear optimization oracle. Describe your implementation of the projection oracle via pseudo-code.\\
	{\em Hint: consider computing the projection via the Frank-Wolfe method.}
\end{enumerate}

\end{document} 
