REVIEW 3 major objections 65 references
Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions
T0 review · 3 major / 0 minor · reviewed 2026-07-14 · grok-4.5
Pith's one-line read A learned continuous relaxation replaces Monte Carlo sampling in optimal-subset oracles, yielding stable gradients, lower cost, and a submodular approximation guarantee.
desk verdict Useful plug-in that kills MC ELBO gradients in OS oracles; theory is standard continuous-submodular ascent plus an unproved alignment step for the discrete claim. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
ReSet: a DeepSets-style surrogate g_θ(ψ) that directly models the continuous relaxation of the set utility (the multilinear extension / ELBO without the entropy term), so that ψ is updated by gradient ascent ψ ← ψ + α∇g_θ(ψ) instead of fixed-point iteration with Monte Carlo marginal-gain estimates.
What would settle it
Train the same architecture on a task whose utility is known to be strongly supermodular (or otherwise far from weakly DR-submodular) and check whether the claimed approximation ratio and the continuous-to-discrete alignment still hold; a large gap would falsify the transfer of the theoretical guarantee.
Extended reading notes
Core claim
Monte Carlo estimation of the multilinear-extension gradient inside mean-field variational inference for optimal-subset oracles can be replaced by a learned continuous surrogate of the set function; the resulting projected-gradient procedure is faster and more stable, admits a γe^{-γ} approximation guarantee when the surrogate is γ-weakly DR-submodular, and simultaneously learns an adaptive energy–entropy trade-off.
Load-bearing premise
The discrete quality guarantee assumes that after training the learned surrogate and the true multilinear extension agree on which fractional solutions are good—an alignment that is hoped for rather than proved for neural networks that need not be weakly submodular.
Editorial extensions
If this is right
- Existing optimal-subset oracles (EquiVSet, INSET, etc.) can drop Monte Carlo sampling and obtain lower memory and wall-clock cost by swapping in the learned relaxation.
- Variational free-energy objectives for set selection become trainable end-to-end with an adaptive temperature rather than a fixed energy–entropy balance.
- Projected gradient ascent on the continuous surrogate inherits a constant-factor guarantee for weakly DR-submodular set functions, giving a new continuous-greedy-style algorithm for neural set models.
- Pipage or randomized rounding of the final fractional solution recovers a discrete subset whose expected utility matches the multilinear value, preserving the approximation ratio in expectation.
Reading between the lines
- The same surrogate idea could amortize other combinatorial variational objectives (e.g., determinantal point processes or matroid-constrained selection) that currently rely on sampling.
- Because the method learns an adaptive free-energy temperature, it may automatically temper exploration on easy instances and increase entropy on multimodal ones—suggesting a built-in curriculum that could be measured by tracking the learned temperature over training.
- If the continuous–discrete alignment fails on some domains, a cheap regularizer that matches multilinear values on a small held-out sample of subsets could restore the theoretical guarantee without full Monte Carlo at every step.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes ReSet, a plug-in for optimal-subset (OS) oracles that replaces Monte Carlo estimation of multilinear-extension / ELBO gradients by a learned continuous surrogate g_θ(ψ) of the set function. Mean-field variational parameters ψ are then updated by projected gradient ascent (with optional Langevin noise and an amortizing RecNet), after which θ is trained by the usual marginal cross-entropy loss. Under the assumption that g_θ is γ-weakly DR-submodular and L-smooth, Theorem 3.1 gives a γe^{-γ} stationary-point guarantee and convergence of gradient ascent; Appendix A.3 further claims an approximate discrete guarantee once the surrogate and true multilinear extension are aligned. The free-energy / ELBO identity at unit temperature is recalled (Corollary 3.3). Empirically, EquiVSet-R and INSET-R improve mean Jaccard coefficient over the corresponding MC baselines on synthetic, Amazon recommendation, anomaly-detection, and compound-selection tasks, with reported reductions in per-iteration time and memory.
Significance. If the efficiency and accuracy claims hold, the work removes a practical bottleneck of recent OS-oracle frameworks (EquiVSet, INSET) and supplies a continuous-submodular analysis that those works lacked. The empirical gains on hard Amazon categories, Two-Moons, and BindingDB, together with the measured speed-ups (Appendix F.2–F.3), are concrete and useful for recommendation and virtual screening. The free-energy reinterpretation is standard but cleanly stated. The main theoretical contribution is conditional on unverified inductive biases of the neural surrogate; those gaps limit the strength of the guarantee but do not erase the practical value of the method as an engineering improvement.
major comments (3)
- Theorem 3.1 and the discrete claim (Eq. 17 / App. A.3) rest on two load-bearing assumptions that are never verified: (i) that the learned DeepSets/MHA surrogate g_θ is γ-weakly DR-submodular (and L-smooth) on the unit box, and (ii) that after training the normalized quality of g_θ and of the true multilinear extension f^{F_θ}_mt differ by a negligible residual ε_sol (Eq. 51). Neural parameterizations need not satisfy weak DR-submodularity, and the paper neither measures γ nor enforces it. Without empirical or architectural support for these assumptions, the continuous stationary-point bound does not transfer to the discrete OS solutions that are actually evaluated by MJC, so the theoretical support for the reported gains is incomplete.
- The free-energy discussion (Prop. 3.2, Cor. 3.3, §3.3) asserts that the method can “learn an adaptive temperature T” and thereby an adaptive energy–entropy trade-off. In the implemented architecture (Eq. 24, Alg. 1–2) the surrogate is a single scalar network with no explicit temperature parameter, and the ELBO entropy term is omitted when differentiating w.r.t. θ. The claim therefore overstates what is actually optimized; either an explicit learnable temperature should be introduced and ablated, or the adaptive-trade-off language should be removed.
- Appendix E.5 acknowledges that the Double-MNIST / F-MNIST / CIFAR-10 protocols of Ou et al. (2022) were reconstructed because public code and precise descriptions were missing. Table 3 therefore compares against re-implemented baselines under a new protocol. To make the large reported lifts (e.g., EquiVSet 38.6 → 71.0 on Double MNIST) interpretable, the paper should either release the exact generation scripts and hyper-parameters used for the original baselines, or clearly mark those three columns as “re-implemented under our protocol” and supply a side-by-side check on CelebA (where the original protocol is public).
Circularity Check
No load-bearing circularity: free-energy identity is standard, continuous guarantees cite external DR-submodular theory, and empirical gains are held-out comparisons; only mild plug-in dependence on the authors' prior OS-oracle line.
full rationale
Walking the claimed chain (ELBO as multilinear relaxation → learn differentiable surrogate g_θ → continuous gradient ascent → Thm. 3.1 under γ-weak DR-submodularity → discrete transfer via assumed alignment → free-energy reinterpretation → held-out MJC gains) does not yield a reduction of any central claim to its own inputs by construction. Corollary 3.3 (F = −ELBO at k_BT = 1) is the textbook variational free-energy identity, not a derivation that forces the empirical results. Theorem 3.1 imports approximation/convergence statements from external continuous weakly DR-submodular maximization literature (Hassani et al., Pedramfar et al.) under an explicit γ-weak-submodularity and L-smoothness assumption; that is conditional theory, not a self-definitional loop. The discrete lower bound (Eq. 17 / App. A.3) honestly postulates post-training alignment of normalized g_θ and f_mt^{F_θ} (ε_sol → 0); an unproved transfer assumption is a correctness gap, not circularity. Training uses OS pairs and evaluates Jaccard on held-out splits against Random/PGM/DeepSet/Set Transformer/EquiVSet/INSET—externally falsifiable, not fitted-input-as-prediction. Mild self-dependence exists only in that ReSet is a plug-in to the Ou/Xie OS-oracle variational skeleton (overlapping coauthors), but that prior line supplies the problem setting, not a uniqueness theorem or ansatz that forces the reported gains. No uniqueness import, no ansatz smuggled via self-citation, no renaming of a known empirical pattern as a first-principles prediction. Score 1 reflects only that non-load-bearing lineage dependence; central claims remain independently supported.
Assumptions & free parameters
free parameters (4)
- gradient ascent step size α (learnable or grid-chosen)
- Langevin noise scale τ / ε
- number of unrolled ascent steps K
- network widths/heads and learning-rate schedule
assumptions (5)
- domain assumption Mean-field factorization: q(ψ) is a product of independent Bernoullis approximating p_θ(S|V).
- ad hoc to paper Learned surrogate g_θ is γ-weakly DR-submodular and L-smooth on the unit box.
- ad hoc to paper After sufficient training, normalized quality of g_θ and the multilinear extension f^{F_θ}_mt align up to small ε_sol.
- standard math ELBO equals multilinear extension plus entropy; with k_BT=1, free energy equals −ELBO.
- domain assumption Permutation-invariant set functions admit DeepSets-style sum-decompositions (and attention can capture interactions).
invented entities (1)
-
ReSet surrogate objective g_θ(ψ)
Cite this review
Pith. "Pith review of Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions." pith.science (2026). https://pith.science/paper/KMBSW2GG
@misc{pith2026260711555,
author = {Pith},
title = {Pith review of: Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions},
year = {2026},
howpublished = {\url{https://pith.science/paper/KMBSW2GG}},
note = {Machine review of arXiv:2607.11555}
}
read the original abstract
Learning neural set functions is pivotal to a wide range of important applications, including compound selection in AI-driven drug discovery and product recommendation. Recent work has introduced optimal subset oracles to implicitly learn set functions under practical weakly supervised settings, where model parameters are optimized through mean-field variational inference. However, these frameworks rely on Monte Carlo sampling to estimate gradients of the evidence lower bound when updating the variational distribution. Repeated sampling across iterations incurs substantial computational overhead, while the resulting stochasticity can destabilize the optimization trajectory. In this work, we reinterpret the evidence lower bound as a continuous relaxation of the set function and learn a surrogate objective that replaces sampling-based ELBO gradient estimation during variational optimization. The learned surrogate provides stable and efficient gradients throughout the continuous domain, thereby reducing computational overhead and accelerating inference. Furthermore, we establish an approximation guarantee for the proposed framework under submodular maximization and characterize its connection to variational free energy. Experiments on a variety of real-world tasks demonstrate consistent improvements over existing baselines.
Figures
Figures from the paper (7 more)
Reference graph
Works this paper leans on
-
[1]
1990 , publisher=
The history of statistics: The measurement of uncertainty before 1900 , author=. 1990 , publisher=
1900
-
[2]
The mathematical intelligencer , volume=
The principle of maximum entropy , author=. The mathematical intelligencer , volume=
-
[3]
Proceedings of the Royal Society of London
An invariant form for the prior probability in estimation problems , author=. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences , volume=
-
[4]
Advances in Neural Information Processing Systems , pages=
Learning neural set functions under the optimal subset oracle , author=. Advances in Neural Information Processing Systems , pages=
-
[5]
Proceedings of the AAAI Conference on Artificial Intelligence , year=
Cooperative learning of energy-based model and latent variable model via MCMC teaching , author=. Proceedings of the AAAI Conference on Artificial Intelligence , year=
-
[6]
arXiv preprint arXiv:1508.00947 , year=
MCMC-based inference in the era of big data: A fundamental analysis of the convergence complexity of high-dimensional chains , author=. arXiv preprint arXiv:1508.00947 , year=
-
[7]
arXiv preprint arXiv:2504.11516 , year=
FEAT: Free energy Estimators with Adaptive Transport , author=. arXiv preprint arXiv:2504.11516 , year=
-
[8]
Neural computation , volume=
The helmholtz machine , author=. Neural computation , volume=
Show all 65 references
-
[9]
The Third Blogpost Track at ICLR , year=
How to compute Hessian-vector products? , author=. The Third Blogpost Track at ICLR , year=
-
[10]
IEEE transactions on pattern analysis and machine intelligence , volume=
Learning graphical model parameters with approximate marginal inference , author=. IEEE transactions on pattern analysis and machine intelligence , volume=
-
[11]
Integer Programming and Combinatorial Optimization , pages=
Maximizing a Submodular Set Function Subject to a Matroid Constraint , author=. Integer Programming and Combinatorial Optimization , pages=
-
[12]
arXiv preprint arXiv:2507.02092 , year=
Energy-Based Transformers are Scalable Learners and Thinkers , author=. arXiv preprint arXiv:2507.02092 , year=
-
[13]
Advances in neural information processing systems , volume=
Implicit generation and modeling with energy based models , author=. Advances in neural information processing systems , volume=
-
[14]
Advances in neural information processing systems , volume=
Deep sets , author=. Advances in neural information processing systems , volume=
-
[15]
International Conference on Learning Representations , year=
Enhancing neural subset selection: Integrating background information into set representations , author=. International Conference on Learning Representations , year=
-
[16]
Journal of Machine Learning Research , volume=
Probabilistic symmetries and invariant neural networks , author=. Journal of Machine Learning Research , volume=
-
[17]
Advances in neural information processing systems , volume=
Attention is all you need , author=. Advances in neural information processing systems , volume=
-
[18]
Proceedings of the International Joint Conference on Artificial Intelligence , pages=
Differentiable submodular maximization , author=. Proceedings of the International Joint Conference on Artificial Intelligence , pages=
-
[19]
International conference on machine learning , pages=
Set transformer: A framework for attention-based permutation-invariant neural networks , author=. International conference on machine learning , pages=
-
[20]
Advances in neural information processing systems , pages=
HORSE: hierarchical representation for large-scale neural subset selection , author=. Advances in neural information processing systems , pages=
-
[21]
the Journal of machine Learning research , volume=
Scikit-learn: Machine learning in Python , author=. the Journal of machine Learning research , volume=
-
[22]
Advances in Neural Information Processing Systems , volume=
Expectation-maximization for learning determinantal point processes , author=. Advances in Neural Information Processing Systems , volume=
-
[23]
arXiv preprint arXiv:1810.04805 , volume=
Pre-training of deep bidirectional transformers for language understanding , author=. arXiv preprint arXiv:1810.04805 , volume=
-
[24]
International Conference on Learning Representations , year=
Set Prediction without Imposing Structure as Conditional Density Estimation , author=. International Conference on Learning Representations , year=
-
[25]
International journal of molecular sciences , volume=
The light and dark sides of virtual screening: what is there to know? , author=. International journal of molecular sciences , volume=
-
[26]
International Conference on Computer Vision , pages=
Deepsetnet: Predicting sets with deep neural networks , author=. International Conference on Computer Vision , pages=
-
[27]
Proceedings of the ACM SIGKDD conference on knowledge discovery and data mining , pages=
Relevance meets diversity: A user-centric framework for knowledge exploration through recommendations , author=. Proceedings of the ACM SIGKDD conference on knowledge discovery and data mining , pages=
-
[28]
SIAM Journal on Computing , volume=
Submodular functions: Learnability, structure, and optimization , author=. SIAM Journal on Computing , volume=
-
[29]
Proceedings of the AAAI Conference on Artificial Intelligence , pages=
Learning Set Functions with Implicit Differentiation , author=. Proceedings of the AAAI Conference on Artificial Intelligence , pages=
-
[30]
Journal of the American statistical Association , volume=
Variational inference: A review for statisticians , author=. Journal of the American statistical Association , volume=
-
[31]
Advances in Neural Information Processing Systems , volume=
Neural set function extensions: Learning with discrete functions in high dimensions , author=. Advances in Neural Information Processing Systems , volume=
-
[32]
Advances in Neural Information Processing Systems , volume=
Gradient methods for submodular maximization , author=. Advances in Neural Information Processing Systems , volume=
-
[33]
GitHub repository , year=
Multi-digit MNIST for few-shot learning , author=. GitHub repository , year=
-
[34]
Proceedings of the IEEE international conference on computer vision , pages=
Deep learning face attributes in the wild , author=. Proceedings of the IEEE international conference on computer vision , pages=
-
[35]
arXiv preprint arXiv:1708.07747 , year=
Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms , author=. arXiv preprint arXiv:1708.07747 , year=
-
[36]
Handbook of Systemic Autoimmune Diseases , volume=
Learning multiple layers of features from tiny images , author=. Handbook of Systemic Autoimmune Diseases , volume=
-
[37]
arXiv preprint arXiv:1510.02855 , year=
AtomNet: a deep convolutional neural network for bioactivity prediction in structure-based drug discovery , author=. arXiv preprint arXiv:1510.02855 , year=
-
[38]
Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining , pages=
Structure-aware interactive graph neural networks for the prediction of protein-ligand binding affinity , author=. Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining , pages=
-
[39]
Proceedings of the AAAI Conference on Artificial Intelligence , pages=
Drugood: Out-of-distribution dataset curator and benchmark for ai-aided drug discovery--a focus on affinity prediction problems with noise annotations , author=. Proceedings of the AAAI Conference on Artificial Intelligence , pages=
-
[40]
Bioinformatics , volume=
PDB-wide collection of binding data: current status of the PDBbind database , author=. Bioinformatics , volume=
-
[41]
Nucleic acids research , volume=
BindingDB: a web-accessible database of experimentally determined protein--ligand binding affinities , author=. Nucleic acids research , volume=
-
[42]
Predicting structured data , volume=
A tutorial on energy-based learning , author=. Predicting structured data , volume=
-
[43]
Proceedings of the AAAI Conference on Artificial Intelligence , pages=
Learning set functions that are sparse in non-orthogonal Fourier bases , author=. Proceedings of the AAAI Conference on Artificial Intelligence , pages=
-
[44]
Advances in Neural Information Processing Systems , pages=
Neural estimation of submodular functions with applications to differentiable subset selection , author=. Advances in Neural Information Processing Systems , pages=
-
[45]
arXiv preprint arXiv:1701.08939 , year=
Deep submodular functions , author=. arXiv preprint arXiv:1701.08939 , year=
-
[46]
Advances in Neural Information Processing Systems , volume=
Deep submodular functions: Definitions and learning , author=. Advances in Neural Information Processing Systems , volume=
-
[47]
Advances in Neural Information Processing Systems , year=
Powerset convolutional neural networks , author=. Advances in Neural Information Processing Systems , year=
-
[48]
International Conference on Machine Learning , pages=
Learning iterative reasoning through energy minimization , author=. International Conference on Machine Learning , pages=
-
[49]
International Conference on Machine Learning , pages=
Learning Iterative Reasoning through Energy Diffusion , author=. International Conference on Machine Learning , pages=
-
[50]
arXiv preprint arXiv:2510.02300 , year=
Equilibrium Matching: Generative Modeling with Implicit Energy-Based Models , author=. arXiv preprint arXiv:2510.02300 , year=
-
[51]
International workshop on artificial intelligence and statistics , pages=
On contrastive divergence learning , author=. International workshop on artificial intelligence and statistics , pages=
-
[52]
, author=
Estimation of non-normalized statistical models by score matching. , author=. Journal of Machine Learning Research , volume=
-
[53]
Neural computation , volume=
A connection between score matching and denoising autoencoders , author=. Neural computation , volume=
-
[54]
Uncertainty in artificial intelligence , pages=
Sliced score matching: A scalable approach to density and score estimation , author=. Uncertainty in artificial intelligence , pages=
-
[55]
Proceedings of the 25th international conference on Machine learning , pages=
Training restricted Boltzmann machines using approximations to the likelihood gradient , author=. Proceedings of the 25th international conference on Machine learning , pages=
-
[56]
2017 , eprint=
Adam: A Method for Stochastic Optimization , author=. 2017 , eprint=
2017
-
[57]
arXiv preprint arXiv:1608.03983 , year=
Sgdr: Stochastic gradient descent with warm restarts , author=. arXiv preprint arXiv:1608.03983 , year=
-
[58]
arXiv preprint arXiv:1703.10603 , year=
Atomic convolutional networks for predicting protein-ligand binding affinity , author=. arXiv preprint arXiv:1703.10603 , year=
-
[59]
Bioinformatics , volume=
DeepDTA: deep drug--target binding affinity prediction , author=. Bioinformatics , volume=
-
[60]
Differentiable Learning of Submodular Models , year =
Djolonga, Josip and Krause, Andreas , booktitle =. Differentiable Learning of Submodular Models , year =
-
[61]
2024 , eprint=
Deep Submodular Peripteral Networks , author=. 2024 , eprint=
2024
-
[62]
2020 , eprint=
Deep Submodular Networks for Extractive Data Summarization , author=. 2020 , eprint=
2020
-
[63]
2020 , eprint=
Probabilistic symmetries and invariant neural networks , author=. 2020 , eprint=
2020
-
[64]
2020 , eprint=
On Learning Sets of Symmetric Elements , author=. 2020 , eprint=
2020
-
[65]
2024 , eprint=
A Unified Approach for Maximizing Continuous DR-submodular Functions , author=. 2024 , eprint=
2024
Reviewed July 14, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.