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

arXiv: https://arxiv.org/abs/2410.17945 · HTML: https://mlsanity.com/paper/2410.17945/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 55 references that are in the map.
- First posted on arXiv 23 Oct 2024.

## Builds on (most cited first, 27 of 27)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Submodular Combinatorial Information Measures with Applications in Machine Learning](https://mlsanity.com/paper/2006.15412/) (2020)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016)
- [PRISM: A Rich Class of Parameterized Submodular Information Measures for Guided Subset Selection](https://mlsanity.com/paper/2103.00128/) (2021)
- [Introduction to Core-sets: an Updated Survey](https://mlsanity.com/paper/2011.09384/) (2020)
- [Towards Sustainable Learning: Coresets for Data-efficient Deep Learning](https://mlsanity.com/paper/2306.01244/) (2023)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Guarantees for Greedy Maximization of Non-submodular Functions with Applications](https://mlsanity.com/paper/1703.02100/) (2017)
- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [Randomized Composable Core-sets for Distributed Submodular Maximization](https://mlsanity.com/paper/1506.06715/) (2015)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems](https://mlsanity.com/paper/2005.05847/) (2020)
- ["Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack](https://mlsanity.com/paper/1910.05646/) (2019)
- [MILO: Model-Agnostic Subset Selection Framework for Efficient Model Training and Tuning](https://mlsanity.com/paper/2301.13287/) (2023)
- [LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation](https://mlsanity.com/paper/2205.10106/) (2022)
- [Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems](https://mlsanity.com/paper/1902.08455/) (2019)
- [Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice](https://mlsanity.com/paper/1805.06990/) (2018)
- [Learning fine-grained search space pruning and heuristics for combinatorial optimization](https://mlsanity.com/paper/2001.01230/) (2020)
- [Maximizing Submodular Functions for Recommendation in the Presence of Biases](https://mlsanity.com/paper/2305.02806/) (2023)
- [Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2305.10292/) (2023)
- [Coresets remembered and items forgotten: submodular maximization with deletions](https://mlsanity.com/paper/2203.01241/) (2022)
- [Scaling Submodular Maximization via Pruned Submodularity Graphs](https://mlsanity.com/paper/1606.00399/) (2016)
- [On Fair Allocation of Indivisible Goods to Submodular Agents](https://mlsanity.com/paper/2303.12444/) (2023)
- [COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems](https://mlsanity.com/paper/2312.09086/) (2023)
- [Learning to Prune Instances of Steiner Tree Problem in Graphs](https://mlsanity.com/paper/2208.11985/) (2022)

## Abstract (arXiv)

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.