\documentclass[10pt]{article}
\usepackage[OT4]{fontenc}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}
\usepackage{enumerate}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\input{preamble.tex}
\newcommand{\psetsol}[3]{\handout{#1}{}{Author:
#2}{Collaborator: #3}{Solutions to Problem Set #1}}

\parindent 0pt

\begin{document}



\psetsol{1}{Your name here}{Name/``None''}

{\bf Problem 1.} Recall the stock market framework (see Section 2 in notes from Lecture 1). Prove that, in the worst case, no \emph{deterministic} prediction algorithm for this framework can make less than $2m^*+\log_2 n$ mistakes. Here, $n$ is the size of the expert set and $m^*$ is the number of mistakes made by the best expert.\\

\emph{(Your solution goes here.)}\\

{\bf Problem 2.} Consider the (general) learning-from-expert-advice framework (see Section 5 in notes from Lecture 1) with $n$ experts. A popular measure of algorithms' performance in this framework is so-called \emph{regret}. The regret is the difference $l_{ALG} - l^*$ between the total loss $l_{ALG}$ of the algorithm and the loss $l^*=\min_i \sum_{t=1}^T l_i^t$ of the best expert in hindsight.\\

Assume that the game lasts for $T$ rounds (and this value is known in advance) and the loss $l_i^t$ in each round $t$ is in the interval $[0,1]$.
\begin{enumerate}[(a)]
\item Show that the regret suffered by the Multiplicative Weights Update algorithm (with appropriate parameters) is $O(\sqrt{T \log n})$.
\item How important was it that the MWU algorithm was allowed to switch between experts in each round, while we compared its performance to the best \emph{fixed} expert? To answer this, show that for any algorithm $ALG$, one can construct an example in which the total loss $l_{ALG}$ of this algorithm will be at least $T(1-1/n)$, while the loss $l_{CH}^*$ of the best ``changing'' expert is $0$,  i.e., $l_{CH}^*=\sum_{t=1}^T \min_i l_i^t = 0$.
\end{enumerate}

\emph{(Your solution goes here.)}\\

{\bf Problem 3.} Show that for any (non-empty) subset $S$ of $n$ experts, the Multiplicative Weights Update algorithm suffers a total loss $l_{MWU}$ of at most
\[
l_{MWU} \leq \max_{i\in S} (\sum_t l_i^t + \varepsilon \sum_t |l_i^t|) + \frac{\rho \ln \frac{n}{|S|}}{\varepsilon},
\]
where $0\leq \varepsilon \leq \frac{1}{2}$ and each $l_i^t\in [-\rho,\rho]$.\\

\emph{(Your solution goes here.)}\\

{\bf Problem 4. (Extra credit)} Consider again the setting from Problem 2. That is, the (general) learning-from-expert-advice framework with $n$ experts, the total number of rounds $T$ known upfront, and $l_i^t\in [0,1]$ for each $i$ and $t$.\\

We now would like to be able to bound our regret not with respect to a one ``fixed'' expert, but to a ``changing'' expert that can switch \emph{at most $k$ times} during the execution of the game. (Of course, we do not know when the switches happen.) Design an algorithm for this setting whose regret is at most $O(\sqrt{kT\log Tn})$.\\

\emph{(Your solution goes here.)}
\end{document}




