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
- When is Multicalibration Post-Processing Necessary? [12.628103786954487]
We conduct the first comprehensive study evaluating the usefulness of multicalibration post-processing.
Our findings can be summarized as follows: (1) models which are calibrated out of the box tend to be relatively multicalibrated without any additional post-processing; (2) multicalibration post-processing can help inherently uncalibrated models; and (3) traditional calibration measures may sometimes provide multicalibration implicitly.
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) - Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers.
We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model.
Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
arXiv Detail & Related papers (2020-06-22T21:12:31Z) - 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.