Research map / Bandits and online learning / Online convex optimization and games
Monotone Individual Fairness
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.
Extends online individual fairness with auditors to monotone aggregation of multiple auditors and gives oracle-efficient algorithms with improved regret/violation bounds in full and partial (one-sided label) information settings.
Problem
Online classification with individual fairness where similar individuals must be treated similarly, with fairness violations reported by (possibly multiple) human auditors whose distance metric is unknown, under full and one-sided label feedback.
Approach
Defines monotone aggregation functions over multiple auditors, proves they reduce to a single instance-specific auditor per pair, and uses a dynamically weighted Lagrangian with Context-FTPL and online gradient descent to get oracle-efficient algorithms with fewer oracle calls per round.
Key results
- Full information: O(sqrt(T)) regret and O(T^{3/4}) fairness violations with O~(alpha^-2) oracle calls per round.
- Partial information (one-sided labels): O(T^{2/3}) regret and O(T^{5/6}) violations with O~(alpha^-2 + k^2 T^{1/3}) oracle calls per round.
- Interpolating frontier achieves uniform O(T^{2/3}) for both full-information accuracy and fairness, improving on prior O(T^{7/9}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use dynamic Lagrangian loss with Context-FTPL + Online Gradient Descent rather than the prior fixed-rate approach | Full information online learning with individual fairness · Full information, adversarial sequence | regret: \mathcal{O}(T^\frac{7}{9}) -> \mathcal{O}\left(s^\frac{3}{4}k^\frac{11}{4}T^{\frac{1}{2}}\log\vert\mathcal{H}\vert\right | Helped |
| Use dynamic Lagrangian loss with Context-FTPL + Online Gradient Descent rather than the prior fixed-rate approach | Full information online learning with individual fairness · Full information, adversarial sequence | fairness violations: \mathcal{O}(T^\frac{7}{9}) -> \mathcal{O}\left(\alpha^{-1}s^\frac{3}{4}k^\frac{7}{4}T^\frac{3}{4}\log\vert\mathcal{H}\ve | Helped |
| Reduce per-round optimization oracle calls using the proposed Context-FTPL reduction | Full information online learning with individual fairness · Full information, adversarial sequence | optimization oracle calls per round: T -> \tilde{\mathcal{O}}\left(\alpha^{-2}\right) | Helped |
| Use dynamic Lagrangian loss with Context-Semi-Bandit-FTPL + Online Gradient Descent rather than the prior approach | Partial-information online learning with individual fairness · Partial information, one-sided label feedback | regret: O(T^\frac{41}{45}) -> \mathcal{O}\left(s^\frac{3}{2}k^\frac{11}{2}T^{\frac{2}{3}}\log\vert\mathcal{H}\vert\right) | Helped |
| Use dynamic Lagrangian loss with Context-Semi-Bandit-FTPL + Online Gradient Descent rather than the prior approach | Partial-information online learning with individual fairness · Partial information, one-sided label feedback | fairness violations: O(T^\frac{41}{45}) -> \mathcal{O}\left(\alpha^{-1}s^\frac{3}{2}k^\frac{9}{2}T^\frac{5}{6}\log\vert\mathcal{H}\vert\right | Helped |
| Reduce per-round optimization oracle calls using the proposed partial-information reduction | Partial-information online learning with individual fairness · Partial information, one-sided label feedback | optimization oracle calls per round: T^\frac{38}{45} -> \tilde{\mathcal{O}}({\alpha^{-2}} + k^2T^\frac{1}{3}) | Helped |
Limitations
- Requires access to a small separating set for the hypothesis class and a batch ERM oracle.
- Bounds are theoretical with no empirical evaluation.
- Oracle-efficiency relies on resampling approximations of the deployed policy.
Experimental setup
Metrics: regret number of fairness violations
Baselines: Gillen et al. (2018) Bechavod et al. (2020) Bechavod et al. (2022) multiple-auditor majority schemes
Builds on: Context-FTPL Online Gradient Descent Gillen et al. 2018 auditing framework Bechavod et al. 2020
Closest papers by meaning
- Metric-Free Individual Fairness in Online Learning (NeurIPS 2020 · similarity 0.93)
- Individually Fair Learning with One-Sided Feedback (ICML 2023 · similarity 0.93)
- Cost Efficient Fairness Audit Under Partial Feedback (NeurIPS 2026 · similarity 0.86)
- Accuracy vs. Accuracy: Computational Tradeoffs Between Classification Rates and Utility (NeurIPS 2026 · similarity 0.86)
- Individual Fairness In Strategic Classification (NeurIPS 2025 · similarity 0.85)
- Geometry of Relaxed Fair Regression: A Unified Framework for Aware and Unaware Settings (NeurIPS 2026 · similarity 0.85)
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.