Difference-of-submodular Bregman Divergence

We thank you for your careful review and comments. We addressed your comments and questions below:

Trivial Solution of the Loss Function

The loss function $L$ is minimized for $f$, not for $(X_A, X_P, X_N)$; therefore, there may be no concern about falling into a trivial solution as suggested by your question. In the submitted version of our paper, we denoted the definition of the triplet loss as $L(X_A, X_P, X_N)$ even we want to minimize the loss with respect to $f$. We have updated the notation to make it less confusing (lines: 360-364). If we have misunderstood the intent of your concern, please let us know. Thank you for your question.

Architectures

Thank you for pointing it out. We have added details about the network architecture on line (lines: 351-359).

Taking Semigradients

For the supergradients, we use grow, shrink, and bar supergradients (Table 1). For the subgradients, we take the extreme point, which is also used in Iyer & Bilmes (2012b). The algorithm to take the subgradient was noted in Section 2.1 (lines: 137-140), but not in the section of the experiment. We have clarified it in Section 5 (lines: 367-369). Note that once a sequence of inputs (a sequence of coordinates in the case of point clouds) is given to a permutation-invariant NN $f_{\mathrm{NN}}$, $f_{\mathrm{NN}}$ can be regarded as merely a set function. Then, the subgradient and supergradient are calculated.

Rotation Invariance and Permutation Invariance

The method used to achieve permutation invariance does not guarantee rotational invariance. Therefore, the statement in question is a mistake in our description. Point cloud data is a set of unordered points, where the order of the points is meaningless. As such, it is desirable for a network processing point clouds to produce outputs that are invariant to changes in the input order. By using the PointNet implementation, we have achieved permutation invariance as originally intended. We have removed the sentences. Thank you for your question.

Suggested Citation

We have added the citation to Faust, Fauzi, Saunderson (2023) at Section 1 (lines:95-96). We overlooked that important paper. Thank you for your suggestion.

Why is the Result by the Bar-supergradient worse?

This is a good question. As seen in Table 1, the bar-supergradient $\bar{g}_Y$ is indeed defined independently on $Y$, unlike grow- and shrink-supergradients. Intuitively, this means the bar-supergradients cannot take the local information around $Y$ into account and it causes the performance degradation. We have added the discussion in Section 5.2 (lines: 462-466).

Benefit of Using Non-submodular Generating Functions

Consider $f = f^1 - f^2$ is modular, that is, $f = m$ holds for a modular function $m$. Then, the DBD (Eq. 9) is also modular. In this case, the DBD ultimately reduces to a simple set operation (and its weighting), and as pointed out in the introduction (lines: 46-50), its representational power becomes highly limited. To address this issue, we believe that defining set function divergences via submodular functions provides a fundamental solution.

Clarification about the Rand Index

Thank you for your suggestion. We have clarified that we used class labels as the reference clusters for computing the Rand index (lines: 450-453).

Revise the Statement

In l.213-218, I suggest replacing "a formal discussion on the well-definedness is lacked", which sounds vague

Thank you for your comment. We agree to your comment and have changed the representation (lines: 229-231).

Eratta

Thank you very much for carefully reviewing and pointing out these details. We have appropriately revised these points.

Again, thank you very much for your comments and questions.

We thank you for your careful review and comments. We addressed your comments and questions in turn.

Dependence on $Y$ of semigradients

The answer to this question is partially yes and partially no. While (strict) subgradients and supergradients generally depend on $Y$, they may also be determined independently of $Y$. In Table 1, the definitions of the shrink supergradient and grow supergradient depend on $Y$. Additionally, for subgradients, the algorithm mentioned in Section 2.1 (lines 137-140) for finding the extreme point also relies on $Y$. On the other hand, the bar supergradient, as defined in Table 1, does not depend on $Y$.

Clarity of Table 2

Thank you for pointing it out. In lines 450-453 we have clarified that the values of the rightmost column in Table 2 indicate the Rand index between the estimated clusters and the true class labels.

Difference from Iyer & Bilmes (2012a)

It is indeed correct that submodularity remains necessary. However, we believe that our introduction of the DS decomposition, which enhances the representational power, is a noteworthy contribution both theoretically (Theorem 3.4) and empirically (Table 2). Moreover, the PointNet model used in our implementation has been shown to possess universal approximation capabilities in the original paper (Qi et al., 2017). In our study, we fixed $\gamma$ in Definition 2.7 to ensure submodularity, but if PointNet retains sufficient representational power under this constraint, our DBD implementation using the two submodular functions $f^1$ and $f^2$ should enable representation of a broad class of set functions $f=f^1 - f^2$. Combined with our discussion on the definability of the (generalized) Bregman divergence for general set functions, we believe our proposed practical construction method offers a significant progress from the prior study.

Again, thank you very much for your comments.

Lack of Baseline Methods in the Set Retrieval Experiment

As an update feasible within the limited rebuttal period, we conducted a quantitative evaluation on the retrieval task using MVTN (Hamdi et al., 2021), considered SoTA, and its predecessor, DensePoint (Liu et al., 2019). The results have been added to Table 4 (Appendix C). The key findings are as follows:

• Despite not employing pretraining, complex hyperparameter tuning, or elaborate architecture design, our method outperformed DensePoint and achieved performance close to MVTN. This demonstrates that our DBD-based framework is sufficiently effective in practical scenarios.
• As in the set clustering task, the quantitative evaluation of the set retrieval task also showed that w/ decomposition ($f = f^1 - f^2$) outperformed w/o decomposition ($f = f^1$, which is effectively equivalent to the submodular Bregman divergence proposed by Iyer & Bilmes (2012b)).

Regarding the comment:

