Fairness with Exponential Weights

• URL: http://arxiv.org/abs/2411.04295v2
• Date: Sun, 16 Feb 2025 14:07:06 GMT
• Title: Fairness with Exponential Weights
• Authors: Stephen Pasteris, Chris Hicks, Vasilios Mavroudis,
• Abstract summary: Motivated by the need to remove discrimination in certain applications, we develop a meta-algorithm that can convert any efficient implementation of Hedge into an efficient for the equivalent contextual bandit problem. Relative to any algorithm with statistical parity, the resulting algorithm has the same regret bound as running the corresponding instance of Exp4 for each protected characteristic independently.
• Score: 4.368185344922342
• License:
• Abstract: Motivated by the need to remove discrimination in certain applications, we develop a meta-algorithm that can convert any efficient implementation of an instance of Hedge (or equivalently, an algorithm for discrete bayesian inference) into an efficient algorithm for the equivalent contextual bandit problem which guarantees exact statistical parity on every trial. Relative to any comparator with statistical parity, the resulting algorithm has the same asymptotic regret bound as running the corresponding instance of Exp4 for each protected characteristic independently. Given that our Hedge instance admits non-stationarity we can handle a varying distribution with which to enforce statistical parity with respect to, which is useful when the true population is unknown and needs to be estimated from the data received so far. Via online-to-batch conversion we can handle the equivalent batch classification problem with exact statistical parity, giving us results that we believe are novel and important in their own right.

Related papers

• Targeted Learning for Data Fairness [52.59573714151884]
  We expand fairness inference by evaluating fairness in the data generating process itself. We derive estimators demographic parity, equal opportunity, and conditional mutual information. To validate our approach, we perform several simulations and apply our estimators to real data.
  arXiv  Detail & Related papers  (2025-02-06T18:51:28Z)
• Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness [0.0]
  We review the statistical estimation problems for randomized smoothing to find out if the computational burden is necessary. We present estimation procedures employing confidence sequences enjoying the same statistical guarantees as the standard methods. We provide a randomized version of Clopper-Pearson confidence intervals resulting in strictly stronger certificates.
  arXiv  Detail & Related papers  (2024-06-25T14:00:55Z)
• Differentially Private Post-Processing for Fair Regression [13.855474876965557]
  Our algorithm can be applied to post-process any given regressor to improve fairness by remapping its outputs. We analyze the sample complexity of our algorithm and provide fairness guarantee, revealing a trade-off between the statistical bias and variance induced from the choice of the number of bins in the histogram.
  arXiv  Detail & Related papers  (2024-05-07T06:09:37Z)
• Inference for an Algorithmic Fairness-Accuracy Frontier [0.9147443443422864]
  We provide a consistent estimator for a theoretical fairness-accuracy frontier put forward by Liang, Lu and Mu (2023) We propose inference methods to test hypotheses that have received much attention in the fairness literature. We show that the estimated support function converges to a tight process as the sample size increases.
  arXiv  Detail & Related papers  (2024-02-14T00:56:09Z)
• Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization [26.4468964378511]
  A replicable algorithm gives the same output with high probability when its randomness is fixed. Using replicable algorithms for data analysis can facilitate the verification of published results. We establish new connections and separations between replicability and standard notions of algorithmic stability.
  arXiv  Detail & Related papers  (2023-03-22T21:35:50Z)
• Statistical Efficiency of Score Matching: The View from Isoperimetry [96.65637602827942]
  We show a tight connection between statistical efficiency of score matching and the isoperimetric properties of the distribution being estimated. We formalize these results both in the sample regime and in the finite regime.
  arXiv  Detail & Related papers  (2022-10-03T06:09:01Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  We propose to use a nearest-neighbor-based $gamma$-divergence estimator as a data discrepancy measure. Our method achieves significantly higher robustness than existing discrepancy measures.
  arXiv  Detail & Related papers  (2020-06-13T06:09:27Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  We develop a framework that yields statistical accuracy based on interplay between the deterministic convergence rate of the algorithm at the population level, and its degree of (instability) when applied to an empirical object based on $n$ samples. We provide applications of our general results to several concrete classes of models, including Gaussian mixture estimation, non-linear regression models, and informative non-response models.
  arXiv  Detail & Related papers  (2020-05-22T22:30:52Z)
• Beyond the Mean-Field: Structured Deep Gaussian Processes Improve the Predictive Uncertainties [12.068153197381575]
  We propose a novel variational family that allows for retaining covariances between latent processes while achieving fast convergence. We provide an efficient implementation of our new approach and apply it to several benchmark datasets. It yields excellent results and strikes a better balance between accuracy and calibrated uncertainty estimates than its state-of-the-art alternatives.
  arXiv  Detail & Related papers  (2020-05-22T11:10:59Z)
• Certified Robustness to Label-Flipping Attacks via Randomized Smoothing [105.91827623768724]
  Machine learning algorithms are susceptible to data poisoning attacks. We present a unifying view of randomized smoothing over arbitrary functions. We propose a new strategy for building classifiers that are pointwise-certifiably robust to general data poisoning attacks.
  arXiv  Detail & Related papers  (2020-02-07T21:28:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.