在线凸优化的广义方法
内容提要
该文综述在线凸优化研究，涵盖随机反馈下的bandit凸优化、风险规避、分布式联邦学习、长期约束及自适应正则化等方向，提出多种算法并给出遗憾界，填补随机与自适应环境间的空白。
延伸解读
随机反馈下的在线凸优化进展
文章指出，针对带有随机反馈的在线凸优化（bandit凸优化），通过将椭球法应用于在线学习，给出了第一个O(√T)遗憾界算法，并引入了离散凸几何中的新工具。这填补了随机反馈环境下高效算法的空白，为后续研究提供了理论基础。
分布式联邦在线优化的合作条件
在自适应对手的分布式在线优化中，若机器能获取一阶梯度信息，合作无益；但在零阶反馈（bandit）下，高维情况合作有益且可能实现线性加速。文章通过新算法给出了严格遗憾界，填补了联邦在线优化中随机与自适应环境间的差距。
风险规避与长期约束的算法创新
文章提出了风险规避在线凸优化的两种算法，其中结合椭球法和中心点装置的算法达到几乎最优遗憾界。对于长期约束问题，自适应在线梯度下降算法在损失和约束违规上分别达到O(T^{max{β,1-β}})和O(T^{1-β/2})的累积遗憾界，优于已有结果。
自适应正则化与无界域学习
文章提出根据已观察损失函数自适应选择正则化函数的算法，其遗憾界在最坏情况下最优，且对某些实际损失函数类别更优，无需预先知道问题结构。同时，文章还关注了算法参数调优和无界域上的学习，并介绍了非凸损失的处理方法。
Q&A
在线凸优化中，针对随机反馈的bandit问题，有什么突破性的算法？
通过将椭球法应用于在线学习，给出了第一个O(√T)-regret算法，并引入了离散凸几何中的新工具。
在分布式在线凸优化中，面对自适应对手时，合作是否有益？
当机器能访问一阶梯度信息时，合作没有益处；但在零阶反馈（bandit）且高维情况下，合作有益并可能带来线性加速。
风险规避的在线凸优化问题有哪些解决方法？
提出了两种算法：一种是易于实现的降落算法；另一种结合椭球法和中心点装置，达到几乎最优的后悔界。
如何处理具有长期约束的在线凸优化问题？
提出了一种适应性在线梯度下降算法，可以处理任意凸约束，在损失和约束违规方面分别具有O(T^max{β,1−β})和O(T^(1−β/2))的累积遗憾界，优于Mahdavi等（2012）的已知界。
在线凸优化中，自适应正则化算法有什么优势？
该算法根据观察到的损失函数自适应选择正则化函数，其遗憾界在最坏情况下最优，且对某些实际损失函数类别比现有界限好得多，无需事先了解问题结构。
在线随机线性优化中，只有一位信息被揭示时如何学习？
假定二元反馈来自对数模型，通过利用观测模型的特定结构，开发了一种高效的在线学习算法来最小化遗憾。
