mlsanityData to 13 Oct 2026

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

arXiv 2410.17945 ↗First posted 23 Oct 2024cs.DS cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

27 of 55 references.

References · 27

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,318
  2. 2017Inductive Representation Learning on Large Graphscited by 6,303
  3. 2020Submodular Combinatorial Information Measures with Applications in Machine Learningcited by 88
  4. 2016SNAP: A General Purpose Network Analysis and Graph Mining Librarycited by 56
  5. 2016Restricted Strong Convexity Implies Weak Submodularitycited by 51
  6. 2021PRISM: A Rich Class of Parameterized Submodular Information Measures for Guided Subset Selectioncited by 50
  7. 2020Introduction to Core-sets: an Updated Surveycited by 45
  8. 2023Towards Sustainable Learning: Coresets for Data-efficient Deep Learningcited by 44
  9. 2020Coresets for Near-Convex Functionscited by 38
  10. 2017Guarantees for Greedy Maximization of Non-submodular Functions with Applicationscited by 34
  11. 2022Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptionscited by 20
  12. 2015Randomized Composable Core-sets for Distributed Submodular Maximizationcited by 19
15 more
  1. 2022The Power of Uniform Sampling for Coresetscited by 18
  2. 2020Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problemscited by 17
  3. 2019"Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsackcited by 14
  4. 2023MILO: Model-Agnostic Subset Selection Framework for Efficient Model Training and Tuningcited by 9
  5. 2022LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisationcited by 8
  6. 2019Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problemscited by 7
  7. 2018Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Latticecited by 6
  8. 2020Learning fine-grained search space pruning and heuristics for combinatorial optimizationcited by 6
  9. 2023Maximizing Submodular Functions for Recommendation in the Presence of Biasescited by 5
  10. 2023Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraintcited by 5
  11. 2022Coresets remembered and items forgotten: submodular maximization with deletionscited by 4
  12. 2016Scaling Submodular Maximization via Pruned Submodularity Graphscited by 3
  13. 2023On Fair Allocation of Indivisible Goods to Submodular Agentscited by 3
  14. 2023COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problemscited by 3
  15. 2022Learning to Prune Instances of Steiner Tree Problem in Graphscited by 2

Built on by

Not cited yet.