学习增强在线算法的最优韧性 - 一致性平衡
本文提出了一种新的模型来增强算法的预测能力,该模型要求算法具有形式上可学性和实例鲁棒性;通过构造在线可学习算法,为网络流量分配问题和受限指派最小化问题提供高质量的预测性能,并证明了这些预测对少量训练实例的数据具有鲁棒性。
Nov, 2020
如何在设计在线算法中最佳利用不确定性量化预测,以及如何利用更一般形式的不确定性量化,提出了基于在线学习的框架来在多实例场景中学习如何充分利用不确定性量化作出最佳决策。
Oct, 2023
本研究解决了学习增强的多选项滑雪租借问题,提出了最佳算法来匹配已知的下界,为随机算法提供了第一个非平凡的下界并呈现了一个改进的随机算法。
Dec, 2023
本文介绍了在学习增强的在线算法中使用回归技术来预测未来输入参数的方法,并在广义滑雪租赁、装箱问题、最小完成时间调度等一般在线搜索方案的背景下探讨了这种方法。通过在设计回归问题的损失函数中结合在线优化基准,我们显示了这种回归问题样本复杂度的近似上下界,并将我们的结果扩展到了不可知设置。
May, 2022
介绍了一种算法设计范例 —— 基于学习预测器的算法,将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度,在构建优美的预测器的同时,在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果,且提供了第一批基于学习理论的担保。
Feb, 2022
设计在线算法,利用机器学习预测,以超越最坏情况范例,解决各种实际相关在线问题(如调度、缓存、聚类、滑雪租赁等)。通过研究设计具备多个专家的在线算法,以超越静态最佳专家的贪心基准。在新的动态基准中提出了具有 O(log K)性能保证的竞争算法,其中 K 是专家数量,适用于 0-1 在线优化问题。此外,我们的多专家方法提供了一种在线组合多个在线算法的新视角,这是在线算法研究社区长期的核心主题。
Dec, 2023
我们研究了一种具有多步非线性切换成本和反馈延迟的挑战性平滑在线凸优化(SOCO)形式,提出了一种新颖的机器学习(ML)增强的在线算法,名为 Robustness-Constrained Learning(RCL),它通过受限投影将不受信任的 ML 预测与可信的专家在线算法结合起来,以增强 ML 预测的鲁棒性。具体而言,我们证明了 RCL 能够对于任何给定的专家保证(1+λ)竞争力,其中 λ>0,同时以鲁棒性感知的方式明确地训练 ML 模型以提高平均性能。重要的是,RCL 是第一个在多步切换成本和反馈延迟情况下具有可证明的鲁棒性保证的 ML 增强算法。我们以电动交通的电池管理为案例研究,展示了 RCL 在鲁棒性和平均性能方面的改进。
Oct, 2023
本文提出一种能够在线预测的算法,能够在概率和对抗性设置下与未知复杂度的情境树专家相竞争。通过将结构风险最小化的概率框架纳入现有的自适应算法中,我们不仅可以稳健地学习存在随机结构的同时获得正确的模型阶数,并取得了能够与拥有强侧面信息的最优算法竞争的遗憾边界,从而提供了对模型和随机性同时适应性的第一个具体保证。
May, 2018
本文研究了在多个机器学习预测的基础上增强的在线算法。我们提出了一个通用的算法框架,用于多重预测的在线覆盖问题,该算法能够获得与最佳预测器性能相竞争的在线解决方案。该算法还能够同时使竞争性达到最佳预测和最佳在线算法的性能水平,并应用于解决一些经典问题。
May, 2022