# Score-Based Methods for Discrete Optimization in Deep Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 16 references that are in the map.
- First posted on arXiv 15 Oct 2023.

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

- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space](https://mlsanity.com/paper/1706.02413/) (2017)
- [ShapeNet: An Information-Rich 3D Model Repository](https://mlsanity.com/paper/1512.03012/) (2015)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Selection via Proxy: Efficient Data Selection for Deep Learning](https://mlsanity.com/paper/1906.11829/) (2019)
- [PointCloud Saliency Maps](https://mlsanity.com/paper/1812.01687/) (2018)
- [Adversarial Attack and Defense on Point Sets](https://mlsanity.com/paper/1902.10899/) (2019)
- [Guarantees for Greedy Maximization of Non-submodular Functions with Applications](https://mlsanity.com/paper/1703.02100/) (2017)
- [Gradient Methods for Submodular Maximization](https://mlsanity.com/paper/1708.03949/) (2017)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [S3VAADA: Submodular Subset Selection for Virtual Adversarial Active Domain Adaptation](https://mlsanity.com/paper/2109.08901/) (2021)
- [Adversarial Coreset Selection for Efficient Robust Training](https://mlsanity.com/paper/2209.05785/) (2022)
- [Minimax Optimization: The Case of Convex-Submodular](https://mlsanity.com/paper/2111.01262/) (2021)

## Abstract (arXiv)

Discrete optimization problems often arise in deep learning tasks, despite the fact that neural networks typically operate on continuous data. One class of these problems involve objective functions which depend on neural networks, but optimization variables which are discrete. Although the discrete optimization literature provides efficient algorithms, they are still impractical in these settings due to the high cost of an objective function evaluation, which involves a neural network forward-pass. In particular, they require O(n) complexity per iteration, but real data such as point clouds have values of n in thousands or more. In this paper, we investigate a score-based approximation framework to solve such problems. This framework uses a score function as a proxy for the marginal gain of the objective, leveraging embeddings of the discrete variables and speed of auto-differentiation frameworks to compute backward-passes in parallel. We experimentally demonstrate, in adversarial set classification tasks, that our method achieves a superior trade-off in terms of speed and solution quality compared to heuristic methods.