研究如何将机器学习预测融入在线算法以提高性能,并提供非平凡的下界来衡量竞争分析的最优权衡.
Oct, 2020
我们研究了两层滑雪租借问题,其中用户需要通过选择三个支付选项之一来满足多个项目的一系列需求:按需使用支付(即租赁),购买单个项目(即单独购买)和购买所有项目(即组合购买)。我们设计了一种稳健的在线算法(RDTSR),它能提供最坏情况下的性能保证。为了兼顾在线算法的稳健性和机器学习的平均性能,我们开发了一种学习增强算法(LADTSR),通过将机器学习预测集成到稳健的在线算法中,即使预测不准确也能确保最坏情况下的性能保证。最后,我们对合成数据和真实迹线数据进行了数值实验以验证我们方法的有效性。
Feb, 2024
设计在线算法,利用机器学习预测,以超越最坏情况范例,解决各种实际相关在线问题(如调度、缓存、聚类、滑雪租赁等)。通过研究设计具备多个专家的在线算法,以超越静态最佳专家的贪心基准。在新的动态基准中提出了具有 O(log K)性能保证的竞争算法,其中 K 是专家数量,适用于 0-1 在线优化问题。此外,我们的多专家方法提供了一种在线组合多个在线算法的新视角,这是在线算法研究社区长期的核心主题。
Dec, 2023
考虑到离散时间系统中的资源受限源,通过时变无线信道将其时间敏感的数据传输到目的地。我们开发了一种鲁棒的在线算法,以最小化传输和信息老化成本之和,确保最坏情况下的性能保证。
Mar, 2024
基于机器学习的方法解决了具有二阶段线性适应鲁棒优化问题中的两个关键问题:二值即时变量和多面体不确定性集。我们通过将最优即时决策、与最优即时决策相关的最差情况以及最优观望决策编码为策略来进行求解。使用列生成和约束生成算法为多个相似的适应鲁棒优化实例提供预先求解,并提取最优策略生成训练集。我们训练了一个机器学习模型,该模型用于预测即时决策、与最优即时决策相关的最差情况以及观望决策的高质量策略。我们还介绍了一种算法来减少机器学习算法需要训练的不同目标类别的数量。我们将所提出的方法应用于设施选址、多项存货控制和机组投资问题,相比于最先进的算法,我们的方法在极短的时间内以高准确性解决了适应鲁棒优化问题。
Jul, 2023
本文介绍了在学习增强的在线算法中使用回归技术来预测未来输入参数的方法,并在广义滑雪租赁、装箱问题、最小完成时间调度等一般在线搜索方案的背景下探讨了这种方法。通过在设计回归问题的损失函数中结合在线优化基准,我们显示了这种回归问题样本复杂度的近似上下界,并将我们的结果扩展到了不可知设置。
May, 2022
该研究提出一种利用机器学习建议进行在线资源分配决策的框架,算法类似于一种 Pareto 最优算法,它能够在机器学习建议存在不准确性的情况下,在保证一定的性能准则的前提下尽量提高稳健比率,最终证明与基准算法相比,该算法能够在最坏和平均情况之间实现平衡,并且获得更好的性能。
Jun, 2023
本文提出一种能够在线预测的算法,能够在概率和对抗性设置下与未知复杂度的情境树专家相竞争。通过将结构风险最小化的概率框架纳入现有的自适应算法中,我们不仅可以稳健地学习存在随机结构的同时获得正确的模型阶数,并取得了能够与拥有强侧面信息的最优算法竞争的遗憾边界,从而提供了对模型和随机性同时适应性的第一个具体保证。
May, 2018
本文提出了一种基于条件风险价值方法的学习选项的方法,旨在处理具有不确定性的模型参数,以实现在平均和最坏情况下都能良好运作的选项,通过实验评估表明该方法在多关节机器人控制任务中获得了较好的表现。
May, 2019
通过在线算法动态地将按需购买和预付预定两种云计算资源实例的选项组合起来,以最小化成本。
May, 2013