本文研究带复杂约束条件下在线凸优化问题,提出了一种基于镜像投影算法的新算法,可以在任何范数空间中实现低后悔和低约束违反度。
Jun, 2020
本文研究在线分配问题,涉及凹收益函数和资源限制,是收益管理和在线广告中的中心问题。通过在线镜像下降,我们提出了一种通用的算法类,可以实现次线性期望遗憾,同时也讨论了这种算法在重复拍卖中的应用。
Feb, 2020
本文提出了基于近似镜像下降的一类在线分布式优化算法,以 Bregman 距离为测量函数,包括欧几里得距离作为特例,考虑两种标准信息反馈模型,并通过在线分布式正则化线性回归问题的仿真结果验证了算法的性能。
Apr, 2020
本文研究带随机约束的在线凸优化问题,提出了一种算法,能够达到预期和高概率的收益掉队和约束违反值等性能保证,并在真实数据中心调度问题上进行了实验验证。
Aug, 2017
本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸 - 凹优化问题,提出了一种有效的算法,可以实现收敛性较好的结果。同时,本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
Nov, 2011
对于一般的凸在线学习问题,我们证明镜像下降法总是可以实现(几乎)最优的遗憾保证。
Jul, 2011
本文提出了一种新的分布式在线优化算法,旨在协同解决网络遗憾和累积约束违规等问题,可以适用于多个代理在有限的回合中进行最小化操作,具有一定的抗干扰能力和优化效果。
May, 2023
本文研究一种在线优化过程,其中目标函数不是凸函数(也不是凹函数),而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体,它可以访问目标函数的全梯度,并证明它对未来最佳可行解的(1-1/e)- 近似具有 O(T 的平方根)的遗憾界。对于只能获得梯度的无偏估计的情况,我们还提出了在线随机梯度上升算法,并证明它也具有 O(T 的平方根)的遗憾界,但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数,并证明相同的次线性遗憾界。最后,在几个问题实例上演示了算法的效率,包括非凸 / 非凹二次规划,子模集函数的多线性扩展和 D - 最佳设计。
Feb, 2018
使用先进的证明技术和 Zinkevich-style 动态遗憾最小化框架,本研究提出了一个强适应的在线学习算法,其总变化控制下的动态遗憾为 O (n^(1/3)*C_n^(2/3)),并且可以扩展到局部自适应非参数回归问题中。
Apr, 2021
该论文探讨了基于在线凸优化的强化学习的新框架,特别是镜像下降及相关算法,提出了一种新的类似于梯度下降的迭代方法。其中,基于不同 Bregman 散度的抛物线梯度强化学习法比常规 TD 学习更为普适。还提出了一种新型的稀疏镜像下降强化学习方法,相比之前基于二阶矩阵方法的方法,在寻找一个 l1 正则化 Bellman 方程的稀疏不动点时具有显著的计算优势。
Oct, 2012