Figure 2 demonstrates the performance of the proposed Bregman divergence, but it is difficult to see how this new divergence improves upon previous divergences, such as those presented in [Iyer and Bilmes (2012a)].

We believe that the quantitative evaluations provide clear evidence of the superiority of our DBD over the work by Iyer & Bilmes (2012b).

Computational Time

To be honest, due to the time constraints of the rebuttal period and queueing issues with cloud computing resources, we were unable to measure precise wall-clock time in a unified computational environment.

As a reference, in our representative computational environment (Ubuntu 22.04 with 16 GiB RAM and 3.6 GHz 4 vCPUs, without GPU usage), the approximate computation times for learning the DBDs are as follows:

• MNIST: About 30 seconds per epoch, totaling approximately 100 minutes for 200 epochs.
• ModelNet40: About 80-100 seconds per epoch, totaling approximately 4.5-5.5 hours for 200 epochs.

These times include data loading overhead and reflect the lack of GPU acceleration and optimization in our implementation. With proper engineering and the use of GPUs, significant speedups are expected.

References

Abdullah Hamdi, Silvio Giancola, and Bernard Ghanem. MVTN: Multi-view transformation network for 3d shape recognition, ICCV2021. Yongcheng Liu, Bin Fan, Gaofeng Meng, Jiwen Lu, Shiming Xiang, and Chunhong Pan. Densepoint: Learning densely contextual representation for efficient point cloud processing, ICCV2019.

We thank you for your careful review and time. We addressed your comments and questions as below:

Lack of Motivation

In the introduction, we have presented numerous examples of how Bregman divergences appear in machine learning and statistics, particularly in continuous spaces. Given their foundational importance in these fields, we believe their significance is widely recognized and undisputed. Building on this established foundation, we believe that our attempt to apply Bregman divergences to discrete spaces and to consider its generalization with the practical meaningfulness is a natural and well-motivated approach. We hope this perspective clarifies the motivation and relevance of our approach.

Again, thank you very much for your review.

Firstly, we thank you for your careful review and comments. We addressed your comments and questions in turn.

Non-strict Submodularity of PointNet

This is a very essential question. Your concern is valid; a vanilla PointNet with ReLU in the final layer of the MLP does not satisfy strict submodularity. Initially, we used the vanilla PointNet for simplicity of explanation (and due to space constraints), but we agree that this may have caused some confusion. We are currently conducting experiments with the activation function changed to Softplus, which addresses the concern about strict submodularity.

Expressiveness of the DBD

the expressiveness of the new DBD is fully explored empirically

In response, we would like to clarify that this statement is not accurate. In Theorem 3.4, we demonstrate that the proposed DBD truly has superior representational power compared to the conventional submodular-Bregman divergence. We believe this theorem will likely address your concerns, so please have a look.

Again, thank you very much for your comments.

Non-strict Submodularity of PointNet (Contd.)

Initially, we attempted to address the issue of non-strict submodularity using the Softplus activation function, but we realized this was a misguided approach. Ultimately, we sought a fundamental solution to this issue through the following steps:

1. We defined an $\varepsilon$-PointNet architecture by replacing the max function in PointNet with the logsumexp function (i.e., $f_\varepsilon(\boldsymbol{x}) = \varepsilon \log \sum_i \exp (x_i / \varepsilon)$)⁡, which converges to vanilla PointNet in the limit as $\varepsilon \to 0$.
2. We proved that the $\varepsilon$-PointNet allows for the realization of a permutation-invariant NN that guarantees strict submodularity (Appendix B).
3. In the set clustering experiment, we added results for $\varepsilon=0$ (i.e., vanilla PointNet) and $\varepsilon=0.001$ (strictly submodular), showing experimentally that the latter achieves equal or better performance (Table 2).

Due to time constraints, we were unable to conduct experiments with $\varepsilon-PointNet$ on tasks other than set clustering. However, we believe that this update fundamentally addresses your concerns. Additionally, we added the set clustering results with the Softplus activation functions in Appendix C.

Expanding Experiments

Due to time constraints, we were unable to add experiments on new datasets or tasks. As a feasible alternative, we conducted additional baseline comparisons and quantitative evaluations on the retrieval task of the ModelNet40 dataset. The results show that our method achieves scores close to those of SoTA methods, despite not involving pretraining, complex hyperparameter tuning, or elaborate architecture design. We believe this reflects the practical strength of our DBD framework.

Furthermore, regarding your comment:

This will help gain more empirical evidence for the substantial gain in expressiveness across tasks and task complexities, and justify the use of DBD which requires more computational resources (two functions instead of one).

We would like to point out that the results labeled w/o decomposition in the tables correspond to the case where only a single function was used. Notably, as described in Section 5, "Network Architecture," despite w/o decomposition ($f = f^1$) having more weight parameters than w/ decomposition ($f = f^1 - f^2$), the quantitative evaluation results demonstrate that w/ decomposition achieves superior performance. We hope this clarifies your concerns.

We thank you for your insightful feedback and time. We addressed your requests as below:

Change the Title of the Paper

We changed the title of the paper from "Discrete Bregman Divergence" to "Difference-of-submodular Bregman Divergence." The revised title slightly differs from your suggestions, but we believe our changes are in line with your intention.

Revision of a Sentence

I think you may want to change the tone of lines 213-216 where you say "a formal discussion on the well-definedness is lacked" as that sounds a bit disparaging.

We can completely agree with your opinion. We changed the representation according to your suggestion (lines: 229-231). Thank you for pointing it out.

Add Citations

Thank you for pointing out the lack of related papers that should be mentioned. We added a paragraph at the end of Section 6 and cited the DSF and DSPN papers there.

Again, thank you very much for your comments.