Online Convex Optimization

$$ \begin{aligned} & \texttt{protocol: Online Convex Optimisation} \\ & \textbf{Given: } \text{ game length } T, \text{ convex and compact action space } \mathcal{K} \subseteq \mathbb{R}^d \\ & \textbf{For } t=1,2, \ldots, T \\ & \quad \text{ The learner picks action } \mathbf{x}_t \in \mathcal{K} \\ & \quad \text{ The adversary picks convex loss } f_t: \mathcal{K} \rightarrow \mathbb{R} \\ & \quad \text{ The learner observes } f_t \quad \triangleleft\, \text{ full information } \\ & \quad \text{ The learning incurs loss } f_t(\mathbf{x}_t) \end{aligned} $$

在线凸优化以 regret 为最小化的目标

$$ \operatorname{Regret}_{T}=\sum_{t=1}^{T} f_{t}\left(\mathbf{x}_{t}\right)-\min _{\mathbf{x} \in \mathcal{K}} \sum_{t=1}^{T} f_{t}(\mathbf{x}) $$

令 $\overline{\mathbf{x}}_T=\frac{1}{T} \sum_{t=1}^T \mathbf{x}_t$，则 $$ \begin{equation} f\left(\overline{\mathbf{x}}_T\right)-f\left(\mathbf{x}^{\star}\right) \leq \frac{1}{T} \sum_{t=1}^T\left[f\left(\mathbf{x}_t\right)-f\left(\mathbf{x}^{\star}\right)\right]=\frac{\text { Regret }_T}{T} \label{oco-rel} \end{equation} $$

First-Order Algorithms for Online Convex Optimization

Online Gradient Descent

Zinkevich^[1] 首先提出了在线版本的梯度下降法： $$ \begin{aligned} & \texttt{{Algorithm: online gradient descent}} \\ & 1: \text{Input: convex set } \mathcal{K}, T, \mathbf{x}_{1} \in \mathcal{K}, \text{ step sizes } \left\{\eta_{t}\right\} \\ & 2: \text{for } t=1 \text{ to } T \text{ do } \\ & 3: \quad \text{Play } \mathbf{x}_{t} \text{ and observe cost } f_{t}\left(\mathbf{x}_{t}\right) \\ & 4: \quad \text{Update and project:} \\ & \qquad \qquad \qquad \mathbf{y}_{t+1}=\mathbf{x}_{t}-\eta_{t} \nabla f_{t}\left(\mathbf{x}_{t}\right) \\ & \qquad \qquad \qquad \mathbf{x}_{t+1}=\prod_{\mathcal{K}}\left(\mathbf{y}_{t+1}\right) \\ & 5: \text{end for} \\ \end{aligned}\notag $$ 每轮迭代都沿着梯度方向走一小步，如果走出了限制的集合，就投影到原来的集合上。

记 $D = \operatorname{diam}(\mathcal{K}), \| \nabla f(x)\| \leq G \;\, \forall x \in \mathcal{K}$ ，$\| \cdot \|$ 为2范数

如果取步长 $\eta_t = \displaystyle \frac{D}{G \sqrt{t}}$，则 $$ \operatorname{Regret}_{T}=\sum_{t=1}^{T} f_{t}\left(\mathbf{x}_{t}\right)-\min _{\mathbf{x}^{\star} \in \mathcal{K}} \sum_{t=1}^{T} f_{t}\left(\mathbf{x}^{\star}\right) \leq \frac{3}{2} G D \sqrt{T} $$

Despite the fact that the next cost function may be completely different than the costs observed thus far, the regret attained by the algorithm is sublinear.

证明：

令 $\mathbf{x}^\star \in \arg \min _{\mathbf{x} \in \mathcal{K}} \sum_{t=1}^T f_t(\mathbf{x})$，证明思路是，先找到 $f_t(\mathbf{x}) - f_t(\mathbf{x}^\star)$ 的上界，再进一步找到 $\displaystyle\sum_{t=1}^T (f_t(\mathbf{x}) - f_t(\mathbf{x}^\star))$ 的上界。

