online4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the 4th post about online convex optimization, and there might be one more yet to come. I'm going to apply the concepts introduced in the <a href=conjugates-and-divergences.html>previous post</a> to prove some regret bounds. \n",
    "\n",
    "In order to do this we'll introduce the Online Mirror Descent framework. Earlier we introduced the Follow-the-Regularized-Leader algorithm for online convex optimization. When we use a quadratic regularizer, the prediction at time step $t$ is purely a function of $z_1+\\dots+z_{t-1}$. In particular, it is $w_t = -\\eta (z_1+\\dots+z_{t-1})$ where $\\eta$ depends on the regularizer. This is just Online Gradient Descent. Online Mirror Descent generalizes this idea by introducing a <i>link function</i> $g$. Instead of $w_t=-\\eta(z_1+\\dots+z_{t-1})$ we set $w_t=g(-z_1-\\dots-z_{t-1})$. When $g(x)=\\eta x$, we recover Online Gradient Descent, but if $g$ is some other function we might end up with a different algorithm.\n",
    "\n",
    "<h3>Online Mirror Descent</h3>\n",
    "\n",
    "Here is the algorithm:\n",
    "\n",
    "<div class=\"algorithm\">\n",
    "<h4>Online Mirror Descent (OMD)</h4>\n",
    "\n",
    "<ol>\n",
    "<li> Initialize $\\theta_t=0$.\n",
    "<br>\n",
    "For each $t=1,2,\\dots$</li>\n",
    "<li> Predict $w_t=g(\\theta_t)$.</li>\n",
    "<li> Receive subgradient $z_t$.</li>\n",
    "<li> Update $\\theta_{t+1}=\\theta_t - z_t$.</li>\n",
    "</ol>\n",
    "</div>\n",
    "\n",
    "The name \"Mirror\" in Online Mirror Descent comes from the fact that prediction vectors $w_t$ and gradient vectors $z_t$ actually live in dual vector spaces. This is because for a function $f:\\R^n\\to \\R$, the gradient $\\nabla f$ is really just the <a href=https://en.wikipedia.org/wiki/Total_derivative#The_total_derivative_as_a_linear_map>total derivative</a> of $f$, which is a linear map $\\R^n\\to \\R$ - an element of the dual space. Thus the link function $g$ is a \"mirror\" that converts gradient vectors in the dual space to prediction vectors in the original space."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One can imagine choosing any sort of wacky link function, but we'll focus on link functions of the form:\n",
    "\n",
    "$$\n",
    "g(\\theta) = \\nabla R^*(\\theta) = \\argmax_{w}(\\langle w,\\theta\\rangle-R(w))\n",
    "$$\n",
    "\n",
    "where $R$ is some fixed function and $\\R^*$ is its Fenchel conjugate. It's also possible to motivate this choice of link function as optimizing a <a href=https://en.wikipedia.org/wiki/Duality_%28optimization%29>dual problem</a> (see <a href=http://papers.nips.cc/paper/3107-convex-repeated-games-and-fenchel-duality>here</a>), but we won't go over this here.\n",
    "\n",
    "The \"workhorse\" result of for this type of link function is\n",
    "\n",
    "<div class = \"theorem\">\n",
    "<h4>Lemma 1</h4>\n",
    "Suppose OMD is run with link function $g=\\nabla R^*$ as above. Then\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T(u) \\le \\sum_{t=1}^T \\langle w_t-u,z_t\\rangle \\le R(u)-\\min_w R(w)+\\sum_{t=1}^T D_{R^*}(-z_{1:t}\\|-z_{1:t-1})\n",
    "$$\n",
    "where $z_{1:t}$ is shorthand for $\\sum_{t'=1}^t z_{t'}$.\n",
    "</div>\n",
    "\n",
    "Notice the similarity of this lemma to regret bounds in <a href=online-gradient-descent.html>previous posts</a>. We see that the overall form of the bound is always the same:\n",
    "\n",
    "$$\n",
    "R \\le a-b+c\n",
    "$$\n",
    "\n",
    "where $a$ and $b$ are some terms that depend on the optimal point $u$ and the initial point $w_1$ while $c$ is a sum of \"stability\" terms that are minimized when some particular quantity changes slowly with each iteration. It's often possible to translate proofs using this theorem directly into the elementary language used to prove the Online Gradient Descent bound.\n",
    "\n",
    "So let's prove the lemma:\n",
    "\n",
    "<i>Proof.</i>\n",
    "\n",
    "The first inequality in which Regret is bounded by inner products with subgradient vectors is just the statement that linear functions are the hardest type of function to learn. See the previous posts to review why that's so.\n",
    "\n",
    "Let's proceed to prove the second inequality.\n",
    "By definition of Fenchel conjugate, we have\n",
    "\n",
    "$$\n",
    "R^*\\left(-\\sum_{t=1}^T z_t\\right) \\ge \\left\\langle u,-\\sum_{t=1}^T z_t\\right\\rangle  - R(u)\n",
    "$$\n",
    "\n",
    "Thus\n",
    "\n",
    "$$\n",
    "\\sum_{t=1}^T\\langle w_t-u,z_t\\rangle \\le R(u)+R^*(-z_{1:T}) +\\sum_{t=1}^T\\langle w_t,z_t\\rangle\n",
    "$$\n",
    "\n",
    "Now use the fact that $w_t = \\nabla R^*(-z_{1:t-1})$ and the definition of Bregman divergence:\n",
    "\n",
    "$$\n",
    "\\sum_{t=1}^T\\langle w_t,z_t\\rangle = \\sum_{t=1}^T \\langle\\nabla R^*(-z_{1:t-1}),z_t\\rangle = \\sum_{t=1}^T  D_{R^*}(-z_{1:t}\\|-z_{1:t-1})-R^*(-z_{1:t})+R^*(-z_{1:t-1})\\\\\n",
    "=R^*(0)-R^*(-z_{1:t})+\\sum_{t=1}^T D_{R^*}(-z_{1:t}\\|-z_{1:t-1})\n",
    "$$\n",
    "\n",
    "making the appropriate substitution, we have\n",
    "\n",
    "$$\n",
    "\\sum_{t=1}^T \\langle w_t-u,z_t\\rangle \\le R(u)+R^*(0)+\\sum_{t=1}^T D_{R^*}(-z_{1:t}\\|-z_{1:t-1})\n",
    "$$\n",
    "\n",
    "Finally, $R^*(0)=\\max_{w} \\langle w,0\\rangle - R(w)=-\\min_{w} R(w)$. This completes the proof."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "\n",
    "Using this lemma and the fact that $R$ is $\\sigma$-strongly convex if and only if $R^*$ is $\\frac{1}{\\sigma}$-strongly smooth (strong/smooth duality), we get the following result:\n",
    "\n",
    "<div class=\"theorem\">\n",
    "<h4>OMD Regret</h4>\n",
    "Suppose $R$ is $\\frac{1}{\\eta}$-strongly convex with respect to some norm $\\|\\cdot\\|$. Then if we run OMD with the link function $g(\\theta)=\\nabla R^*(\\theta)$, we have:\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T(u) \\le R(u) -\\min_{w} R(w) + \\frac{\\eta}{2}\\sum_{t=1}^T \\|z_t\\|^2_{*}\n",
    "$$\n",
    "\n",
    "where $\\|\\cdot\\|_{*}$ is the dual norm.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see what we can do with this theorem. <a href=online-gradient-descent.html>Recall</a> that when we derived the regret of online gradient descent using the Follow-the-Regularized-Leader approach we obtained a regret bound of\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T \\le \\sqrt{2}BL\n",
    "$$\n",
    "\n",
    "where the feasible set was the ball of radius $B$ and $L=\\sqrt{\\sum_{t=1}^T z_t^2}$. However, when we used Zinkevich's analysis to derive the regret of online gradient descent with a decaying stepsize we found a regret bound of \n",
    "\n",
    "$$\n",
    "\\text{Regret}_T \\le BL\n",
    "$$\n",
    "\n",
    "We'll be able to match this bound using the OMD Regret theorem.\n",
    "\n",
    "Set $R(w)=\\frac{1}{2\\eta} \\|w\\|^2$. Then $R$ is $\\frac{1}{\\eta}$-strongly convex. Further, a little inspection shows that\n",
    "\n",
    "$$\n",
    "\\nabla R^*(\\theta) = \\Pi_{S} \\eta\\theta\n",
    "$$\n",
    "\n",
    "where $S$ is the feasible set and $\\Pi_S x$ is the projection of $x$ to $S$. In particular, online gradient descent (with lazy projections) is online mirror descent using link function $g(\\theta)=\\nabla R^*(\\theta)$. Now the dual of the euclidean norm is itself, so the theorem tells us\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T(u) \\le \\frac{1}{2\\eta} \\|u\\|^2 +\\frac{\\eta}{2}\\sum_{t=1}^T \\|z_t\\|^2 \n",
    "$$\n",
    "\n",
    "so that when the feasible set $S$ has diameter $B$,\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T(S) \\le \\frac{1}{2\\eta} B^2 +\\frac{\\eta}{2}\\sum_{t=1}^T \\|z_t\\|^2 \n",
    "$$\n",
    "\n",
    "and setting $\\eta =  \\frac{B}{\\sqrt{\\sum_{t=1}^T \\|z_t\\|^2 }}$ we obtain the desired regret bound."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So far in this series we've talked about three ways to prove regret bounds. Two of these were the Follow-the-Regularized-Leader (FTRL) approach and now Online Mirror Descent. The last method (we'll call it the \"direct method\") is to apply a cute trick: write \n",
    "\n",
    "$$\n",
    "(w_{t+1}-w^*)^2=(w_{t}-w^*-\\eta_t z_t)^2\n",
    "$$\n",
    "\n",
    "and then expand both sides, solve for $(w_t-w^*)z_t$, and sum. This results in a nice telescoping sum whenever the $\\eta_t$ are non-increasing and so yields a very useful regret bound.\n",
    "\n",
    "Of these, only this last method can deal with changing learning rates so far. As a direct result, it is the only method that we've used to analyze algorithms that don't need to know the time horizon $T$, the sizes of the gradient $\\|z_t\\|$ or the size of the domain $B$. Unfortunately, it's also in some sense the least general; it can only handle updates of the form $w_{t+1}=w_t -\\eta_t z_t$. Certainly this is a very powerful type of update, but one might imagine scenarios in which there is something better.\n",
    "\n",
    "Thus it would be nice if we could generalize the FTRL and OMD approaches to incorporate parameters that change over time. We'll first explore this possibility for OMD, and then we'll examine how to do the same for FTRL"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>Varying OMD with Time</h3>\n",
    "\n",
    "The natural path to take here is to have a time-varying link function. In particular, let's consider updates of the form\n",
    "\n",
    "$$\n",
    "w_t=g_t(\\theta_t)=g_{t-1}(-z_{1:t-1})\n",
    "$$\n",
    "\n",
    "where\n",
    "\n",
    "$$\n",
    "g_t(\\theta) = \\nabla R_t^*(\\theta)\n",
    "$$\n",
    "\n",
    "We use choose to subscript the link functions in such a way as to track \"information\". That is, $g_{t-1}$ can potentially be chosen with knowledge of $z_{t-1}$, but it cannot use knowledge of $z_t$.\n",
    "\n",
    "With these definitions, the proof of lemma 1 can be essentially copied over to get:\n",
    "\n",
    "<div class=\"theorem\">\n",
    "<h4>Lemma 2</h4>\n",
    "Suppose OMD is run with link function $g_t=\\nabla R_t^*$ as above. Then\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T(u) \\le \\sum_{t=1}^T \\langle w_t-u,z_t\\rangle \\le R_{T-1}(u)-\\min_w R_0(w)+\\sum_{t=1}^T R_{t}^*(-z_{1:t})-R_{t-1}^*(-z_{1:t})+\\sum_{t=1}^T D_{R_{t-1}^*}(-z_{1:t}\\|-z_{1:t-1})\n",
    "$$\n",
    "</div>\n",
    "\n",
    "Note the similarity to the direct method for bounding regret: We have two \"leftover\" terms at first that don't fit into the \"almost telescoping\" first sum. The last sum represents some kind of sum over the subgradients - for strongly smooth $R_t^*$ it's bounded by a sum of the subgradients squared just as in the direct regret bound."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also translate the OMD Regret theorem when the link function is varying.\n",
    "\n",
    "<div class=\"theorem\">\n",
    "<h4>OMD Regret with Varying Link functions</h4>\n",
    "Suppose $R_t$ is $\\frac{1}{\\eta_t}$-strongly convex with respect to some (potentially time-varying) norm $\\|\\cdot\\|_{(t)}$, and further suppose $R^*_{t+1}(\\theta)\\le R^*_t(\\theta)$ for all $t$ and $\\theta$. Then if we run OMD with the link function $g_t(\\theta)=\\nabla R_t^*(\\theta)$, we have:\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T(u) \\le R_{T-1}(u) -\\min_{w} R_{0}(w) + \\sum_{t=1}^T \\frac{\\eta_{t-1}}{2}\\|z_t\\|^2_{(t),*}\n",
    "$$\n",
    "\n",
    "where $\\|\\cdot\\|_{(t),*}$ is the dual norm.\n",
    "</div>\n",
    "\n",
    "We don't always need to have the norm be time-varying - we can often encode all the necessary variations in the $\\eta_t$.\n",
    "\n",
    "Let's apply this bound to online gradient descent: Suppose our loss functions satisfy $L^2\\le \\frac{1}{T}\\sum_{t=1}^T z_t^2$. Then if we set $R_t(x) = \\frac{\\sqrt{2t+1}L}{2B}\\|x\\|^2$, then we satisfy the conditions of the theorem with $\\eta_t = \\frac{B}{L\\sqrt{2t+1}}$ and $\\|\\cdot\\|_{(t)}$ equal to the standard Euclidean norm. and so obtain:\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T\\left(\\{u\\ |\\ \\|u\\|\\le B\\}\\right) \\le \\sqrt{2T-1}\\frac{LB}{2} + \\frac{BL}{2}\\left(1+\\int_1^T\\frac{dt}{\\sqrt{2t-1}}\\right) =BL\\sqrt{2T-1}\\le BL\\sqrt{2T}\n",
    "$$\n",
    "\n",
    "The <a href=http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-19.pdf>optimal regret</a> for this feasible set is $BL\\sqrt{T}$. What I mean by optimal regret here is that if the environment is as evil as possible to your algorithm, subject to never giving gradients greater than $L$, then you can never achieve better regret than $BL\\sqrt{T}$. We're achieving $\\sqrt{2}$ higher than this bound. Recall that this is the same bound as when we analyzed OGD with a $\\frac{1}{\\sqrt{t}}$-decaying learning rate <a href=http://artishoke.com/notes/online-gradient-descent.html>previously</a>, but now we are using <i>lazy projections</i> rather than greedy projections.\n",
    "\n",
    "It's possible to use the same result given above to derive an AdaGrad-type bound by setting \n",
    "\n",
    "$$\n",
    "R_t(x)  = \\frac{\\sqrt{Z+\\sum_{t'=1}^{t-1} z_{t'}^2}}{\\eta}\n",
    "$$\n",
    "\n",
    "where $Z\\ge \\sup \\|z_t\\|$. It's a good exercise to see what happens without this extra $Z$ - you'll notice an \"off-by-one\" error that confounds the bound.\n",
    "\n",
    "There are various other ways to modify Mirror Descent to obtain different algorithms. For example, one could take a <i>proximal</i> view and use the update\n",
    "\n",
    "$$\n",
    "x_{t+1} = \\nabla D_{R_t}(x\\|x_t)^*(-z_t)\n",
    "$$\n",
    "\n",
    "which explicitly encourages $x_{t+1}$ to be close to $x_t$ while taking into account the most recent gradient $z_t$. This scheme can avoid the \"off-by-one\" error when using an adaptive step size. For now though, we'll move on to Follow-the-Regularized-Leader (FTRL)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>Fixing up Follow-the-Regularized-Leader</h3>\n",
    "\n",
    "Previously when we used the FTRL framework to derive regret bounds we found that our regret bound was $\\sqrt{2}$ worse than we were able to get with the more direct schemes (or now with mirror descent). That is, even though the algorithm was exactly the same, we achieved worse regret bounds. Thus the fault was not in the algorithm but in the mathematical framework used to analyze it.\n",
    "\n",
    "Secondly (and perhaps less urgently), the vanilla FTRL scheme doesn't yield time-varying learning rates. In this section we'll fix both of these issues. The analysis follows <a href=http://arxiv.org/abs/1403.3465>McMahan's exposition</a>. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is the FTRL algorithm we'll be analyzing:\n",
    "\n",
    "<div class=\"algorithm\">\n",
    "<h4>Follow-the-Regularized-Leader (FTRL)</h4>\n",
    "\n",
    "<ol>\n",
    "<li> Input: regularizing function $r_0$.\n",
    "<br>\n",
    "For each $t=0,1,\\dots$</li>\n",
    "<li> Predict $w_{t+1}=\\argmin_{w} r_{0:t}+f_{1:t}$. </li>\n",
    "<li> Receive loss function $f_{t+1}$.</li>\n",
    "<li> Choose additional regularizing function $r_{t+1}$.</li>\n",
    "</ol>\n",
    "</div>\n",
    "\n",
    "Here we're using the notation $r_{0:t}=\\sum_{k=0}^t r_k$. We'll also define $h_t = r_t+f_t$. Thus the update in FTRL can be written:\n",
    "\n",
    "$$\n",
    "w_{t+1} = \\argmin_w h_{0:t}(w)\n",
    "$$\n",
    "\n",
    "The \"regularizing\" functions can really be any functions at all. Of course, in general you'd like the functions $r_k$ to have some various nice properties in order to actually have a good algorithm. We'll describe these properties later.\n",
    "\n",
    "The \"vanilla\" FTRL we looked at earlier is a special case of this algorithm where $r_t=0$ for all $t>0$. By allowing this incremental changing of the regularizer we're allowing varying step sizes and updates.\n",
    "\n",
    "<h4>The \"weak\" and \"strong\" FTRL analysis</h4>\n",
    "\n",
    "Normally, FTRL is analyzed using a lemma that bounds regret as a function of differences of loss functions at successive prediction points. We'll tighten this analysis in a bit, but just to refresh let's go through the original argument. First consider FTRL where $r_t=0$ for all $t$ (that is, don't do any regularizing. This is called Follow-the-Leader or FTL). We'll show that in this case:\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T(u,FTL) = \\sum_{t=1}^T f_t(w_t)-f_t(w_{t+1})\n",
    "$$\n",
    "\n",
    "To see this, consider the \"Be-the-Leader\" algorithm in which $w_t^{\\text{BTL}} = \\argmin_w f_{1:t}$. Note that this algorthim can't actually be run - we have to know the future to use it. Clearly BTL has at most 0 regret. Further, the predictions of FTL lag behind those of BTL by one time step: $w_t^{\\text{BTL}}= w_{t+1}$. Therefore\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T(u,FTL)\\le \\text{Regret}_T(u,FTL) -\\text{Regret}_T(u,BTL) = \\sum_{t=1}^T f_t(w_t)-f_t(w_t^{\\text{BTL}})= \\sum_{t=1}^T f_t(w_t)-f_t(w_{t+1})\n",
    "$$\n",
    "\n",
    "Now notice that the FTRL algorithm is just playing FTL on $h_t$ instead of $f_t$. Thus we can use the FTL result to bound our regret <i>against the $h_t$</i>. Let's write this down (adding in a \"dummy\" prediction $w_0$ in order to directly apply the FTL result):\n",
    "\n",
    "$$\n",
    "r_0(w_0)+\\sum_{t=1}^T h_t(w_t) - r_0(u)-\\sum_{t=1}^T h_t(u) \\le r_0(w_0)-r_0(w_1) +\\sum_{t=1}^T h_t(w_t)-h_t(w_{t+1})\n",
    "$$\n",
    "\n",
    "Expanding the definition of $h_t$ and rearranging, we have\n",
    "\n",
    "$$\n",
    "\\sum_{t=1}^t f_t(w_t)-f_t(u) - r_{0:t}(u)+\\sum_{t=0}^Tr_t(w_t) \\le  r_0(w_0)-r_0(w_1) + \\sum_{t=1}^T h_t(w_t)-h_t(w_{t+1})\\\\\n",
    "\\text{Regret}_T(u) \\le r_{0:t}(u) +\\sum_{t=1}^T h_t(w_t)-r_0(w_1)+h_t(w_{t+1}) - r_t(w_t)\n",
    "$$\n",
    "\n",
    "Now we may as well assume (say by adding a constant) that $r_0(w_1)=0$ - this will have no effect on the predictions produced by FTRL. Thus our bound becomes:\n",
    "\n",
    "\n",
    "$$\n",
    "\\sum_{t=1}^t f_t(w_t)-f_t(u) - r_{0:t}(u)+\\sum_{t=0}^Tr_t(w_t) \\le  r_0(w_0)-r_0(w_1) + \\sum_{t=1}^T h_t(w_t)-h_t(w_{t+1})\\\\\n",
    "\\text{Regret}_T(u) \\le r_{0:t}(u) +\\sum_{t=1}^T h_t(w_t)+h_t(w_{t+1}) - r_t(w_t)\n",
    "$$\n",
    "\n",
    "If we assume that $r_k\\ge 0$ for all $k$ then we can bound the sum on the RHS to get\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T(u) \\le r_{0:t}(u) + \\sum_{t=1}^T f_t(w_t)-f_t(w_{t+1})\n",
    "$$\n",
    "\n",
    "which is the \"weak\" FTRL lemma. \n",
    "\n",
    "As the name implies, the weak lemma is not as good as the \"strong\" lemma, which we'll prove next:\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<div class = \"theorem\">\n",
    "<h4>Strong FTRL lemma</h4>\n",
    "The regret of FTRL is bounded by\n",
    "$$\n",
    "\\text{Regret}_T(u) \\le  r_{0:T}(u) + \\sum_{t=1}^T h_{0:t}(w_t)-h_{0:t}(w_{t+1})-r_t(w_t)\n",
    "$$\n",
    "</div>\n",
    "\n",
    "Note that this is <i>almost</i> the same as the bound we simplified to get the weak version, but now we have $h_{0:t}$ rather than $h_t$ in the sum. This lemma makes critical use of the fact that the Be-the-Leader algorithm is actually better than just picking the best point in hindsight. Here's the proof:\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "\\sum_{t=1}^T h_t(w_t)-h_{0:T}(u)&=\\sum_{t=1}^T h_{0:t}(w_t)-h_{0:t-1}(w_t)-h_{0:T}(u)\\\\\n",
    "&\\le\\sum_{t=1}^T h_{0:t}(w_t)-h_{0:t-1}(w_t) - h_{0:T}(w_{T+1})\\\\\n",
    "&=\\sum_{t=1}^T h_{0:t}(w_t)-h_{0:t}(w_{t+1})\n",
    "\\end{align*}\n",
    "$$\n",
    "where inequality is due to the definition of $w_{T+1}=\\argmin_{w} h_{0:T}(w)$.\n",
    "\n",
    "Now we note\n",
    "\n",
    "$$\n",
    "f_t(w_t)-f_t(u) =h_t(w_t)-f_t(u) -r_t(w_t)-r_t(u)\n",
    "$$\n",
    "\n",
    "and combining this with the above argument completes the proof."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Without further ado, here is a general FTRL regret bound that we can prove using the strong lemma:\n",
    "\n",
    "<div class = \"theorem\">\n",
    "\n",
    "<h4>FTRL Regret </h4>\n",
    "Suppose we run FTRL with $r_t$ chosen such that $h_{0:t}+f_{t+1}$ is 1-strongly convex with respect to some norm $\\|\\cdot\\|_{(t)}$ and $r_t\\ge 0$ for all $t$. Let $z_t$ be a subgradient of $f_t$ at $x_t$. Then\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T(u) \\le r_{0:T-1}(u) + \\frac{1}{2}\\sum_{t=1}^T \\|z_t\\|^2_{(t-1),*}\n",
    "$$\n",
    "</div>\n",
    "\n",
    "In the OMD regret bound we assumed our link functions were $\\frac{1}{\\eta_t}$-strongly convex with respect to $\\|\\cdot\\|$, while here we only assume 1-strongly convex. This is not actually making the theorem any weaker: if a function is $\\sigma$-strongly convex with respect to $\\|\\cdot\\|$, then it is 1-strongly convex with respect to $\\sigma\\|\\cdot\\|$. So all that's happened here is that we're favoring a little more abstraction for some simpler notation.\n",
    "\n",
    "Also note that here we have a $\\frac{1}{2}$ in front of the summation. If we were to just use the weak FTRL lemma we'd get a similar result without the $\\frac{1}{2}$, which is why the strong lemma is better.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's prove the FTRL regret bound. To do this we'll bound each term of the sum in the strong FTRL lemma:\n",
    "\n",
    "$$\n",
    "h_{0:t}(w_t)-h_{0:t}(w_{t+1})-r_t(w_t)=h_{0:t-1}(w_t)+f_t(w_t)-h_{0:t-1}(w_{t+1})-f_t(w_{t+1})-r_t(w_t)\\le h_{0:t-1}(w_t)+f_t(w_t)-h_{0:t-1}(w_{t+1})-f_t(w_{t+1})\n",
    "$$\n",
    "\n",
    "Now <a href = conjugates-and-divergences.html>recall</a> that when $R+f$ is strongly convex, $x_1=\\argmin_x R(x)$ and $z$ is a subgradient of $f$ at $x_1$, then\n",
    "\n",
    "$$\n",
    "R(x_1)+f(x_1)-R(x')-f(x')\\ge \\frac{1}{2}\\|z\\|^2_*\n",
    "$$\n",
    "\n",
    "for all $x'$.\n",
    "\n",
    "Examining our expression aboce for $h_{0:t}(w_t)-h_{0:t}(w_{t+1})-r_t(w_t)$, we see that this statement directly applies with $z=z_t$, and so applying the strong FTRL lemma concludes the proof."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>OGD as FTRL</h3>\n",
    "\n",
    "To finish up, let's show that this \"varying regularizer\" version of FTRL can recover the standard OGD regret bound.\n",
    "\n",
    "Let $\\eta_t$ be any decreasing sequence, and let $r_{0:t}(w)=\\frac{1}{2\\eta_t}\\|w\\|^2$ where $\\|w\\|^2$ is the squared euclidean norm. That is, $r_t(0) = \\left(\\frac{1}{2\\eta_t}-\\frac{1}{2\\eta_{t-1}}\\right)\\|w\\|^2\\ge 0$. Then $h_{0:t}$ is 1-strongly convex with respect to the norm $\\frac{1}{\\eta_t}\\|\\cdot\\|$. Applying the FTRL regret theorem gives\n",
    "\n",
    "$$\n",
    "\\text{Regret}_T(u) \\le \\frac{1}{2\\eta_{T-1}}\\|u\\|^2 + \\frac{1}{2}\\sum_{t=1}^T \\eta_t\\|z_t\\|^2\n",
    "$$\n",
    "\n",
    "Setting $\\eta_t\\propto \\frac{1}{\\sqrt{t}}$ recovers the standard OGD bound. Further, notice that when we replace $f_t(w)$ with the linearized functions $\\langle z,w\\rangle$ we get the same projected gradient descent algorithm we had with the OMD framework.\n",
    "\n",
    "As a final note, it is possible to derive a different bound for a \"proximal\" version of FTRL in which we assume $x_t=\\argmin_x r_{t+1}(x)$ for all $t$. The bound in this case has a sum of $\\|z_t\\|^2_{(t),*}$ instead of $\\|z_t\\|^2_{(t-1),^*}$, which allows us to more easily construct adaptive regularizers. This is the same issue as the \"off-by-one\" error that can come up with the OMD regret bound we showed earlier."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}