Bridging Jensen Gap for Max-Min Group Fairness Optimization in Recommendation
Authors: Chen Xu
Yuxin Li
Wenjie Wang
Liang Pang
Jun Xu
Tat-Seng Chua
Venue: ICLR 2025 Poster (2025)
Keywords: Jensen Gap
Recommender Systems
Max-min Fairness
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: A dual gradient method is proposed to bridge the Jensen Gap to conduct recommendation tasks based on max-Min group fairness constraint.

Abstract: Group max-min fairness (MMF) is commonly used in fairness-aware recommender systems (RS) as an optimization objective, as it aims to protect marginalized item groups and ensures a fair competition platform. However, our theoretical analysis indicates that integrating MMF constraint violates the assumption of sample independence during optimization, causing the loss function to deviate from linear additivity. Such nonlinearity property introduces the Jensen gap between the model's convergence point and the optimal point if mini-batch sampling is applied. Both theoretical and empirical studies show that as the mini-batch size decreases and the group size increases, the Jensen gap will widen accordingly. Some methods using heuristic re-weighting or debiasing strategies have the potential to bridge the Jensen gap. However, they either lack theoretical guarantees or suffer from heavy computational costs. To overcome these limitations, we first theoretically demonstrate that the MMF-constrained objective can be essentially reformulated as a group-weighted optimization objective. Then we present an efficient and effective algorithm named FairDual, which utilizes a dual optimization technique to minimize Jensen gap. Our theoretical analysis demonstrates that FairDual can achieve a sub-linear convergence rate to the globally optimal solution and the Jensen gap can be well bounded under a mini-batch sampling strategy with random shuffle. Extensive experiments conducted using six large-scale RS backbone models on three publicly available datasets demonstrate that FairDual outperforms all baselines in terms of both accuracy and fairness.

Published as a conference paper at ICLR 2025
BRIDGING JENSEN GAP FOR MAX-MIN GROUP FAIR- NESS OPTIMIZATION IN RECOMMENDATION
Chen Xu', Yuxin Li', Wenjie Wang', Liang Pang', Jun
Chua
Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China
2 School of Information Science and Technology.
University of Science and Technology of China, Hefei, China
3 Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China,
4 NExT++ Research Center, National University of Singapore, Singapore
[xc_chen, yuxin 11) } @ @ruc.edu.en, wenj j ewang 9 @ @gmail.com, pangli i ang ict.ac.cn, junxu @ Ceruuceduu edu.en dcscts s @ @nus.edu.sg
ABSTRACT
Group max-min fairness (MMF) is commonly used in fairness-aware recommender systems (RS) optimization objectíve, it aims to protect marginalized item groups and ensures a fair competition platform. However, our theoretical analysis indicates that integrating MMF constraint violates the assumption of sample independence during optimization, causing the loss function to deviate from linear additivity. Such nonlinearity property introduces the Jensen gap between the model's convergence point and the optimal point if mini-batch sampling is applied. Both theoretical and empirical studies show that as the mini-batch size decreases and the group size increases, the Jensen gap will widen accordingly. Some methods using heuristic re- re-weighting or debiasing strategies have the potential to bridge the Jensen gap. However, they either lack theoretical guarantees suffer from heavy computational costs. To overcome these limitations, we first theoretically demonstrate that the MMF-constrained objective be essentially reformulated as a grouh-weighted optimization objective. Then we present an efficient and effective algorithm named FairDual, which utilizes dual optimization technique to minimize Jensen gap. Our theoretical analysis demonstrates that FairDual can achieve a sub-linear convergence rate to the globally optimal solution and the Jensen gap can be well bounded under a mini-batch sampling strategy with random shuffle. Extensive experiments conducted using six large-scale RS backbone models on three publicly available datasets demonstrate that FairDual outperforms all baselines in terms of both accuracy and fairness, Our data and codes are shared at hhtttp::: // com 2ttmm//hhee222/aaaaraaa
INTRODUCTION
Group max-min faimess (MMF) has gained significant attention in industrial recommender systems (RS), it seeks to provide support for marginalized item groups, where item groups are usually divided by item categories or providers (Xu et al., 2023 Patro et al. 2020; Xu et al. 2024b). For example, optimizing MMF can alleviate the low exposure problem of small sellers in the Amazon RS platform (Patro et al.) 2020). As illustrated in European competition law (Jones et al.) 2014), protecting these weak supplier groups is essential for preventing large platforms from engaging in unfair strategies, thereby ensuring fair competition (Matten et al. 2008).
Formally, the group MMF optimization objective entails calculating the overall utility of each group and maximizing the utility of the least advantaged group. 'Typically, group utility computation often necessitates aggregating the overall recommendation ranking list over a specified period (Xu et al.) 2023 Do et al. 2021 Xu et al. 2024b), for example, the group utility could be the exposures of action movies within a day. Due to the limited ranking slots, adjusting the exposure of items to improve the
* "Corresponding author. Work partially done at Engineering Research Center of Next-Generation Intelligent.
Search and Recommendation, Ministry of Education.

---

