Related papers: Proper losses regret at least 1/2-order

Proper losses regret at least 1/2-order

URL: http://arxiv.org/abs/2407.10417v1
Date: Mon, 15 Jul 2024 03:46:15 GMT
Title: Proper losses regret at least 1/2-order
Authors: Han Bao, Asuka Takatsu,
Abstract summary: We show that the strict properness of a loss is necessary and sufficient to establish a non-vacuous surrogate regret bound. We also show that the order of convergence in p-norm cannot be faster than the $1/2$-order of surrogate regrets for a broad class of strictly proper losses.
Score: 1.7986307635828565
License: http://creativecommons.org/licenses/by-sa/4.0/
Abstract: A fundamental challenge in machine learning is the choice of a loss as it characterizes our learning task, is minimized in the training phase, and serves as an evaluation criterion for estimators. Proper losses are commonly chosen, ensuring minimizers of the full risk match the true probability vector. Estimators induced from a proper loss are widely used to construct forecasters for downstream tasks such as classification and ranking. In this procedure, how does the forecaster based on the obtained estimator perform well under a given downstream task? This question is substantially relevant to the behavior of the $p$-norm between the estimated and true probability vectors when the estimator is updated. In the proper loss framework, the suboptimality of the estimated probability vector from the true probability vector is measured by a surrogate regret. First, we analyze a surrogate regret and show that the strict properness of a loss is necessary and sufficient to establish a non-vacuous surrogate regret bound. Second, we solve an important open question that the order of convergence in p-norm cannot be faster than the $1/2$-order of surrogate regrets for a broad class of strictly proper losses. This implies that strongly proper losses entail the optimal convergence rate.

Related papers

Rejection via Learning Density Ratios [50.91522897152437]
Classification with rejection emerges as a learning paradigm which allows models to abstain from making predictions. We propose a different distributional perspective, where we seek to find an idealized data distribution which maximizes a pretrained model's performance. Our framework is tested empirically over clean and noisy datasets.
arXiv Detail & Related papers (2024-05-29T01:32:17Z)
U-Calibration: Forecasting for an Unknown Agent [29.3181385170725]
We show that optimizing forecasts for a single scoring rule cannot guarantee low regret for all possible agents. We present a new metric for evaluating forecasts that we call U-calibration, equal to the maximal regret of the sequence of forecasts.
arXiv Detail & Related papers (2023-06-30T23:05:26Z)
On Second-Order Scoring Rules for Epistemic Uncertainty Quantification [8.298716599039501]
We show that there seems to be no loss function that provides an incentive for a second-order learner to faithfully represent its uncertainty. As a main mathematical tool to prove this result, we introduce the generalised notion of second-order scoring rules.
arXiv Detail & Related papers (2023-01-30T08:59:45Z)
Sample-Efficient Optimisation with Probabilistic Transformer Surrogates [66.98962321504085]
This paper investigates the feasibility of employing state-of-the-art probabilistic transformers in Bayesian optimisation. We observe two drawbacks stemming from their training procedure and loss definition, hindering their direct deployment as proxies in black-box optimisation. We introduce two components: 1) a BO-tailored training prior supporting non-uniformly distributed points, and 2) a novel approximate posterior regulariser trading-off accuracy and input sensitivity to filter favourable stationary points for improved predictive performance.
arXiv Detail & Related papers (2022-05-27T11:13:17Z)
On the Difficulty of Epistemic Uncertainty Quantification in Machine Learning: The Case of Direct Uncertainty Estimation through Loss Minimisation [8.298716599039501]
Uncertainty quantification has received increasing attention in machine learning. The latter refers to the learner's (lack of) knowledge and appears to be especially difficult to measure and quantify. We show that loss minimisation does not work for second-order predictors.
arXiv Detail & Related papers (2022-03-11T17:26:05Z)
Unifying Lower Bounds on Prediction Dimension of Consistent Convex Surrogates [12.751555473216683]
Given a prediction task, understanding when one can and cannot design a consistent convex surrogate loss is an important area of machine learning research. We unify these settings using tools from property elicitation, and give a general lower bound on prediction dimension. Our lower bound tightens existing results in the case of discrete predictions, showing that previous calibration-based bounds can largely be recovered via property elicitation. For continuous estimation, our lower bound resolves on open problem on estimating measures of risk and uncertainty.
arXiv Detail & Related papers (2021-02-16T15:29:05Z)
A Symmetric Loss Perspective of Reliable Machine Learning [87.68601212686086]
We review how a symmetric loss can yield robust classification from corrupted labels in balanced error rate (BER) minimization. We demonstrate how the robust AUC method can benefit natural language processing in the problem where we want to learn only from relevant keywords.
arXiv Detail & Related papers (2021-01-05T06:25:47Z)
Calibrated Surrogate Losses for Adversarially Robust Classification [92.37268323142307]
We show that no convex surrogate loss is respect with respect to adversarial 0-1 loss when restricted to linear models. We also show that if the underlying distribution satisfies the Massart's noise condition, convex losses can also be calibrated in the adversarial setting.
arXiv Detail & Related papers (2020-05-28T02:40:42Z)
Optimal Change-Point Detection with Training Sequences in the Large and Moderate Deviations Regimes [72.68201611113673]
This paper investigates a novel offline change-point detection problem from an information-theoretic perspective. We assume that the knowledge of the underlying pre- and post-change distributions are not known and can only be learned from the training sequences which are available.
arXiv Detail & Related papers (2020-03-13T23:39:40Z)
Understanding and Mitigating the Tradeoff Between Robustness and Accuracy [88.51943635427709]
Adversarial training augments the training set with perturbations to improve the robust error. We show that the standard error could increase even when the augmented perturbations have noiseless observations from the optimal linear predictor.
arXiv Detail & Related papers (2020-02-25T08:03:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.