Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization

Ankur Nath, Alan Kuhnle
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:3664-3672, 2025.

Abstract

Modern instances of combinatorial optimization problems often exhibit billion-scale ground sets, which have many uninformative or redundant elements. In this work, we develop light-weight pruning algorithms to quickly discard elements that are unlikely to be part of an optimal solution. Under mild assumptions on the instance, we prove theoretical guarantees on the fraction of the optimal value retained and the size of the resulting pruned ground set. Through extensive experiments on real-world datasets for various applications, we demonstrate that our algorithm, QuickPrune, efficiently prunes over 90% of the ground set and outperforms state-of-the-art classical and machine learning heuristics for pruning.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-nath25a, title = {Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization}, author = {Nath, Ankur and Kuhnle, Alan}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {3664--3672}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/nath25a/nath25a.pdf}, url = {https://proceedings.mlr.press/v258/nath25a.html}, abstract = {Modern instances of combinatorial optimization problems often exhibit billion-scale ground sets, which have many uninformative or redundant elements. In this work, we develop light-weight pruning algorithms to quickly discard elements that are unlikely to be part of an optimal solution. Under mild assumptions on the instance, we prove theoretical guarantees on the fraction of the optimal value retained and the size of the resulting pruned ground set. Through extensive experiments on real-world datasets for various applications, we demonstrate that our algorithm, QuickPrune, efficiently prunes over 90% of the ground set and outperforms state-of-the-art classical and machine learning heuristics for pruning.} }
Endnote
%0 Conference Paper %T Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization %A Ankur Nath %A Alan Kuhnle %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-nath25a %I PMLR %P 3664--3672 %U https://proceedings.mlr.press/v258/nath25a.html %V 258 %X Modern instances of combinatorial optimization problems often exhibit billion-scale ground sets, which have many uninformative or redundant elements. In this work, we develop light-weight pruning algorithms to quickly discard elements that are unlikely to be part of an optimal solution. Under mild assumptions on the instance, we prove theoretical guarantees on the fraction of the optimal value retained and the size of the resulting pruned ground set. Through extensive experiments on real-world datasets for various applications, we demonstrate that our algorithm, QuickPrune, efficiently prunes over 90% of the ground set and outperforms state-of-the-art classical and machine learning heuristics for pruning.
APA
Nath, A. & Kuhnle, A.. (2025). Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:3664-3672 Available from https://proceedings.mlr.press/v258/nath25a.html.

Related Material