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.<n>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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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)
• Semiparametric conformal prediction [79.6147286161434]
  We construct a conformal prediction set accounting for the joint correlation structure of the vector-valued non-conformity scores. We flexibly estimate the joint cumulative distribution function (CDF) of the scores. Our method yields desired coverage and competitive efficiency on a range of real-world regression problems.
  arXiv  Detail & Related papers  (2024-11-04T14:29:02Z)
• 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)
• Information Capacity Regret Bounds for Bandits with Mediator Feedback [55.269551124587224]
  We introduce the policy set capacity as an information-theoretic measure for the complexity of the policy set. Adopting the classical EXP4 algorithm, we provide new regret bounds depending on the policy set capacity. For a selection of policy set families, we prove nearly-matching lower bounds, scaling similarly with the capacity.
  arXiv  Detail & Related papers  (2024-02-15T19:18:47Z)
• 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)
• Contextual Bandits with Stage-wise Constraints [46.412612374393895]
  We study contextual bandits in the presence of a stage-wise constraint (a constraint at each round) We propose an upper-confidence bound algorithm for the problem and prove a $T$-round regret bound for it.
  arXiv  Detail & Related papers  (2024-01-15T23:58:21Z)
• Optimal cross-learning for contextual bandits with unknown context distributions [28.087360479901978]
  We consider the problem of designing contextual bandit algorithms in the cross-learning'' setting of Balseiro et al. We provide an efficient algorithm with a nearly tight (up to logarithmic factors) regret bound of $widetildeO(sqrtTK)$, independent of the number of contexts. At the core of our algorithm is a novel technique for coordinating the execution of an algorithm over multiple epochs.
  arXiv  Detail & Related papers  (2024-01-03T18:02:13Z)
• 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)
• Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms [39.70492757288025]
  We address the contextual linear bandit problem, where a decision maker is provided a context. We show that the contextual problem can be solved as a linear bandit problem. Our results imply a $O(dsqrtTlog T)$ high-probability regret bound for contextual linear bandits.
  arXiv  Detail & Related papers  (2022-11-08T22:18:53Z)
• Reproducible Bandits [95.8830340560603]
  A policy in the bandit environment is called reproducible if it pulls, with high probability, the exact same sequence of arms in two different executions. We show that not only do reproducible policies exist, but also they achieve almost the same optimal (non-reproducible) regret bounds in terms of the time horizon. Our results show that even though randomization is crucial for the exploration-exploitation trade-off, an optimal balance can still be achieved while pulling the exact same arms in two different rounds of executions.
  arXiv  Detail & Related papers  (2022-10-04T20:36:45Z)
• 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)
• Learning in Distributed Contextual Linear Bandits Without Sharing the Context [39.70492757288025]
  Contextual linear bandits is a rich and theoretically important model that has many practical applications. In this paper, we consider a distributed memoryless contextual linear bandit learning problem.
  arXiv  Detail & Related papers  (2022-06-08T22:07:01Z)
• Stochastic Conservative Contextual Linear Bandits [8.684768561839146]
  We study the problem of safe real-time decision making under uncertainty. We formulate a conservative contextual bandit formulation for real-time decision making.
  arXiv  Detail & Related papers  (2022-03-29T14:50:50Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  This paper unifies the analysis of risk-averse Thompson sampling algorithms for the multi-armed bandit problem. Using the contraction principle in the theory of large deviations, we prove novel concentration bounds for continuous risk functionals. We show that a wide class of risk functionals as well as "nice" functions of them satisfy the continuity condition.
  arXiv  Detail & Related papers  (2021-08-25T17:09:01Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• Relative Deviation Margin Bounds [55.22251993239944]
  We give two types of learning bounds, both distribution-dependent and valid for general families, in terms of the Rademacher complexity. We derive distribution-dependent generalization bounds for unbounded loss functions under the assumption of a finite moment.
  arXiv  Detail & Related papers  (2020-06-26T12:37:17Z)
• $\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.