Distributional Lifting for Discrete Optimization
Abstract
We introduce a framework that transforms discrete optimization into continuous optimization over parameterized probability distributions. The framework reveals a common distributional structure behind several methods that have largely developed independently, including continuous reformulations for multilinear binary optimization, Markov decision processes and reinforcement learning, the cross-entropy method, mean-field variational optimization, and the quantum approximate optimization algorithm. It enables flexible and modular algorithm design, for example, by using neural networks to incorporate contextual information or by enforcing convexity of the lifted problem. We establish two theoretical results: a link between the lifted optimality gap and sampling quality in the original discrete problem, and a convergence guarantee for the lifted optimization problem under suitable conditions. These results lead to a unified algorithmic template based on batched sampling and stochastic gradient updates that is naturally compatible with GPU computation. We demonstrate the framework through three case studies spanning multidimensional knapsack, covering-constrained three-dimensional assignment, and a stochastic mixed-integer location-allocation problem, showing that it can accommodate distinct combinatorial structures and scale to large discrete and mixed-integer settings.
Related
- Admissibility-Preserving Constraint Lifting for Conditional Deadbeat Control of Discrete-Time Nonlinear Systems
- Conic-Lifting for Learning-rate-free Convex Optimization
- GUIDE-FBO: Guidance via Uncertainty Intervention and Distributional Exchange for Federated Bayesian Optimization
- Adjustable Robust Optimization with Discrete Uncertainty
- Discrete-time feedback linearization control for nonsmooth constrained optimization
BibTeX
@misc{wei2026distributional,
title = {{Distributional Lifting for Discrete Optimization}},
author = {Ningji Wei and Jiaming Liang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26521},
eprint = {2610.26521},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26521},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Distributional Lifting for Discrete Optimization
AU - Ningji Wei
AU - Jiaming Liang
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26521
UR - https://arxiv.org/abs/2610.26521
AB - We introduce a framework that transforms discrete optimization into continuous optimization over parameterized probability distributions. The framework reveals a common distributional structure behind several methods that have largely developed independently, including continuous reformulations for multilinear binary optimization, Markov decision processes and reinforcement learning, the cross-entropy method, mean-field variational optimization, and the quantum approximate optimization algorithm. It enables flexible and modular algorithm design, for example, by using neural networks to incorporate contextual information or by enforcing convexity of the lifted problem. We establish two theoretical results: a link between the lifted optimality gap and sampling quality in the original discrete problem, and a convergence guarantee for the lifted optimization problem under suitable conditions. These results lead to a unified algorithmic template based on batched sampling and stochastic gradient updates that is naturally compatible with GPU computation. We demonstrate the framework through three case studies spanning multidimensional knapsack, covering-constrained three-dimensional assignment, and a stochastic mixed-integer location-allocation problem, showing that it can accommodate distinct combinatorial structures and scale to large discrete and mixed-integer settings.
ER -