Learning-augmented smooth integer programs with PAC-learnable oracles
This work addresses the challenge of efficiently solving combinatorial optimization problems for researchers and practitioners in algorithms and machine learning, offering an incremental improvement by integrating learning into classical approximation methods.
The paper tackles the problem of solving smooth integer programs like MAX-CUT and MAX-k-SAT by introducing a learning-augmented framework that uses a predictive oracle to create a linear surrogate, solved via linear programming and rounding, ensuring consistent and smooth solution quality against prediction errors. It extends tractable approximations from dense to near-dense regimes and proves the oracle is PAC-learnable with polynomial samples, achieving bounded pseudo-dimension for near-optimal performance.
This paper investigates learning-augmented algorithms for smooth integer programs, covering canonical problems such as MAX-CUT and MAX-k-SAT. We introduce a framework that incorporates a predictive oracle to construct a linear surrogate of the objective, which is then solved via linear programming followed by a rounding procedure. Crucially, our framework ensures that the solution quality is both consistent and smooth against prediction errors. We demonstrate that this approach effectively extends tractable approximations from the classical dense regime to the near-dense regime. Furthermore, we go beyond the assumption of oracle existence by establishing its PAC-learnability. We prove that the induced algorithm class possesses a bounded pseudo-dimension, thereby ensuring that an oracle with near-optimal expected performance can be learned with polynomial samples.