Bridging Jensen Gap for Max-Min Group Fairness Optimization in Recommendation

Thanks for your hard work and valuable questions.

W1. It'd be helpful if the authors could provide more interpretations for Theorem 4, the main theoretical result and, in particular, comment on their technical contributions. What is the main technical novelty in attaining this theoretical result? A proof sketch could also be helpful.

• A1: The main technical novelty lies in transforming the Jansen gap problem into its dual form and leveraging dual gradient learning techniques to bound the complementary slackness and establish the theoretical bounds. Next is the proof sketch:

Firstly, we write the dual form of the Jansen gap:

$J(B) = |\sum_{j=1}^Nw({\mu}^j)-w({\mu})|$ and $w({\mu}^j)= ({\mu}^j)^{\top}({e}-({A}^j)^{\top}{l}^j)$

Then we utilize the online gradient descent to bound the complementary slackness of $w({\mu}^j)$: The gradient of $w({\mu}^j)$ can be bounded as $\|\widetilde{{g}}^j\|_2^2 \leq L|\mathcal{G}|^2$.

Finally, we put them together will have our conclusion. We will re-organize the proof and state the main technical novelty.

W2: Following the point above, in the numerical experiments, there appears to be some non-monotonic variation of the Jensen gap w.r.t. the batch size. I wonder if the authors can comment on why this is the case. Is this consistent with the theoretical results?

• A2: Thanks for the question.

Firstly, our previous monotonic variation of the Jensen gap w.r.t. the batch size is based on ideal fairness aware algorithms. However, in real algorithms, some bias (e.g. gradient and online bias) will influence the process, making it not strict monotonic.

Secondly, our theoretical results provide an upper bound on the Jansen gap, and we observe that the Jansen gap in our method exhibits a monotonic trend with respect to batch size and group size. This aligns with the theoretical results, as the theory does not strictly require the gap to be perfectly monotonic.

W3: Could the results extend to alternative fairness constraints beyond max-min fairness?

• A3: Thanks for the question. In Theorem 1, we demonstrate that our optimization objective is equivalent to the power-family fairness framework, which encompasses mainstream fairness definitions such as Entropy Fairness, $\alpha$-Fairness, and Theil Index [1]. Consequently, our method is highly adaptable and can be generalized to various fairness objectives within this framework.

We also test the performances of other fairness metric Gini Index Compared to the baselines (Table 1) on MIND datasets. Note smaller Gini Index means more fairness.

From the results, we can observe that our model can still perform good on other fairness metrics.

We believe our paper can help other researchers explore its applicability to various loss functions, and other fairness metrics, which is also our contributions to the communities.

[1] Lan, T., & Chiang, M. (2011). An axiomatic theory of fairness in resource allocation. George Washington University, http://www. seas. gwu. edu/tlan/papers/fairness. pdf, Tech. Rep.

W4: What is the computational complexity of the proposed algorithm and how does it compare with the other baselines?

• A4: Thanks for the question.

Firstly, we all have parameters of the same magnitude (i.e., group size parameters, which are in the range of hundreds and negligible compared to the backbone). Our method only requires additional space for Q item embeddings and extra training time (Q * 1.5s). Applications can trade off Q based on available resources:

Secondly, as mentioned in Table 3 of the original paper, although there is an additional time overhead per round, our convergence speed accelerates by 30% compared to the best baseline. This 30% improvement in convergence speed is highly significant for industrial applications, along with enhanced performance.

We will add the discussion in the revised paper. Thanks for your question again.

W1: I suggest the authors to add state-of-the-art baselines in optimization-based methods mentioned in the paper.

• A1: We involve four baselines covered from optimizing-based methods, and group fair-aware recommendation methods. Note FOCF, Reg is designed for the non-LLMs RS models and FairNeg is designed for the pair-wise RS models. We conduct experiments on different LLMs and non-LLMs backbones on MIND dataset.

