LEAP：基于 PAC 可学习预言机的学习增强平滑整数规划框架
Learning-augmented smooth integer programs with PAC-learnable oracles
AI 导读
arXiv 论文提出 LEAP，一个面向平滑整数规划（含 MAX-CUT 和 MAX-k-SAT）的端到端学习增强框架，由从采样实例学习的预言机预测完整布尔赋值。
正文 · 原文
Abstract:We study an end-to-end learning-augmented framework for smooth integer programs, a broad class of Boolean polynomial optimization problems including MAX-CUT and MAX-k-SAT. An oracle learned from sampled instances predicts a full Boolean assignment for each unseen instance. For fixed-degree objectives, our polynomial-time pipeline, LEAP, linearizes the objective around the predicted assignment, solves an error-budgeted linear program, and rounds the fractional solution. We establish two guarantees. First, for any prediction, the approximation loss of LEAP degrades gracefully with prediction error: it is controlled by an error footprint that quantifies how much mispredicted coordinates can perturb the objective's local coefficients. Second, we bound the pseudo-dimension of the LEAP-induced cost class, yielding a PAC-style guarantee for learning an oracle from a predictor class via empirical risk minimization on instances from an unknown distribution. Together, these results give an end-to-end bound that separates the expected footprint loss of the best oracle in the class from the statistical error of learning. In experiments on MAX-CUT and MAX-SAT, LEAP substantially repairs imperfect predictions, empirical risk minimization selects effective oracle candidates, and the pipeline scales to application benchmarks with up to two million clauses.
| Subjects: | Data Structures and Algorithms (cs.DS); Artificial Intelligence (cs.AI); Machine Learning (cs.LG) |
| Cite as: | arXiv:2602.02505 [cs.DS] |
| (or arXiv:2602.02505v2 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2602.02505 arXiv-issued DOI via DataCite |
Submission history
From: Hao-Yuan He [view email]
[v1]
Thu, 22 Jan 2026 05:55:36 UTC (60 KB)
[v2]
Wed, 11 Nov 2026 10:11:01 UTC (146 KB)
来源：arXiv cs.AI · arxiv.org