LapSum - One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection

Thank you for your detailed review and constructive suggestions for improving our paper.

1. Applications of our method

   Our paper introduces several applications including top-k learning, soft ranking, sorting, and permutation learning. To address your request for concrete examples:

   • Vector Quantized-VAE models can directly leverage our differentiable sorting approach in their codebook optimization process, improving representation learning efficiency.

   • Large Language Models benefit from our ranking method when analyzing token distributions and building optimized dictionaries, enabling more effective model analysis and interpretation. Finding the dictionary of a trained Transformer dictionary provides a method for its deeper analysis.

   We have included pseudocode for the LapSum model in Appendix A, designed for straightforward implementation. Additionally, the attached code contains complete implementations in both PyTorch and CUDA, with performance competitive with existing methods.

2. Experiments

   While our paper focused primarily on classification applications, we will expand the experimental section to include soft ranking and sorting evaluations. These additions will demonstrate that LapSum provides a unified approach applicable across all differentiable soft ordering problems. The results will show comparable or superior performance to specialized methods while maintaining our closed-form advantages. Link to figures with comparison of ranking and sorting solutions.

Results for sorting methods on forward (CPU, 10* - space dimension):

Results for ranking methods on forward (CPU, 10* - space dimension):

We appreciate your thoughtful feedback and believe these clarifications and additions will strengthen the paper considerably.

Thank you for your thoughtful review of our paper.

1. Related references

   We appreciate your suggestions regarding additional references. Our literature review focused primarily on differentiable soft ordering, ranking, sorting, and top-k methods as addressed in works by Cuturi, Lapin, Berrada, Petersen, Blondel, and others (all included in bibliography). While our primary aim was to propose a new theoretically well-founded and computationally efficient tool to compare with these approaches, we acknowledge the importance of gradient boosting stochastic smoothing methods and Plackett-Luce based models. We will include these references in our revised manuscript.

2. Experiments

   For direct comparisons, we utilized applications addressed in existing literature, such as top-k classification and permutation matrix classification, particularly in high-dimensional spaces. While the additional datasets you suggest are very valuable, incorporating them would extend beyond our current scope. We plan to evaluate our framework on a wider range of applications in future work.

   Regarding experimental setup, we followed protocols established in the aforementioned literature to ensure direct compatibility, as our main goal was to develop a well-grounded and computationally effective tool. The direct comparisons with boosting approaches are in plans for our research.

   We have not included soft ranking due to limited availability of solutions with probability values. However, we have defined the LapSum approach for both ranking and sorting tasks and will include these results in the final version. Link to figures with comparison of ranking and sorting solutions.

Results for sorting methods on forward (CPU, 10* - space dimension):

Results for ranking methods on forward (CPU, 10* - space dimension):

3. Theoretical claims

   Thank you for recommending a more formal definition connecting ranking to the CDF. We will incorporate this description to improve clarity, following your recommended approach. A key advantage of LapSum is its theoretically elegant closed-form solution, naturally not forgetting its computational efficiency. This non-iterative approach provides enhanced stability compared to existing methods that rely on iterative processes.

4. Other concerns and concluding remarks

   We believe we have addressed your primary concerns and will implement the suggested improvements in our final manuscript. In the revised version, we will add the missing references to better describe the related research field, include a formal description of ranking and CDF, and more clearly articulate the impact of our proposal on the field.

Thank you for your very careful reading and insightful review of our paper. We address your questions as follows:

1. Why haven't we considered sorting and ranking applications?

   Our research focused on designing an efficient model with a closed form for soft ordering tasks, and we defined models for both ranking and sorting. For applications, we deliberately aligned with Petersen's established framework to facilitate meaningful comparisons. Our experimental scope was partially constrained by implementations that allow cross-entropy loss value comparisons. Nevertheless, we conducted experiments for both sorting and ranking using LapSum, achieving results comparable to existing solutions. These will be included in the final version. Link to figures with comparison of ranking and sorting solutions.

Results for sorting methods on forward (CPU, 10* - space dimension):

Results for ranking methods on forward (CPU, 10* - space dimension):

2. Justification for using our model over Xie's given comparable computation time and memory

   While both models demonstrate similar computational efficiency as shown in our statistical tests (Figures 5, 7), LapSum outperforms Xie's model in all but one test. Both methods offer high accuracy (important in application, as Xie notes) and handle all derivatives effectively. However, the key advantage of our approach is its closed-form solution, whereas Xie's method relies on an iterative approach for both the model and its derivatives. This closed-form formulation provides theoretical elegance and potentially better stability in complex applications.

3. Missing reference to Berthet's paper

   We acknowledge the omission of Berthet et al. 2020 "Learning with differentiable..." paper. While we referenced a Blondel et al. 2020 "Fast differentiable..." paper which addresses related solutions, we will include Berthet's work in our final version, as it aligns very well with our approach and provides excellent context on related research.

4. Theoretical claims

   Thank you for your detailed analysis. We confirm that:

   • The definition in line 154 should indeed be $(F-Rank_\alpha(r))_k$ and will be corrected. In later lines, where some indices may be obvious, we shall note it clearly.
   • For $F-Sort_\alpha$ (line 125), we will add a footnote clarifying that $r$ in the definition is the default parameter.
   • In Theorem 3.2 proof the ${1}\over{2}$ is the value of $F_\alpha$ function at $0$, see e.g. Fig.2. The mismatch between the formulation and proof of the theorem is a typo to be corrected.
   • The proof for $F-Sort_\alpha$ is very similar, and we can add it in the final version.

5. Experimental issues

   We appreciate your positive assessment of our experimental flow. Regarding standard deviations in experiment tables: we relied on published results from other researchers where original code wasn't always available. Reimplementing these approaches would introduce potential inconsistencies and errors. Consequently, we cannot provide deviation values at this stage but acknowledge this as an area for future work.

6. Potential overstatement in abstract

   Our intention was to emphasize that our tool is theoretically sound, offers a closed-form solution, and is computationally competitive for high-dimensional spaces. The wording was not meant to imply superiority but rather computational competitiveness. We will revise this to better reflect our position.

7. Typographical errors

   We will correct all identified typos (as addressed above) to improve clarity. Regarding "doubly stochastic matrix" we were referring to permutation matrices $P_{k,c}$ that are both row- and column-stochastic, as described in Petersen 2022 "Differentiable top-k..." The $n$ and $k$ in the introduction denote the space dimension and the number of top values to be selected — this shall be clarified. Thank you for careful reading.