cs.DSJan 22, 2026

Learning-augmented smooth integer programs with PAC-learnable oracles

Authors: Hao-Yuan He, Jiang-Tian Xue, Ming Li, Zhi-Hua Zhou

Organizations: National Key Laboratory for Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University

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.

Figures & tables

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

    Jul 16, 2026Haifeng Li, Mo HaiCombinatorial OptimizationLearning-Augmented Algorithms

  2. Learning Augmented Exact Exponential Algorithms

    Jun 17, 2026Tatiana Belova, Yuriy Dementiev, Danil SagunovLearning-Augmented Algorithms

  3. Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications

    Sep 4, 2026Hailiang Zhao, Xueyan Tang, Peng Chen +4Learning-Augmented Algorithms