ADVANCING OPTIMAL SUBSET ORACLE VIA LEARNING RELAXATION OF NEURAL SET FUNCTIONS

Learning neural set functions—which assign utility values to subsets of items—is essential for tasks like drug discovery and product recommendation. Current approaches typically use optimal subset (OS) oracles, which rely on variational inference to learn these functions. However, these methods suffer from high computational costs and optimization instability because they use Monte Carlo sampling to estimate the gradients of the evidence lower bound (ELBO).

The authors propose ReSet, a framework that replaces sampling-based gradient estimation with a learned, differentiable surrogate objective. By treating the ELBO as a continuous relaxation of the set function, the model learns a surrogate that provides stable gradients across the continuous domain. This allows the optimization of the variational distribution to proceed via efficient gradient ascent rather than stochastic sampling. The authors further connect this to variational free energy, allowing the model to adaptively balance expected energy and entropy, and provide theoretical guarantees regarding convergence and approximation ratios for submodular maximization.

By eliminating the need for repeated Monte Carlo sampling, ReSet significantly reduces the computational overhead associated with training neural set functions. The resulting optimization trajectory is smoother and more stable, leading to faster convergence and better performance on real-world tasks. This approach provides a more scalable and theoretically grounded way to perform subset selection in high-dimensional spaces.