Mirror Descent (Bubeck 1-9)

请忽略这部分内容，它非常凌乱，但还是放在这里。

From GPT:

镜像下降法（Mirror Descent）是一种优化算法，它可以被视为在对偶空间（dual space）进行的梯度下降。要理解这一点，可以从以下几个方面来解释：

1. 基本概念

在传统的梯度下降法中，我们直接在原始空间（primal space）更新变量，以最小化目标函数。假设我们的目标函数是 (f(x))，那么梯度下降的更新规则为：

$ x_{t+1} = x_t - \eta \nabla f(x_t) $

其中，(\eta) 是学习率。

2. 对偶空间

镜像下降法引入了一个凸函数 ( \psi(x) )，称为“镜像函数”或“规范化函数”（potential function），它是强凸的。这个函数定义了一个从原始空间到对偶空间的映射：

$\nabla \psi(x): \mathbb{R}^n \rightarrow \mathbb{R}^n $

镜像下降法在对偶空间中进行优化，然后映射回原始空间。

3. 镜像下降的步骤

镜像下降法的更新步骤如下：

1. 计算梯度： 在原始空间计算目标函数的梯度 ( \nabla f(x_t) )。
2. 映射到对偶空间： 使用镜像函数 ( \psi(x) ) 将当前点 ( x_t ) 映射到对偶空间，即计算 ( \nabla \psi(x_t) )。

3. 在对偶空间更新： 在对偶空间进行梯度下降更新：

   $ y_{t+1} = \nabla \psi(x_t) - \eta \nabla f(x_t) $

4. 映射回原始空间： 使用镜像函数的对偶映射将更新后的点 ( y_{t+1} ) 映射回原始空间：

   $ x{t+1} = (\nabla \psi)^{-1}(y{t+1}) $

4. 理解为对偶空间的梯度下降

从以上步骤可以看出，镜像下降法首先通过镜像函数将原始空间中的点映射到对偶空间，然后在对偶空间中执行梯度下降更新，最后再映射回原始空间。因此，可以理解为镜像下降法是在对偶空间中进行的梯度下降。

---

但是这个算法好像能用到online learning里？？？

lecture23-draft.pdf (wisc.edu)

CS880的笔记。

---

Chapter1

lemma2

如果有

$$K=\{x:\forall j\in [m],a_j\cdot x\le b_j\}\\$$

那么有

$$N_{K}(x)=\set{\sum_{j,a_j\cdot x=b_j}\lambda_j a_j,\lambda_j\ge 0,\forall j\in [m]}\\$$

KKT这些东西全忘了

这里重新解释两个概念(参考文献)，首先切锥 $T_K(x)$ 定义为集合 $K$ 在点 $x$ 处的全体切向量构成的集合（也就是到达 $x$ 的路径序列最后的方向的极限），那么法锥 normal cone 定义为，对于给定的 $x$，如果一致地存在一个趋向于 $z$ 的序列 $z_k$ 和一个趋向于 $x$ 的序列 $x_k$，使得 $z_k \in T_C(x_k)^$，那么 $z$ 称为法向量，他们的集体叫做法锥。如果有 $N_C(x)=T_C(x)^$，我们叫做 $C$ 在 $x$ 是正则的。

normal cone consists of all the directions that would take you out of $K$.

如果 $S$ 是n维欧氏空间中的非空集合，那么 $N_S(x)={z\in R^n\mid \left \le 0,y \in T_S(x)}$

如果 $S$ 是凸集，法锥可以表示为 $N_S(x)={z\in R^n\mid \left \le 0,y\in S}$

证明考虑两个角度，第一是 右边 的任何一个元素都在 左边

• $$\sum_{j,a_j\cdot x=b_j} \lambda_{j} a_j\cdot (y-x) =\sum_{j}\lambda_j (a_j\cdot y-b_j) \le 0$$

第二是左边的任何一个元素都在右边

• 假设存在一个左边的元素不在右边，所以存在一个平面能分开这个元素和 $a_j$ 张成的空间，$w\cdot \theta=1,w\cdot p <1$ 也就是 $w \cdot p\le 0$，这里 $p$ 是 $\sum \lambda_ja_j$ 的一个。所以选取足够小的 $\epsilon$，$x+\epsilon w \in K,\epsilon w \in K$, and $\epsilon w$ 与 $\theta$ 正相关。这和它在左边这个集合矛盾。

但这是怎么想出来的，不太明白

总结：半平面的交的集合，它的法锥是它现在恰好在的那些边上的法向量的线性组合（也挺合理，毕竟半平面交是凸的）

---

Constraint do not matter