Published as a conference paper at ICLR 2025
utility of one item group will inevitably affect the ranking outcomes of other item groups. Therefore, the loss function with the MMF constraint for RS violates a crucial assumption: the independence of samples, resulting in the MMF loss of different item groups not adhering to linear additivity (see theoretical proof in Section
We theoretically and empirically show that the non-linear additivity property of the MMF-constrained
objective will introduce a Jensen gap (Gao et al.) 2017; Ullah et al.) (021) between the model's s convergence point and the optimal point when if mini-batch sampling is applied for optimization (see Section Meanwhile, it is proved that as the mini-batch size decreases and the group size increases, the Jensen gap will become more pronounced in the optimization process, significantly harming the model's 's performance. However, mini-batch sampling strategies are essential for accelerating the model training process, especially as data and model sizes RS continue to grow, such as the development of large language models (LLMs) based RS (Bao et al. 2023
Lin et al. 2024a b).
Some previous approaches have the potential to bridge the Jensen gap for RS. One type of heuristic approach can be applied to bridge the Jensen gap, such as sample re-weighting strategies (Chen) jet al. 2023b] Wen et al.) 2022), which dynamically assigns a higher weight to the weaker group across different batches. However, the effectiveness of this research line is limited due to the lack of theoretical guarantees. Another type of work utilizes machine learning techniques that can help to optimize the non-linen non-linear additive loss functions. For example, /Abernethy et al. (2022): Coussins (2222) have proposed sampling strategies to obtain unbiased samples, while some methods utilize debiasing gradient descent (Demidovich et al. 2023 Agarwal et al., 2018) to introduce bias correction term in the gradient. However, these methods cannot be applied to existing large-scale industrial RS, as they often require a convex optimization process that is impractical for RS that typically serves millions of users and hundreds of groups.
To overcome the challenges for bridging the Jensen gap, in this paper, we firstly theoretically demon- strate that the optimization objectives when incorporating group MMF constraint can be essentially reformulated as a group-weighted accuracy optimization objective on different groups. Then, we in- troduce a large-scale friendly, and effective algorithm called FairDual to optimize the group- weighted objective for minimizing the Jensen gap. Specifically, we formulate the caintes--onnsraint problem as its dual, where the dual variable (referred to as the shadow price in economics (Drèze and Stern 1990)) can be interpreted as the sample weight assigned to each sample in the mini-batch optimization process. Then, FairDual leverages dual-optimization techniques to optimize the weight of different group losses utilizing dual mirror gradient techniques efficiently.
Our theoretical analysis demonstrates that FairDual can achieve sub-linear convergence rate to the globally optimal point under a random shuffling mini-batch training style. Moreover, the Jensen gap can be well bounded (See Section 5.2.3) even when confronted with small mini-batch sizes and large group sizes. Extensive experiments using six large-scale RS backbone models on three publicly available datasets show that FairDual consistently reduces the Jensen gap and outperforms all baselines with a large margin in terms of both accuracy and fairness while achieving better efficiency.
RELATED WORK
Fairness concept in RS. One common categorization is based on the involvement of different stakeholders (Abdollahpouri et al. 2020 Abdollahpouri and Burke, 2019), divides fairness into individual fairness (Marras et al. 2022 Li et al. 2021), which aims ensure equitable treatment
for individual users, and group faimesss which classifies items into various groups (Xu et al. 2023
2024b Patro al.) 2020 Naghiaci et al. 2022, Wu al. 2021). Various approaches have been proposed to optimize fairness utilizing different fairness objectives. For instance, Patro et al. (022))
proposed using the Shapley value, while (Do and Usunier (2022) suggested optimizing the Gini Index. On the other hand, works such Xu et al. (2023); Do et al. (202 Xu et al. (0024b) advocate for optimizing MMF, which requires every group should receive a "minimum wage". Typically, we mainly focus the group MMF, which is closer to the industrial scenarios since certain studies propose to ensure minimum item exposures for attracting providers to join or enhancing the visibility of specific item categories (Patro et al. 2020 Xu et al. 2024b Zhu et al. 2020).
Optimizing fairness in RS. When optimizing fairness, previous research often categorizes methods into three categories based recommendation phases, including pre-processing (Calmon al.
2

---

Published as a conference paper at ICLR 2025
Xiong et al., 2024| Xu et al. 2024a), post-procsssing (Xu et al. 2023 Patro et al. 2020 Wu et al. 2021 Xu et al. 2024c) and in processsin (Narasimhan et al. 2020 lang et al. 2. In this paper, we theoretically demonstrate that the in pr-oresssingg method constrained by group MMF can be essentially reformulated as a re-weighting approach. Prior research employed static or dynamic group weights to achieve fairness. For static weights, Tiang et al. (2024); Xiong et al. (2024) proposes to set item weight according to its popularity and the Wasserstein distance of two groups, respectively, For dynamic weighting, some work (Chen et al. 2023b Chai and Wang 2022] Wen al., 2022) propose to design weights based on the training state, while Hu et al. (2023) employs a dynamic re-weighting strategy to mitigate distribution shifts between training and test data. |Roh et al. (2020) also proposes to set different batch sizes to optimize fairness. However, these methods are either designed for simple cases involving only two groups, or they lack theoretical guarantees when applied to group
2017
MMF settings.
Optimizing fairness in MI. machine learning (ML), previous work aims to optimize different fairness functions to achieve various social welfare objectives. For example, the power-mean welfare family seeks to balance accuracy and fairness objectives by applying the exponential form (Cousins 2021 2023) and max-min faimess (Abernethy et al., 2022; Agarwal al. 2018) aims to support the worst-off groups. When optimizing fairness, we commonly try to optimize a nonlinear fairness function. When adopting optimization methods such as stochastic gradient descent (SGD), an unavoidable bias will exist (Demidovich et al. [023] Hu et al.] (0200). To bridge this bias, previous ML methods have employed sampling strategies (Abernethy et al. [022 Cousins 2022) to obtain unbiased samples, while some methods have utilized debiasing SGD DDmidovich et al. 2023 Agarwal al. 2018) mitigate the bias. However, these works cannot be applied to large-scale industrial RS since they often require convex optimization process that is impractical for RS tasked with serving millions of users and hundreds of groups. To efficiently bridge the Jensen gap. our method improves debiasing SGD by developing large-scale friendly mirror SGD learning algorithm.
3 FORMULATION
In RS, let U, I be the set of users and items, and each item i E I is associated with a unique group g E G, where the set of items associated with g is denoted as Ig. In RS, an item i may belong to a different group g (e.g., movie can be categorized under various genres such as action, or drama). We define the number of groups to which the item belongs as n,,
Suppose that the RS manages set of user-item historical interactions D= = {(u, i, ). where each tuple (u, i, Cua) records that a user u E U accessed the system and interacted with an item E I with behavior Cu.; E {0, 1}. Gu.i 1 means that the user u clicked/purchased the item i, and 0 otherwise. The task of recommendation becomes, based on the user-item interactions in D, learning an empirical estimation č., = suu i) for real label Cu.i. Then RS will suggest K items to the user according to predicted preference scores E,, with the ranking list denoted as L (u) E IK In general, the f-) can be either the traditional matrix factorization model (He et al. 2016 or more advanced LLMs-based recommender models (Bao et al.) 2023).
Following the practice in recommendation tasks (He et al. 2017 2016), the cross-entropy loss -Cu,s log()..)) is regarded as common and better choice compared to other loss functions. Mean- while, to fulfill the group MMF requirement (Patro et al.) 2020 Xu et al. 2024b). the recommendation model also strives maintain the expected utility of specific group g (where the group's 's utility is defined as the negative sum of the entropy loss within the group) exceeds a basic threshold M. MMF constraint aims to ensure every group can receive the required group-specifie "minimum wage" during the training phases. Formally, we can write the ideal optimization objective as follows:
Il2 E Ig) Cu.s log(Cu.)) S M
L = min Aui
Σ>>
Cu.s log(Co,)) NEE RET.
s.t.
max SEG NEW (ELx(U) (u)
Σ
Σ
147gg
recommendation accuracy less
MMF constraint: loss of wonst off group 5 should at or smaller than
where I(.) denotes the indicator function, and the number of users [4| could represent the daily or weekly user traffic. The my can be regarded as the weight for different group g. Note that, following the practice in time-aware RS (Kang and McAuley 22088b [Sun et al. 2019). we utilize the recent H interactions, which represent the truncated user historical behavior numbers.
3

---

Published as a conference paper at ICLR 2025
B+2
B
Bw52
Bimin--blkhh
Group
Seam gii 710)
Se A40
16
10-
converge
2150
115
optimal points
2000
1005
06
Group 1
02
(a)
(b)
Figure Loss converges simulation with 1000 users and 1000 items. Sub-figure (a) and (b) illustrate the distance away from the optimal point (i.e., Jensen gap) w.t.t mini-batch and group size, respectively. Figure (a) was conducted with the same group size (G=7) under different batch sizes, while Figure (b) was conducted with the same batch size (B=32) under different group sizes. Sub-figure (c) describes the converged trace under different batch sizes.
4 PROBLEM ANALYSIS
In real-world scenarios, the number of users [Ld] is often large, and a mini-batch sampling strategy with a batch size of B is often necessary due to the large computational costs. Each batch only contains a subset of users. However, we show that the non-linear additivity property of the MMF. based objective will introduce the Jensen gap between the model's convergence point and the optimal point when employing mini-batch sampling strategies.
this section, we analyze why the Jensen gap exists and how will influence model's 's convergence in both theoretical and empirical ways.
4.1 THEORETICAL ANALYSIS
Firstly, we will re-write the optimization objective using the following theorem:
Theorem 1. For vector x: TR" x² denotes the element of the vector raised to the power of Similarly, log(z) denotes the element of the vector reduced as log(ær)) Let A E [ is the item-group adjacent matrix, and Aig
indicates item i Ig. and 0 otherwise. Let [ -'veu Cu, log((o,,)) and its feasible region is W {ww] Eiez Cut S K, K,Yu
U, E [0, 1}. Then there exist E [0, oo) (value of relates to the value of M) and weight
vector b E Rlol 2 0, s.t. Equation
1 can be optimized
min (ÁÁTT) w+)++
wEW
where À is the row-normalized matrix for A: Á diag( A A. diag (x) denotes to construct diagonal mairix based on vector
The detailed proof of Theorem can be seen in Appendix When transforming the original optimization process in Equation (1) into Equation (2). we can easily observe that the loss function does not adhere linear additivity. Then the Jensen gap will arise under mini-batch sample strategy by formulating it using the following theorem:
Theorem 2. Under mini-batch sample strategies, we partition the user set into MU/B subsets and perform optimization on each subset. Let e <Rlll be the group accumulated utility under j-th partition, where each element ej.g = = -mEE, EiEI, Cu,i log(Cu.)). Let f(x) = _++1 1 We can write the mini-batch optimizing loss objective CB as: CB min Σ /4/BB bT f(e,), where Uj is the j-th partition of the user set U. Then, Jensen gup (Gao el al.
2017 Ullah et al. 2027 is defined as:
M//B
J(B) = C. - - C min b f(
Σ
+0)
1=1
When optimizing Equation (2) under the mini-batch sampling style, the mini-batch size B becomes smaller and group size becomes larger, the Jensen gap J(B) will become larger. Moreover, when
4

---

Published as a conference paper at ICLR 2025
the mini-bated size becomes smaller, more likely to underestimate the original loss, i.e., L 1 C. The loss underestimattin will result in the Jensen gap.
The detailed proof of Theorem 2 can be seen in Appendix The intuitive reason behind the Jensen gap raised by group MMF is that the accuracy-fairnest trade-off problem does not adhere to linear additive attributes. Essentially, the combination of different batches forms concave function. Mini- batch size and group size both measure the degree of data partitioning, where smaller batch sizes and larger group sizes lead fewer data partitions. As result, due to the non-linear and intricate function form of neural network (Sun) 2019), these errors in estimating the loss function impede the model from converging to the optimal point, thus diminishing the performance. Next, we will give an empirical analysis to prove this.
4.2 EMPIRICAL ANALYSIS
In this section, we illustrate a simulation (Figure I conducted under the assumption of knowing every user-item true preference score validate the correctness of our theoretical analysis. We use the simple recommendation model: Matrix Factorization (Singh and Gordon, 2008) since we can have closed-form expression parameter updating. Then apply common mini-batch training strategy to optimize accuracy-fairness objective based on the parameters outlined in Xu et al. (2023) Patro et al. (2020), with the accuracy-fainee fairness coefficient 0.5.
As shown in Figure (a) and (b), we uncover that the Jensen gap (distance away from the optimal point) will deviate with smaller mini-batch sizes and larger group sizes. Figure (c) describes the converge trace under different batch sizes by mapping the top-K simplex space of three groups of recommendation ranking to a 2-dimensional space through topological homeomorphic trans- formation (Kozlov 2008). Figure [ (c) also indicates that different batch sizes result in different gradient optimization directions, with smaller batch sizes leading to larger shifts in the error of the optimization direction. These empirical results confirm the correctness of our theoretical analysis.
For other types of fairness, such as the power-mean welfare family (Cousins) 202I) and the Gini welfare function (Do and Usunier 2022), also exhibit non-linear properties. leading to analogous Jensen gap phenomena. We discuss them the Appendix H and Appendix M
METHOD
In this section, we will introduce our method FairDual.
5.1 OPTIMIZING MAX-MIN FAIRNESS AS GROUP-WEIGHTER OBJECTIVE
In this section, in order to tackle this problem, show that the MMF-constrained objective can be regarded as the sroup-weighted optimization problem using the following theorem: Theorem 3. By introducing the dual variable μl, the dual form of the Equation 7
L' = min
-Σ 8g
Gu, log(Cu.))
(4)
Eu,t
wEl DE9
VEI,
where 8g 1 pby and μ arg min (max EuEu Egeg 8y EiEr, Cu, log(Cu,)) + (11)) where r" r'( maxx,5mm (minges my (Aw), + AT Awppt/)
MgMg/ + M
{M Eges my 2 A, VS E } where G3 is the set of all subsets of G (i.e., power set).
The detailed proof of Theorem 3 can be seen in Appendix F From Theorem 3 observe that the recommendation task constrained by max-min fairness can be viewed as a re-weiigting approach across different groups the original loss function solely optimized for accuracy.
Intuitively, s, = 1 - My is the negative shadow price (Drèze and Stern 1990). The high shadow price Mg indicates that this constraint is the primary factor constraiming accuracy optimization. Conversely, a low or zero shadow price suggests that the fairness constraint currently imposes little restriction on accuracy. Specifically, high 8y signifies that this constraint is the primary factor limiting fairness
5

---

Published as a conference paper at ICLR 2025
Algorithm 1: FairDual
Require: Dataset D = {u, i, C.,a). item item-group adjacent matrix A, dual learning rate 7, trade-off coefficient X, (rreeee (-) updating step 89 batch size and sample item number Q and the weight Wig for each group
= diag( A1) ( A.
Ensure: The model parameters of m² (.), m m.)--
1: for n 1.. .N do
2:
Set 11.9 = mg Vg EG
3: for 1,... [ / do
4:
if (n [NI/B+j)90 = 0 then
5: Copy parameters from m' m'(-) minesse and get all item embedding E
6: Initialize dual solution = 0, and momentum gradient 0 and t = 0.
7: end if
8:
Get sub-dataset {u, i, Gu,i) and user feature e, and item feature e;
9:
L =I [-- (og(C,.,))bmn) 8) AAp
10:
Apply gradient descent based on loss (s
11:
Wh Σm=1 (e E*)
[kK) Vb
12:
g' - (A)) TT 77 .g'
ag' (1 aag g 9=9 g=
Y = 7 (Ai) T
w. μ arg min M. [(g)] no + 7 mllmo 11
14: end for
end for
optimization for group g, whereas a low or zero implies that the accuracy constraint for group currently has little impact on the overall optimization.
5.2 FAIRDUAL
We then will introduce our method FairDual under random shuffling mini-batch training strategies. The overall workflow FairDual under every two batches j and j + 1 can be seen Figure 2 According to analysis in Theorem 3 under each epoch, the overall optimization process will become:
KUBB Σ (
C = mimn
(5)
where 1i 3 8d E IR BgBi is loss and its weight under j-th batch. Next, we will explain how and 8 update on each batch j. Detailed algorithm workflow can be seen in Algorithm Note that, following the practice in Bao et al. (2023), we utilize the user's historical behaviors to represent each user, thereby treating each sample unique user.
5.2.1 ACCURACY Loss CONSTRUCTING
In the mainstream recommender architectures, the primary objective is to make the predicted score close to the true user preference. That is, at each batch j. there are user-item pair [(u, i)] arrives. Then the loss vector L) computed as:
1' [-cu. log(E..))
where dn,i = d(e,, ei) S 1, where d(-) is the normalized distance between embedding eu, e; The commonly used distance metric the dot-product, i.e. d(en, eq) = -e] e,, and the e, and e; are calculated by complex model, i.c. en m" (1), mi),, where m²(-) and m' are two embedding extraction networks. Typically, the user u is represented by the item-clicked history sequences before clicking the item i: [i ,.......,",,, ,i"], where is the fixed item sequence length.
Note that in text- bastd recommendation models such as BigRec (ao et al. 2023) and Rec- former (Li et al.) 2023). each item i is represented guage: 2 [w] "....... w'), where I is the length of the sentence and user behaviors are also represented in prompt form (Bao al. 2023). In such cases, Equation (6) is extended to
sequence of words in natural lan-

---

Published as a conference paper at ICLR 2025
Copy every batches
Batch
Batch J
Froseed estractor chooaa ()
Items
axtractoem
Nenn Gealure
Taggel embebettdngger
eightia
Lees H
W Weight
X
Lisers
Extract all
embedding
X
History 8
Predicted runking
Torget enleseehiinggs e, cstruttorm*))
User
Sampled item embelelldings
Sub gradieen g
1
Stored Item embebedidings
Sample items
Figure 2: Overall workflow of FuirDual under every two batches j and j 1.
log C..i = Ei log(P(w")), where P(w) refers to the predicted probability of the word w gener- ated by the LLMs, while other equations remain unchanged.
5.2.2 MIRROR GRADIENT DECENT FOR GROUP WEIGHT
For each batch j. the model needs to decide the weight 8 for each sample. The weight s is computed utilizing mirror- grroortgraiitttt descent (Balseiro et 2021 technique. Specifically,
8 A'p²,
where A TR represents the row-normalized item- item-group adjacency matrix for A in batch (see details in Equation (2), with Ai.. = 1 indicating that the b-th item in batch is E Zg belongs to group g. and O otherwise. And ue is the dual variable at j-th batch, which updates as:
Fº arg min (g')) f nlı 111
s.t. Σ Hjm + 0, 4gg 1.2..... 191,
where 77 is the learning rate, g is the sub-gradient of the Equation 44 w.r. the dual variable 2² E IR Gl. The projection step can be efficiently solved using convex optimization solvers (Balseiro et al. 2021 since D is wordinate-wisely symmetric.
Specifically, to ensure smoothness and make user of historical information, we utilize the momentum gradient descent to update g":
g =o + (1-ag) 10-",,----0 C'
= (AA)) w +
where Yj R19) is the vector, whose element of index denotes the remaining required loss (i.e,, reward) for the group y at batch step j. w E RB represents the estimated ranking score that each user query will receive. However, given the vast size the item corpus in recommendation systems, conducting a full ranking on all items is impractical. Therefore, we randomly sample Q items approximate the ranking scores across all items. The Q items' embeddings are denoted as
xd Formally, for the b-th element WG. we can write: w, = > (E e 1Bs, where F(k] denote the k-th largest element in vector and K is the ranking size.
Note that E is sampled from the pro-stored item embedding E E Z which is pre-calculated using the freezer network m (.). This is done to mitigate the significant fluctuations in caused by unstable training (Fan al. 2020). To achieve this, we freeze the item feature extractor m (-)
as mineree (+) and transfer the parameters from m² m²(-) to m (-) every / batches. For the first batch process, initialize g' as O, which will not make an effect on the first batch.
5.2.3 BOUND ON JENSEN GAP
We will provide the Jensen gap converge analysis of FairDual in the following theorem.
7

---

Published as a conference paper at ICLR 2025
Theorem 4 (Bound on Jensen Gap). There exists H 0 such that || 11
< H and function 11212 is a strongly convex. Then, there exists L >> 0, the Jensen gap of FairDual can be bounded as:
L J(B) - H. + B(1 B(1-a)o" 2(1 a)-on)
L
(10)
When setting learning rate 1j = O(B-1/2), the bound of Jensen gap is comparable with (B-1/22)
The detailed proof can be seen in Appendix G From Theorem it is apparent that the Jensen gap will widen as the batch size B decreases and the group size |9], as well as the max-min fairesss degree X, increase. However, FairDual demonstrates sub-linear convergence rate concerning the batch size B, and it maintains strong performance even with small batch sizes and large group sizes across various fairness degrees.
EXPERIMENT
We conduct experiments to demonstrate the effectiveness of the proposed FuirDual.
6.1 EXPERIMENTAL SETTINGS
Datasets.
The experiments are conducted on the commonly used two widely used and publicly available recommendation datasets, including MIND (Wu al. 2020 Amazon-Book and Amazon-
Electronic (He and McAuley 2016 Their detailed statistical information is in Appendix !
Evaluation. We arrange all interactions in the dataset chronologically by their timestamps and employ the first 80% interactions as training data. The remaining 20% of interactions are divided equally, with each 10% segment used for validation and testing, respectively, during evaluation.
Regarding the metric, following the practice in Dai et al. (2023), we utilize Normalized Discounted Cumulative Gain (NDCG) and mean Reciprocal Rank (MRR) to measure the accuracy: NDCG@K
M |44 (2..(
MRR@K T. Σ Eu=1 rank,' where rank; is the rank of
[27
(2 1)/(log, (1))
the first correct answer. Meanwhile, we employ MMF@K K to gauge the degree of fairness, which
quantifies the aggregated ranking score of the 20% worst-off groups (Do et al. 2021 Xu et al. 2023).
Backbones and baselines. For the backbone, we first select three large-scale recommender models: NRMS (Wu et al.) 2019), RecFormer (Li al. 2023) and BigRec (Bao et al. 2023). Note that BigRec only utilizes 1024 samples to train due to large computational cost.
For the baselines, choose several fair-aware re-weight baselines that aim to improve group MMF: UNI (without considering fairness), DRO (Hashimoto et al.) 2018). S-DRO (Wen et al. 2022).
Prop (Hu et al., 2023), FairLLS (Jiang et al. 2024) and Maxmin Sample (Abernethy et 2022)
The detailed descriptions of the backbones and baselines are in Appendix [
Implemtation details. We provide our detailed running environment, all hyper-parameter settings, utilized L.MSs settings, and used the toolkit Appendix !
6.2 EXPERIMENTAL RESULTS ON FULLI DATASETS
Firstly, we conduct experiments to show the performance FairDual and other baselines across all large-scale recommendation backbones. Table presents the experimental outcomes for our FairDual model and the baseline methods across all datasets, respectively. Suble@[preser outcomes for our FairDual model and the baseline methods across other different backbones on the MIND dataset. To make fair comparisons, all the baselines were tuned to their hyperparameters to obtain the best trade-off accuracy and fairness performance under our settings.
the experimental
From the experiments, it is evident that FairDual consistently outperforms the bascline methods across all datasets and various base models, spanning different top-K ranking sizes. This reflected
httos://microsoftneet
http://jnnaulee.uucs www.y..ssddcommm www.ddddduddttt. amazon/
8

---

Published as a conference paper at ICLR 2025
Table I: Performance comparisons between ours and the baselines on three datasets under best- performing BigRec backbones. The * means the improvements are statistically significant (t-tests and p-value < 0.05). The bold number indicates that the accuracy value exceeds that of all the baselines.
ModelsMMetries
NDCG (96
MRR (4)
MMP (%)
(DCG(9))
MRR (56)
MMP (S)
NDCG (8)
MRR (%)
MMF (%)
UNI
1,02
0.79
1.63
1.50
0.98
2.33
2.16
1.16
2.94
1.54
Prop
1.11
0.88
1.97
1.62
1.09
2.53
2.14
1,23
3.05
MIND
S-DRO
0,91
0.70
1.57
1.42
0.91
2.41
1.93
1.04
3.02
IFirLLS
0.87
0.66
2.21
1.27
0.83
2,91
1.78
2.86
sample
Ours
1,15
0.88
2,82
1,69
1.11
2,99
2.28
1.27
improx.(%)
3.60
0.00
25.33
4.32
1,83
2.75
4.10
3.25
5.61
UNI
DRO
2.94
2.72
3.15
2.81
8.29
3.37
2.87
Prop
2.64
2.45
8.68
2.83
2,53
8.30
3.05
2.59
8.01
Book
[Fairf
S-DRO
2,61
2.44
8.37
2,80
2.52
8.21
3.05
2.59
8.07
Maxmin sample
2.49
2.31
6.80
2.72
2.43
6.80
2.97
2.74
7.50
Ours
3,11
2,88
8,90"
3,31
2,96
9,00"
3,60"
3,04
8.89
(5p)
2.53
8.81
UNI
4.61
4.30
0.26
4.33
4.43
3.30
0.21
DRO
4.65
4,34
0.24
4.96
4.46
0.24
5.33
4,57
0.21
Prop
4,63
4.33
0.26
4,96
4.47
5.33
S-DRO
Electronic
|airr RS
2.21
2,06
0.19
2.46
2.16
0.17
2.69
2.22
0.12
Maxmin sample
4.60
4.31
0.27
4.92
4.44
0.25
5.31
4.55
0.21
5.08
improv.(%)
9.24
10.1
14.8
9.47
10.0
19.9
0.95
10.0
23.8
Table 2: Performance comparisons between ours under other backbones on MIND dataset. The means the improvements are statistically significant (t-tests and p-value < 0.05). The bold number indicates that the accuracy value exceeds that of all the baselines.
Modek/MMetries
top-5
top-10
top-20
NDCG
MRR (%)
MMF (95)
NDCG (5)
MRR
MMF
NDCG (%)
MRR (%)
MMF
DRO
0.44
0.32
0.12
0.66
3.60
1.06
9:94
Prop
0.44
0.32
0.12
0.66
0.42
3.49
1.06
0.52
9.94
S.DRO
0.52
0.34
0.10
0.76
0.40
2.05
1.30
0.52
9.74
[FaiLLRS
sample
4,00
Ours
0.60
0.40
1,07"
0.84
0.46
4.93
1.28
0.60"
11.35
DRO
0.57
0.45
1.08
1.08
1.41
Prop
0.57
0.45
1.08
0.89
0.58
1.08
1.41
0.72
1.52
S-DRO
0.57
0:15
1.20
0.91
0.50
1,15
1,16
0.73
1.62
Maxmin sample
0.51
0.41
0.94
0.85
0.55
1.50
1.37
0.69
2.48
Ours
0.59
0.45
1,88"
0.99*
0.60
1.94
1.55
0.75
2.58
accuracy metrics such as NDCG and MRR, as well as fairness metric MMF, The results conclusively demonstrate that FairDual effectively ensures the model reaches better convergence point in terms both accuracy and fairness by leveraging dual gradient descent.
We also conduct experiments traditional RS backbones, detailed in Appendix The results also consistently confirm the effectiveness of our model FairDual.
6.3 EXPERIMENTAL ANALYSIS
In this section, we first replicate the simulation settings outlined Section 4.2 to investigate how the Jensen gap changes. Then conduct analysis on MIND dataset under BigRec base models.
Jensen gap. Firstly, we investigate the variations in the Jensen gap concerning batch size and group size [G] across both baseline methods and our proposed FairDual model. As shown in Figure (a), we can see that FairDual has a lower Jensen gap than other online models across different batch sizes and group sizes. Furthermore, it's evident that the Jensen gap exhibited by FairDual remains consistently stable across various batch sizes, with only marginal increase observed as the group size expands. This indicates that FairDual consistently maintain low Jensen gap level.

---

Published as a conference paper at ICLR 2025
FunDrl
Icaes po 1005
Sputaa
Spatt
Kreo
(a) Jensen gup comparision stae
20
Batdh
64
13c
17.
64
135
24
MMPY
Cheuttrtte
tire
Spor
Danthal
(b) Influence on trad-off co-efficient
(c) Case study for bsad group News and biil group Sports
Figure 3: Sub-figure (a) conducts a simulation to show Jensen gap (B) changes w.r.t batch size B and group size [9] for all baselines and FairDual. Sub-figure(b.c) conducts on MIND dataset under BigRec. Sub-figure (b) describes the NDCG and MMF changes w.r.f. accuracy-fairnes trade-off co-efficient A. Sub-figure (c) conducts the case study the advantage group News and worst-off' group Sports. We show their weight 8y. group score Wys and t-SNE embeddings of UNI and FairDual.
Influence on co-efficient A. Then, we will investigate the impacts of trade-off co-efficient X. Figure (b) illustrates that the fairness degree (MMF) increases proportionally with the rise in X, aligning with our expectations. However, we also observe that the accuracy increases as X changes from 0 to 5 and then decreases. This phenomenon occurs due to the presence of popularity bias in recommendation datasets (Jiang et al. 2024). A relatively higher fairness degree helps mitigate this bias, leading to increased accuracy. However, when À becomes too large, it inevitably enlarges the Jensen gap, which hurts the model's performance. We also conduct an experiment analyze the effect of the popularity bias in Appendix N
Case study. Finally, conduct case study the head group News, which consistently exhibited superior exposure compared to other groups, in contrast to the tail group Sports, which typically had lower exposure levels. Firstly, from the two figures at the top of Figure (c), we observe that the training progresses, the tail group Sports gradually gains more weight (sy), while the head group News consistently receives relatively low weight. Consequently, this leads to the group scores of the two groups being close to each other.
At the same time, we visualize the item embeddings using T-SNE (Van der Maaten and Hinton 2008 for both the baseline UNI and our model FairDual, as shown in the bottom two sub-figures of Figure
(c). From the figure, we compute the embedding KL divergence of two different groups between UNI (0. 10.13 13) and our method FairDual (0.083). This shows that UNI establishes clear classification line to distinguish between different groups. However, FairDual tends to bring the embeddings the tail group closer those of the head group, ultimately increasing the faimess.
Other experimental analysis. For analysis of other parameters dual learning rate 17, updating gap B, user history length Ht, the sample size Q, and the impact of the hidden layer numbers, please the Appendix K For the computational and storage costs analysis can be seen in Appendix L We also test the performance of other fairness metric in Appendix M
7 CONCLUSION
In this paper, we theoretically demonstrate that adapting mini-bate training with the objective constrained by group MMF inevitably leads the Jensen gap, thereby impairing the performance of the RS model. We theoretically and empirically analyze the origins of the Jensen gap by demonstrating that the integration of the MMF constraint disrupts the assumption of sample independence during optimization, leading to deviation of the loss function from linear additivity. Then, to efficiently bridge the Jensen gap. we develop a large-scale friendly algorithm named FairDual, which employs dutl-optimization techniques to minimize the Jensen gap at sub-ling linear rate. Extensive experiments conducted on three large-scale recommendation system backbone models using two publicly available datasets show that FairDual consistently outperforms all baseline methods.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was funded by the National Key R&D Program of China (2023YFA1008704) the National Natural Science Foundation of China (62472426, 62276248), and the Youth Innovation Promotion Association CAS under Grants No. 2023111. This work was also funded for building world-class universities (disciplines) of Renmin University of China. Supported by the Outstanding Innovative Talents Cultivation Funded Programs 2025 of Renmin University of China.
REFERENCES
H. Abdollahpouri and R. Burke. Multi-stakeholder recommendation and its connection to multi-sided fairness. arXiv preprint arXiv:/907.133: 13/158 2019.
H. Abdollahpouri, G. Adomavicius, R. Burke, I. Guy, D. Jannach, T. Kamishima, J. Krasnodebski, and L. Pizzato. Multistakccolder recommendation: Survey and research directions. User Modeling and User-Adapted Interaction, 30(1):127-158, 20200
J. D. Abemetthy, Awasthi, M. Kleindessner, Morgenstern, C. Russell, and Zhang. Active sampling for min-max fairness. In International Conference on Machine Learning, pages 53-65. PMLR, 2022.
A. Agarwal, A. Beygelzimer, M. Dudik, J. Langford, and H. Wallach. A reductions approach to fair classification. In International conference on machine learning, pages 69-69. PMLR, 2018.
S. Balseiro, H. Lu, and Mirrokni. Regularized online allocation problems: Fairness and beyond. In International Conference on Machine Learning, pages 630-639. PMLR, 2021.
K. Bao, Zhang, W. Wang, Zhang, Z. Yang. Y. Luo, Feng, He, and Q. Tian. bi-step grounding paradigm for large language models in recommendation systems. arXiv preprint wxXiv:2308.08434 2023.
I. Beltagy, M. E. Peters, and A. Cohan. Longformer: The long document transformer. arXiv preprint +xXi::2004.05555 2020.
R. I. Bot, S.-M. Grad, and G. Wanka. On strong and total lagrange duality for convex optimization problems. Journal of Mathematical Analysis and Applications, 337(2):3155-125, 2008.
P. Calmon, D. Wei, B. Vinzamuri, K. N. Ramamurthy, and K. R. Varshney. Optimized pre- processing for discrimination prevention. In Proceedings of the 31st International Conference Neural Information Processing Systems, NIPS' 17, page 3995-4004, Red Hook, NY, USA, 2017.
Curran Associates Inc. ISBN 9781510860964.
Chai and X. Wang. Fairness with adaptive weights. In International Conference on Machine Learning, pages 2853-28882 236-.866. PMLR, 2022.
X. Chen, W. Fan, J. Chen, H. Liu, Liu, Z. Zhang, and Q. Li. Fairly adaptive negative sampling for recommendations. In Proceedings of the ACM Web Conference 2023, pages 3723 27333, 2023a.
X. Chen, W. Fan, J. Chen, H. Liu, Liu, Z. Zhang, and Q. Li. Fairly adaptive negative sampling for recommendations. In Proceedings of the ACM Web Conference 2023, pages 3723-3733, 2023b.
C. W. Churchman, R. L. Ackoff, and E. L. Arnoff. Introduction to operations research. 1957.
C. Cousins. An axiomatic theory provably-fair welfare-centric machine learning. Advances in Neural Information Processing Systems, 34: 16610-16621, 2021.
C. Cousins. Uncertainty and the social planner's problem: Why sample complexity matters. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 2004-2015, 2022.
C. Cousins. Revisiting fair-pac learning and the axioms of cardinal welfare. International Conference Artificial Intelligence and Statistics, pages 6422-6442 PMLR, 2023.
11

---

Published as a conference paper at ICLR 2025
S. Dai, N. Shao, H. Zhao, W. Yu, Z. Si, C. Xu, Z. Sun, X. Zhang, and J. Xu. Uncovering chatgpt's ca- pabilities in recommender systems. In Proceedings of the 17th ACM Conference on Recommender Systems, RecSys '23, page 1 1126-1132, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400702419. doi: 10. 15145/604911.3611000
Y. Demidovich, G. Malinovsky, I. Sokolov, and P. Richtárik. A guide through the zoo of biased sgd. Advances in Neural Information Processing Systems, 1923158-231777 2023.
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1rXiv: 04805, 2018
S. Diamond and S. Boyd. Cvxpy: A python-embedded modeling language for convex optimization. The Journal of Machine Learning Research, 17(1):2909-299 2910, 2016.
V. Do and N. Usunier. Optimizing generalized gini indices for fairness in rankings. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 737-747, 2022.
V. Do, S. Corbett- Davies, J. Atif, and N. Usunier. Two-sided fairness in rankings via lorenz dominance. Advances in Neural Information Processing Systems, 34:8596-8600 2021.
J. Drèze and N. Stern. Policy reform, shadow prices, and market prices. Journal of public economics, 42(1):1-45 1990.
J. Fan, Z. Wang, Y. Xie, and Z. Yang. A theoretical analysis of deep q-learning, In Learning for dynamics and control, pages 486 489. PMLR, 2020.
X. Gao, M. Sitharam, and A. E. Roitherg. Bounds on the jensen gap, and implications for mean- concentrated distributions. arXiv preprint arXiv:1712.05266 2017.
Hashimoto, M. Srivastava, H. Namkoong, and Liang. Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning, pages 1929-1938 1938. PMLR, 2018.
R. He and J. McAuley, Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. proceedings of the 25th international conference on world wide web, pages 507-517, 2016.
X. He, H. Zhang, M.-Y. Kan, and T.-S. Chua. Fast matrix factorization for online recommendation with implicit feedback. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 549-558, 2016.
X. He, L. Liao, H. Zhang, L. Nie, X. Hu, and T.-S, Chua. Neural collaborative filtering. In Proceedings of the 26th international conference on world wide web, pages 173-182, 2017.
B. Hidasi, A. Karatzoglou, L. Baltrunas, and D. Tikk. Session- based recommendations with recurrent neural networks. arXiv preprint arXiv:1511.0633 2015.
E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu Y. Li. S. Wang. L. Wang, and W. Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2 06600685, 2021.
Y. Hu, Zhang, X. Chen, and N. He. Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning. Advances in Neural Information Processing Systems, 33:2759-2770, 2020.
7. Hu, Y. Xu, and X. Tian. Adaptive priority reweighing for generalizing faimesss improvement. In 2023 International Joint Conference on Neural Networks (IJCNN), pages 01-08. IEFF, 2023.
M. Jiang, K. Bao. J. Zhang, W. Wang, Z. Yang, F. Feng, and X. He. Item-side fairness of large language model-based recommendation system, 2024.
A. Jones, B. Sufrin, and et al. EU competition law: text, cases, and materials. Oxford University Press, USA, 2014.
12

---

Published as a conference paper at ICLR 2025
T. Kamishima and S. Akaho. Considerations recommendation independence for find-gon good-iteess task. 2017.
W.-C Kang and J. McAuley. Self-attentive sequential recommendation. In 2018 IEEE international conference on data mining (ICDM), pages 197-206. IEEE, 2018a.
W.-C. Kang and J. McAuley. Self-attentive sequential recommendation. In 2018 IEEE international conference on data mining (ICDM), pages 197-206. IEEE, 2018b.
D. Kozlov. Combinatorial algebraic topology, volume 21. Springer Science & Business Media, 2008.
T. Lan and M. Chiang. An axiomatic theory of faimess in resource allocation. George Washington University, htlp://www: seas. gwu. eduuhtaa/pppers/fiinness. pdf, Tech. Rep, 2011.
J. Li, M. Wang, Li, J. Fu, X. Shen, J. Shang, and J. McAuley. Text is all you need: Learning language representations for sequential recommendation. In Proceedings the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, page 1258-1267, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701030. doi: 10. 11.1/ 1580305.3599519
Y. Li, H. Chen, S. Xu, Y. Ge, and Y. Zhang. Towards personalized faimess based on causal notion. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1054-1063, 2021.
X. Lin, W. Wang. Y. Li, F. Feng, S.-K. Ng. and T.-S. Chua. Bridging items and language: transition paradigm for large language model-based recommendation. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1816-1826. ACM, 2024a.
X. Lin, W. Wang, Y. Li, S. Yang, F. Feng. Y. Wei, and T.-S. Chua. Data-efficient fine-tuning for llmebased recommendation. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 365-374. ACM, 2024b.
J. Lindenstrauss, G. Olsen, and Y. Sternfeld. The poulsen simplex. In Annales de I' l'institut Fourier, volume 28, pages 91-114, 1978.
M. Marras, L. Boratto, G. Ramos, and G. Fenu. Equality of learning opportunity via individual fairness in personalized recommendations. International Journal of Artificial Intelligence in Education, 32(3):636-688 2022.
D. Matten, Moon, and al. "implicit" and "explicit" esr: A conceptual framework for comparative understanding of corporate social responsibility. Academy of management Review, 33(2):404 424, 2008.
M. Naghiaei, H. A. Rahmani, and Y. Deldjoo. Cpfair: Personalized consumer and producer fairness re-ranking for recommender systems. arXiv preprint arXiv:2204. 2022.
H. Narasimhan, A. Cotter, M. Gupta, and S. Wang. Pairwise faimess for ranking and regression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5248-5255, 2020.
A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang. Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and Lerer. Automatic differentiation pytorch. 2017.
G. K. Patro, A. Biswas, N. Ganguly, K. P. Gummadi, and A. Chakraborty, Fairrec: Two-sided faimess for personalized recommendations two-sided platforms. In Proceedings of The Web Conference 2020, pages 1904,204, 2020.
Rendle, C. Freudenthaler, Z. Gantner, and L. Schmidt-Thieee Bpr: Bayesian personalized ranking from implicit feedback. arXiv preprint arXiv: /205.2618 2012.
Y. Roh, K. Lee, S. E. Whang, and C. Suh. Fairbatch: Batch selection for model fairness. arXiv preprint 2011 2020.
13

---

Published as a conference paper at ICLR 2025
A. P. Singh and J. Gordon. A unified view of matrix factorization models. In Joint European Con- ference on Machine Learning and Knowledge Discovery in Databases, pages 358-373. Springer, 2008.
Sun, Liu, J. Wu, C. Pei, X. Lin, W. Ou, and P. Jiang. Bert4rec: Sequential recommendation with bidirectional encoder representations from transformer. In Proceedings of the 28th ACM international conference on information and knowledge munagement, pages 1441-1450, 2019.
R. Sun. Optimization for deep learning: theory and algorithms. arXiv preprint arXiv:1912.088 2019.
Tang, Shen, Z. Wang, Z. Gong, J. Zhang, and X. Chen. When fairness meets bias: debiased framework for fairesss aware top-n recommendation. In Proceedings of the 17th ACM Conference on Recommender Systems, RecSys '23, page 200-210, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400702419, doi: 10.1 10.114573049155336098
H. Touvron, L. Martin, K. Stone, P. Albert, A. Almahairi, Y. Babaei, N. Bashlykov, S. Batra, P. Bhargava, S. Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint (iix:2307.092880 2023.
H. Ullah, M. Adil Khan, and Saeed. Determination bounds for the jensen gap and its applications. Mathematics, 9(23):3132, 2021.
L. Van der Maaten and G. Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(1 9(11), 2008.
H. Wen, X. Yi, T. Yao, J. Tang, L. Hong, and E. H. Chi. Distributionally-robuus recommendations for improving worst-case user experience. In Proceedings of the ACM Web Conference 2022, pages 3606-3610, 2022.
C. Wu, F. Wu, S. Ge. T. Qi. Y. Huang, and X. Xie. Neural news recommendation with multi-head self-attention. K. Inui, J. Jiang, V. Ng. and X. Wan, editors, Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing TEMNLP-IJCNLPP pages 6389-6394, Hong Kong, China, Nov. 2019, Association for Computational Linguisties. doi: 10.18863311/119-111
Wu, Qiao, J.-H. Chen, C. Wu, T. Qi, Lian, D. Liu, X. Xie, J. Gao, W. Wu, et al. Mind: large-scale dataset for news recommendation. In ACL, pages 3597-3606, 2020.
Y. Wu, J. Cao, G. Xu, and Y. Tan. Tfrom: A two-sided fairnes--aware recommendation model for both customers and providers. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1013-1022, 2021.
Z. Xiong, N. Dalmasso, A. Mishler,
Potluru, Balch, and M. Veloso. Fairwasp: Fast and optimal fair wasserstein pre- preproocessing In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 16128, 2024.
C. Xu, Xu, X. Chen, Z. Dong, and J.-R. Wen. Dually enhanced propensity score estimation in sequential recommendation. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 2269, 2022.
C. Xu, S. Chen, J. Xu, W. Shen, X. Zhang, G. Wang, and Z. Dong. P-mmf: Provider max-min fairness re-ranking in recommender system. In Proceedings of the ACM Web Conference 2023, pages 3701-3711. 2023.
C. Xu, W. Wang, Y. Li, L. Pang, Xu, and T.-S. Chua. study of implicit ranking unfairness in large language models. In Y. Al-Onaizan, M. Bansal, and Y.-N, Chen, editors, Findings the Association for Computational Linguistics: EMNLP 2024, pages 7957-7970, Miami, Florida, USA, Nov. 2024a. Association for Computational Linguistics. doi: 10. N0.18653/v1/2000 2t0.33////222.//// htto:///w//2222f/nnnnnneeeeaaaaa findings-eenmp..67.. URL
connthooogy.co org/2044. ndin maiinng-eem.e emn p. 4677
C. Xu, Xu, Y. Ding. X. Zhang, and Q Qi. Fairsyne: Ensuring amortized group exposure in distributed recommendation retrieval, 2024b.
14

---

Published as a conference paper at ICLR 2025
C. Xu, X. Ye, W. Wang, L. Pang, J. Xu, and T.-S. Chua. A taxation perspective for fair re-ranking. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '24, page 1494-1503, New York, NY, USA, 2024c. Association for Computing Machinery. ISBN 9798400704314, 14. doi: 10. 10.1145/6626772.35776.
S. Yao and B. Huang. Beyond parity: Faimness objectives for collaborative filtering. Advances in neural information processing systems, 30, 2017.
Z. Zhu, J. Wang, and Caverlee. Measuring and mitigating item undernnccommnnnaaioo bias in personalized ranking systems. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '20, page 449-458, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781 9781450380164.
15

---

Published as a conference paper at ICLR 2025
APPENDIX
A PROOF OF THEOREM
R | is the item -iem-group adjacent matrix, and Aig indicates item i E Ig. and 0 otherwise. Let E R I = | Eveu Cu,i log(Cu,))liez.
Proof. Let A E
Firstly, if an item belongs to multiple groups, it often has greater impact on other items the model. Therefore, will conduct normalization the adjacency matrix A with size T G to mitigate this influence: conduct Á is the row-normalized matrix for A: Á diag(A1) A. diag(a) denotes to construct a diagonal matrix based on vector æ.
Then, in RS, since the ranking list Lg(u (u) is selected according to the highest preference score Ca therefore we can re-write Equation ( as:
min 1 (AA w)
1(i Ig)
8g
Σ E
Cua log(Cu,i) S Mg Vg E g
ni
(II)
(ETx(())) (1)
Σ Cus S KKN
RET
Then can still write the Equation as
min
1 (A w)
(12)
s.t.
max gEg
A w) M.
Due to Lagrange dual method (Bot et al. 2008 we can still convert the problem as:
(À (Tw)g M).
min max -1 1 w) + A(max gEg
(13)
X
mg
Therefore, we can always find a À 2 (A value relates to the value of M), such that we can directly optimize
(ÁTw) ww)
min 1 A ur + À Aaxx
(14)
9Eg
mg
Let r IR the vector [L/m1, 1/m2, ... 1/mg// then the equation can be written as:
min ITÀ w max 7g (Aww), 9E9
(15)
Furthermore, the minimum function max() :) can be viewed as the infinite norm function:
max & lim (1 T T/t
t-+00
Then we consider the following function:
g(æ; k;; s) (k' x t
where x < M1. Therefore, Equation (15) can be regarded linear trade-off between two points with the À 2 0 as the trade-off coefficient:
min g w; 1;0) Ag w: 7;00))
wEW
Since g(x; t) is continuous w E W is the linear transformation over a simplex space (Lindenstrauss et al. 1978)), there exists constant number 2 0 and b E G s.t. Equation (I] can be optimized as:
and the feasible region of x is convex and continuous (because
f min b (Á w+)
16

---

Published as a conference paper at ICLR 2025
This is because t is a constant number and k for optimizing g k; s) is linear w.r.t to (+++)) (Since the x is the variable and 8 is constant).
Note that the specific value of f is implicit function and cannot be solved explicitly in closed förm. This is because according to the fact that the function g is continuous with respect to over its entire domain and based the intermediate value theorem for continuous functions, there must exist t such that the linear combination of the linear functions at the two endpoints equals.
Nonetheless, emphasize that the subsequent methods and proof strategies independent of the explicit solution for L. As long as there exists a / A O, the Jansen gap exists, and as increases, / will also increase.
B LEMMA 1
Lemma 1. When 2 0, let
f(x)= = +t1
where x > O. And
i
e(1) Σ f(w)
(16)
S.I. Σ 31 Sc 20
where e is a constant number. Then we have when j 2 we have ming, e(i) S miny e(t).
Proof. According to the Lagrange dual method, we have
min e(i) min max $20
f(y1)
-02 n1) Ac,
then according the condition of the first derivative equaling zero, have
de(i)
de(i)
of + -
Σ 1=1
31 - c
8y
Ox
Taking these two condition together, we have:
Um
Vk. m = (1,2,...,
Therefore, we have
min e(j) min e(t) min Σ [((1)
min Σ f(v) 21
25
v/3
- ())
-G))
Then we can see function 1 - is a decreasing function function, therefore, ming, e(i) S ming e(1).
17

---

Published as a conference paper at ICLR 2025
C PROOF OF THEOREM 2
Proof. Under mini-batch sample strategies, we partition the user set 4 into / subsets and perform optimization each subset. For each batch, the optimization becomes
B
_ min
Σ bT (ATT))))
_=1
(17)
s.t.
Σ KEdl
Cu,
,
where U6 is the b-th partition of the user set U.
Since the function fa)) = ++ is not a linear function, we have
21/B
Σ b (
wj) ())) + bb (A w) 1+
and we can get the Jensen gap
J(B) L - L + 0.
Then we will observe how e(B) changes w.r.t. the mini- mini-batch size B.
Let e = A w. where each element e, represents the utility (sum of user-item scores) of group According to the recommendation constraint, we have e, L. meaning that the utility of group is at least as high as when all items belonging to group are recommended to the users.
Therefore, taking f fee) ++ into Lemma | without loss of generality, when batch size B₂ < B1, casily have:
have: (2/B22 [1]/B1,
12///12
RB//8,
min Σ
(A T w. w, 1+1 S min Σ
(A "w 11+ S min e
1+
Therefore, we have
[M] F2
M//B1
min Σ (A < min Σ j=1
w, S min eTe
e+
In other words, the mini-batch size becomes smaller, and we are more likely to underestimate the original loss function that trades off MMF and recommendation accuracy. The recommendation loss underestimation will result in the Jensen gap when optimizing the loss function constraint with MMR
D LEMMA 2
Lemma 2. Considering the following function, for À > 0, L 0 and for the d-th dimension variable I Rd, when μ E M:
r(H))
max x m 41" x/>).
(18)
=Sm
where
M
Σ 2 2 PE(d]
2, where S is power set [1,
d]. i.c., the set of all subsets of [1, 2......... d).
When μ E M, the optimization function r(-) has closed form: r(u) = m. u//x / + 1, and m arg max (min x a/m + μ x/2).
When μa M, the function r(.) will diverge to cc.
18

---

Published as a conference paper at ICLR 2025
Proof. Let the variable z/m 1. Then we have:
r(p)
max aSm
[min z/m m + j x/A]
m + max #50
min 2, + (1/A)/ (=
where @ is the Hadamard product.
Let
1= ==mo + p
then we define
s(v) = max
min 2, + TT v)
=50
From the definition the region M, we can re-wright M as
M
{ul
Σ 02
2 vld E ES.
sE[d]
Suppose that there exists subset S [1,2,. d] such that Eies V, < -1. For any c/|S| 1,
can get a feasible solution:
e/|s| i s otherwise.
0, 0,
Then, because such solution feasible and min; 2, = -,, and |S| 2 1, we obtain that
s(v) 2 min
(E/1S))
Σ v.)
v. + 1/ S|)
i
iES
iES
2 E + 1).
iES
Let c - co, we have s(v) + co.
Then we show that s(u) 0 for v E M. Note that is feasible. Therefore, we have min 0; 2 s(0) = 0.
Then have S 0 and without loss of generality, that the vector is sorted in increasing order, i.e., 21 S 22, S zd. The objective value is
5(1) = 21 + v
d
= Σ
(zj
zz+1)
1 Σ Us
S 0.
j=l
Thus we can have s(p) = 0 for v E M. Finally, we can have arg max (min, Tg/m, m x=\)== m.
LEMMA
3
Lemma 3. The feasible space M of dual variable μr is convex.
Proof. Suppose la E M, from Lemma
2 we have
r(p) max (min x e/r + p To x/1) < 00,
therefore, for any E G and e > 0, we have
r(u + cb) = mmaxmmin + ( + cb) x/1)
#S7
r(() + Lcb < 00.
Therefore, y cb E M.
19

---

Published as a conference paper at ICLR 2025
F PROOF OF THEOREM 3
Proof. e Aw, where each clement e measures the ranking score accumulated among group Let L be the maximum ranking score for each group, i.e., L1.
According to the proof in Theorem
1
we can see the Equation can be written as:
min ΣΣ
Cu.i log(Co,s) + A(max eg/mg)
gEg
wEU IEI
I(i E Ig)
s.t.
eg
Cu,i log(C,,,),. E g.
n4
Then the equation be re- re-written
max
Σ
Cu.i log((u,)) + A(min e m/mg) gEG
Bu.é
WEM
(19)
S.t.
eg
[li log((,.)) Vg g.
Then can utilize the Lagrangian condition (Balseiro et al. and model prediction Gn,5 in Equation
202
to decompose the relation between
19):
max maxmin Cu.i
ΣΣ NEl RET.
cu.s log(C..s) + A(min e mmm)) Σ
Mg
Cz - Σ'
I(i Ig)eu, log(Eu,))
gEG
9EG
nell IET
min max
ΣΣ Cu.s log(C,,s) + A(min e m/mg)
Σ
Mo
Cg ΣΣ
I(i E Ig, log(Cuus)
buti
gEg
WEM
DEG
NEM
min max
ΣΣ
- gEg
Mylli E Cg)) log(Cu,))
+ + eanine//mi e + +
well EEI
ΣΣ wEll 9Eg
Σ IEI
Cus log (Cus))))) + Amineg//mg + + pr Te.
min max Cu,t
Mgg
(20)
From the Equation (20). we can observe that the recommendation task constrained by max-min fairness can be viewed re-weighting approach across different groups on the original loss function solely optimized for accuracy:
C min ΣΣ
8
Σ iEZ,
Cu,i (og(C.,)),
WEti DEG
where the fairness weight μ is determined by
arg min WEM
max ΣΣ
89
Ca. log(Cu.)) Ar Axr(w))
wEl gES
IEI,
(11)
max wSm
min( A + w////\ = =m 11/+1
To make the functions do not diverge, need ensure r (1)) oc. Taking the r" (11) into Lemma we show M, where
M
Eumm -X,
gES
where G. is power set of G. i.e., the set of all subsets of G.
20