[1] Max-min sample: applies optimizing techniques to dynamically sample groups. [2] FOCF: applies a fair-aware regularization loss of different groups into non-LLMs RS. [3] Reg: Penalizes the squared difference between the average scores of two groups for all positive user-item pairs into non-LLMs RS. [4] FairNeg: A negative sampling way for pair-wise recommendation into non-LLMs RS.

For MIND dataset

For Amazon-book dataset

BPR[5] backbones:

The results of GRU4Rec [6]:

For the results of SASRec [7]:

From the results, we can also see that our model can outperform all the baselines except MMF@5 in SASRec, showing our effectiveness on non-LLMs RS models.

[1] J. D. Abernethy, et al.. Active sampling for min-max fairness. [2] Yao sirui et al. Beyond parity: Fairness objectives for collaborative filtering. [3] Toshihiro Kamishima and Shotaro Akaho. 2017. Considerations on recommendation independence for a find-good-items task. [4] Chen, Xiao, et al. Fairly Adaptive Negative Sampling for Recommendations. [5] Steffen Rendle et al. "BPR: Bayesian Personalized Ranking from Implicit Feedback.". [6] Yong Kiam Tan et al. "Improved Recurrent Neural Networks for Session-based Recommendations.". [7] Wang-Cheng Kang et al. "Self-Attentive Sequential Recommendation.".

W1: The assumption of convexity is too strong and impractical for large-scale recommendation models.

• A1: Sorry for the confusion. We do not assume that all functions are convex; rather, we only assume that the optimization objective loss function is convex, which allows it to be transformed into its dual form. Common recommendation objectives, including BCE loss, Entropy loss, and BPR loss, all exhibit convexity. We will clarify and re-state this assumption regarding convexity.

W2: Why can the reported NDCG exceed 1, which is theoretically impossible? Also, please specify the number of items in the truncated list K.

• A2: Sorry for the confusion.

For the first question, in caption (line 400) of Table 1 and Table 2, we state that all the numbers with “%” omitted, which means 1.15 in the Table means 1.15%. Since we evaluate the performance with full ranking (after filtering, for MIND, we rank nearly 1000 items and for Amazon dataset, we rank nearly 4000 items), which will make our ndcg and mrr be this kinds of magnitude [1].

For the second question, The truncated $K$ number in the table denotes the top-$K$, for example, top5 means $K=5$. We will modify the table $top5$ into $K=5$. Thanks for your suggestions.

[1] K. Bao, J. Zhang, W. Wang, Y. Zhang, Z. Yang, Y. Luo, F. Feng, X. He, and Q. Tian. A bi-step grounding paradigm for large language models in recommendation systems. arXiv preprint arXiv:2308.08434, 2023a.

Thank you for sharing your detailed and insightful questions and suggestions, they really help us to improve our paper.

Q1: In the proof of Theorem 1 (Appendix A), why is Problem (15) equivalent to Problem (2). Providing an explicit solution for $t$ and $b$ is important for Theorems 1 and 2.

• A1: Thanks for the question.

Following the same definition $g(x;k;s)=(k^{\top}x^{1+s})^{\frac{1}{1+s}}$, in Problem (15), we have the simplified form ${\gamma}^{\top}x + \lambda\min({\gamma}^{\top}x)=g(x;{\gamma};0) + \lambda g(x;{\gamma};-\infty)$.

In such a way, $b=\gamma^{\frac{1}{1+s}}$.

However, the specific value of $t$ is an implicit function and cannot be solved explicitly in closed form. This is because according to the fact that the function $g$ is continuous with respect to $s$ over its entire domain and based on the intermediate value theorem for continuous functions, there must exist a $t$ such that the linear combination of the linear functions at the two endpoints equals.

Nonetheless, we emphasize that the subsequent methods and proof strategies are independent of the explicit solution for t. As long as there exists a $t\neq0$, the Jansen gap exists, and as $\lambda$ increases, $t$ will also increase. We will include the discussion into the Theorem statements, meanwhile, we ensure our proof conclusion remain the valid.

Q2: The organization of Lemma 2, Lemma 3, and Theorem 3 (Appendix D-F) is somewhat disorganized. Place Lemma 3 before Lemma 2 and rewrite the proof of Lemma 2 to explain why the conclusion can be derived.

