Research map / Learning theory and algorithms / Fairness
Bridging Jensen Gap for Max-Min Group Fairness Optimization in Recommendation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that max-min fairness constraints in mini-batch recommender training induce a Jensen gap, and proposes FairDual, a dual mirror-gradient method that reweights groups to shrink this gap with a sub-linear convergence and bounded-gap guarantee.
Problem
Group max-min fairness (MMF) constraints in recommender systems break sample independence, so mini-batch training converges to a point that deviates from the optimum (a Jensen gap), which worsens as batch size shrinks and group count grows.
Approach
Reformulates the MMF-constrained objective via Lagrangian duality as a group-weighted accuracy loss whose weights (1 - mu_g) come from a dual variable, updated per batch with momentum mirror/dual gradient descent and a frozen item-encoder snapshot for ranking scores.
Key results
- On MIND with BigRec backbone at K=5, FairDual reaches NDCG 1.15% and MMF 2.82% versus best baseline MMF 2.25% (Maxmin Sample).
- On Amazon-Electronic with BigRec at K=10, FairDual achieves MMF 0.30% vs 0.25% for UNI, a 19.9% relative improvement.
- Jensen gap of FairDual stays stable across batch sizes in simulation, while baselines widen as batch size decreases and group size increases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FairDual instead of the strongest listed baseline | BigRec · MIND, top-5 | NDCG (%): 1.11 -> 1.15 | Helped |
| Use FairDual instead of the strongest listed baseline | BigRec · MIND, top-5 | MRR (%): 0.88 -> 0.88 | No clear effect |
| Use FairDual instead of the strongest listed baseline | BigRec · MIND, top-5 | MMF (%): 2.25 -> 2.82 | Helped |
| Use FairDual instead of the strongest listed baseline | BigRec · Amazon-Book, top-5 | NDCG (%): 2.99 -> 3.11 | Helped |
| Use FairDual instead of the strongest listed baseline | BigRec · Amazon-Book, top-5 | MMF (%): 8.68 -> 8.90 | Helped |
| Use FairDual instead of the strongest listed baseline | BigRec · Amazon-Electronic, top-5 | MRR (%): 4.34 -> 4.78 | Helped |
| Increase the fairness trade-off coefficient λ from 0 to 5 | FairDual with BigRec · MIND | NDCG | Helped |
| Increase the fairness trade-off coefficient λ beyond 5 | FairDual with BigRec · MIND | NDCG | Hurt |
| Increase λ | FairDual with BigRec · MIND | MMF | Helped |
| Use FairDual instead of UNI | BigRec · MIND | embedding KL divergence between groups: 0.113 -> 0.083 | Helped |
Surprising findings
- Accuracy first rises and then falls as the fairness coefficient lambda grows, attributed to popularity bias in the datasets and to the Jensen gap at large lambda.
Limitations
- BigRec was trained on only 1024 samples due to computational cost.
- The value of the trade-off t and the bound constants are implicit and not solved in closed form; theory relies on assumptions such as bounded gradients and strong convexity.
Experimental setup
Datasets: MIND Amazon-Book Amazon-Electronic
Benchmarks: MIND Amazon-Book Amazon-Electronic
Metrics: NDCG MRR MMF@K
Baselines: UNI DRO S-DRO Prop IFairLRS Maxmin Sample FOCF Reg FairNeg
Builds on: Jensen gap analysis debiasing SGD mirror descent Lagrangian duality
Closest papers by meaning
- Intra- and Inter-group Optimal Transport for User-Oriented Fairness in Recommender Systems (AAAI 2024 · similarity 0.87)
- Interpolating Item and User Fairness in Multi-Sided Recommendations (NeurIPS 2024 · similarity 0.86)
- User-item fairness tradeoffs in recommendations (NeurIPS 2024 · similarity 0.86)
- ENSUR: Equitable and Statistically Unbiased Recommendation (ICML 2025 · similarity 0.85)
- CUGF: A Reliable and Fair Recommendation Framework (AAAI 2025 · similarity 0.85)
- Stability and Multigroup Fairness in Ranking with Uncertain Predictions (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.