Follow-the-Regularized-Leader

纯 FTL 每轮最小化历史损失，微小的新损失也可能让最优解在可行集两端跳动。强凸 $R$ 让累计目标具有曲率，相邻两轮 minimizer 的移动可由新梯度控制。在线性损失 $f_t(x)=⟨g_t,x⟩$ 下，必须把可行域也放进共轭。令 $\mathrm{\Psi }(x)=R(x)$（$x\in K$），域外取 $+\mathrm{\infty }$；也写作 $\mathrm{\Psi }=R+{\iota }_K$。若 $\mathrm{\Psi }$ 是有限维实空间上的 proper 闭凸函数，并相对所选范数为 $1$-强凸，则每个线性扰动有唯一极小点，共轭 ${\mathrm{\Psi }}^{\ast }$ 可微。最优性写为

这里使用的是约束延拓 $\mathrm{\Psi }$ 的凸共轭理路凸共轭与 Fenchel–Young 不等式Convex conjugate · Fenchel conjugate · Fenchel–Young inequality以线性函数的最佳配对代价定义共轭，并导出原变量与对偶变量间的基本不等式。。强凸性使 ${\mathrm{\Psi }}^{\ast }$ 相对对偶范数为 $1$-光滑；把它在 $-\eta G_{t-1}$ 处的二次上界沿时间求和，再用 Fenchel–Young 比较 $-\eta G_T$ 与 $u$，得到累计线性 regret

负熵给出指数权重 ​

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

正是Hedge理路指数权重与 HedgeHedge algorithm · exponential weights在全信息有界损失下按累计损失指数加权，并取得平方根级专家 regret。。这里约定 $0\log 0=0$，并将 $R$ 在单纯形外延拓为 $+\mathrm{\infty }$；对应共轭为 ${\mathrm{\Psi }}^{\ast }(y)=\log \sum _i{e}^{y_i}$，其梯度才是归一化的 softmax。在欧氏空间取二次正则器，则得到与梯度更新密切相关的形式。FTRL 因而是共同优化框架，不是把几种算法只按名字并列。

约束不能从这个式子中省略。例如 $K=[0,1]$、$R(x)=x^2/2$、$\eta =1$ 且累计梯度为 $-2$。若只取无约束二次函数的共轭梯度，会输出 $2\notin K$；对 $\mathrm{\Psi }$ 取共轭则输出约束极小点 $1$。

失败边界与静态对应 ​

没有正则器的 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 只能近似求解，优化误差必须额外累积，不能隐藏在静态正则目标中。