• A2: Thanks for the suggestions.

For the first question, we will place Lemma 3 before Lemma 2.

For the second question, we will re-write the beginning of the Lemma 2 as: after we get the conclusion from Lemma 3, we will have $r(\mu)<\infty$. Then we will proof for any $b\in M, c>0$, we have $r(\mu+cb)<\infty$. The rest of the parts remain the same.

Q3: The authors should provide some intuitive explanations for the weight sg to better elucidate the experimental phenomena (Case study in Section 6.3). For instance, under what circumstances is $s_g$ larger, and when is it smaller?

• A3: Thanks for the suggestions.

Intutively, $s_g=1-\mu_g$ is the negative showadow prices. In Lines 298-303, the high shadow price $\mu_g$ indicates that this constraint is the primary factor constraining accuracy optimization. Conversely, a low or zero shadow price suggests that the fairness constraint currently imposes little restriction on accuracy.

We will revise the description to clarify the meaning of $s_g$​, indicating that a high $s_g$​ signifies that this constraint is the primary factor limiting fairness optimization for group $g$, whereas a low or zero $s_g$​ implies that the accuracy constraint for group $g$ currently has little impact on the overall optimization. Additionally, we will revisit this concept in the case study presented in Section 6.3.

Q4: Can the authors provide a theoretical analysis of this bias? Alternatively, could the authors change the sampling-based ranking to random sampling, and test the impact of this bias on the convergence rate of Jensen gap?

• A4: Intuitively, a larger Q provides a more accurate gradient estimation but also incurs higher computational costs. We have conducted experiments to evaluate the impact of Q and will present the results. The results were conducted under the same settings of analysis section.

From the results, we observe that increasing the sample value Q leads to improvements in both accuracy and fairness performance. However, in LLM-based recommender systems, a larger Q significantly increases training time (with each item requiring an additional 1.5 seconds) and storage space. Different applications should select appropriate Q values based on their specific accuracy, fairness requirements, and computational constraints. We will include these experimental results and discussion in the Appendix.

W3.3 Recommendation models related to large language models, and more research lines of fair recommendation methods mentioned in related work should be included as baselines.

• A3.3: Thank you for your suggestions. You are correct that our backbone models do not necessarily need to be LLMs; we use LLMs in this case because the small batch size poses greater challenges for LLM-based recommender models in addressing the Jansen gaps.

As mentioned in previous responses, we add three most widely used non-LLMs-based recommendation backbones (BPR [1], GRU4Rec [2], SASRec [3]) on MIND dataset to show our methods are effective in a general setting. We already report the results on BPR in previous responses.

The results of GRU4Rec:

For the results of SASRec:

From the results, we can also see that our model can outperform all the baselines except MMF@5 in SASRec, showing our effectiveness on non-LLMs RS models. We will add the results in the main body of the revised paper.

Thanks again for your question and suggestions.

W3.1: The current description of the implementation details is oversimplified, which is not conducive to reproducibility. Secondly, $\lambda$ is mentioned to range from 0 to 5, but in Figure 3 it is inclusive of 0 to 10.

• A3.1: Sorry for the confusion.

For the first question, we will add the following implementation details in the Appendix of revised version to help readers to reproduce our results:

(1) For the environment, our experiments were implemented using Python 3.9 and PyTorch 2.0.1+cu117. All experiments were conducted on a server with an NVIDIA A5000 running Ubuntu 18.04.

(2) The pre-processing steps are detailed in Appendix H. For the missing hyper-parameters, we tune sample number $Q\in [50, 400]$ (results show in the previous responses), historical length $H\in [3,7]$ (results show in Table 4), freeze parameter updating gap $\beta\in[128, 3840]$.

(3) To mitigate the impact of randomness, we set the temperature coefficient to 0.2 for the LLM and ran each model three times, taking the average of the results. Other LLMs settings are: the penalty for frequency is 0.0, and the penalty for presence is 0.0, the maximum generated token number to 1024.

