LEAP：面向平滑整数规划的端到端学习增强框架，具备 PAC 可学习 oracle 保证

View PDF HTML (experimental)

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)