根据凸性，我们有 $$ f_t\left(\mathbf{x}_t\right)-f_t\left(\mathbf{x}^{\star}\right) \leq \nabla f_t(\mathbf{x}_t)^{\top}\left(\mathbf{x}_t-\mathbf{x}^{\star}\right) $$ 再根据勾股定理，有 $$ \begin{aligned} \left\|\mathbf{x}_{t+1}-\mathbf{x}^{\star}\right\|^2=\left\|\Pi_{\mathcal{K}}\left(\mathbf{x}_t-\eta_t \nabla f_t(\mathbf{x})\right)-\mathbf{x}^{\star}\right\|^2 & \leq\left\|\mathbf{x}_t-\eta_t \nabla f_t(\mathbf{x})-\mathbf{x}^{\star}\right\|^2 \\ & = \left\|\mathbf{x}_t-\mathbf{x}^{\star}\right\|^2+\eta_t^2\left\|\nabla f_t(\mathbf{x})\right\|^2-2 \eta_t \nabla f_t(\mathbf{x})^{\top}\left(\mathbf{x}_t-\mathbf{x}^{\star}\right) \end{aligned} $$ 于是 $$ \begin{equation} 2 \nabla f_t(\mathbf{x})^{\top}\left(\mathbf{x}_t-\mathbf{x}^{\star}\right) \leq \frac{\left\|\mathbf{x}_t-\mathbf{x}^{\star}\right\|^2-\left\|\mathbf{x}_{t+1}-\mathbf{x}^{\star}\right\|^2}{\eta_t}+\eta_t G^2 \label{oco-sum-1-to-T} \end{equation} $$ 对 $\eqref{oco-sum-1-to-T}$ 式令 $\eta_t = \displaystyle\frac{D}{G \sqrt{t}}$，并从 $t=1$ 累加至 $T$，得到 $$ \begin{aligned} &2\left(\sum_{t=1}^T f_t\left(\mathbf{x}_t\right)-f_t\left(\mathbf{x}^{\star}\right)\right) \\ & \leq 2 \sum_{t=1}^T \nabla f_t(\mathbf{x})^{\top}\left(\mathbf{x}_t-\mathbf{x}^{\star}\right) \\ &\leq \sum_{t=1}^T \frac{\left\|\mathbf{x}_t-\mathbf{x}^{\star}\right\|^2-\left\|\mathbf{x}_{t+1}-\mathbf{x}^{\star}\right\|^2}{\eta_t}+G^2 \sum_{t=1}^T \eta_t \\ &\leq \sum_{t=1}^T\left\|\mathbf{x}_t-\mathbf{x}^{\star}\right\|^2\left(\frac{1}{\eta_t}-\frac{1}{\eta_{t-1}}\right)+G^2 \sum_{t=1}^T \eta_t & \quad \left\|\mathbf{x}_{T+1}-\mathbf{x}^\star\right\|^2 \geq 0,\;\; \frac{1}{\eta_0} \stackrel{\text { def }}{=} 0 \\ &\leq D^2 \sum_{t=1}^T\left(\frac{1}{\eta_t}-\frac{1}{\eta_{t-1}}\right)+G^2 \sum_{t=1}^T \eta_t \\ &\leq D^2 \frac{1}{\eta_T}+G^2 \sum_{t=1}^T \eta_t & \text{telescoping series} \\ &\leq 3 D G \sqrt{T} & \sum_{t=1}^T {1}/{\sqrt{t}} \leq 2 \sqrt{T} \end{aligned} $$

如果设置 $\eta_t$ 为定长 $\eta = \displaystyle\frac{D}{G\sqrt{T}}$，可得到 regret 界为 $\displaystyle\frac{D^2}{2\eta} + \displaystyle\frac{\eta}{2}TG^2 \Rightarrow GD\sqrt{T}$ .

对 $\displaystyle\frac{D^2}{2\eta} + \displaystyle\frac{\eta}{2}TG^2$ 可以这么解释：

$\eta$ 越大，第一部分（underfitting）的带来的 regret 越小，第二部分（overfitting）带来的 regret 越大。

$\eta$ 越小，第一部分的带来的 regret 越大，第二部分带来的 regret 越小。

Lower Bounds

任何在线凸优化算法在最坏情况下的 regret 至少为 $\Omega(\sqrt{T})$ .

这说明 OCO 算法给出的 $\sqrt{T}$ 的 regret 界是紧的，这种次线性的界是非常好的。如果 adversary 刻意地选取（对 $\mathbf{x}_t$ 而言）成本高的 $f_t$，那么这时候最优的 $\mathbf{x}$ 的成本也会增高。

