Online Linear Optimization via Smoothing
Online Linear Optimization via Smoothing
复制标题
通过平滑进行在线线性优化
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Ambuj Tewari
中科院分区：
文献类型：
--
作者：
Jacob D. Abernethy;Chansoo Lee;Abhinav Sinha;Ambuj Tewari
我们提出了一种新的优化理论方法来分析跟随领导者风格的算法，特别是在使用扰动作为正则化工具的情况下。我们证明，向决策规则添加强凸惩罚函数和向数据添加随机扰动分别对应于确定性和随机平滑操作。我们在“跟随正则化领导者”和“跟随扰动领导者”之间建立了平滑属性的等价性。这种直觉导致了一种新的通用分析框架，该框架恢复并改进了通常称为“跟随扰动领导者”的算法类别的先前已知的遗憾界限。
We present a new optimization-theoretic approach to analyzing Follow-the-Leader style algorithms, particularly in the setting where perturbations are used as a tool for regularization. We show that adding a strongly convex penalty function to the decision rule and adding stochastic perturbations to data correspond to deterministic and stochastic smoothing operations, respectively. We establish an equivalence between “Follow the Regularized Leader” and “Follow the Perturbed Leader” up to the smoothness properties. This intuition leads to a new generic analysis framework that recovers and improves the previous known regret bounds of the class of algorithms commonly known as Follow the Perturbed Leader.