$$x_{k+1}=x_k-\eta \nabla f(x_k)$$

Lemma3: Project only make it better

具体根据之前的推导我们可以知道一个结论

$$\sum_{t=1}^T g_t \cdot (x_t-x^*) = \frac{||x^*-x_1||^2-||x^*-x_{T+1}||^2}{2\eta}+\frac{\eta}{2}\sum_{t=1}^T ||g_t||^2_2$$

利用 $||a||^2-||a-b||^2=2ab-b^2$，取 $a=x^*-xT,b=x{T+1}-x_T$

我们把前半部分叫做range，后半部分叫做variance

如果有 $E[g_t\mid part]=\nabla f(x_t)$，那它就是一个SGD。

我们直接带入（选择optimal $\eta$）就会发现

$$E[f(x_t)-f(x^*)]\le \frac{||x^*-x_1|| B}{\sqrt T}$$

where $B = \max _t E[||g_t||^2]$

First miracle: Robust 每一步如果有噪声，对总的没怎么影响。

如果有noise，或者叫bias，$\epsilon$-fraction也是最后期望加了个一个epsilon

$$E[f(x_t)-f(x^*)]\le \frac{||x^*-x_1|| B}{\sqrt T}+\epsilon$$

---

Chapter2

regret against $f_1,…f_T$ of sequence of convex function.

$$\frac{1}{T}\sum_{t=1}^T(f_t(x_t)-f_t(x^*)) \le \frac{1}{\sqrt T}$$

A first non-Euclidean setting

• prediction with expert advice.

第一种方法：

在 $ft(p)=l_t \cdot p$ 上使用GD, with $K=\Delta _n={p\in R+^m\mid \sum p_i=1}$, $\nabla f_t(p)=l_t$

那么这时候如果用之前的分析方法，gradient $\nabla f_t(p)=l_t$,似乎和dimension 有关，但是我们之后会说这个和dimension无关。

$$\sum_{t=1}^T l_t\cdot p_t-l_t\cdot q \le \frac{1}{2\eta} + \frac{\eta}{2} Tn \le \sqrt {Tn}$$

这个问题中， $\sqrt {Tn}$ 其实可以改进到 $\sqrt{T\log n}$，用别的方法，这个是因为GD没有利用上问题的好的性质：这个问题的OPT是sparse的。

MWU

我们之后会说这只是MD的一种特例

如果犯错则 $wt=(1-\eta)w{t-1}$ ，否则 $wt=w{t-1}$，然后 $p_t=\frac{w_t}{||w_t||_1}$

经典机器学习算法sigh

定义

$$L_T=\sum_{t=1}^T l_t \cdot p_t\\ L^*=\min_{q\in\Delta_n} \sum_{t=1}^T l_t \cdot q$$ $$L_T-L^* \le \eta L^*+\frac{\log n}{\eta} \le C\sqrt{T\log n}$$

选的势能函数是 $||w_t||_1$ 这个potential函数。

$$||w_{t+1}||_1 =||w_t||_1-\eta \cdot l_t \cdot w_t=(||w_t||_1)(1-\eta l_tp_t)\\ \le ||w_t||_1 e^{-\eta l_t p_t}\le ne^{\eta L_T}$$

所以这是一个upperbound，我们考虑还有一个lowerbound

然后 $L^=w_{T}(i^)\le ||w_T||_1$。

注意看，这里已经是optimal了。

---

一个更加principal的方式导出这个算法

$$f(x+dx)\approx f(x)+\left< \text{grad }f(x), dx\right>_X$$

这个 $\left<\cdot \mid \cdot \right> $ 可以当成 $\nabla ^2\Phi(x)[\cdot \mid \cdot ]$

所以这就控制了这个速度，就好像有两个维度的时候你可以控制其中一个维度步伐大一点其中一个维度步伐小一点，但总而言之，比如你在一个凸集中找最优点，可以在边界的时候慢一点平时快一点。

$$x_{t+1}=x_t-\eta \nabla ^2 \Phi(x_t)^{-1} g_t$$

这里的 $\Phi$ 是一个fixed convex function。

问题在于，你怎么去分析这个的复杂度，我的potential是什么呢？

Miracle：$D_\Phi$ is a potential，D是bregman divergence。79年最早提出MD的时候形式定义成这样然后就能得到一个potential。[Neminovski79]

为什么EG是一种MD

$$x_{t+1} = \arg\min_{x \in \mathcal{C}} \left\{ \langle \nabla f(x_t), x \rangle + \frac{1}{\eta} B_{\Phi}(x, x_t) \right\}$$ $$B_{\Phi}(x, y) = \Phi(x) - \Phi(y) - \langle \nabla \Phi(y), x - y \rangle$$

