From Pseudorandomness to Multi-Group Fairness and Back

• URL: http://arxiv.org/abs/2301.08837v3
• Date: Wed, 26 Apr 2023 04:48:59 GMT
• Title: From Pseudorandomness to Multi-Group Fairness and Back
• Authors: Cynthia Dwork, Daniel Lee, Huijia Lin, Pranay Tankala
• Abstract summary: We identify and explore connections between the recent literature on multi-group fairness for prediction algorithms and the pseudorandomness notions of leakage-resilience and graph regularity. We frame our investigation using new, statistical distance-based variants of multicalibration that are closely related to the concept of outcome indistinguishability.
• Score: 17.677928204060628
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We identify and explore connections between the recent literature on multi-group fairness for prediction algorithms and the pseudorandomness notions of leakage-resilience and graph regularity. We frame our investigation using new, statistical distance-based variants of multicalibration that are closely related to the concept of outcome indistinguishability. Adopting this perspective leads us naturally not only to our graph theoretic results, but also to new, more efficient algorithms for multicalibration in certain parameter regimes and a novel proof of a hardcore lemma for real-valued functions.

Related papers

• Proximal Interacting Particle Langevin Algorithms [0.0]
  We introduce Proximal Interacting Particle Langevin Algorithms (PIPLA) for inference and learning in latent variable models. We propose several variants within the novel proximal IPLA family, tailored to the problem of estimating parameters in a non-differentiable statistical model. Our theory and experiments together show that PIPLA family can be the de facto choice for parameter estimation problems in latent variable models for non-differentiable models.
  arXiv  Detail & Related papers  (2024-06-20T13:16:41Z)
• Multivariate Bayesian Last Layer for Regression: Uncertainty Quantification and Disentanglement [4.137574627759939]
  We present new Bayesian Last Layer models in the setting of multivariate regression under heteroscedastic noise. We propose an optimization algorithm for parameter learning. We show that the framework can be used to transfer a canonically trained deep neural network to new data domains with uncertainty-aware capability.
  arXiv  Detail & Related papers  (2024-05-02T21:53:32Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Causal Feature Selection via Transfer Entropy [59.999594949050596]
  Causal discovery aims to identify causal relationships between features with observational data. We introduce a new causal feature selection approach that relies on the forward and backward feature selection procedures. We provide theoretical guarantees on the regression and classification errors for both the exact and the finite-sample cases.
  arXiv  Detail & Related papers  (2023-10-17T08:04:45Z)
• Variational Voxel Pseudo Image Tracking [127.46919555100543]
  Uncertainty estimation is an important task for critical problems, such as robotics and autonomous driving. We propose a Variational Neural Network-based version of a Voxel Pseudo Image Tracking (VPIT) method for 3D Single Object Tracking.
  arXiv  Detail & Related papers  (2023-02-12T13:34:50Z)
• Causal Graph Discovery from Self and Mutually Exciting Time Series [10.410454851418548]
  We develop a non-asymptotic recovery guarantee and quantifiable uncertainty by solving a linear program. We demonstrate the effectiveness of our approach in recovering highly interpretable causal DAGs over Sepsis Associated Derangements (SADs)
  arXiv  Detail & Related papers  (2023-01-26T16:15:27Z)
• Accelerated and instance-optimal policy evaluation with linear function approximation [17.995515643150657]
  Existing algorithms fail to match at least one of these lower bounds. We develop an accelerated, variance-reduced fast temporal difference algorithm that simultaneously matches both lower bounds and attains a strong notion of instance-optimality.
  arXiv  Detail & Related papers  (2021-12-24T17:21:04Z)
• Trustworthy Multimodal Regression with Mixture of Normal-inverse Gamma Distributions [91.63716984911278]
  We introduce a novel Mixture of Normal-Inverse Gamma distributions (MoNIG) algorithm, which efficiently estimates uncertainty in principle for adaptive integration of different modalities and produces a trustworthy regression result. Experimental results on both synthetic and different real-world data demonstrate the effectiveness and trustworthiness of our method on various multimodal regression tasks.
  arXiv  Detail & Related papers  (2021-11-11T14:28:12Z)
• Causal Graph Discovery from Self and Mutually Exciting Time Series [12.802653884445132]
  We develop a non-asymptotic recovery guarantee and quantifiable uncertainty by solving a linear program. We demonstrate the effectiveness of our approach in recovering highly interpretable causal DAGs over Sepsis Associated Derangements (SADs)
  arXiv  Detail & Related papers  (2021-06-04T16:59:24Z)
• Multivariate Deep Evidential Regression [77.34726150561087]
  A new approach with uncertainty-aware neural networks shows promise over traditional deterministic methods. We discuss three issues with a proposed solution to extract aleatoric and epistemic uncertainties from regression-based neural networks.
  arXiv  Detail & Related papers  (2021-04-13T12:20:18Z)
• Domain Adaptation: Learning Bounds and Algorithms [80.85426994513541]
  We introduce a novel distance between distributions, discrepancy distance, that is tailored to adaptation problems with arbitrary loss functions. We derive novel generalization bounds for domain adaptation for a wide family of loss functions. We also present a series of novel adaptation bounds for large classes of regularization-based algorithms.
  arXiv  Detail & Related papers  (2009-02-19T18:42:16Z)

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.