- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper claims that previous ML literature lacks sample-efficient optimization methods that learn sparse logical rules that act on high-dimensional continuous data. As a motivation of this problem's relevance, it raises scientific and tabular regression and classification problems as an important instance where sparse functional structure that act on high-dimensional ambient input exist.
The paper assumes that these sparse functions often take a Boolean form as a low-degree disjunctive normal form (DNF), i.e. an OR aggregation of a few sparse AND-terms. The paper then claims that the low sample efficiency of previous optimizing sparse neural operators is because existing differentiable relaxations of sparse AND and OR operations have vanishing partial derivative norms as the input dimension grows. To substantiate this, it theoretically shows how the partial derivative of two previous AND relaxations vanishes with the input dimension .
To overcome this issue, it proposes to learn sparse logical AND through softmax and sparse logical OR through "softmin" (which is just softmax with sign-inverted weights), and aggregate these real-valued terms using a linear layer. It puts forward a theoretical result that the sample complexity to learn the correct sparse function with this optimization formulation would only grow logarithmically in the dimension of the input, while any inner-product based architecture (such as an MLP) would have a complexity that grows linearly with the input dimension.
Finally, it conduct a some experiments to substantiate this claim about superior sample complexity. It considers regression of several sparse boolean target functions, and compares the proposed architecture to two types of MLPs, a Transformer and XGBoost. On all of these benchmarks, XGBoost achieves the highest accuracy, closely followed by the author's tailored architecture and then followed by the MLPs and the transformer architecture with a wide margin. On other datasets that are not referenced, the latter architectures catch up and mostly close the margin.
All in all, I feel this paper is quite problematic, and I am sceptical about its value and faithfulness. I'll point out my concerns below.
Critical strengths
None
Critical weaknesses
1. The paper initially makes several claims that contradict my understanding of previous literature.
For example, it claims that only "two differentiable approximations of AND exist in the literature". This is outright wrong, there are several differentiable relaxations, and this paper even cites Petersen et al. (2022), who provides a comprehensive overview of them. What's worse, these two relaxations are hardly representative for the parametrizations that are used in current differentiable logic literature, which this paper again cites (e.g. Andronic et al. 2023, Andronic et al. 2024, Petersen et al. 2022).
Also, it does not mention recent advances in few-sample regression of tabular data. For example, TabPFN (Hollmann et al., 2023) advanced the state-of-the-art of sample efficiency in tabular datasets significantly.
1.1. The paper's claims about the benefits of their softmax AND-parametrization is questionable
Choosing softmax as a parametrization for sparse functions does not seem to benefit the magnitude of backpropagated gradients. While gradients in a linear layer are independently scaled by the corresponding weight , the gradient distribution of softmax will lead to imbalanced gradients where most inputs receive tiny fractions of the gradient norm. This is precisely the inverse of what the authors claim. softmax rescales and will shrink the gradient norm for most components, while a linear layer retains a dimension-independent partial derivative (i.e. the weight ).
2. The experimental evaluation does not match the paper's initial motivation The paper initially address tabular and scientific problems, where sparse logical rules would frequently appear. Their evaluation in the main paper however restricts on synthetic boolean functions and unreferenced(!) datasets. What's more, it does not outperform the XGBoost baseline even on these synthetic examples that are tailored to meet the design of their own architecture.
Questions for authors
- Where are the four "real-world datasets" in Table 1 from? Why have the authors chosen them and not some scientific or tabular datasets that they had initially put emphasis on?
- Why do the authors regard their method as a valuable contribution if XGBoost outperforms it even on the synthetic boolean functions that this paper adresses? In particular, the weaker performance of the architecture on low-dimensional parity functions might highlight a concerning potential shortcoming of the softmax relaxation of a sparse AND.
- In the light of XGBoost's superiority, why do the authors present their method as a particularly interpretable one? XGBoost remains more accurate and also more interpretable than any neural relaxation evaluated in this paper.
- Parametrizing a sparse AND through softmax does not seem quite stable to converge to a sparse AND of multiple(!) inputs. softmax was rather introduced to relax the maximum, i.e. the selection of a single value from many. This is however insufficient to approximate k-DNF with some learnability guarantees. Why have the authors made that choice?
- Why do the authors even keep the softmin parametrization for a soft OR when they eventually augment each input with its negation and thus achieve the functional completeness with the softmax AND already?
3 comments
Part 2/2
[W2, Q1, Q2, Q3] Do the datasets match the motivation, and why LNU if XGBoost is more accurate and interpretable? The real-world evaluation is on the tabular and scientific data the motivation names: the four datasets are referenced UCI benchmarks chosen for their logical target structure and cited in the Table 1 caption (Splice: Noordewier 1991, Section 5.2); all four are tabular, and Splice (DNA splice-junction recognition) is a scientific task. On these sets LNU's value does not rest on beating XGBoost, because it is a layer evaluated against the inner-product or FFN unit it replaces. XGBoost is a standalone learner: it wins the clean synthetic formulas (Table 1), and on the real-world sets held-out results put it ahead or tied on three of four (see the uKRJ reply, [W6, W8]). Against the unit it replaces, the MLP, LNU leads significantly on three of the same four sets (). For the same reason, its interpretability is of a different kind: LNU extracts an exact Boolean formula at from a layer inside a trained network, when its learned weights satisfy the dominance condition of Observation 4, which is a different capability from a post-hoc explanation of a standalone tree, not a claim to be more interpretable than one.
[Q2, parity] Does the weaker parity result show a flaw in the softmax relaxation? The weaker result on low-dimensional parity reflects training a single layer, not the soft-AND relaxation. One layer represents XOR, but parity gives no single literal a correlation with the label, so it is learned only partly, and only at small , and a second layer makes it learnable at low (see the TZ2v reply, [upper bound, XOR]).
[W1, Q5, clarification] Do only two AND relaxations exist, and what about TabPFN and soft-OR? There are many differentiable relaxations of AND; the two the submission names are the D-dimensional soft-AND aggregators it compares against, NLN and LNN, while the logic-gate and LUT family (Petersen 2022; Andronic 2023) uses small-fan-in gates, a different primitive, as Section 2 states. The revised PDF rewrites that sentence to say that many relaxations exist, including those gates, and cites TabPFN (Hollmann 2023) with tree ensembles as strong learners on tabular data (revised Section 1); LNU is a layer, compared against the unit it replaces. Soft-OR is not needed for completeness, since with complement augmentation soft-AND alone is functionally complete by De Morgan (Section 3.2); the ablation in Appendix E keeps it because AND+OR scores highest on the mixed MAJ target, though all three variants are within seed noise.
I thank the authors for some clarifications on the intent and meaning behind their statements.
Still, my assessment is unchanged. I do not recommend this paper for publication. The paper is still hardly readable for a human and its value is questionable.
I encourage the authors to present and evaluate their work more consistently, clearly and rigorously.
Part 1/2 (continued in the next comment)
We thank the reviewer for the detailed review and for the summary that the paper "theoretically shows" how the "partial derivative of two previous AND relaxations vanishes with the input dimension D". The reviewer's summary concern is being "sceptical about its value and faithfulness". The substantive points come first: the gradient and convergence questions in [W1.1, Q4], the datasets, the value of LNU next to XGBoost and interpretability in [W2, Q1, Q2, Q3], and the parity result in [Q2, parity]. The AND relaxations and TabPFN and the soft-OR unit are clarified together in [W1, Q5, clarification]. Results marked held-out use a protocol added in the revision: configuration and epoch are selected on a validation split, accuracy is reported on an untouched test split, and methods are compared over 10 seeds with paired Wilcoxon tests. In the revised PDF, revised and added text is shown in color.
[W1.1, Q4] Does the softmax AND help the gradients, and why use it for a multi-input AND? The paper's AND is the softmin, the minimum of the products of weight and input, and its imbalance is intended: it concentrates the gradient on the coordinate whose product is smallest. The per-coordinate derivative of a linear layer is its weight, as the reviewer notes, and does not shrink with D; what shrinks is that coordinate's share of the output gradient, which dilutes as O(1/D) because the layer sums over D coordinates (Proposition 2). Under the softmin the share of the coordinate that sets the minimum stays order 1 (revised Proposition 3). Table R1 measures this share directly.
Table R1. Share of the output gradient carried by the most relevant input coordinate at initialization (β=10, 400 random draws; revised Appendix J.25).
This concentration does not make the unit a single-input selector. The minimum is low whenever any one of its selected literals is low, so the unit computes a k-way AND over all of them, not the choice of a single value. On convergence, Theorem 4 is a sample-complexity result, not an SGD proof, and the submission shows convergence empirically: across 120 runs, recovery of the true multi-input support and accuracy correlate at 0.91 (Appendix J.1).