Nov, 2020

在线匹配、流量和负载均衡的可学习和实例鲁棒性预测

PDF
TL;DR本文提出了一种新的模型来增强算法的预测能力，该模型要求算法具有形式上可学性和实例鲁棒性；通过构造在线可学习算法，为网络流量分配问题和受限指派最小化问题提供高质量的预测性能，并证明了这些预测对少量训练实例的数据具有鲁棒性。
algorithmspredictionslearnabilityinstance robustnessnetwork flow allocation
发现论文，激发创造
  • 学习增强在线算法的最优韧性 - 一致性平衡

    研究如何将机器学习预测融入在线算法以提高性能，并提供非平凡的下界来衡量竞争分析的最优权衡.

    Oct, 2020

  • 带有预测的算法学习

    介绍了一种算法设计范例 —— 基于学习预测器的算法，将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度，在构建优美的预测器的同时，在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果，且提供了第一批基于学习理论的担保。

    Feb, 2022

  • 多重好处：在线监督学习中的稳健模型选择

    本文提出一种能够在线预测的算法，能够在概率和对抗性设置下与未知复杂度的情境树专家相竞争。通过将结构风险最小化的概率框架纳入现有的自适应算法中，我们不仅可以稳健地学习存在随机结构的同时获得正确的模型阶数，并取得了能够与拥有强侧面信息的最优算法竞争的遗憾边界，从而提供了对模型和随机性同时适应性的第一个具体保证。

    May, 2018

  • 在线图算法预测

    本文研究具有预测的在线图形问题，提出了一个新的度量误差的定义 (metric error)，并给出了一个通用框架，用于在线预测算法。采用这个框架，我们能够获得关于竞争比率的紧密限制，并将其作为度量误差的函数来描述。

    Dec, 2021

  • 具有不确定性量化预测的在线算法

    如何在设计在线算法中最佳利用不确定性量化预测，以及如何利用更一般形式的不确定性量化，提出了基于在线学习的框架来在多实例场景中学习如何充分利用不确定性量化作出最佳决策。

    Oct, 2023

  • 基于学习预测的在线动态应答

    研究在线动态确认问题及其使用机器学习预测的算法，通过新的预测误差测量，实现同时最优一致性和鲁棒性，可用于其他具有时间特征的在线问题。

    May, 2023

  • 鲁棒性和泛化性

    基于稳健性的学习算法的普适性界限推导及其稳健性被证明是学习算法发挥作用的基本属性。

    May, 2010

  • 在线图形探索方法的鲁棒化

    利用机器学习预测作为辅助，通过引入预测算法结合最近邻算法，探索未知环境的学习增加变种基于线上图探索问题的研究，证明当预测精度高时算法显著优于其他线上算法，并在预测较差时保持良好保证，提供了与预测误差平稳退化的理论最坏情况下的绑定，并通过计算实验证实了结果，同时还扩展了该概念到鲁棒算法的一般框架，通过在给定算法与最近邻算法之间进行谨慎插值，证明了新的性能边界，既利用特定输入的良好性能，又确立了对任意输入的鲁棒性。

    Dec, 2021

  • 在线分类与预测

    在线分类研究中，研究者利用对未来示例的预测来改进在线学习算法，以减小期望遗憾并提高分类准确性。该研究还证明了当未来示例可准确预测时，在线学习可以与转导式在线学习相媲美，从而对近期基于预测和分布假设的在线算法的研究提供了补充。

    May, 2024

  • 面对攻击具有强鲁棒性和高可靠性的学习者

    研究了如何在多个角度上面对数据污染攻击实现强大的鲁棒性保证和提供可靠的预测，同时提供算法计算文本类问题的区间，并针对线性分离器提供了真正的多项式时间算法。

    Mar, 2022