An Exploration of Multicalibration Uniform Convergence Bounds
- URL: http://arxiv.org/abs/2202.04530v1
- Date: Wed, 9 Feb 2022 15:48:10 GMT
- Title: An Exploration of Multicalibration Uniform Convergence Bounds
- Authors: Harrison Rosenberg, Robi Bhattacharjee, Kassem Fawaz, and Somesh Jha
- Abstract summary: 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.
- Score: 25.500680663483624
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Recent works have investigated the sample complexity necessary for fair
machine learning. The most advanced of such sample complexity bounds are
developed by analyzing multicalibration uniform convergence for a given
predictor class. We present a framework which yields multicalibration error
uniform convergence bounds by reparametrizing sample complexities for Empirical
Risk Minimization (ERM) learning. From this framework, we demonstrate that
multicalibration error exhibits dependence on the classifier architecture as
well as the underlying data distribution. We perform an experimental evaluation
to investigate the behavior of multicalibration error for different families of
classifiers. We compare the results of this evaluation to multicalibration
error concentration bounds. Our investigation provides additional perspective
on both algorithmic fairness and multicalibration error convergence bounds.
Given the prevalence of ERM sample complexity bounds, our proposed framework
enables machine learning practitioners to easily understand the convergence
behavior of multicalibration error for a myriad of classifier architectures.
Related papers
- Bridging Multicalibration and Out-of-distribution Generalization Beyond Covariate Shift [44.708914058803224]
We establish a new model-agnostic optimization framework for out-of-distribution generalization via multicalibration.
We propose MC-Pseudolabel, a post-processing algorithm to achieve both extended multicalibration and out-of-distribution generalization.
arXiv Detail & Related papers (2024-06-02T08:11:35Z) - Trade-off Between Dependence and Complexity for Nonparametric Learning
-- an Empirical Process Approach [10.27974860479791]
In many applications where the data exhibit temporal dependencies, the corresponding empirical processes are much less understood.
We present a general bound on the expected supremum of empirical processes under standard $beta/rho$-mixing assumptions.
We show that even under long-range dependence, it is possible to attain the same rates as in the i.i.d. setting.
arXiv Detail & Related papers (2024-01-17T05:08:37Z) - Optimal Multi-Distribution Learning [88.3008613028333]
Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.
We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
arXiv Detail & Related papers (2023-12-08T16:06:29Z) - A Unifying Perspective on Multi-Calibration: Game Dynamics for
Multi-Objective Learning [63.20009081099896]
We provide a unifying framework for the design and analysis of multicalibrated predictors.
We exploit connections to game dynamics to achieve state-of-the-art guarantees for a diverse set of multicalibration learning problems.
arXiv Detail & Related papers (2023-02-21T18:24:17Z) - Adaptively-weighted Integral Space for Fast Multiview Clustering [54.177846260063966]
We propose an Adaptively-weighted Integral Space for Fast Multiview Clustering (AIMC) with nearly linear complexity.
Specifically, view generation models are designed to reconstruct the view observations from the latent integral space.
Experiments conducted on several realworld datasets confirm the superiority of the proposed AIMC method.
arXiv Detail & Related papers (2022-08-25T05:47:39Z) - Pairwise Learning via Stagewise Training in Proximal Setting [0.0]
We combine adaptive sample size and importance sampling techniques for pairwise learning, with convergence guarantees for nonsmooth convex pairwise loss functions.
We demonstrate that sampling opposite instances at each reduces the variance of the gradient, hence accelerating convergence.
arXiv Detail & Related papers (2022-08-08T11:51:01Z) - 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) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data.
Our algorithms are validated extensively on synthetic and real-world datasets.
arXiv Detail & Related papers (2021-10-12T02:21:30Z) - 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) - Sample Complexity of Uniform Convergence for Multicalibration [43.10452387619829]
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.
arXiv Detail & Related papers (2020-05-04T18:01:38Z)
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.