# Learning-augmented smooth integer programs with PAC-learnable oracles

DevFeed: [Learning-augmented smooth integer programs with PAC-learnable oracles](<https://devfeed.tech/articles/learning-augmented-smooth-integer-programs-with-pac-learnable-oracles-131874.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2602.02505>)

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

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [Predictive AI](<https://devfeed.tech/topics/predictive-ai.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [boolean](<https://devfeed.tech/tags/boolean.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [error](<https://devfeed.tech/tags/error.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [framework](<https://devfeed.tech/tags/framework.md>), [guarantees](<https://devfeed.tech/tags/guarantees.md>), [learning](<https://devfeed.tech/tags/learning.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [oracles](<https://devfeed.tech/tags/oracles.md>)

## AI overview

LEAP improves predicted Boolean assignments for fixed-degree smooth integer programs, including MAX-CUT and MAX-k-SAT. It linearizes the objective around each predicted assignment, solves an error-budgeted linear program, then rounds the fractional solution. Its approximation loss degrades with prediction error according to an error footprint measuring how mispredicted coordinates affect local coefficients. A bound on the pseudo-dimension of LEAP's induced cost class supports PAC-style oracle learning by empirical risk minimization, with an end-to-end guarantee separating the best in-class oracle's expected footprint loss from learning error. Experiments report substantial repair of imperfect predictions and scaling to benchmarks with up to two million clauses.

## Source excerpt

arXiv:2602.02505v2 Announce Type: replace-cross 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.