---

Published as a conference paper at ICLR 2025
G PROOF OF THEOREM
Proof. We first bound the performance on the primal space.
Let N [/ be the total batch number. Considering the j-th batch, we have the accuracy loss
B
function without fairness at j-th batch as:
L2 (ACC) = (8* A
and the max-min fairness loss function will become:
L2 (Fair) r" (nL) (1x) ) e/A,
therefore, the overall loss across L the primal space utillizig batch training will become:
NE,IC*] [E2] + AC' (Fair)]
.NE, ((' + A' (²) T + Ar" (n)) -1x2)
f B - NE,((E)) (e- (Ai) TP)]
The term
- (e-))
considered as the complementary slackness dual theory (Churchman et al. 1957), which captures error from the dual transformation. And C B is the same in Equation (5). Therefore, the original loss be viewed the dual form augmented with complementary slackness form.
Then we utilize the online gradient descent to bound the complementary slackness.
Let = Σx 1x, then the loss without dividing the full dataset into batches can be represented as:
L == w()).
After observing the dual form of L', we can see the L' is linear w.rt. dual variable μa, therefore, have
L' ='= C.
and the Jensen gap
N
J(B) =
Σ
w w((+²) - w((a))
1=1
Given | 12 I G. for all j. we have:
lg 2l [1(1 a) Σ (0)
Next, we will bound the value of G. Firstly, according the dual gradient descent, we have:
g - C + Xr" (x²)) = - (A²) T w + 7j-
where 7, is the remain maximum loss column at j-th th updating batch. Therefore, we have the each element of wh has the bound of
W K,
since each user can obtain a maximum ranking score of for each preferred item in the ranking list with size of K. Typically, the group size is smaller than batch size (9)) B) and there exists = max, my (lypically, m, is proportional to the group size [G]. Then we get
1 < [ K)² L1913
where L > 0.
21

---

Published as a conference paper at ICLR 2025
According to the Theorem 2 in Balseiro al. (2021), have
H
G
[
G
J(B) Σ
w(px) mr(14)] -
+
1)
(1 a
B
2(1 -a)an
==1
H
[
1.19/2
= 17 B(1 11-aajo"
7 n
2(1 - 211-a)Pam
where function | is o-strongly convex. When setting learning rate O(B-1/2), the Jensen Bound is comparable with O(B-1/²).
H GENERALIZABILITY TO OTHER FORMS OF FAIRNESS
In fact, our method can be easily generalized to the user group level by replacing the adjacency matrix with a user-side equivalent while keeping the rest unchanged. For the two-sided form, simply requires introducing two coefficients, Å1 and X2, and applying two independent dual gradient descent updates as described in our algorithm.
In Theorem I demonstrate that optimization objective equivalent the power-family fairness framework, which encompasses mainstream fairness definitions such as Entropy Fairness, a-Fairness, and Theil Index [an and Chiang (201T). Consequently, method is highly adaptable and can be generalized to various fairness objectives within this framework.
I DETAILS OF EXPERIMENTAL SETTINGS
Here we will provide the details of experimental settings. Detailed Implementation Details.
Environment: experiments
implemented using Python 3.9 and PyTorch 2.0.1+cul11 17 (Paszke et al., 2017). All experiments were conducted on a server with an NVIDIA A5000 running Ubuntu 18.04. We implement FairDual with the evxpy (Diamond and Boyd 2016) for optimization.
Hyper- plyperrparameter settings: the learning rate 1) E [1e_2, 1e-4] (results shown in Figure 5)
and trade-off factor À E [0, 10] (results shown in Figure 3 We set the my the group size m, = |. J. We also tune sample number Q E [50, 400 (results shown in the Table 5).
historical length H [3,7] 7] (results shown in Table 4 freeze parameter updating gap
3 E [128, 3840] (results shown in Figure 4
LLMs settings: 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 0.0, and the penalty for presence is 0.0, the maximum generated token number to 1024.
Used toolkit: For the Non-LLMs-RS. backbones, we mainly reference the RecBole toolki F For the LLMs tuning, we reference the BigRec pipelines [ And we have also included our code in the supplementary materials to ensure reproducibility.
Datasets. The experiments are conducted on the commonly used two widely used and publicly available recommendation datasets, including:
MIND Wu et al. 2020 it is constructed from news click behavior logs the Microsoft News platform. we utilize the major topic category of the news to group the items. The dataset contains 94,057 users, 18,801 items, 124, 154 interactions, and 17 groups.
22

---

Published as a conference paper at ICLR 2025
Amazon- Amazon-Book The Amazon dataset from the book domain (He and McAuley 2016 with item grouping based on the "categories" field. As part of the preprocessing (Xu et al. 2024b). groups containing fewer than 50 items amalgamated into a single group, referred as the "infrequent group". The dataset contains 15,362,619 users, 1,175,085 items, 1,051,862 interactions, and 25 groups.
Amazon-Eleee Electronic The Amazon dataset from the electronic products (He and McAuley 2016 with item grouping based on the "categories" field. As part of the preprocessing (Xu et al., 2024b), groups containing fewer than 50 items are amalgamated into single group, referred as the "infrequent group". The dataset contains 728,719 users, 160,052 items, 6,739,590 interactions, and 19 groups.
Backbones. For the backbone, we first select three large-scale recommender models:
NRMS (Wu et al.
2019) with 110M parameters utilizes BERT (Devlin et al. 2018 as the
feature extractor.
2023) with 150M parameters utilizes LongFormer (Beltagy et al. 2020 learn text- bastd representation from items
RecFormer (Li et al.
BigRec (Bao et al., 2023) utilizes Lora techniques (Hu et al. 2021 to fine-tune Llama
2 (Tourron et al.) 2023) (with 7B parameters). Note that BigRec only utilizes 1024 samples to train due to large computational cost.
Meanwhile, also cover three traditional recommender models:
BPR Rendle et al. (0012) utilized a pair-wise loss function to train a matrix factorization model for recommendation.
GRU4Rec Hidasi et al. (2015) utilized gated recurrent unit network to learn the historical
behaviors of users.
SASRec Kang and McAuley (018a) utilized attention network to learn the historical behaviors of users.
Baselines.
For the baselines, choose several fair-aware re-weight baselines that aim to improve group MMF:
UNI: each sample has the same weight during training.
DRO (Hashimoto al. 2018): every step, the model only optimizes the worst-off groups to enhance grou MMF.
S-DRO (Wen et al.
2022): improves DRO with the distributional shift optimize group
MMF.
Prop (Hu et al. 2023) assigns higher group weight to the samples closer to the decision
boundary in each group
IFairLRS (Jiang et al. 2024) employs the reciprocal of the sum popularity of items within the group the weight assigned to that group.
Maxmin Sample (Abernethy et al.) 2022) applies optimizing techniques to dynamically sample groups.
Meanwhile, we also choose three fair-aware non- LLM recommender models that aim to improve group faimess:
FOCF (Yao and Huang. 2017) applies a fair-aware regularization loss of different groups
into non-LLMs RS.
Reg (Kamishima and Akaho 2017) penalizes the squared difference between the average scores of two groups for all positive user-item pairs into non-LLMs RS.
FairNeg (Chen et al. 2023a proposed a negative sampling way for pair-wise recommenda-
tion into Mon RS. Note that FainNeg only be applied to pair-wise RS models.
wwdd edu
23

---

Published as a conference paper at ICLR 2025
1.2
2.5
NDCC(19)
MME (36)
1.5
0.6
128
640
1280
2560
3840
128
640
1280
2560
3840
B
(a)
(b)
Figure 4: Sub-figure (a) and (b) describe the NDCG and MMF changes w.r.f. freeze parameter updating gap B.
2.3
NDCG
MMF(5)
0.75
0.5
1.5
1e-5
5e-5
1e4
1e-3
5e-3
1e-5
5e-5
le-1
1e-3
5e-3
Learning Rate 77
Learning Rate 7j
(a)
(b)
Figure 5: Sub-figure (a) and (b) describe the NDCG and MMF changes w.r.f dual learning rate 7).
NDOC(1))
MMP(%)
1.0
0.5
10
20
30
10
20
30
Hidden Layer ID
Hidden Layer ID
a
(b)
Figure 6: Sub-figure (a) illustrates the density distribution of embeddings for each hidden layer of
Llama2. Sub-figures (b) and (c) depict the changes in NDCG and MMF metrics when different hidden layers utilized to represent user item embeddings.
24

---

Inference Updating Gap 3. We first will investigate the impacts of freeze parameter updating gap 3. As shown in Figure 4 we can observe that the accuracy degree (NDCG) increases when observe that the Published as a conference paper at ICLR 2025
Table 3: Performance comparisons between ours under other non-LLMs backbones on MIND dataset.
The * means the improvements are statistically significant (t-tests and p-value < 0.05). The bold number indicates that the accuracy value exceeds that of all the baselines.
Spp-5
top-
top-20
NDCG (?)
MRR (%)
MMF (36)
NDCG (R)
MRR (R)
MMF (36
NDCG (8)
MRR (3)
(?)
DRD
0.73
0.62
12.9
0.87
0.72
11.8
1.12
0.79
12.9
0.42
0.32
0.05
0.57
0.38
0.06
0.95
0.45
10.0
[FairLRS
0.68
0.57
0.13
0.77
0.61
1.07
0.09
1.38
BPR
Maxmin sample
ROCF
0.40
0.66
0.58
6.54
0.57
0.81
0.64
8.8
1,05
0.71
10.87
10.0
Reg
HarrNeg
0.72
0.63
6.07
0.91
0.71
8.8
1.21
0.79
12.64
Ours
0.76
0.64
11,84
0.944
0.72
13,87
1.27
0..1
14.6
DRO
0.36
0.36
0.36
0.76
0.64
5.50
1.13
0.71
10.7
Prop
0.42
0.35
7.94
0.63
0.44
10.19
0.90
0.51
13.10
S-DRO
0.67
12.05
1FaiLRS
0.45
7.12
0.68
0.47
9:21
1,02
0.56
11.70
GRU
Maxmin sample
0.43
0.33
10.9
0.62
D.41
14:27
0.91
0.48
13.06
FOCF
0.56
0.11
5.62
0.79
0.63
7.11
0,70
10.29
Rog
Ours
0.59"
0,47
12.13
0.85
0.68'
12.77
1.16
0.76
14,09*
Prop
0.54
0.45
11.69
0.80
0.55
12.
1.16
0.57
13.01
S S-DRO
0.49
0.40
10.66
0.74
0.49
11.64
1.09
0.59
14.02
[FaiLLRS
0.58
0.57
12.63
0.60
0.58
12.35
0.58
13.73
Maxmin sample
FOCF
0.47
0.46
10.52
0.50
0.47
12.73
0.53
0.48
14.45
Reg
0.47
0.38
9:42
0.70
0.47
9.52
1.03
0.55
10.91
Ours
0.64
0
11.98
0.64"
13,08
1.31
0.67
14.51
Table 4: We conduct empirical experiments to show the effect of the length of item clem-elicked sequences. The experiments are conducted on the MIND dataset under BigRec backhones.
History length
NDCG@5(5)
MMF@5
NDCG@10
MMF@10 (%)
NDCG@20 (%)
MMF AMF@@20 (%)
1.88
0.81
1.63
1.36
2,65
1.99
3.21
6
1,04
2.57
1.64
2,66
2.26
3.29
3.27
3.5
2.16
MAIN EXPERIMENTS ON NON-LLMS BACKBONES.
We choose three non- Los-LLMs recommender models: BPR (Rnnlle et al. 2012), GRU4Rec (Hidasi
al. 2015) and SASRec KKngg and McAuley 2018a). And we also compare three group fair-aware on- on-LLMs recommender models: FOCF (Yao and Huang 2017), Reg (Kamishima and Akaho 2017). and FairNeg (Chen et al., 2023a). These models compared using traditional recommender system backbones, as detailed in Appendix
From Table further observe that FairDual consistently surpasses all baseline methods across ious datasets under non-I.LM backbones and different top-K ranking sizes. These results demonstrate that FairDual remains highly effective even when applied to non-LLM-based models.
Also note that another widely used loss function is the BPR loss Rendle et al. (2012), which aims increase the distance between positive and negative samples. Interestingly, from the table, we can observe that our methods can also be applied to this loss, as BPR loss is convex function with respect positive items, and our dual formulation remains valid.
K ANALYSIS FOR HYPER-PARAMETE
We also conduct analysis for other important hyper-parameterr of FairDual MIND dataset under BigRec base models.
E 1188, 1280] and then drops slightly when 33 [1280, 3840). Similarly,
25

---

Published as a conference paper at ICLR 2025
Table 5: We conduct empirical experiments show the effect of the sample size Q. The experiments are conducted on the MIND dataset under BigRec backbones.
sample size Q
50
100
200
300
400
full (unbiased)
(
1.08
1.08
1.15
1.19
1.19
1.29
MMF(%)
1.2
1.28
2.18
2.10
2.29
2.31
Table 6: The convergence time (performance stabilizing within 50 steps) of our method compared to other baselines under BigRec backhones on the MIND dataset.
Model
DRO
Prop
S-DRO
IFairLRS
FairDual(ours)
Improvment
Convergence time
10.1h
11.7h
7.9h
7.1h
5h
28.5%
fairness degree (MMF) increases when 3 E [128, 640) and then drops with a large margin when E [640, 3840). The results align with our expectations: excessively frequent updates lead to instability during training, while infrequent updates may cause the model to miss new ranking patterns, ultimately affecting performance negatively.
Inference on dual learning rate 7). We then investigate the impacts of dual learning rate y). As shown in Figure we can observe that the accuracy degree (NDCG) increases when v) [le 7.5e-5 5] and then drops when [5c-5, 5e- 3]. On the other hand, the fairness performance drops when 1) goes larger. The results demonstrate that the learning rate 1) serves as a trade-off off factor: excessively large values detrimentally affect both accuracy and faimess, whereas excessively small values improve fairness at the expense of accuracy in recommendation system models.
Performances under Different Hidden Layers. In this experiment, we aim to analyze the FairDual performance under different hidden layers in Llama2. We test the NDCG and MMF performance when we utilize different hidden layers represent and (b), it is evident that the accuracy (NDCG) and fairness (MMF) trends exhibit distinct patterns: accuracy performance initially ascends, peaking in the middle layer before gradually declining, whereas fairness performance initially descends, hitting a nadir before steadily increasing.
item embeddings. From Figure 6 (a)
This phenomenon be interpreted follows: in the initial layers, which are not yet fully trained, the recommendation system tends to suggest more random items, resulting in lower accuracy but higher fairness. As the layers deepen, the accuracy increases, but it also tends recommend more unipolar items. Eventually, as the layers approach the last layer, our FairDual model emphasizes fairness more by adjusting the weights for the weaker groups. This will also help better understand the mechanisms of FairDual.
Performances under different lengths // of item-clicked sequences. In Table conduct the empirical experiments to show the effect for the length of item-clicked sequences. The experiments are conducted on MIND dataset under BigRee backbones.
From the experiments, we can observe that the length of history is a trade-off factor for the methods: initially, increasing the length improves accuracy and faimess, but once it reaches peak, performance begins to drop. We analyze the reason as follows: the length of history sequences indeed influences performance. Sequences that are too short make it difficult learn user preferences, while sequences that are too long increase computational costs and risk hitting the prompt limit of LLMs.
Performances under different sample sizes Q. Intuitively, 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 the analysis section. The experiments were conducted under BigRec on MIND dataset with ranking size K- 5.
From the results in Table 5 we observe that increasing the sample value Q leads to improvements in both accuracy and fairness performance. However, LLM-based recommender systems, a larger Q significantly increases training time (with each item requiring additional 1.5 seconds) and storage
26

---

Published as a conference paper at ICLR 2025
Table 7: Performances of other fairness metric Gini Index.
Models
GINI@5
GINI@ 10
GINI@20
Prop
0.488
0.488
0.472
DRO
0,511
0.476
0,487
SDRO
0,503
0.478
0,453
IFairLRS
0,458
0.454
0.448
FairDual(ours)
0.444
0.450
0.441
Table 8: Popularity bias effect utilizing Inverse Propensity Score (IPS)-based Xu et al. (2022) reweighting method.
A
0.1
1
2
5
NDCG(%)
IPS
0.58
0.58
0.58
0.58
FairDual
0.53
0,60
0.57
0,67
IairDual+IPS
0.59
0.56
0.56
0.58
MMF(%)
IPS
12.63
12.63
12.63
12.63
FairDual
4.50
11.98
13.46
13.76
IPSS
10.90
12,40
12.40
14.36
space. Different applications should select appropriate Q values based on their specific accuracy, fairness requirements, and computational constraints.
L COMPUTATIONAL AND STORAGE COSTS
In Table measured the convergence time (performance stabilizing within 50 steps) of method compared to other baselines under BigRec backbones on MIND dataset.
Firstly, all have parameters of the same magnitude (i.e., group size parameters (hundred level), which are in the range of hundreds and negligible compared to the backbone (million level)). Our method only requires additional space for Q item embeddings and extra training time (1.5Qs). Applications can trade off Q based on available resources (as discussed in a previous response).
Secondly, as observed in Table 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.
M PERFORMANCES ON OTHER FAIRNESS METRICS
We test the performances another fairness metric Gini Index (Do and Usunier 2022) Compared to the baselines ( on MIND datasets. Note that a smaller Gini Index means more fairness. From the results, we can observe that our model can still perform well other fairness metries. We believe our paper can help other researchers explore its applicability to various loss functions, and other fairness metrics, which also our contribution the communities.
N EFFECT OF POPULARITY BIAS
Since the popularity bias will influence the accuracy estimation in real dataset shown in Figure 3 we conduct the experiments relatively light transformer-hased SASRec (Kang and McAuley 2018a)
27

---

Published as a conference paper at ICLR 2025
backbones and MIND datasets. We apply the Inverse Propensity Score (IPS)-based Xu et al. (2022) to our method to see whether can improve our methods.
Table 8 shows the results K = 5 results. From the results, small, adding the IPS will increase the accuracy and fairness with a large margin due to the popularity bias. However, when À is large, the FairDual+IPS will not perform very well. This is because IPS will break the convergence condition of FairDual. Therefore, when À large, is preferable not to involve IPS. We will include the related experiments and discussion in the Appendix of the revised paper.
observe that when the À is
28


Reviews:
[{"review_id": "kdTcqtccLq", "reviewer": "Reviewer_REQg", "summary": "This paper, through theoretical and empirical analysis, argues that existing methods with group max-min fairness (MMF) optimization for fairness-aware recommender systems will introduce Jensen gaps during model convergence when applying mini-batch sampling. It theoretically reformulates the MMF constraint objective as a group-weighted optimization objective and proposes a FairDual algorithm to minimize the Jensen gap. The effectiveness of FairDual is verified on two public datasets combined with three skeleton recommendation models.", "questions": "Please see the description in Weaknesses.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "S1: Sufficient support is provided for motivation through theoretical and empirical analysis.\n\nS2: A new perspective based on group-weighted optimization is provided for MMF, and some corresponding theoretical insights are provided.\n\nS3: Combining different skeleton models on multiple datasets provides various experimental results.", "weaknesses": "W1: The quality and clarity of the presentation need to be improved. Including some unclear statements that need to be revised, the organization of figures and tables needs to be revised, and some content coherence needs to be further revised. For example,\n* For Formula 1, the meaning of the symbol $n_i$ seems missing. Secondly, based on the description in the second paragraph of Section 3, $L_k(u)$ is used to represent the recommendation list, and $K$ identifies the list length. However, in the description in the last paragraph, the statement \"following the practice in time-aware RS, there may be users with interactions cu,i greater than the ranking size K, in which case we will only consider the least recent K interactions to represent their recent preferences\" is confusing. 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?\n\n* Regarding the first paragraph of Section 4, the statement “In real-world scenarios, the number of users |U| is often large, and a mini-batch sampling strategy is often necessary due to the large computational costs. This involves dividing the |U| users into |U|/B batches and performing gradient descent methods on each batch” is also confusing. In my experience, in practice, grouping users into different batches for optimization is not usually adopted, i.e., 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. The purpose of emphasizing this aspect here is unclear.\n\n* 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.\n* For the last paragraph of Section 5.2.1, the meaning of *P* is missing.\n\n* 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.\n\n* The current placement of figures and tables does not facilitate reading and needs to be placed as close to the corresponding description as possible.\n\n* I like the first half of this paper. However, I am confused about why fairness must be associated with large recommendation models (especially large language recommendation models) after the methods section. On the one hand, this makes some of the treatments required for large language recommendation models appear abruptly. On the other hand, it is not conducive to evaluating the effectiveness of the proposed solution for fairness in a more general setting.\n\nW2: The proposed FairDual lacks some deeper and more valuable insights. For example,\n* Does it have the same performance or properties for other types of loss functions?\n\n* Does it have the same behavior or properties as other fairness optimization constraints?\n\n* How does it compare to existing work regarding storage space, computational complexity, and parameter size? Some static or dynamic group weighting methods discussed in related work seem lightweight. Is the additional overhead worthwhile?\n\n* If it is not just about fairness at the item group level, does it apply to fairness at the user group level or even in situations where both users and items exist in groups?\n\nW3: The current experimental setup and experimental results are not convincing enough.\n* Representative datasets adopted by many previous fairness recommendation methods should be included more.\n\n* Related to the previous concerns, the current version's selection criteria for baselines are confusing and not sufficiently representative. Skeleton models should not be constrained to be recommendation models related to large language models, and more research lines of fair recommendation methods mentioned in related work should be included as baselines, especially those aimed at designing group weighting.\n\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pxyKJMds0E", "reviewer": "Reviewer_SoKV", "summary": "This paper analyze the Group max-min fairness (MMF) constrained optimization problem in recommendation. The authors first explain the Group MMF constrained objective as a non-linear polynomial form, indicating that the Jensen gap is non-negligible in mini-batch sampling based optimization (i.e., the gap between the overall loss and the sum of batched loss). To bridge the Jensen gap, this paper propose a dual optimization method called FairDual. Specifically, they rewrite the objective as a group-weighted BCE loss, and utilize the dual mirror gradient descent algorithm to optimize this loss. They further conduct experimental validation of FairDual's effectiveness and provide a detailed analysis of its proposed theoretical advantages.", "questions": "**Major Concerns:**\n\n**Questions about Theoretical Analysis and Algorithm.** I have the following questions about the theoretical analysis and algorithm in this paper that need clarification:\n\n- In the proof of Theorem 1 (Appendix A), why is Problem (15), i.e., $\\min\\mathbf{1}^\\top\\hat{\\boldsymbol{A}}^\\top\\boldsymbol{w}+\\lambda\\max_{g\\in\\mathcal{G}}\\gamma_g(\\hat{\\boldsymbol{A}}^\\top\\boldsymbol{w})_g$ , equivalent to Problem (2), i.e., $\\min\\boldsymbol{b}^\\top(\\hat{\\boldsymbol{A}}^\\top\\boldsymbol{w})^{1+t}$ ? Specifically, considering the limit in the function $g(\\cdot; \\infty)$ , how is the constant $t$ determined? Providing an explicit solution for $t$ and $\\boldsymbol{b}$ is important for Theorems 1 and 2.\n- The organization of Lemma 2, Lemma 3, and Theorem 3 (Appendix D-F) is somewhat disorganized. I suggest reorganizing these proofs, e.g.:\n  - Place Lemma 3 before Lemma 2, as the conclusion of Lemma 2 depends on Lemma 3.\n  - Rewrite the proof of Lemma 2 to explain why the conclusion can be derived from $r(\\boldsymbol{\\mu} + c\\boldsymbol{b}) < \\infty$ (i.e., Lemma 3).\n- The group-weighted form (4) of the Group MMF-constrained objective in Theorem 3 is concise, but its weight $\\boldsymbol{s}_g$ is not. The authors should provide some intuitive explanations for the weight $\\boldsymbol{s}_g$ to better elucidate the experimental phenomena (Case study in Section 6.3). For instance, under what circumstances is $\\boldsymbol{s}_g$ larger, and when is it smaller?\n\n- In the calculation of $\\widetilde{w}$, the authors randomly sample $Q$ items and set $\\widetilde{\\boldsymbol{w}} _ b=\\sum _ {k=1}^K(\\boldsymbol{E} ^ j\\boldsymbol{e} _ {u _ b}) _ {[k]}$ (cf. line 12 in Algorithm 1, and line 358). I am primarily concerned about the bias caused by sampling-based ranking (although it does not affect the fairness bound given in Theorem 4). Can the authors provide a theoretical analysis of this bias? Alternatively, could the authors change the sampling-based ranking to random sampling of $\\boldsymbol{E}^j\\boldsymbol{e} _ {u _ b}$ , and test the impact of this bias on the convergence rate of Jensen gap?\n\n**Questions about Experiments.** I have the following concerns about the experiments:\n\n- There are only two datasets utilized in the main results (Tables 1 and 2), which is insufficient. The authors might consider adding one or two widely-used datasets, such as Amazon-Electronic, which can be processed using the same method as in Appendix H.\n- In Section 6.3 \"Experimental Analysis\", the authors find that the accuracy first increases then decreases as $\\lambda$ increases, and attribute the phenomenon to the popularity bias. Then, is it possible to apply popularity debias method to the proposed algorithm, e.g., Inverse Propensity Score (IPS)-based reweighting method?\n\n**Minor Concerns:**\n\n- Line 324, $\\hat c _{u, i} =  -d(\\boldsymbol{e} _u, \\boldsymbol{e}  _i)$, should there be $\\hat c _{u, i} =  d(\\boldsymbol{e} _u, \\boldsymbol{e} _i)$ ?\n- Line 325, the authors should suppose that $\\boldsymbol{e}_u$ and $\\boldsymbol{e}_i$ are normalized to make sure $d(\\boldsymbol{e}_u, \\boldsymbol{e}_i) \\leq 1$ , which is relied on by the proof of Theorem 4 (cf. Line 1064).\n- Line 357, \"The $L$ items’ embeddings are denoted as ...\", the $L$ should be $Q$ ?\n- Line 979, the minus in $-\\mathcal{I}$ should be placed at the loss term.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The Group MMF studied by the authors is significant for  recommendation fairness research.\n- The motivation of the paper is clear, the algorithm introduction is straightforward, and the experimental analysis is detailed.\n- The paper employs dual optimization to separate MMF and predicted score, resulting in a simple form of group-weighted BCE loss, and uses the dual mirror gradient descent algorithm for optimization, which is somewhat novel.", "weaknesses": "- Theoretical proofs contain parts that require clarification, and the writing of the proof needs further improvement.\n- The authors' analysis of the proposed group-weighted BCE loss is insufficient.\n- In the implementation of FairDual algorithm, sampling-based ranking may introduce bias that is not adequately discussed.\n- The authors conducted experiments on only two datasets, which may not be sufficient to demonstrate the algorithm's generalization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lRy72WoX5h", "reviewer": "Reviewer_w1tq", "summary": "This paper observes that the MMF-based optimization introduces a Jensen gap, which will become more pronounced when mini-batch size decreases and group size increases. The authors reformulate MMF into a group-weighted optimization, and solve its dual to minimize Jensen gap. Theoretical analysis reveals that the proposed method achieves a sub-linear convergence rate. Experiments are conducted across three recommendation models on two datasets.", "questions": "Please refer to Weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tThe paper provides both theoretical analysis and empirical results for motivation derivation and the effectiveness of the proposed method.\n2.\tThe experiments are conducted across large-scale recommendation models, which aligns well with the stated motivation.\n3.\tThe paper is generally well-written, with a clear structure.", "weaknesses": "1.\tThe assumption of convexity is too strong and impractical for large-scale recommendation models.\n2.\tWhy can the reported NDCG exceed 1, which is theoretically impossible? Also, please specify the number of items in the truncated list K.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uRxBpEuA7P", "reviewer": "Reviewer_EADi", "summary": "In this paper, the authors claimed that current group max-min fairness (MMF) methods would introduce a Jensen gap between the model’s\nconvergence point and the optimal point. The authors analyzed the existence of Jensen gap theorically and emprically. Then, the authors proposed FairDual, a  dual-optimization approach that guaranteed a bound for the Jesen gap. They conducted comprehensive experiments to show the effectiveness and efficiency of FairDual compared to baselines.", "questions": "- Can authors explain is there a reason that in some cases the MRR is not statistically significant as shown in Table 1 and 2? For example, the MRR in the top-5 results of RecFormer and BigRec is not significant and no improvement, while the improvement of NDCG and MMF is significant. Can authors give some insights on this observation?\n\n- In the visualization of Figure 3(c), the differences in the patterns of the two figures are not quite obvious. The classification boundary of FairDual also seems to exist. Could the authors provide some quantitative results to distinguish the different patterns, such as divergence in the two distributions?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The motivation is well established with theorical and emprical analysises of the Jesen gap in Section 4.\n- The method is solid with a guaranteed bound for Jesen gap, and the experiment also showed that the proposed method indeed has lower gap than other baselines.\n- The authors conducted complete and comprehensive evaluations, including the effictiveness, Jensen gap analysis, case study, training efficiency and parameter analysis.", "weaknesses": "- Baselines. The authors mentioned that there are two types of approaches to bridge the Jensen gap,  re-weighting and optimization-based methods. But the authors mostly compared only re-weighting methods in the experiments, while ignoring optimization-based methods they mentioned in the introduction part, such as  Abernethy et al. 2022, Cousins 2022, Demidovich et al., 2023 and Agarwal et al., 2018. I suggest the authors to add state-of-the-art baselines in optimization-based methods mentioned in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SaNYIGDVJe", "reviewer": "Reviewer_1uT1", "summary": "In this paper, the authors address the challenge of integrating a max-min fairness constraint, which introduces a Jensen gap between the model’s convergence point and the optimal point. They first demonstrate that using mini-batch sampling optimization strategies leads to a Jensen gap that increases as the mini-batch size decreases. To bridge this gap, the authors propose an algorithm that reformulates the original optimization problem through a re-weighting approach, leveraging dual-optimization techniques to update the weights of each group. They theoretically prove that their approach achieves a sublinear convergence rate and numerically demonstrate its effectiveness.", "questions": "- Could the results extend to alternative fairness constraints beyond max-min fairness?\n- What is the computational complexity of the proposed algorithm and how does it compare with the other baselines?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well written and provides interesting insights. \n- The authors well motivated the problem in Section 4 where they established the existence of Jensen gap.\n- The theoretical results appear sound. The authors also provided extensive numerical evaluations of their method.", "weaknesses": "- It'd be helpful if the authors can 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. \n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)