(4) For the Non-LLMs-RS backbones, we mainly reference the RecBole toolkit (https://github.com/RUCAIBox/RecBole). For the LLMs tuning, we reference the BigRec pipelines (https://github.com/SAI990323/BIGRec). And we have also included our code in the supplementary materials to ensure reproducibility.

For the second question, we are sorry for the typo, the $\lambda$ should be tuned among [0,10]. We will revise it accordingly.

W3.2 Representative datasets adopted by many previous fairness recommendation methods should be included more. Baselines are confusing and not sufficiently representative.

• A3.2 Thanks for the question, as mentioned in summary, we add a representative dataset Amazon-Electronic [4] tested on all baselines and our method to the effectiveness of our methods and involve four baselines covered from optimizing-based methods, and group fair-aware recommendation methods: : Max-min sample[5], FOCF [6], Reg[7] and FairNeg [8]. Note FOCF, Reg is designed for the non-LLMs RS models and FairNeg is designed for the pair-wise RS models.

For new dataset Amazon-Electronic, we test on the most advanced model BigRec, and the following is the results:

For other two dataset, the following is the new baseline results:

For MIND dataset

For Amazon-book dataset

From the results, we can also see that our model can outperform all the baselines, showing our effectiveness. We will add the results in the main body of the revised paper.

For other baselines FOCF, Reg and FairNeg, we compare them in the following non-LLM backbone model experiments.

W1.1: For Formula 1, the meaning of the symbol $n_i$ seems missing. Why is it emphasized that there are users with more than K interactions? Why must the most recent K interactions be kept instead of other numbers?

• A1.1: Apologies for the confusion.

$n_i$ is defined in line 129, representing the number of groups to which item $i$ belongs. We will recall this definition when introducing Formula 1 for clarity.

For the $K$ interactions, apologies for the confusion in notation. $K$ should be replaced with another parameter $H$, which represents the truncated user historical behavior numbers. We have conducted experiments (see Table 4 in the appendix) to demonstrate performance changes with respect to $H$. We will make the necessary corrections.

W1.2: Dividing the |U| users into |U|/B batches and performing gradient descent methods on each batch” is also confusing. In my experience, each batch only contains a subset of users, and all interactions of each user are included. Secondly, the following description seems to use a random batch sampling, which is unclear.

• A1.2: Sorry for the confusion.

For the first question, we indeed use the settings you mentioned: each batch contains only a subset of users, and all interactions are utilized. Here, we simply wanted to emphasize that in each epoch, we apply random batch sampling with a batch size of B. To clarify, we will revise the sentence to: We apply the regular mini-batch sampling strategy with a batch size of B.

Secondly, we emphasize this aspect because our algorithm does not depend on the order in which users arrive, unlike other debiasing online learning algorithms that may require specific user training sequences. We will compare our approach with existing methods and highlight that our algorithm can be seamlessly integrated into regular mini-batch strategies, offering broader applicability.

W1.3: Regarding the second paragraph of Section 4.2 and Figure 1, as far as I understand, the convergence of the same group should be examined under different batch sizes to obtain the desired observations and conclusions.

• A1.3: Thank you for your suggestions. Figure 1(a) was conducted with the same group size (G=7) under different batch sizes, while Figure 1(b) was conducted with the same batch size (B=32) under different group sizes. We will include these details in the experimental descriptions for better clarity.

W1.4: For the last paragraph of Section 5.2.1, the meaning of P is missing.

• A1.4: Apologies for the confusion. $P(w)$ refers to the predicted probability of the word $w$ generated by the LLMs. We will clarify this in the revised version.

W1.5: Based on the current description of Section 5.2.2, I can't find any instructions on handling the first batch since it lacks a pre-batch to compute $g$. Secondly, does the operation of sampling Q items bring noise or instability? This requires more discussion and experimental analysis.

• A1.5: Sorry for the confusion.

For the first question, in Algorithm 1 line 7, we initialize $g$ as 0, which will not make an effect on first batch. We will illustrate it in Section 5.2.2.

For the second question, intuitively, a larger Q provides a more accurate gradient estimation but also incurs higher computational costs. We have conducted experiments to evaluate the impact of Q and will present the results. The results were conducted under the same settings of analysis section.

From the results, we observe that increasing the sample value Q leads to improvements in both accuracy and fairness performance. However, in LLM-based recommender systems, a larger Q significantly increases training time (with each item requiring an additional 1.5 seconds) and storage space. Different applications should select appropriate Q values based on their specific accuracy, fairness requirements, and computational constraints. We will include these experimental results and discuss them in the appendix.

W1.6: The current placement of figures and tables does not facilitate reading and needs to be placed as close to the corresponding description as possible.

• A1.6: Thanks for your suggestions! We will put the figures and tables more close to the corresponding description as possible in the revised version.

Thank you for sharing your detailed and insightful questions and suggestions, they really help us to improve our paper.

Firstly, we will summarize our changes in the rebuttal as follows:

(1) We recheck and review our quality and clarity of the presentation according to your questions.

(2) For the deeper and more valuable insights, we conduct the following discussion and rebuttal

• We involve more discussion about our method is highly adaptable and can be generalized to various group fairness form.
• We conduct the experiments on other loss functions and fairness metrics. The experiments also verify the effectiveness of our methods.

(3) For the experimental setup and results:

• We add three most widely used non-LLMs-based recommendation backbones (BPR [1], GRU4Rec [2], SASRec [3]) on MIND dataset to show our methods are effective in a general setting.

• We also add a representative dataset Amazon-Electronic [4] tested on all baselines and our method to the effectiveness of our methods.

• We involve four baselines covered from optimizing-based methods, and group fair-aware recommendation methods. Note that group fair-aware recommendation models cannot well adapted into LLMs-based recommender models since they are often developed under pair-wise form of recommendation [1].

Optimizing-based baselines: [5] Max-min sample: applies optimizing techniques to dynamically sample groups. [6] FOCF: applies a fair-aware regularization loss of different groups into non-LLMs RS.

Group fair-aware methods in recommendation: [7] Reg: Penalizes the squared diference between the average scores of two groups for all positive user-item pairs into non-LLMs RS. [8] FairNeg: A negative sampling way for pair-wise recommendation into non-LLMs RS.

• We conduct more analysis about the sample number $Q$, storage space, complexity, and parameter size.

Secondly, we want to emphasize that our paper primarily addresses the significant yet often overlooked bias (Jensen gap) that arises when optimizing fairness objectives in recommendation systems. We thoroughly analyze the reasons behind this bias and propose FairDual, a well-generalized and efficient algorithm to bridge the Jensen gap. Our approach is validated across three diverse datasets and six state-of-the-art backbones, compared against various types of baselines. We believe our paper can help other researchers explore its applicability to various loss functions, objectives, and fairness concepts.

In summary, we kindly ask you to consider both our theoretical contributions and real-industrial applications for the fairness communities. In the following responses, we will address your question one by one to ensure clarity and thoroughness.

[1] Steffen Rendle et al. "BPR: Bayesian Personalized Ranking from Implicit Feedback." in UAI 2009. [2] Yong Kiam Tan et al. "Improved Recurrent Neural Networks for Session-based Recommendations." in DLRS 2016. [3] Wang-Cheng Kang et al. "Self-Attentive Sequential Recommendation." in ICDM 2018. [4] R. He and J. McAuley. Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. [5] J. D. Abernethy, P. Awasthi, M. Kleindessner, J. Morgenstern, C. Russell, and J. Zhang. Active sampling for min-max fairness in ICML 2022. [6] Yao sirui et al. Beyond parity: Fairness objectives for collaborative filtering in Neurips 2017. [7] Toshihiro Kamishima and Shotaro Akaho. 2017. Considerations on recommendation independence for a find-good-items task. [8] Chen, Xiao et al. Fairly Adaptive Negative Sampling for Recommendations in WWW 2023.

Dear reviewer REQg,

As the discussion deadline will end in less than three days, we would like to know whether our responses have adequately addressed your concerns. Please do not hesitate to reach out if you have any further questions or need clarification before the deadline. We greatly appreciate your dedicated time and effort in reviewing our work.

Best regards,

Authors

Dear reviewer,

Thanks a lot for your hard work and your suggestions. It really helps us improve our paper.

Thank you for your suggestion regarding re-polishing the paper and placing additional experiments. In the revised version, we will refine the entire paper, include the efficiency experiments in the main text, and move the non-LLM experiments to the Appendix.

For the second concern, (1) Our three datasets, MIND and Amazon, are industrial-scale datasets that can also be utilized for click-through rate prediction tasks [1]. Additionally, our efficiency experiments demonstrate that our methods are suitable for industrial-scale applications.

(2) Typically, recommendation systems involve several key tasks, such as rating prediction, click-through rate prediction, and ranking tasks [2]. In this paper, we primarily focus on fair ranking tasks (Section 3 Formulation), which are crucial and among the most widely used applications [3]. In the revised version, we place greater emphasis on the ranking task settings. Moreover, we want to emphasize that our methods can also be easily extended to other tasks, as mentioned in our previous responses, which we believe will provide significant inspiration to the research community.

For the minor concerns:

Q1: Is the added BPR baseline based on the original form of matrix factorization? A1: Yes, the original BPR model is based on matrix factorization, we will emphasize it in the revised version.

Q2: some recommendation models based on large language models are compatible with pairwise losses. A2: Due to the substantial computational costs of LLMs, recent LLM-based RS are often trained on small subsets of data, whereas traditional models can be trained on full datasets, often achieving comparable performance to LLMs on certain datasets, as noted in [4].

In summary, we want to emphasize that, in accordance with ICLR policy, the evaluation should be based on the revised version, and we assure you that your new concerns regarding content organization and clarifications will be appropriately addressed in the camera-ready version (if accepted). We kindly ask you to consider both our contributions for identifying and mitigating the ignoring Jensen gap for the fairness and RS communities. We believe our paper can help other researchers explore its applicability to various applications.

Best regards,

Authors

[1] Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. 2018. Deep Interest Network for Click-Through Rate Prediction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery; Data Mining (KDD '18). Association for Computing Machinery, New York, NY, USA, 1059–1068. [2] Ko, H., Lee, S., Park, Y., & Choi, A. (2022). A survey of recommendation systems: recommendation models, techniques, and application fields. Electronics, 11(1), 141. [3] Li, Y., Chen, H., Xu, S., Ge, Y., Tan, J., Liu, S., & Zhang, Y. (2022). Fairness in recommendation: A survey. arXiv preprint arXiv:2205.13619. [4] K. Bao, J. Zhang, W. Wang, Y. Zhang, Z. Yang, Y. Luo, F. Feng, X. He, and Q. Tian. A bi-step grounding paradigm for large language models in recommendation systems. arXiv preprint arXiv:2308.08434, 2023a.

I am grateful to the authors for providing a detailed response that addresses my concerns.

If the evaluation is based on the revised version, my three concerns are:

• Re-polishing the entire paper was necessary because there were numerous revised sections. For example, the description in the last paragraph of the first section was not updated and was inconsistent with the abstract.

• To avoid the abruptness of the content and too many necessary experimental results being placed outside the main text, I suggest that the authors focus their perspective and writing on a specific type of recommendation scenario, such as group fairness issues around recommendations based on large language models or sequence recommendations.

• To verify the authors’ description of the advantages of FairDual on an industrial scale, it may be necessary to conduct experiments on some corresponding datasets, such as some datasets provided by the industry commonly used in click-through rate prediction tasks.

Other minor issues: 1) Results from previous lightweight work on group fairness should be included in the efficiency experiments; 2) Is the added BPR baseline based on the original form of matrix factorization? This may be ambiguous since it is a loss function compatible with many models. 3) some recommendation models based on large language models are compatible with pairwise losses.

If the evaluation is based on the original submission status, the revisions that need to be included may be far beyond what is acceptable for a normal camera-ready version and numerous experimental results may lack a second review.

Considering the above comments, I will increase my score appropriately, but still do not think this submission is at an unquestionably acceptable level in this venue.