Sample Complexity of Uniform Convergence for Multicalibration
- URL: http://arxiv.org/abs/2005.01757v2
- Date: Mon, 7 Jun 2021 15:28:21 GMT
- Title: Sample Complexity of Uniform Convergence for Multicalibration
- Authors: Eliran Shabat, Lee Cohen and Yishay Mansour
- Abstract summary: We address the multicalibration error and decouple it from the prediction error.
Our work gives sample complexity bounds for uniform convergence guarantees of multicalibration error.
- Score: 43.10452387619829
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: There is a growing interest in societal concerns in machine learning systems,
especially in fairness. Multicalibration gives a comprehensive methodology to
address group fairness. In this work, we address the multicalibration error and
decouple it from the prediction error. The importance of decoupling the
fairness metric (multicalibration) and the accuracy (prediction error) is due
to the inherent trade-off between the two, and the societal decision regarding
the "right tradeoff" (as imposed many times by regulators). Our work gives
sample complexity bounds for uniform convergence guarantees of multicalibration
error, which implies that regardless of the accuracy, we can guarantee that the
empirical and (true) multicalibration errors are close. We emphasize that our
results: (1) are more general than previous bounds, as they apply to both
agnostic and realizable settings, and do not rely on a specific type of
algorithm (such as deferentially private), (2) improve over previous
multicalibration sample complexity bounds and (3) implies uniform convergence
guarantees for the classical calibration error.
Related papers
- Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems.
We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
arXiv Detail & Related papers (2024-10-22T10:19:27Z) - When is Multicalibration Post-Processing Necessary? [12.628103786954487]
Multicalibration is a property of predictors which guarantees meaningful uncertainty estimates.
We conduct the first comprehensive study evaluating the usefulness of multicalibration post-processing.
We distill many independent observations which may be useful for practical and effective applications of multicalibration post-processing.
arXiv Detail & Related papers (2024-06-10T17:26:39Z) - An Inexact Halpern Iteration with Application to Distributionally Robust
Optimization [9.529117276663431]
We investigate the inexact variants of the scheme in both deterministic and deterministic convergence settings.
We show that by choosing the inexactness appropriately, the inexact schemes admit an $O(k-1) convergence rate in terms of the (expected) residue norm.
arXiv Detail & Related papers (2024-02-08T20:12:47Z) - On Regularization and Inference with Label Constraints [62.60903248392479]
We compare two strategies for encoding label constraints in a machine learning pipeline, regularization with constraints and constrained inference.
For regularization, we show that it narrows the generalization gap by precluding models that are inconsistent with the constraints.
For constrained inference, we show that it reduces the population risk by correcting a model's violation, and hence turns the violation into an advantage.
arXiv Detail & Related papers (2023-07-08T03:39:22Z) - Low-Degree Multicalibration [16.99099840073075]
Low-Degree Multicalibration defines a hierarchy of increasingly-powerful multi-group fairness notions.
We show that low-degree multicalibration can be significantly more efficient than full multicalibration.
Our work presents compelling evidence that low-degree multicalibration represents a sweet spot, pairing computational and sample efficiency with strong fairness and accuracy guarantees.
arXiv Detail & Related papers (2022-03-02T17:24:55Z) - Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound [21.273964864852612]
We provide the first PAC-Bayes bound capable of providing rich information by bounding the Kullback-Leibler divergence between the empirical and true probabilities of a set of M error types.
Our bound is especially useful in cases where the severity of different mis-classifications may change over time.
arXiv Detail & Related papers (2022-02-11T11:35:21Z) - An Exploration of Multicalibration Uniform Convergence Bounds [25.500680663483624]
We present a framework which yields multicalibration error uniform convergence bounds by reparametrizing sample complexities for Empirical Risk Minimization learning.
From this framework, we demonstrate that multicalibration error exhibits dependence on the classifier architecture as well as the underlying data distribution.
arXiv Detail & Related papers (2022-02-09T15:48:10Z) - A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
Binary density ratio estimation (DRE) provides the foundation for many state-of-the-art machine learning algorithms.
We develop a general framework from the perspective of Bregman minimization divergence.
We show that our framework leads to methods that strictly generalize their counterparts in binary DRE.
arXiv Detail & Related papers (2021-12-07T01:23:20Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO.
We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size.
Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
arXiv Detail & Related papers (2021-06-30T18:32:46Z) - Distribution-free binary classification: prediction sets, confidence
intervals and calibration [106.50279469344937]
We study three notions of uncertainty quantification -- calibration, confidence intervals and prediction sets -- for binary classification in the distribution-free setting.
We derive confidence intervals for binned probabilities for both fixed-width and uniform-mass binning.
As a consequence of our 'tripod' theorems, these confidence intervals for binned probabilities lead to distribution-free calibration.
arXiv Detail & Related papers (2020-06-18T14:17:29Z)
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.