arXiv cs.AI· Hao-Yuan He, Jiang-Tian Xue, Ming Li, Zhi-Hua Zhou·· 1 天前AI 评分29
LEAP：面向平滑整数规划的端到端学习增强框架，具备 PAC 可学习 oracle 保证
Learning-augmented smooth integer programs with PAC-learnable oracles
AI 导读
研究者提出 LEAP，一个面向平滑整数规划（含 MAX-CUT、MAX-k-SAT）的端到端学习增强框架：由采样实例学到的 oracle 预测完整布尔赋值，再围绕预测线性化目标、求解带误差预算的线性规划并取整。
正文 · AI 翻译
摘要：我们研究一种用于平滑整数程序的端到端学习增强框架，平滑整数程序是一大类布尔多项式优化问题，包括 MAX-CUT 和 MAX-k-SAT。从采样实例中学习得到的 oracle 会为每个未见实例预测完整的布尔赋值。对于固定次数的目标函数，我们的多项式时间流水线 LEAP 围绕预测赋值对目标函数进行线性化，求解一个带误差预算的线性规划，并对分数解进行舍入。我们建立了两项保证。第一，对于任意预测，LEAP 的近似损失会随预测误差平缓退化：它由一个误差足迹控制，该足迹量化了误预测坐标能在多大程度上扰动目标函数的局部系数。第二，我们界定了 LEAP 诱导的成本类的伪维度，从而给出一种 PAC 式保证：在来自未知分布的实例上通过经验风险最小化，从预测器类中学习 oracle。综合起来，这些结果给出了一个端到端界，将类中最佳 oracle 的期望足迹损失与学习的统计误差分离开来。在 MAX-CUT 和 MAX-SAT 上的实验中，LEAP 大幅修复了不完美的预测，经验风险最小化选出了有效的 oracle 候选，且该流水线可扩展到包含多达两百万个子句的应用基准。
| 学科： | 数据结构与算法（cs.DS）；人工智能（cs.AI）；机器学习（cs.LG） |
| 引用为： | arXiv:2602.02505 [cs.DS] |
| （或本版本的 arXiv:2602.02505v2 [cs.DS]） | |
| https://doi.org/10.48550/arXiv.2602.02505 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：Hao-Yuan He [查看电子邮件]
[v1]
2026年1月22日星期四 05:55:36 UTC（60 KB）
[v2]
2026年11月11日星期三 10:11:01 UTC（146 KB）
来源：arXiv cs.AI · arxiv.org