← 研踪 PaperTrailarXiv:2602.02505 · v2
Learning-augmented smooth integer programs with PAC-learnable oracles
首次提交 2026-01-22 13:55
版本更新 2026-11-11 18:11
雷达观测 2026-11-13 14:16
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-11 18:11 · 最新观测版本
Learning-augmented smooth integer programs with PAC-learnable oracles
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.
查看此版本解读 →查看此版本原文 ↗