Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers the problem of learning submodular functions using neural networks. More precisely the paper considers two different settings.

1 - There exists an oracle that given a set $S$, responds with the value of the function $f$ for $S$.

2- There exists an oracle function that given a set $S$, returns $\argmax_{T\subseteq S} f(T)$.

The first setting is known as the value oracle in the literature and the second one can be simulated by demand oracle (put the price of infinity on any item not in set $S$). For the first setting, the goal is to minimize $\sum_{i \in [I]} (f(S) - F_\theta(S))$ over the parameters $\theta$ of a neural network. The paper proposes a specific class of submodular functions that arise from concave combination of modular functions in a recursive way and a neural network based on this class of functions. They deal with some issues for learning these functions such as permutation invariance in the input sets and dealing with the non-positivity of the second-order derivative. They also show that their approach can be extended to the class of $\alpha$-submodular functions and non-monotone submodular functions. The experiments also illustrates that on some synthetic data and a real-world dataset (Amazon baby registry dataset), they outperform other neural networks such as transformers, deep submodular functions, and deep sets.
strengths_and_weaknesses: The paper considers an interesting and fundamental problem. The paper is mostly written clearly and cleanly, but some discussions regarding the below topics could help understand its position in the literature better. 

I think the paper makes a good case regarding its approach, but I'm not sure if some of the empirical comparisons make sense. For example, my understanding is that the deep sets essentially suggest a layer of a neural network that guarantees invariance/equivariance for datasets comprising of sets. This does not give a specific neural network but rather can be used as a component of more complicated networks. I wonder how the suggested method would interact with such a layer to guarantee order invariance. Please let me know if there is an issue that prevents this combination. Another concern is that all of the considered functions are simple concave/submodular functions. I'm wondering how these methods would compare on more extreme examples. For example, one candidate could be the worst-case example mentioned in [1] to prove the lower bound for approximation submodular functions.

Moreover, some discussion on the learnability of the functions could improve the paper. For example, in Proposition 4, it is mentioned that there exists a neural network with a certain width to learn a certain submodular function, but there is no mention of the number of samples needed or the running time.
questions: - The characterization of \alpha-submodular functions described in Theorem 2 is very similar to the recently introduced notions of one-sided smoothness and meta-submodularity. Please see [2] and [3]. These notions also consider functions where the second-order derivative is bounded by some factor of the first-order derivative. Please add a discussion about the connections. Is this a special case of one-sided smoothness? I'm asking because the regularization with the size of the set is looser than $1/k$.

- What is exactly the objective function for the second setting with (perimeter-set, high-value-subset) setting. Is it some ordering function? Please add a discussion about this. I don't think it is clear in the paper.

Comments:

- I think it is worth mentioning in the paper that learning submodular functions with poly(n) number of value oracle queries is hard in the worst case. Please see [1].

- Moreover, some discussion on the difference of theoretical upper bounds and lower bounds of approximation for the two different setting considered in the paper is useful, i.e., value-oracle setting and demand oracle setting.

- In Line 84, “and” is repeated.

References:

[1] Goemans, Michel X., Nicholas JA Harvey, Satoru Iwata, and Vahab Mirrokni. "Approximating submodular functions everywhere." In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pp. 535-544. Society for Industrial and Applied Mathematics, 2009.

[2] Ghadiri, Mehrdad, Richard Santiago, and Bruce Shepherd. "Beyond submodular maximization via one-sided smoothness." In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1006-1025. 2021.

[3] Ghadiri, Mehrdad, Richard Santiago, and Bruce Shepherd. "A Parameterized Family of Meta-Submodular Functions." arXiv preprint arXiv:2006.13754 (2020).

limitations: The paper does not have any negative societal impact since it considers a fundamental problem.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes new families of submodular (and $\alpha$ approximate submodular) functions which can be parameterized efficiently by neural networks. Then the authors use this formulation to learn submodular functions given (set, value) examples. Additionally, they propose a new max-min method to learn to sample high-value subsets from a submodular function given (perimeter-set, high-value subset) examples. The inner min objective uses a Gumbel-Sinkhorn network to encourage permutation invariance.
strengths_and_weaknesses: ## Originality
- Novel combination of previous work (Deep Submodular Functions, Gumbel-Sinkhorn NNs, Unconstrained Monotonic NNs) with new insights and techniques. 
- Cites previous related work where appropriate, except that Reference [42] in the Appendix does not appear in main paper

