本文提出了基于近似镜像下降的一类在线分布式优化算法,以 Bregman 距离为测量函数,包括欧几里得距离作为特例,考虑两种标准信息反馈模型,并通过在线分布式正则化线性回归问题的仿真结果验证了算法的性能。
Apr, 2020
对于一般的凸在线学习问题,我们证明镜像下降法总是可以实现(几乎)最优的遗憾保证。
Jul, 2011
在线学习不仅仅是记住一切。通过使用自适应在线学习中近期开发的技术重新审视折扣遗憾的经典概念,我们提出了一个能够优雅地在新数据到达时遗忘历史的关键算法,改进了传统的非自适应算法,即使用固定学习率的梯度下降算法。具体而言,我们的理论保证不需要任何除了凸性之外的结构假设,该算法在次优超参数调整时可以证明是鲁棒的。通过在线符合预测,我们进一步展示了这些好处,它是一个具有集合成员决策的下游在线学习任务。
Feb, 2024
本文设计并分析了一种不需要任何上限或下限的在线线性优化算法,实现了适应损失向量范数的缩放不变性,并且通过 FTRL 和 MD 元算法实现了最优遗憾,并为无界决策集开发了一种非真空遗憾绑定的自适应算法,并对基于 MD 的无标度算法在无界域上的下限进行了研究。
Jan, 2016
该论文探讨了基于在线凸优化的强化学习的新框架,特别是镜像下降及相关算法,提出了一种新的类似于梯度下降的迭代方法。其中,基于不同 Bregman 散度的抛物线梯度强化学习法比常规 TD 学习更为普适。还提出了一种新型的稀疏镜像下降强化学习方法,相比之前基于二阶矩阵方法的方法,在寻找一个 l1 正则化 Bellman 方程的稀疏不动点时具有显著的计算优势。
Oct, 2012
本文介绍了一种将常规优化算法转化为在线学习动态的方法,以解决具有多个局部极小值的给定训练目标的最小化,通过在线学习算法的遗憾界来获得隐式偏差率,并比较了梯度下降、镜像下降和最陡下降这三种不同的优化算法的隐式偏差率。
May, 2023
本文介绍了在线学习的基本概念和现代在线凸优化的视角,并针对凸丢失,在欧几里得和非欧几里得环境中介绍了一阶和二阶算法。同时,还特别关注了算法参数调优和在无界域上的学习,并介绍了对非凸损失的处理方法和信息缺失的决策问题中的多臂赌博机问题。
Dec, 2019
提供了乐观镜面下降算法的几个应用:将其用于线下优化中的镜像近端算法、扩展到 Holder 平滑函数、并将结果应用于鞍点问题;将其用于有限零和矩阵博弈中,为两个强耦合玩家提供最小化最大值均衡的渐进速率 O ((log T)/T);再考虑问题的部分信息版本并将结果应用于凸规划,展示了近似最大流问题的简单算法。
Nov, 2013
本文介绍了在学习增强的在线算法中使用回归技术来预测未来输入参数的方法,并在广义滑雪租赁、装箱问题、最小完成时间调度等一般在线搜索方案的背景下探讨了这种方法。通过在设计回归问题的损失函数中结合在线优化基准,我们显示了这种回归问题样本复杂度的近似上下界,并将我们的结果扩展到了不可知设置。
May, 2022
通过结合多个赌博机算法,创建一个主算法,它可以像单独运行的最优基础算法一样表现优秀。本文通过 Online Mirror Descent 和学习率算法,实现了更好地权衡探索和利用基础算法,达到了更好的拒绝界。这些结果可以应用于多种情况,如多臂赌博机、上下文赌博机和凸赌博机,并且提出了两种主要应用:第一种是在环境相对容易时,同时享有最坏情况的稳健性和最好的表现,第二种是在不同的先验参数或不同的损失结构下同时工作。
Dec, 2016