Toward Simultaneously Optimal Regret in U-Calibration

• URL: http://arxiv.org/abs/2606.18527v1
• Date: Tue, 16 Jun 2026 22:44:37 GMT
• Title: Toward Simultaneously Optimal Regret in U-Calibration
• Abstract summary: Existing U-calibration algorithms achieve worst-case optimal $O(sqrtT)$ regret for every bounded proper loss.<n>We show, even for smooth losses such as squared loss, they incur $(sqrtT)$ regret instead of the optimal $O(log T)$ regret.<n>Specifically, we design a single forecast algorithm that simultaneously achieves $tilde O(sqrtT)$ regret for every bounded proper loss.
• Score: 41.366442572915496
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: U-calibration studies online forecasting algorithms whose predictions can be consumed by any unknown downstream agent, guaranteeing sublinear regret simultaneously for all proper loss functions. Existing U-calibration algorithms achieve worst-case optimal $O(\sqrt{T})$ regret for every bounded proper loss, but they fail to adapt to easier losses: as we show, even for smooth losses such as squared loss, they incur $Ω(\sqrt{T})$ regret instead of the optimal $O(\log T)$ regret. In this work, we show that this limitation is not inherent. Specifically, we design a single forecast algorithm that simultaneously achieves $\tilde O(\sqrt{T})$ regret for every bounded proper loss and $O(\log T)$ regret for every bounded smooth proper loss. More generally, our algorithm also attains logarithmic regret for losses that are smooth relative to the log-barrier, which include several non-Lipschitz examples. Our approach is based on a novel variant of Follow-the-Perturbed-Leader (FTPL) in which perturbations are applied directly in the prediction space using self-concordant noise. The resulting analysis also departs substantially from prior FTPL analyses due to the complex nature of this noise and may be of independent interest.

Related papers

• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  We investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner.<n>The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm.<n>We establish an information-theoretic lower bound that scales as $(sqrtmathbbE[S_T])$, providing a fundamental characterization of the best achievable prediction-adaptive regret.
  arXiv  Detail & Related papers  (2026-05-21T08:57:38Z)
• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging aggregate bandit feedback model.<n>Our results rely on a combination of FTRL over occupancy measures, self-bounding techniques, and new loss estimators inspired by recent advances in online shortest path problems.
  arXiv  Detail & Related papers  (2025-10-20T02:28:08Z)
• When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses [10.329071967218054]
  We develop adaptive algorithms that do not require prior knowledge about the range or the second moment of the losses.<n>Existing adaptive algorithms have what is typically considered a lower-order term in their regret guarantees.
  arXiv  Detail & Related papers  (2025-06-02T14:29:05Z)
• Simultaneous Swap Regret Minimization via KL-Calibration [31.959887895880765]
  We introduce a new stronger notion of calibration called (pseudo) KL-Calibration, which we show is equivalent to the (pseudo) swap regret for log loss.<n>A technical contribution of our work is a new randomized rounding procedure and a non-uniform discretization scheme to minimize the swap regret for log loss.
  arXiv  Detail & Related papers  (2025-02-23T00:23:18Z)
• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  We study Online Convex Optimization (OCO) with adversarial constraints.<n>We focus on a setting where the algorithm has access to predictions of the loss and constraint functions.<n>Our results show that we can improve the current best bounds of $ O(sqrtT) $ regret and $ tildeO(sqrtT) $ cumulative constraint violations.
  arXiv  Detail & Related papers  (2024-12-11T03:06:42Z)
• Optimal Multiclass U-Calibration Error and Beyond [31.959887895880765]
  We consider the problem of online multiclass bounds U-calibration, where a forecaster aims to make sequential distributional predictions over $K$ classes with low U-calibration error. We show that the optimal U-calibration error is $Theta(sqrtKT)$.
  arXiv  Detail & Related papers  (2024-05-28T20:33:18Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  We propose an algorithm called Mild-OGD for the full-information case, where delayed gradients are available.<n>We show that the dynamic regret of Mild-OGD can be automatically bounded by $O(sqrtbardT(P_T+1))$ under the in-order assumption.<n>We also develop a bandit variant of Mild-OGD for a more challenging case with only delayed loss values.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)

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.