Follow-the-Regularized-Leader

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

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

负熵给出指数权重 ​

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

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

失败边界与静态对应 ​

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

强凸正则器通过凸共轭公理库凸共轭与 Fenchel–Young 不等式Convex conjugate · Fenchel conjugate · Fenchel–Young inequality以线性函数的最佳配对代价定义共轭，并导出原变量与对偶变量间的基本不等式。把累计梯度映到稳定决策，并产生“初始正则代价加累计对偶梯度平方”的 regret 分解。平衡学习率即可恢复 $O(\sqrt{T})$ 界。

负熵给出 Hedge，二次正则器给出欧氏几何更新，其他 Legendre 正则器则适配不同域。若每轮 argmin 只能近似求解，优化误差必须额外累积，不能隐藏在静态正则目标中。