Homework 1
在在线优化设置中，玩家玩点$w_t \in W $，对手以非负函数$f_t$响应，并且玩家遭受$f_t(w_t)$的损失。 假设$W$是一个有界集合，并且每个$f_t$在$W$上有较低的界限。玩家在$T$轮之后的遗憾被定义为：
$$ \sum_{t = 1}^{T} f_t(w_t) - \min\limits_{w \in W} \sum_{t = 1}^{T} f_t(w) $$
遗憾的界限是函数$R(T)$，使得对于任何序列$f_1, …, f_T$它保持：
$$ \forall T \sum_{t = 1}^{T} f_t(w_t) - \min\limits_{w \in W} \sum_{t = 1}^{T} f_t(w) \leq R(T) $$
首先，证明我们可以在不失一般性的情况下假设每个$t$的$\min f_t(x) = 0$。
如果：
$$ f_t(w_t) = 0 \Rightarrow w_{t + 1} = w_t $$
在线优化算法是保守的。换句话说，保守算法只要不遭受任何损失就会保持同一点。设$A$为具有$R(T)$的后悔界限的在线优化算法。使用$A$定义具有相同后悔限制的保守在线优化算法$A’$.回想一下，如果对于$f$域中的任何$\alpha \in [0, 1]$和任何$x$和$x’$，$f(\alpha x + (1 - \alpha)x’) \leq \alpha f(x) + (1 - \alpha) f(x’)$则函数$f$是凸的。 令$f: R \mapsto R$为凸函数，并且令$g: R \mapsto R$为凸单调非递减函数。 证明组合物$g \circ f$是凸的$(g \circ f(x) \equiv g(f(x)))$
考虑在没有交易成本的市场中管理在线股票投资组合的问题。 假设市场有$n$个不同的股票，我们可以在每个交易日结束时改变我们的投资组合，并且在第$t$天结束时的$n$个股票的价格由向量$c_t$表示。 我们最初的财富是$\phi_0$，而我们在$t$之后的财富是$\phi_t$。 在每一轮中，我们播放分布向量$w_t \in W$（$W$是总和为1的非负向量的集合）。 也就是说，在第$t$轮，我们在股票$i$上投资$\phi_{t - 1}w_{t, i}$美元。
- 根据$w_1, …, w_t$和$c_0, c_1, …, c_t$写$\phi_t$
- 由固定概率向量$w$定义的不断重新平衡的投资组合（CRP）是一种每天重新平衡的投资策略，因此我们每天都将我们的财富$w_i$投资于股票$i$。 设$\phi_t^w$表示在第$t$天由$w$定义的CRP的财富。 根据$w$和$c_0, c_1, …, c_t$写$\phi_t^w$
- 在$T$轮之后将事后的最佳CRP定义为$\phi_T^* = max_w \phi_T^w$。 在$T$轮之后定义遗憾作为$log(\phi_T^* / \phi_T)$。表明最小化这种遗憾的定义是在课堂上讨论的在线凸优化框架的一个特例（提示：使用问题2来表明–$log(u \cdot v)$是凸的并且将投资组合管理问题写成在线凸优化问题）
Homework 2
- 加倍的把戏 你得到一个在线算法$A$保证$Regret \leq T^p$，对于某些$p \in (0, 1)$，但它有参数必须作为$T$的函数选择。使用这个算法作为黑盒子，我们将构造一个遗憾的算法 对所有$T$同时保留的绑定$O(T^p)$.特别是，我们将分析以下转换：
$\textbf{for}\ epoch\ m = 0, 1, 2, …\ \textbf{do}$
$\qquad Reset\ A\ with\ parameters\ chosen\ for\ T = 2^m$
$\qquad \textbf{for}\ rounds\ t = 2^m, …, 2^{m + 1} - 1\ \textbf{do}$
$\qquad \qquad Run\ A$
本质上，该算法最初猜测$T = 1$，当它观察到这个猜测太低时，它将它的初始猜测加倍并重新启动$A$.因此，这被称为“双重技巧”
要显示所需的遗憾，请考虑任何T，和- 表明对边界$1$到$T$的遗憾小于或等于时期$m = 0$到时期$m_T = [log_2(T)]$结束时的遗憾。 然后，使用$A$的遗憾绑定这些时代的累积遗憾
- 简化(a)的界限，表明它的上限是常数$T^p$的上限。提示：使用$x \neq 1$的事实:
$$ \sum\limits_{k = 0}^n x^k = \frac{x^{n + 1} - 1}{x - 1} $$
