526互联

【笔记】在线凸优化 - Ch1. Introduction

发布时间 2023-09-09 11:54:28作者: zrkc

1.1 The Online Convex Optimization Setting

在线凸优化 Online convex optimization (OCO)，是一个带有博弈论、统计学习、凸优化的新玩意
给出如下问题叙述：

考虑一种博弈游戏，回合制，第 \(t\in [T]\) 回合，先由玩家从决策集 \({\cal K}\in \mathbb{R} ^n\) 中选择一个决策 \({\bf x} _t\)，然后对手从有界函数族 \(\cal F:{\cal K}\to \mathbb{R}\)（可能对抗地）选择一个函数 \(f _t\) 给玩家，玩家受到的损失 loss 为 \(f _t({\bf x} _t)\)（当然给函数有点理想了，现实情况可能就只知道这个决策点的值，但这样没法算 regret）
玩家的目的是尽可能缩小总损失与某个最优固定决策点的差值（而对手最大化它），并考虑这个差值关于 \(T\) 的增长函数
这个游戏为了正常运行，有两个最基本的限制：（待我根据具体情境再想想）

  1. 损失是有界的
  2. 决策集 \(\cal K\) 不一定有穷，但必须是有界的 (somehow bounded and/or structured)

对于凸情况，令 \({\cal K}\) 是有界凸集，\(\cal F\) 是凸函数集（总之两者都是有界且凸的）

一个 OCO 算法 \(\cal A\) 根据历史做出当前的决策 \({\bf x} _t={\cal A}(f _1,\dotsb, f _{t-1})\in \cal K\)
我们考虑用 regret 来衡量 \(\cal A\)，为该算法的总损失与一个最优的固定决策的差值、对于损失函数序列的上界：

\[\text{Regret} _T(\mathcal{A})=\sup _{\{f _1,\dotsb,f _T\}\sube \mathcal{F}} \left\{\sum _{t=1}^{T}f _t(\mathbf{x} _t)-\min _{\mathbf{x}\in\mathcal{K}}\sum _{t=1}^{T}f _t(\mathbf{x})\right\} \]

这个式子里，我们直接用 \(\sup\) 来刻画对手的决策，并限定了一个固定决策 \(\bf x\) 作为这组 \(\{f _1,\dotsb,f _T\}\) 下的最优解，作为我们的决策的参考

我们定义一个算法 \(\cal A\) 是好的，若 \(\text{Regret} _T\) 随 \(T\) 的增长函数是亚线性的 sublinear：\(\text{Regret} _T=o(T)\)，即 \(\forall c>0,\exist T _0,\forall T\ge T _0, 0\le \text{Regret} _T < c\cdot T\)

考虑一个平凡的算法：决策始终不变，记为 \({\bf x} ^*\)，取 \(f _t\) 始终为 \({\bf x} ^*\) 与最低点的差最大的那个，记差为 \(d\)，则 regret \(=dT=O(T)\)；所以亚线性算是最低限度的要求了

此外，我们还需要关注算法给出决策的最坏时间复杂度

1.2 Examples of OCO

1.2.1 Prediction from expert advice