definition space and corresponding mirror map

$$\Delta_n = \{x \in \mathbb{R}^n: x_i \geq 0, \sum_{i=1}^n x_i = 1\}$$ $$\Phi(x) = \sum_{i=1}^n x_i \log x_i$$ $$\nabla \Phi(x) = \left[1 + \log x_1, 1 + \log x_2, ..., 1 + \log x_n\right]$$ $$B_{\Phi}(x, y) = \sum_{i=1}^n x_i \log x_i - \sum_{i=1}^n y_i \log y_i - \sum_{i=1}^n (1 + \log y_i)(x_i - y_i)\\ B_{\Phi}(x, y) = \sum_{i=1}^n x_i \log \frac{x_i}{y_i}$$ $$x_{t+1} = \arg\min_{x \in \Delta_n} \left\{ \langle \nabla f(x_t), x \rangle + \frac{1}{\eta} \sum_{i=1}^n x_i \log \frac{x_i}{x_{ti}} \right\}$$ $$L(x, \lambda) = \langle \nabla f(x_t), x \rangle + \frac{1}{\eta} \sum_{i=1}^n x_i \log \frac{x_i}{x_{ti}} + \lambda \left(\sum_{i=1}^n x_i - 1\right)\\ \frac{\partial L}{\partial x_i} = \nabla f_{ti} + \frac{1}{\eta} \left(1 + \log \frac{x_i}{x_{ti}}\right) + \lambda = 0\\ x_{t+1,i} = x_{ti} \exp(-\eta (\nabla f_{ti} + \lambda))$$

得到更新公式

$$x_{t+1,i} = \frac{x_{ti} \exp(-\eta g_{ti})}{\sum_j x_{tj} \exp(-\eta g_{tj})}$$

我想要的不等式是怎么来的，就是 no regret 和 mirror descent 有什么关联。

lecture23-draft.pdf (wisc.edu)

Continuoustune mirror descent

如果 $g:R_+\to R^n$ 是一个smooth vector filed

$$\frac{d}{dt}x(t)=-\nabla ^2 \Phi(x(t))^{-1}(\eta g(t)+\lambda (t))$$

where

$$\lambda(t) \in N_k(x(t)),x(t)\in K$$

换句话说

$$x(t+dt)=\arg \min_{x\in K} \eta g(t)\cdot x + \frac{1}{2}||x-x(t)||^2_{x_{(t)}}$$

---

回到定义

$$D_\Phi(y,x(t))=\Phi(y)-\Phi(x(t))- \nabla \Phi(x(t))\cdot (y-x(t))$$

带入

$$\frac{d}{dt}D_\Phi=-\nabla \Phi(x(t))\cdot \frac{d}{dt}x(t)-\nabla ^2 \Phi(x(t))\frac{d}{dt}x(t)\cdot (y-x(y))\\ -\nabla \Phi(x(t))\cdot (-\frac{d}{dt}x(t))\\ =-\nabla ^2 \Phi(x(t))\frac{d}{dt}x(t)\cdot (y-x(t))$$

另一方面，利用normal cone的性质，

$$\frac{d}{dt}D\Phi=(\eta g(t)+\lambda(t))\cdot (y-x(t))\\ \le \eta g(t)\cdot (y-x(t))$$

积分后得到

$$\int_{0}^T g(t)\cdot (x(t)-y) \le \frac{D_\Phi(y,x(t))}{\eta}$$

Discrete time version：

$$\frac{d}{dt}x(t)=-\nabla ^2 \Phi(x(t))^{-1}g(t)\\ \implies \nabla^2 \Phi(x(t)) \frac{d}{dt} x(t)=-g(t)$$

GD的 $g(t)$ 是一个dual 上做的，但是GD是在 primal space 上对每个元素做。但是对于MD（离散时间的形式是）

$$\nabla \Phi(x_{t+1})=\nabla \Phi(x_t) - \eta g(t)$$

你会发现这里都是在dual space上做的。Doing the update in the dual, and then mapping them into the promal point.

Chapter3

MTS: Metrical task systems

Let $X$ be finite metrice space, the player maintains a state $\rho_t \in X$

At time $t+1$, we receive a task function. $C{t+1}:X\to R+$ and move to $\rho_{t+1}$.

movement cost: $dist(\rhot,\rho{t+1})$; service cost: $c{t+1}(\rho{t+1})$

这个建模可以应对好多好多的问题。（比如电脑什么时候休眠的问题）。

这个和之前的问题 的差别还包括，我是先看到cost function，然后再有我的decision。

