顶会包装黑话揭秘，深度学习科研包装神器—Regret Bound从入门到精通

这篇文章我来分析一个我发现的有趣的现象。好多论文都爱推导“Regret Bound”

前两天刷到这个文章

本科生开发AI新算法媲美SGD、Adam，北大95后学霸：这是我第一次研究优化方法

https://zhuanlan.zhihu.com/p/57915596

我们看看大学霸怎么做的（ADAPTIVE GRADIENT METHODS WITH DYNAMIC BOUND OF LEARNING RATE ）

再找一篇量化领域的牛X工作

“Towards Unified INT8 Training for Convolutional Neural Network ”用int8全流程训练神经网络

是不是感觉很相似？

你再去翻一翻顶会的很多论文，这个东西经常出现。已经成为一种标准的学术包装的工具。

也许在一些大组已经广为流传，互联网上没多少人注意到。

看起来很吓人，然而推导并不难。完全可以流水线化。

1 初探 Regret

举一个简单的例子

小明每天都在炒股

但问题是你没法预知未来。你今天选了 A 股，结果 B 股暴涨，你就会说：“我真后悔没买 B！
数学上，后悔 就是：
你实际赚的钱 vs 如果你一直买“最赚钱的那只股”，能赚多少钱的差距
我们把这个差距叫做 Regret（后悔值）。

稍微嵌入一点数学公式可以表示成这样

你每天做一个决策  当天的＂损失＂是  如果你一直用＂最优策略＂  ，每天的损失是   那么，经过   天后，你的总 Regret 是：

最后的推导结果应该是，看到Rt的增长究竟是O(n^2)还是O(n)或者是O( sqrt(n) )

因为我们控制不了每次的决策都落在最优上。因此只能考察“增长”的时间复杂度

2 Regret Bound流水线

这里用optimization举例子

Step1：先写一个＂能量函数＂ 最常用的是欧几里得距离  然后我们看它怎么变化： 这叫＂递推关系＂

Step2 ：代入优化算法的更新规则 比如你用的是   ：

代入上式：

整理一下：

Step3：利用凸性 如果   是凸函数，就有

也就是

Step4 ：结合上面两步 从递推式：

代回去：

移项

Step5 ：对   到   求和右边 ：

所以：

Step6：假设学习率和梯度有界 假设  （Lipschitz连续） 假设  假设  （凸优化标准结论） 代入：

所以：

得到RegretBound：

这就是一个标准的   RegretBound！

在使用梯度下降，并且给一个这样的界。此时是根号的复杂度。（最优学习率上界）

3 天才本科生的Regret Bound推导流程

论文：ADAPTIVE GRADIENT METHODS WITH DYNAMIC BOUND OF LEARNING RATE

我们要证明论文的核心公式

先说一下这个adabound算法的流程

我们可以注意到，整个算法首先1和2就是标准的Adam操作。然后3是一个clip，4是一个学习率调度。

第 5 步。这个投影操作定义为：

这可以简写为：

其中   。

其实我写到这里突然想到。我们的很多二阶方法。其实都是在对学习率缩放。在fisher使用对角近似这就是Adam。本质上都是对不同方向的学习率投影（缩放）。

对于这个投影操作，如果Q是单位矩阵，这就是欧几里得距离。

接下来我们讨论论文中的推导过程

以下全部用图片展示。知乎的公式太难用了

Done

感谢阅读，祝我们每个人都能学会包装，“水”出更多的论文！

公众号后台回复“数据集”获取100+深度学习各方向资源整理