Follow-the-Regularized-Leader

定义 ​

给定凸决策集 $K$、正则器 $R$ 和学习率 $\eta >0$，FTRL 在第 $t$ 轮选择

$$x_t\in \arg \underset{x\in K}{min}\{\sum _{s=1}^{t-1}{f}_s(x)+\frac{1}{\eta }R(x)\}.$$

求和只到 $t-1$，因为 $f_t$ 尚未揭示。若把 $1/\eta$ 已写在正则项外，就不应又在 $R$ 内重复缩放。

为什么正则化能稳定 leader ​

纯 FTL 每轮最小化历史损失，微小的新损失也可能让最优解在可行集两端跳动。强凸 $R$ 让累计目标具有曲率，相邻两轮 minimizer 的移动可由新梯度控制。对线性损失 $f_t(x)=⟨g_t,x⟩$，最优性可写为

$$x_t=\mathrm{\nabla }{R}^{\ast }(-\eta G_{t-1}),G_{t-1}=\sum _{s<t}{g}_s,$$

其中 $R^{\ast }$ 是凸共轭公理库凸共轭与 Fenchel–Young 不等式Convex conjugate · Fenchel conjugate · Fenchel–Young inequality以线性函数的最佳配对代价定义共轭，并导出原变量与对偶变量间的基本不等式。。若 $R$ 相对某范数为 $1$-强凸，则 $R^{\ast }$ 的梯度相对对偶范数光滑，累计线性 regret 可控制为

$${\mathrm{Reg}}_T(u)\le \frac{R(u)-\underset{K}{min}R}{\eta }+\frac{\eta }{2}\sum _{t=1}^T\Vert g_t{\Vert }_{\ast }^2.$$

负熵给出指数权重 ​

在概率单纯形上取 $R(p)=\sum _i{p}_i\log p_i$，线性损失向量为 ${\ell }_t$。解一阶条件并归一化得到

$$p_{t,i}\propto \exp (-\eta \sum _{s<t}{\ell }_{s,i}),$$

正是Hedge公理库指数权重与 HedgeHedge algorithm · exponential weights在全信息有界损失下按累计损失指数加权，并取得平方根级专家 regret。。在欧氏空间取二次正则器，则得到与梯度更新密切相关的形式。FTRL 因而是共同优化框架，不是把几种算法只按名字并列。

失败边界与静态对应 ​

没有正则器的 FTL 可在线性 regret：在区间上令线性损失梯度交替并刻意使历史和在零附近翻转，leader 会不断选到下一轮不利端点。argmin 的存在和计算效率也不是 regret 定理自动提供的。正则化 ERM公理库正则化经验风险最小化regularized ERM · RERM在经验拟合项上加入结构惩罚，以显式控制解的复杂度与统计—优化权衡。在固定数据上最小化一次目标；FTRL 每轮只用过去损失重解累计目标，时间协议不同。

参考资料

• Elad Hazan, Introduction to Online Convex Optimization, 2016/2019.
• Shai Shalev-Shwartz, Online Learning and Online Convex Optimization, Foundations and Trends in Machine Learning, 2012.