## Quality
- Several technical contributions: parameterizing (alpha) submodular functions efficiently, max-min formulation of selecting a greedy sequence via adversarial permutation
- Experimental results look impressive, but I have some concerns with experimental setup/evaluation of baseline methods:
    - For experiments involving with set transformer, using a batch size less than 66 could have reduced gpu memory consumption
    - On the Amazon baby registry dataset, can still use other baselines such as set transformer to predict the next element, even if submodularity is not enforced
    - The paper would be stronger if it evaluated performance in additional ways; for example, training time and sample complexity
    - Unclear why NDCG is an appropriate metric when it depends on order. The problem is designed to be permutation invariant

## Significance
- This paper presents interesting, potentially high-impact ideas for an important, relevant problem of learning submodular functions from data.
- In addition to the 2 planted $\alpha$-submodular set functions, the paper would be improved if it motivated this family of functions with practical applications

## Clarity
- This paper is organized well and is generally a pleasure to read
- While the theoretical details are quite clear, there are many missing details from the experimental evaluation. For example, no details on how the max-min objective is trained. Also it is somewhat unclear how the product recommendation dataset is converted into a (perimeter set, high-value subset) format.
- Note that some references such as [1] use $1 - \alpha$ in the definition of approximate submodularity.


[1]  Gatmiry and Gomez Rodriguez. Non-submodular Function Maximization subject to a Matroid Constraint, with Applications. https://arxiv.org/abs/1811.07863
questions: - How wide is each FlexSubNet layer? More generally, how many parameters does FlexSubNet have compared to baselines?
- The hyperparameter configuration looks very similar across most methods, how were these selected? If cross validation, what was the range of values for $N$, $\alpha$, number of hidden layers, etc.
- What values of $\alpha$ do ground truth planted set functions (v) and (vi) have?
- In Table 2, is N=1 with Decoupling or End-end?
- When using the Amazon baby registry dataset, how large are the sampled sets and prefixes?
limitations: The authors could have commented on the tradeoff between using (set, value) and (perimeter-set, high-value subset) datasets. The latter appears to have a higher risk of introducing bias into the learned model
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper propose a family of neural models for monotone and non-monotone submodular functions and monotone approximately submodular functions, which can be estimated both from (set, value) observations and (perimeter-set, high-value subset) observations. The model proposed for monotone submodular functions consists of recursively applying an increasing concave activation function on a linear combination of the submodular function from the previous step and a positive modular function. This model is extended to a class of monotone approximately submodular functions by replacing the increasing concave activation function by an activation function satisfying a second-order differential inequality (which is stricter than concavity). The model proposed for non-monotone submodular functions consists of the composition of a concave activation function (not necessarily increasing) on only one positive modular function. Unlike prior work which use a fixed concave function, the authors choose to model the concave activation functions using a neural network which involve double integrals and propose methods to train it.  The authors also propose an order-invariant greedy sampling method for learning set functions from (perimeter-set, high-value subset) observations based on a max-min game between an adversarial permutation generator and the set function learner. Finally, they present some experiments showing that their models outperform other baselines in both supervision settings.
strengths_and_weaknesses: 
Strengths:
- Designing a practical method for learning submodular and approximately submodular functions is useful for a number of ML applications.
- Proposing a neural network model for the concave activation function which can be learned from data is a good alternative to having to choose a fixed one.
- Paper is well written with clearly presented results

Weaknesses:
- Unlike some prior work, the proposed models are only shown to be good estimators of monotone submodular function of the form of concave composed modular function, which is too limited.
- The proposed model for non-monotone submodular functions is too simple to capture complex functions.
- The empirical comparison with the deep submodular function (DSF) baseline is limited (see questions).
- Missing related work: 

	Balcan, Maria-Florina, and Nicholas JA Harvey. Submodular functions: Learnability, structure, and optimization. SIAM Journal on Computing 47.3: 703-754, 2018.

	Vitaly Feldman and Jan Vondrak. Optimal bounds on approximation of submodular and xos functions by juntas. SIAM Journal on Computing, 45(3):1129–1170, 2016. 

	R. Sipos, P. Shivaswamy, and T. Joachims. Large-margin learning of submodular summarization mod- els. In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 224–233. Association for Computational Linguistics, 2012.
questions: - For a more fair comparison with the DSF baseline, it would be good to consider few other popular choices for the concave function.
- How are high-value subsets chosen in the Amazon baby registry dataset?
limitations: Authors discuss limitations of their work in Appendix A, but do not discuss potential negative societal impact.
review_title: null

Meta-review: metareview: All 3 knowledgable reviewers recommended acceptance of the paper and had active discussions with the authors. I agree, that the paper makes several interesting and relevant contributions and suggest acceptance of the paper. Please consider the reviewers' comments when preparing the final version of the paper. 
confidence: Certain
Decision: Accept