在线镜像下降的普适性
本文研究具有随机约束的在线凸优化问题,提出了一种新的原始 - 对偶镜像下降算法,其可以在不需要 Slater 条件的情况下达到与先前的方法相似的性能并允许等式约束。
Aug, 2019
本文提出了基于近似镜像下降的一类在线分布式优化算法,以 Bregman 距离为测量函数,包括欧几里得距离作为特例,考虑两种标准信息反馈模型,并通过在线分布式正则化线性回归问题的仿真结果验证了算法的性能。
Apr, 2020
研究一种基于连续时间的在线优化策略族,证明其能够达到无遗憾学习。从传统的离散时间角度来看,这种方法可导出大量离散时间算法(包括一些经典遗憾分析算法)的无遗憾性质,并统一了许多经典的遗憾上界,得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。
Jan, 2014
本文提出了一种简单的方法,可以将两个具有不同遗憾保证的无参数在线学习算法结合起来得到一个新的算法,其遗憾值是两个算法中的最小值。此外,作者还提出了一种基于该方法的黑盒子算法,可以生成乐观的在线学习算法,并提供无拘束设定下的第一个乐观遗憾保证。
Feb, 2019
提供了乐观镜面下降算法的几个应用:将其用于线下优化中的镜像近端算法、扩展到 Holder 平滑函数、并将结果应用于鞍点问题;将其用于有限零和矩阵博弈中,为两个强耦合玩家提供最小化最大值均衡的渐进速率 O ((log T)/T);再考虑问题的部分信息版本并将结果应用于凸规划,展示了近似最大流问题的简单算法。
Nov, 2013
本文研究在线分配问题,涉及凹收益函数和资源限制,是收益管理和在线广告中的中心问题。通过在线镜像下降,我们提出了一种通用的算法类,可以实现次线性期望遗憾,同时也讨论了这种算法在重复拍卖中的应用。
Feb, 2020
本文介绍了在线学习的基本概念和现代在线凸优化的视角,并针对凸丢失,在欧几里得和非欧几里得环境中介绍了一阶和二阶算法。同时,还特别关注了算法参数调优和在无界域上的学习,并介绍了对非凸损失的处理方法和信息缺失的决策问题中的多臂赌博机问题。
Dec, 2019
研究使用镜像下降和熵正则化的方法在维度上实现对于一系列的一般化后的后悔情况的误差上界,其中包括了位移、自适应、折扣等等,并且得到了和权值分享方法的等价结果。研究同时提出了对于小的误差和参数的自适应调整等的改进。
Feb, 2012
该论文探讨了基于在线凸优化的强化学习的新框架,特别是镜像下降及相关算法,提出了一种新的类似于梯度下降的迭代方法。其中,基于不同 Bregman 散度的抛物线梯度强化学习法比常规 TD 学习更为普适。还提出了一种新型的稀疏镜像下降强化学习方法,相比之前基于二阶矩阵方法的方法,在寻找一个 l1 正则化 Bellman 方程的稀疏不动点时具有显著的计算优势。
Oct, 2012