问题描述：
有 \(N\) 个专家，\(T\) 个回合，每回合专家们给出自己的建议决策，玩家决定选择专家 \(i\) 后，会获得对手给出的专家们的损失向量 \({\bf g} _t\in \bf [0,1]\)，而玩家受到和专家 \(i\) 相同的损失 \({\bf g} _t(i)\)
决策集可以为确定性的 \({\cal K}=[N]\)；或者为以某一个分布 \(\bf x\) 选择专家，即 \({\cal K}=\{{\bf x}\in \mathbb{R} ^n, \sum _i {\bf x} _i = 1,{\bf x\ge 0}\}\)，从而损失为 \(f _t({\bf x})={\bf g} _t'{\bf x}\)

Discrete losses case

我们先考虑加一些条件：每回合，赋予每个专家所谓“决策”以实际意义，为仅有两种选择 \(A,B\)，两者一对一错，而损失定义为对 0 错 1（实际上我们可以蛮不讲理地赋予专家损失，而不依赖于所谓决策的实际意义，毕竟我们的目的只是缩小与最优专家的差距）
可以意识到，令决策集为确定性的并不是一个好主意，因为对手可以始终确定地宣布我们的决策是错的；我们可以考虑决策为分布
有定理：

Th. Bounds for deterministic and randomized algorithms, discrete losses case
令 \(\epsilon\in (0,1/2)\)，假设最好的专家的错误次数为 \(L\)，则：

  1. 存在一个确定性算法，错误次数小等于 \(2(1+\epsilon)L+\frac{2\log N}{\epsilon}\)
  2. 存在一个随机性算法，期望错误次数小等于 \((1+\epsilon)L+\frac{\log N}{\epsilon}\)

思路：考虑 regret 式子，在某一回合若某个专家被狠狠惩罚了，那他更难在最后成为最优决策点，因此接下来我们会减少跟随这个专家的概率，可以用降低权值刻画之

确定性算法证明：weighted majority (WM)
定义专家 \(i\) 在回合 \(t\) 的权值为 \(W _t(i)\)，\(W _1(i)=1\)
第 \(t\) 回合，将选 \(A,B\) 的专家划为 \(S _t(A), S _t(B)\) 集合，若 \(\sum _{i\in S _t(A)}W _t(i)\ge \sum _{i\in S _t(B)}W _t(i)\) 则选 \(A\)，否则选 \(B\)
选完后获知每个专家是否正确，若专家 \(i\) 正确则权值不变，否则降低权值 \(W _{t+1}(i)=W _t(i)(1-\epsilon)\)
分析算法（套路）：
定义 \(\Phi _t=\sum _i W _t(i),\Phi _1=N\)，定义 \(M _t\) 为算法前 \(t\) 回合的错误次数，\(M _t(i)\) 为专家 \(i\) 的错误次数
首先，每次算法犯错，总有 \(\Phi _{t+1}\le \Phi _{t}(\frac{1}{2}+\frac{1}{2}(1-\epsilon))=\Phi _{t}(1-\frac{\epsilon}{2})\)，故 \(\Phi _{T+1}\le N(1-\frac{\epsilon}{2}) ^{M _T}\)
其次，对每个专家 \(i\)，权值 \(W _{T+1}(i)=(1-\epsilon) ^{M _T(i)}\)
最后，由于 \(W _{T+1}(i)\le \Phi _{T+1}\)，代入上式，取 \(\log\) 并运用 \(-x-x ^2\le \log(1-x)\le -x\) 放缩，最后得

\[M _T\le 2(1+\epsilon)M _T(i)+\frac{2\log N}{\epsilon}\quad,i\in [N] \]

随机性算法证明：Randomized weighted majority (RWM)
作为 WM 的随机版本，\(t\) 回合取 \({\bf x} _t\)，使得 \({\bf x} _t(i)= W _t(i)/\sum _j W _t(j)\)
定义指示变量 \(m _t=M _t-M _{t-1}, m _t(i)=M _t(i)-M _{t-1}(i)\)，则 \(W _{t+1}(i)= W _{t}(i)(1-\epsilon m _t(i))\)；则：

\[\begin{aligned}\Phi _{t+1}&=\sum _{i=1} ^N W _t(i)(1-\epsilon m _t(i)) &;\text{套路，指示变量 $m$ 方便下手}\\ &= \Phi _t(1-\epsilon \sum _{i=1} ^N {\bf x} _t(i)m _t(i)) &;\text{套路，提出 $\Phi _t$ 引入 ${\bf x} _t$} \\ &= \Phi _t(1-\epsilon \mathbb{E}[m _t]) \\ &\le \Phi _t \exp \left(-\epsilon \mathbb{E}[m _t]\right) &;\text{套路，底放到幂，期望求和} \\ \Phi _{T+1}&\le N \exp(-\epsilon\mathbb{E}[M _T])\end{aligned} \]

另一方面，\(W _{T+1}(i)=(1-\epsilon) ^{M _T(i)}\le \Phi _{T+1}\)，放缩得

\[M _T\le (1+\epsilon)M _T(i)+\frac{\log N}{\epsilon}\quad,i\in [N] \]

General case

现在回到一般的连续情况，假设每回合专家受到损失 \({\boldsymbol{l}} _t\in \bf [0,1]\)，给出 Hedge 算法：

Th. Hedge
定义权值惩罚为 \(W _{t+1}(i)= W _t(i)e ^{-\epsilon {\boldsymbol{l}} _t(i)}\)，也就是乘以 \([e ^{-\epsilon},1]\)；依然取 \({\bf x} _t(i)= W _t(i)/\sum _j W _t(j)\)，则总损失 \(\mathbb{E}[M _T]\) 满足：

\[\mathbb{E}[M _T]=\sum _{t=1} ^T {\bf x} _t'{\boldsymbol{l}} _t\le \sum _{t=1} ^T{\boldsymbol{l}} _t(i)+\epsilon \sum _{t=1} ^T {\bf x} _t'{\boldsymbol{l}} ^2 _t + \frac{\log N}{\epsilon}\quad,i\in[N] \]

其中 \({\boldsymbol{l}} ^2 _t(i)={\boldsymbol{l}} _t(i) ^2\)

证明

\[\begin{aligned} \Phi _{t+1} &= \sum _{i=1} ^{N} W _t(i)\exp(-\epsilon {\boldsymbol{l}} _t(i)) \\ &= \Phi _t \sum _{i=1} ^{N} {\bf x} _t(i)\exp(-\epsilon {\boldsymbol{l}} _t(i)) &;\text{提出 $\Phi _t$ 引入 ${\bf x} _t$} \\ &\le \Phi _t \sum _{i=1} ^{N} {\bf x} _t(i) (1-\epsilon {\boldsymbol{l}} _t(i)+\epsilon ^2 {\boldsymbol{l}} ^2 _t(i))&;\text{幂放到底，从而点乘} \\ &= \Phi _t (1-\epsilon {\bf x} _t' {\boldsymbol{l}} _t +\epsilon ^2 {\bf x} _t' {\boldsymbol{l}} ^2 _t) \\ &\le \Phi _t\exp(-\epsilon {\bf x} _t' {\boldsymbol{l}} _t +\epsilon ^2 {\bf x} _t' {\boldsymbol{l}} ^2 _t) &;\text{底放到幂，期望求和} \\ \Phi _{T+1}&\le N \exp(-\epsilon\Sigma _{t=1} ^T {\bf x} _t' {\boldsymbol{l}} _t +\epsilon ^2 \Sigma _{t=1} ^T {\bf x} _t' {\boldsymbol{l}} ^2 _t) \end{aligned} \]

另一方面，\(W _{T+1}(i)=\exp(-\epsilon \sum _{t=1} ^T {\boldsymbol{l}} _t(i))\le \Phi _{T+1}\)，放缩得证
但是这个放缩 \(e ^{-x}\le 1-x+x ^2,x\ge 0\) 也不漂亮...