Logarithmic Regret

The main reason OCO has taken the stage in online learning in recent years is the simplicity of its algorithms and their analysis, which allow for numerous variations and tweaks in their host applications.

对于强凸的函数，可以使用更小的步长，来达到更小的 regret.

如果 $f_t$ 是 $\alpha$ 强凸函数，那么取步长 $\eta_t = \displaystyle\frac{1}{\alpha t}$，就有 $$ \operatorname{Regret}_{T} \leq \frac{G^{2}}{2 \alpha}(1+\log T) $$

证明的思路是类似的。

根据 $\alpha$ 强凸这一性质 $$ 2\left(f_t\left(\mathbf{x}_t\right)-f_t\left(\mathbf{x}^{\star}\right)\right) \leq 2 \nabla f_t(\mathbf{x}_t)^{\top}\left(\mathbf{x}_t-\mathbf{x}^{\star}\right)-\alpha\left\|\mathbf{x}^{\star}-\mathbf{x}_t\right\|^2 $$ 根据更新规则和勾股定理，同样可以得到式 $\eqref{oco-sum-1-to-T}$ ；令 $\eta_t = \displaystyle\frac{1}{\alpha t}$，并从 $t=1$ 累加至 $T$，得到 $$ \begin{aligned} &2\left(\sum_{t=1}^T f_t\left(\mathbf{x}_t\right)-f_t\left(\mathbf{x}^\ast\right)\right) \\ &\leq 2 \sum_{t=1}^T \nabla f_t(\mathbf{x})^T\left(\mathbf{x}_t-\mathbf{x}^\ast\right)-\sum_{t=1}^T \alpha\left\|\mathbf{x}^\ast-\mathbf{x}_t\right\|^2 \\ &\leq \sum_{t=1}^T\left\|\mathbf{x}_t-\mathbf{x}^\ast\right\|^2\left(\frac{1}{\eta_t}-\frac{1}{\eta_{t-1}}-\alpha\right)+G^2 \sum_{t=1}^T \eta_t \\ &=0+G^2 \sum_{t=1}^T \frac{1}{\alpha t} \\ &\leq \frac{G^2}{\alpha}(1+\log T) \end{aligned} $$

Applications

Offline optimization

对于任意一个凸函数 $f$，只要我们能获得它的梯度信息，令 OCO 中的 $f_t=f$，应用 OCO 的结论，有： $$ f(\bar{\mathbf{x}}_T) -f(\mathbf{x}^\star)= f\left(\frac{1}{T} \sum_{i=1}^T \mathbf{x}_t\right) - f(\mathbf{x}^\star)\leq \frac{GD}{\sqrt{T}} $$ 这意味着在 $T = G^2D^2/\epsilon^2$ 轮迭代后，我们能找到 $\epsilon$-optimal 的解。

Stochastic Gradient Descent

同离线优化不同，在在线优化的场景中，我们可能不能得到完整的梯度信息，比如，可能只能得到一个梯度的无偏估计。

假设要最小化凸函数 $f(\mathbf{x})$，有一个 oracle $\mathcal{O}(\mathbf{x})$ 提供了梯度的一个粗糙的估计 $$ \mathcal{O}(\mathbf{x}) \stackrel{\text { def }}{=} \tilde{\nabla}_{\mathbf{x}} \; \text { s.t. } \quad \mathrm{E}\left[\tilde{\nabla}_{\mathbf{x}}\right]=\nabla f(\mathbf{x}), \mathrm{E}\left[\left\|\tilde{\nabla}_{\mathbf{x}}\right\|^{2}\right] \leq G^{2} $$ SGD 用近似的梯度来代替 OGD 的梯度，取 $\eta_t = \displaystyle\frac{D}{G \sqrt{t}}$，SGD 的 regret 满足： $$ \mathrm{E}\left[\frac{1}{T} \sum_{t=1}^T f(\mathbf{x}_t)\right] - f(\mathbf{x}^\ast) \leq \frac{3 G D}{2 \sqrt{T}} $$