可以类似在线算法的方式定义离线最优算法和竞争比

就是 $ALG/OPT$ 。

人们认为的定理是，对于 $\forall X, |X|=m$ 存在一个算法的竞争比是 $O(\log n)$

所以这个 $\log n$ 和 $T\log n$ 和entropy的 $\log n$ 有什么差别呢——

18年的结果是，[B Cohen, J Lee, YTLee 18] 证明了 $O(\log ^2n)$

以及 $\Omega(\frac{\log n}{\log \log n})$ 是必要的，如果我们不知道关于问题的特殊性质。

结论：deterministic algorithm不行，下面证明deterministic的问题，一定是 $\Omega(n),O(n)$

证明一个上界：假设有一个算法，每次从一个没有mark的状态出发，一直呆着等到代价超过1，然后移动到另一个节点。一旦所有节点都标记了，我的算法代价不超过2n，但是OPT大于等于1。 （没有特别理解）

证明一个下界：我可以让每个位置 $c{t+1}(e{t}=\infty)$ ，也就是每次都把这个人从当前的位置赶出去，这里我显然需要转移，而且是被迫转移，总的转移复杂度是 $n$，因为OPT能看到未来的情况，所以OPT<=1。（确实，OPT其实看到所有的话可以不动或者最多动一次，而我要动n次）。

随机的话：

如果让 $f(n)$ 表示d当 $n$ 个state 都被mark的时候，我期望的移动此时。$f(n)=1/n+f(n-1)$，$f(n)=\log n$。

所以最坏的人对我来说，只能是：每次hit一个randomly的location。那么我的cost在n次之后期望上是1，但是OPT根据COUPON COLLETE的结论，应该要 $n\log n$ 次。

mirror descent 在 weighted 的情况下的应用：

类似于weighted coupon collector。

Lemma 对于discrete time的cost function和continuous time的cost function，连续时间的保证能够迁移到离散时间的保证。

证明：使用water filling的方法，只要让离散时间的状态cost小于等于连续时间的状态cost。离散情况的移动cost小于等于连续情况的移动cost。但是，连续时间的OPT小于等于离散时间的OPT，（这个证明还是没看懂，pass先）

SC表示service cost，$SC=\int c(t)\cdot x(t) dt$。

MC表示Movement cost，$MC=\int ||\frac{d}{dt} x(t)||dt$ 。

---

Mirror Descent Flow 在 $\Delta _n$ 上。

$$\frac{d}{dt} x(y)=-\nabla ^2 \phi(x(t))^{-1}(c(t)+\lambda(t))\\ \lambda(t)\in N_k(x(t)), x(t)\in K$$

注意MD的性质， Miracle 2

$$\frac{d}{dt} D_\phi(y,x(t))\le \eta \cdot c(t)\cdot (y-x(t))$$

这个可以理解成，比如最优的在 $y$，但是我在 $x$，

Miracle 3

$$\frac{d}{dt} D_\phi(y(t),x) \le \text{?some movement of y(t) = }||\dot y(t)||$$

这个可以这么理解，左边的展开其实就是

$$(\nabla \phi(y(t))-\nabla \phi(x)) \cdot \dot y(t)$$

假设 $L = \sup{z\in K}||\nabla \phi(z)||*$，也就是对偶范数最大的那个地方的梯度，两倍其实就能bound住差

那么

$$(\nabla \phi(y(t))-\nabla \phi(x)) \cdot \dot y(t) \le 2 L\cdot ||\dot y(t)||$$

所以合起来就是

$$0\le D_\phi(y(T),x(T))-D_\phi(x(0),y(0)) \le \eta (SCOPT-SCALG)+2L(MCOPT)$$

take $\eta=2L$ , then $SCALG \le OPT$

也没懂

---

Chapter4

一个独立的问题

如果对于两个空间 $X,Y$ 的度量，以及一个映射，使得

$$1 \le \frac{D_Y(f(A),f(B))}{D_X(A,B)} \le D$$

其中第一个等号严格成立，第二个等号期望上成立，那么就有（如果有 $\alpha$ 竞争比）

$$ALG_X\le ALG_Y\le \alpha OPT_Y \le \alpha D\cdot OPT_Y$$

一个定理

存在一个 $O(\log n)$ 的

一个引理

hierarchical partition lemma：任何一个度量空间，都存在一个随机的分割 $P_X$，使得所有的分割的元素的都比较小，小于等于 $\Delta$，使得对于所有 $x \in X$，任何标量 $r \ge \Delta/poly(n)$，都有

$$P(B(x,r) \text{is cut by $P_X$}) = O(\frac{r\log n}{\Delta})$$