Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration

• URL: http://arxiv.org/abs/2302.06726v2
• Date: Sun, 21 Jan 2024 13:53:33 GMT
• Title: Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration
• Authors: Parikshit Gopalan and Michael P. Kim and Omer Reingold
• Abstract summary: We introduce and study Swap Agnostic Learning. Despite the strength of the adversary, we demonstrate the feasibility Swap Agnostic Learning for any convex loss.
• Score: 6.91367883100748
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce and study Swap Agnostic Learning. The problem can be phrased as a game between a predictor and an adversary: first, the predictor selects a hypothesis $h$; then, the adversary plays in response, and for each level set of the predictor $\{x \in \mathcal{X} : h(x) = v\}$ selects a (different) loss-minimizing hypothesis $c_v \in \mathcal{C}$; the predictor wins if $h$ competes with the adaptive adversary's loss. Despite the strength of the adversary, we demonstrate the feasibility Swap Agnostic Learning for any convex loss. Somewhat surprisingly, the result follows through an investigation into the connections between Omniprediction and Multicalibration. Omniprediction is a new notion of optimality for predictors that strengthtens classical notions such as agnostic learning. It asks for loss minimization guarantees (relative to a hypothesis class) that apply not just for a specific loss function, but for any loss belonging to a rich family of losses. A recent line of work shows that omniprediction is implied by multicalibration and related multi-group fairness notions. This unexpected connection raises the question: is multi-group fairness necessary for omniprediction? Our work gives the first affirmative answer to this question. We establish an equivalence between swap variants of omniprediction and multicalibration and swap agnostic learning. Further, swap multicalibration is essentially equivalent to the standard notion of multicalibration, so existing learning algorithms can be used to achieve any of the three notions. Building on this characterization, we paint a complete picture of the relationship between different variants of multi-group fairness, omniprediction, and Outcome Indistinguishability. This inquiry reveals a unified notion of OI that captures all existing notions of omniprediction and multicalibration.

Related papers

• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  We introduce the notion of a margin complement, which measures how much a prediction score $S$ changes due to a thresholding operation. We show that under suitable causal assumptions, the influences of $X$ on the prediction score $S$ are equal to the influences of $X$ on the true outcome $Y$.
  arXiv  Detail & Related papers  (2024-05-24T11:22:19Z)
• Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs [32.29254118429081]
  We show that the optimal mistake bound under bandit feedback is at most $O(k)$ times higher than the optimal mistake bound in the full information case. We also present nearly optimal bounds of $tildeTheta(k)$ on the gap between randomized and deterministic learners.
  arXiv  Detail & Related papers  (2024-02-12T07:20:05Z)
• Agnostically Learning Single-Index Models using Omnipredictors [15.36798336447733]
  We give the first result for agnostically learning Single-Index Models (SIMs) with arbitrary monotone and Lipschitz activations. We also provide new guarantees for standard algorithms like GLMtron and logistic regression in the agnostic setting.
  arXiv  Detail & Related papers  (2023-06-18T18:40:07Z)
• Loss Minimization through the Lens of Outcome Indistinguishability [11.709566373491619]
  We present a new perspective on convex loss and the recent notion of Omniprediction. By design, Loss OI implies omniprediction in a direct and intuitive manner. We show that Loss OI for the important set of losses arising from Generalized Models, without requiring full multicalibration.
  arXiv  Detail & Related papers  (2022-10-16T22:25:27Z)
• Omnipredictors for Constrained Optimization [5.969079530101132]
  We show how to obtain omnipredictors for constrained optimization problems, relying on appropriate variants of multicalibration. We also investigate the implications of this notion when the constraints used are so-called group fairness notions.
  arXiv  Detail & Related papers  (2022-09-15T17:04:49Z)
• Fair Wrapping for Black-box Predictions [105.10203274098862]
  We learn a wrapper function which we define as an alpha-tree, which modifies the prediction. We show that our modification has appealing properties in terms of composition ofalpha-trees, generalization, interpretability, and KL divergence between modified and original predictions.
  arXiv  Detail & Related papers  (2022-01-31T01:02:39Z)
• Omnipredictors [19.735769148626588]
  Loss minimization is a dominant paradigm in machine learning. We introduce the notion of an ($mathcalL,mathcalC$)-omnipredictor, which could be used to optimize any loss in a family. We show that such "loss-oblivious'' learning is feasible through a connection to multicalibration.
  arXiv  Detail & Related papers  (2021-09-11T23:28:49Z)
• A Variational Inequality Approach to Bayesian Regression Games [90.79402153164587]
  We prove the existence of the uniqueness of a class of convex and generalize it to smooth cost functions. We provide two simple algorithms of solving them with necessarily strong convergence.
  arXiv  Detail & Related papers  (2021-03-24T22:33:11Z)
• Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations [78.23408201652984]
  Top-k predictions are used in many real-world applications such as machine learning as a service, recommender systems, and web searches. Our work is based on randomized smoothing, which builds a provably robust classifier via randomizing an input. For instance, our method can build a classifier that achieves a certified top-3 accuracy of 69.2% on ImageNet when an attacker can arbitrarily perturb 5 pixels of a testing image.
  arXiv  Detail & Related papers  (2020-11-15T21:34:44Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  We propose a weaker assumption that we call $2$-adjacency faithfulness. We propose a sound orientation rule for causal discovery that applies under weaker assumptions.
  arXiv  Detail & Related papers  (2020-10-27T13:04:08Z)
• Provable tradeoffs in adversarially robust classification [96.48180210364893]
  We develop and leverage new tools, including recent breakthroughs from probability theory on robust isoperimetry. Our results reveal fundamental tradeoffs between standard and robust accuracy that grow when data is imbalanced.
  arXiv  Detail & Related papers  (2020-06-09T09:58:19Z)

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.