$$ \begin{align} \text{proof：} \quad & \mathrm{E}\left[\frac{1}{T} \sum_{t=1}^T f\left(\mathbf{x}_{t}\right)\right]-f\left(\mathbf{x}^{\star}\right) \notag \\ & \leq \frac{1}{T} \mathrm{E}\left[\sum_{t} \nabla f\left(\mathbf{x}_{t}\right)^{\top}\left(\mathbf{x}_{t}-\mathbf{x}^{\star}\right)\right] \notag \\ &=\frac{1}{T} \mathrm{E}\left[\sum_{t} \tilde{\nabla}_{t}^{\top}\left(\mathbf{x}_{t}-\mathbf{x}^{\star}\right)\right] \tag{a} \\ &=\frac{1}{T} \mathrm{E}\left[\sum_{t} f_{t}\left(\mathbf{x}_{t}\right)-f_{t}\left(\mathbf{x}^{\star}\right)\right]\notag \\ &\leq \frac{\operatorname{Regret}_{T}}{T} \notag\\ &\leq \frac{3 G D}{2 \sqrt{T}} \notag \end{align} $$

这里令 $f_{t}(\mathbf{x}) \triangleq\left\langle\tilde{\nabla}_{t}, \mathbf{x}\right\rangle$，再应用 OGD 的结果，就能够得到如上的 SGD 的 regret bound.

上面推导中的 (a) 式，也可以不这样，转而应用技巧 $\eqref{oco-sum-1-to-T}$ 可以得到同样的结论

当 $f$ 具有强凸性，则其 $\log T$ 的 regret bound 的证明过1程为

$$ \begin{aligned} \text{proof：} \quad & \mathrm{E}\left[\frac{1}{T} \sum_{t=1}^T f\left(\mathbf{x}_{t}\right)\right]-f\left(\mathbf{x}^{\star}\right)\\ & \leq \frac{1}{T} \mathrm{E}\left[\sum_{t} \left( \nabla f\left(\mathbf{x}_{t}\right)^{\top}\left(\mathbf{x}_{t}-\mathbf{x}^{\star}\right) - \frac{\alpha}{2}\|\mathbf{x}_t - \mathbf{x}^\star\|^2 \right) \right] \\ & =\frac{1}{T} \mathrm{E}\left[\sum_{t} \left(\tilde{\nabla}_t^{\top}\left(\mathbf{x}_{t}-\mathbf{x}^{\star}\right) - \frac{\alpha}{2}\|\mathbf{x}_t - \mathbf{x}^\star\|^2 \right) \right] \\ &=\frac{1}{T} \mathrm{E}\left[ \sum_t \left( \frac{\|\mathbf{x}_t - \mathbf{x}\|^2 - \|\mathbf{x}_{t+1} - \mathbf{x}\|^2}{2\eta_t} - \frac{\alpha}{2} \|\mathbf{x}_t - \mathbf{x}^\star\| + \frac{\eta_t}{2}G^2 \right) \right] \\ &\leq \frac{G^{2}}{2 \alpha T}(1+\log T) \end{aligned} $$

Example: stochastic gradient descent for SVM training

【对于一个具体的函数做 SGD】

