Score-Based Methods for Discrete Optimization in Deep Learning
Eric Lei Arman Adibi Hamed Hassani
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.