Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses

• URL: http://arxiv.org/abs/2505.09432v2
• Date: Thu, 15 May 2025 02:26:10 GMT
• Title: Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses
• Authors: Yuzhou Cao, Han Bao, Lei Feng, Bo An,
• Abstract summary: We construct a convex smooth surrogate loss with a linear regret bound composed with a tailored prediction link.<n>The construction is based on Fenchel-Young losses generated by the convolutional negentropy.<n>Our results are a novel demonstration of how convex analysis penetrates into optimization and statistical efficiency in risk minimization.
• Score: 17.368130636104354
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Surrogate regret bounds, also known as excess risk bounds, bridge the gap between the convergence rates of surrogate and target losses, with linear bounds favorable for their lossless regret transfer. While convex smooth surrogate losses are appealing in particular due to the efficient estimation and optimization, the existence of a trade-off between the smoothness and linear regret bound has been believed in the community. That being said, the better optimization and estimation properties of convex smooth surrogate losses may inevitably deteriorate after undergoing the regret transfer onto a target loss. We overcome this dilemma for arbitrary discrete target losses by constructing a convex smooth surrogate loss, which entails a linear surrogate regret bound composed with a tailored prediction link. The construction is based on Fenchel-Young losses generated by the convolutional negentropy, which are equivalent to the infimal convolution of a generalized negentropy and the target Bayes risk. Consequently, the infimal convolution enables us to derive a smooth loss while maintaining the surrogate regret bound linear. We additionally benefit from the infimal convolution to have a consistent estimator of the underlying class probability. Our results are overall a novel demonstration of how convex analysis penetrates into optimization and statistical efficiency in risk minimization.

Related papers

• Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses [4.509643050721454]
  "Decision swap regret" generalizes prediction for downstream swap regret and omniprediction.<n>We also give algorithms for obtaining it for arbitrary multi-dimensional Lipschitz loss functions in online adversarial settings.
  arXiv  Detail & Related papers  (2025-02-18T06:01:52Z)
• Refined Risk Bounds for Unbounded Losses via Transductive Priors [58.967816314671296]
  We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression.<n>Our key tools are based on the exponential weights algorithm with carefully chosen transductive priors.
  arXiv  Detail & Related papers  (2024-10-29T00:01:04Z)
• LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
  An adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown to the learner. We present a robust online rounds optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown.
  arXiv  Detail & Related papers  (2024-08-12T17:08:31Z)
• Expressive Losses for Verified Robustness via Convex Combinations [67.54357965665676]
  We study the relationship between the over-approximation coefficient and performance profiles across different expressive losses. We show that, while expressivity is essential, better approximations of the worst-case loss are not necessarily linked to superior robustness-accuracy trade-offs.
  arXiv  Detail & Related papers  (2023-05-23T12:20:29Z)
• Accelerated Rates between Stochastic and Adversarial Online Convex Optimization [2.628557920905129]
  We establish novel regret bounds for online convex optimization in a setting that interpolates between i.i.d. and fully adversarial losses. In the fully i.i.d. case, our regret bounds match the rates one would expect from results in acceleration, and we also recover the optimalally accelerated rates via online-to-batch conversion.
  arXiv  Detail & Related papers  (2023-03-06T16:41:57Z)
• An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates [17.596501992526477]
  We study the design of convex surrogate loss functions via embeddings, for problems such as classification, ranking, or structured links. An embedding gives rise to a consistent link function as well as a consistent link function. Our results are constructive, as we illustrate several examples.
  arXiv  Detail & Related papers  (2022-06-29T15:16:51Z)
• Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness [2.628557920905129]
  We establish novel regret bounds for online convex optimization in a setting that interpolates between i.i.d. and fully adversarial losses. To accomplish this goal, we introduce two key quantities associated with the loss sequence, that we call the cumulative variance and the adversarial variation. In the fully i.i.d. case, our bounds match the rates one would expect from results in acceleration, and in the fully adversarial case they gracefully deteriorate to match the minimax regret.
  arXiv  Detail & Related papers  (2022-02-15T16:39:33Z)
• 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)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• 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)

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.