结合式 $\eqref{oco-rel}$，我们有： $$ \mathrm{E}\left[f\left(\overline{\mathbf{x}}_T\right)\right]-f\left(\mathbf{x}^{\star}\right) \leq \mathrm{E}\left[\frac{1}{T} \sum_t f\left(\mathbf{x}_t\right)\right]-f\left(\mathbf{x}^{\star}\right) $$ 对于 SVM 来说，它的优化目标是： $$ \begin{aligned} &f(\mathbf{x})=\min _{\mathbf{x} \in \mathbb{R}^d}\left\{\lambda \frac{1}{n} \sum_{i \in[n]} \ell_{\mathbf{a}_i, b_i}(\mathbf{x})+\frac{1}{2}\|\mathbf{x}\|^2\right\} \\ &\ell_{\mathbf{a}, b}(\mathbf{x})=\max \left\{0,1-b \cdot \mathbf{x}^{\top} \mathbf{a}\right\} \end{aligned} $$ 对此，一种 SGD 的算法是： $$ \begin{aligned} & \texttt{{Algorithm: SGD for SVM training}} \\ & \text{1: Input: training set of } n \text{ examples } \left\{\left(\mathbf{a}_i, b_i\right)\right\}, T. \text{ Set } \mathbf{x}_1=0 \\ & \text{2: } \textbf{for } t=1 \text{ to } T \textbf{ do } \\ & \text{3: } \quad \text{ Pick an example uniformly at random } t \in[n]. \\ & \text{4: } \quad \text{ Let } \tilde{\nabla}_t=\lambda \nabla \ell_{\mathbf{a}_t, b_t}\left(\mathbf{x}_t\right)+\mathbf{x}_t \text{ where } \\ & \qquad \qquad \qquad \nabla \ell_{\mathbf{a}_t, b_t}\left(\mathbf{x}_t\right)= \begin{cases}0, & b_t \mathbf{x}_t^{\top} \mathbf{a}_t>1 \\ -b_t \mathbf{a}_t, & \text { otherwise }\end{cases} \\ & \text{5: } \quad \mathbf{x}_{t+1}=\mathbf{x}_t-\eta_t \tilde{\nabla}_t \\ & \text{6: } \textbf{end for} \\ & \text{7: } \textbf{return }\; \overline{\mathbf{x}}_T \stackrel{\text { def }}{=} \frac{1}{T} \sum_{t=1}^T \mathbf{x}_t \end{aligned}\notag $$ 根据 strongly-convex SGD 的理论结果，如果我们想要得到期望误差界为 $\epsilon$，那么使用迭代步长 $\eta_t = O(1/t)$，估计的迭代次数略超过 $O(1/\epsilon)$ .

Computing Saddle Points

给定 $$ g(x, y) $$ $g$ 对 $x$ 凸，对 $y$ 凹，记 $V^\ast=\displaystyle\min _x \max _y g(x, y)=\max _y \min _x g(x, y)$ .

一个 $\epsilon$-saddle point 满足： $$ V^\ast-\epsilon \leq \min _x g(x, \bar{y}) \leq V^\ast \leq \max _y g(\bar{x}, y) \leq V^\ast+\epsilon $$

Regularization

与凸优化不同，在线凸优化的目标函数是 regret，这引出了一类新的算法叫做“Regularized Follow The Leader”(RFTL)。

对一个 OCO 问题，一个最直接的、选取下一个点的方法是 $$ \mathbf{x}_{t+1}=\underset{\mathbf{x} \in \mathcal{K}}{\arg \min } \sum_{\tau=1}^t f_\tau(\mathbf{x}) $$ 这种策略叫做 “ﬁctitious play”，也叫做 “Follow the Leader” (FTL)。

但是，这种简单的策略，很容易找到一个实例使得它的表现很差。

如，令 $\mathcal{K}=[-1, 1], f_1(x)=x/2, \, f_\tau (\tau =2, \dots, T)$ 在 $-x, x$ 中交替选取。这就使得： $$ \sum_{\tau=1}^t f_\tau(x)= \begin{cases}\frac{1}{2} x, & t \text { is odd } \\ -\frac{1}{2} x, & \text { otherwise }\end{cases} $$

$$ \|\mathbf{x}\|_{\mathbf{y}} \stackrel{\text { def }}{=}\|\mathbf{x}\| \nabla^2 R(\mathbf{y}) $$

Bregman divergence

定义关于连续可微的严格凸函数 $R$ 的 Bregman divergence $B_R(\mathbf{x} \| \mathbf{y})$ 为 $$ B_R(\mathbf{x} \| \mathbf{y})=R(\mathbf{x})-R(\mathbf{y})-\langle\nabla R(\mathbf{y}), \mathbf{x}-\mathbf{y} \rangle $$

例如：

当 $R(\mathbf{x}) = \|\mathbf{x}\|_2^2$ 时，$B_R(\mathbf{x} \| \mathbf{y}) = \| \mathbf{x} - \mathbf{y} \|_2^2$ 是欧式距离。
当 $R(\mathbf{x}) = \mathbf{x}^\top Q \mathbf{x}$ 时，$B_R(\mathbf{x} \| \mathbf{y}) = (\mathbf{x} - \mathbf{y})^\top Q(\mathbf{x} - \mathbf{y})$ 。
当 $R(\mathbf{x}) = \displaystyle\sum_i x_i \log x_i$ 时，$B_R(\mathbf{x} \| \mathbf{y})=D_{\text{KL}}(\mathbf{x} \| \mathbf{y})$ 是广义 KL 散度。

特别地，对任意概率分布 $\mathbf{x}, \mathbf{y}$，都有 $D_{\text{KL}}(\mathbf{x} \| \mathbf{y}) \geq \displaystyle\frac{1}{2} \| \mathbf{x} - \mathbf{y}\|_1^2$

因此，当 $R(\mathbf{x}) = \displaystyle\sum_i x_i \log x_i$ 时，$R(\mathbf{x})$ 是关于 $l_1$ norm 1-strongly convex 的。

当 $R(\mathbf{X}) = \text{tr}(\mathbf{X} \log \mathbf{X})$ 时，$B_R(\mathbf{X} \| \mathbf{Y})=\operatorname{tr}(\mathbf{X} \log \mathbf{X}-\mathbf{X} \log \mathbf{Y}-\mathbf{X}+\mathbf{Y})$，称为 von Neumann divergence, or quantum relative entropy.
当 $R(\mathbf{X}) = -\log \det \mathbf{X}$ 时，$B_R(\mathbf{X} \| \mathbf{Y}) = \operatorname{tr}\left(\mathbf{X} \mathbf{Y}^{-1}-\mathbf{I}\right)-\log \operatorname{det}\left(\mathbf{X} \mathbf{Y}^{-1}\right)$，称为 log-det divergence.

Bregman divergence 的几点性质：

Non-negativity. $B_R(\mathbf{x} \| \mathbf{y}) \geq 0$ 且 $B_R(\mathbf{x} \| \mathbf{y}) = 0 \,\Leftrightarrow \, \mathbf{x} = \mathbf{y}$，这源于 $R$ 的严格凸性。

Asymmetry. 一般来说，$B_R(\mathbf{x} \| \mathbf{y}) \neq B_R(\mathbf{y} \| \mathbf{x})$ 。

Convexity. $B_R(\mathbf{x} \| \mathbf{y})$ 对 $\mathbf{x}$ 是凸的，但对 $\mathbf{y}$ 不一定是凸的。进一步地，如果函数 $R$ 是 $\alpha$-强凸函数，那么 $B_R(\mathbf{x} \| \mathbf{y}) \geq \displaystyle\frac{\alpha}{2} \| \mathbf{x} - \mathbf{y}\|_2^2$

如果 $R$ 是二阶连续可微的函数，使用 Taylor 展开我们很容易知道 $$ B_R(\mathbf{x} \| \mathbf{y}) = \frac{1}{2} (\mathbf{x} - \mathbf{y})^T \nabla R(\mathbf{z}) (\mathbf{x} - \mathbf{y}), \quad \mathbf{z} \in [\mathbf{x}, \mathbf{y}] $$ $\mathbf{z}$ 是线段 $[\mathbf{x}, \mathbf{y}]$ 上的某点。

定义与矩阵相关的范数和对偶范数： $$ \|\mathbf{x}\|_A=\sqrt{\mathbf{x}^{\top} A \mathbf{x}} \, , \qquad \|\mathbf{x}\|_A^\ast=\|\mathbf{x}\|_{A^{-1}} $$

RFTL meta-algorithm

假定 $R$ 是一个强凸的函数。 $$ \begin{aligned} & \texttt{Algorithm 13 Regularized Follow The Leader} \\ & \text{1: Input: } \eta>0, \text{ regularization function } R, \text{ and a bounded, convex and closed set } \mathcal{K}. \\ & \text{2: Let } \mathbf{x}_1=\underset{\mathbf{x} \in \mathcal{K}}{\arg \min} \{R(\mathbf{x})\}. \\ & \text{3: } \textbf{for } t=1 \text{ to } T \textbf{ do}\\ & \text{4: } \quad \text{ Play } \mathbf{x}_t \text{ and observe cost } f_t\left(\mathbf{x}_t\right). \\ & \text{5: } \quad \text{ Update } \\ & \qquad \qquad \qquad\mathbf{x}_{t+1}=\underset{\mathbf{x} \in \mathcal{K}}{\arg \min }\left\{\eta \sum_{s=1}^t \nabla_s^{\top} \mathbf{x}+R(\mathbf{x})\right\} \\ & \text{6: } \textbf{end for} \end{aligned}\notag $$

Martin Zinkevich. Online convex programming and generalized inﬁnitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pages 928–936, 2003.

Online Convex Optimization