Simultaneous Swap Regret Minimization via KL-Calibration

• URL: http://arxiv.org/abs/2502.16387v1
• Date: Sun, 23 Feb 2025 00:23:18 GMT
• Title: Simultaneous Swap Regret Minimization via KL-Calibration
• Authors: Haipeng Luo, Spandan Senapati, Vatsal Sharan,
• Abstract summary: 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.
• Score: 31.959887895880765
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Calibration is a fundamental concept that aims at ensuring the reliability of probabilistic predictions by aligning them with real-world outcomes. There is a surge of studies on new calibration measures that are easier to optimize compared to the classical $\ell_1$-Calibration while still having strong implications for downstream applications. One recent such example is the work by Fishelson et al. (2025) who show that it is possible to achieve $O(T^{1/3})$ pseudo $\ell_2$-Calibration error via minimizing pseudo swap regret of the squared loss, which in fact implies the same bound for all bounded proper losses with a smooth univariate form. In this work, we significantly generalize their result in the following ways: (a) in addition to smooth univariate forms, our algorithm also simultaneously achieves $O(T^{1/3})$ swap regret for any proper loss with a twice continuously differentiable univariate form (such as Tsallis entropy); (b) our bounds hold not only for pseudo swap regret that measures losses using the forecaster's distributions on predictions, but also hold for the actual swap regret that measures losses using the forecaster's actual realized predictions. We achieve so by introducing a new stronger notion of calibration called (pseudo) KL-Calibration, which we show is equivalent to the (pseudo) swap regret for log loss. We prove that there exists an algorithm that achieves $O(T^{1/3})$ KL-Calibration error and provide an explicit algorithm that achieves $O(T^{1/3})$ pseudo KL-Calibration error. Moreover, we show that the same algorithm achieves $O(T^{1/3}(\log T)^{-1/3}\log(T/\delta))$ swap regret w.p. $\ge 1-\delta$ for any proper loss with a smooth univariate form, which implies $O(T^{1/3})$ $\ell_2$-Calibration error. 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.

Related papers

• Full Swap Regret and Discretized Calibration [18.944031222413294]
  We study the problem of minimizing swap regret in structured normal-form games.<n>We introduce a new online learning problem we call emphfull swap regret minimization<n>We also apply these tools to the problem of online forecasting to calibration error.
  arXiv  Detail & Related papers  (2025-02-13T13:49:52Z)
• Any-stepsize Gradient Descent for Separable Data under Fenchel--Young Losses [17.835960292396255]
  We show arbitrary-stepsize gradient convergence for a general loss function based on the framework of emphFenchel--Young losses.<n>We argue that these better rate is possible because of emphseparation margin of loss functions, instead of the self-bounding property.
  arXiv  Detail & Related papers  (2025-02-07T12:52:12Z)
• Revisiting Projection-Free Online Learning with Time-Varying Constraints [35.573654458435854]
  We investigate constrained online convex optimization, in which decisions must belong to a fixed and typically complicated domain.<n>Several projection-free methods have been proposed with an $mathcalO(T3/4 sqrtlog T)$ regret bound and an $mathcalO(T3/4 sqrtlog T)$ cumulative constraint violation (CCV) bound for general convex losses.<n>In this paper, we improve this result and further establish textitnovel regret and CCV bounds when loss functions are strongly convex
  arXiv  Detail & Related papers  (2025-01-27T13:38:51Z)
• Rate-Preserving Reductions for Blackwell Approachability [72.03309261614991]
  Abernethy et al. (2011) showed that Blackwell approachability and no-regret learning are equivalent. We show that it is possible to tightly reduce any approachability instance to an instance of a generalized form of regret minimization.
  arXiv  Detail & Related papers  (2024-06-10T23:23:52Z)
• Orthogonal Causal Calibration [55.28164682911196]
  We prove generic upper bounds on the calibration error of any causal parameter estimate $theta$ with respect to any loss $ell$. We use our bound to analyze the convergence of two sample splitting algorithms for causal calibration.
  arXiv  Detail & Related papers  (2024-06-04T03:35:25Z)
• 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)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
  This paper revisits the weighted strategy for non-stationary parametric bandits. We propose a refined analysis framework, which produces a simpler weight-based algorithm. Our new framework can be used to improve regret bounds of other parametric bandits.
  arXiv  Detail & Related papers  (2023-03-05T15:11:14Z)
• Scale-free Unconstrained Online Learning for Curved Losses [1.5147172044848798]
  We investigate the possibility of adapting simultaneously to the norm $U$ of the comparator and the maximum norm $G$ of the gradients. Surprisingly, recent results show that no such price for adaptivity is needed in the specific case of $1$-Lipschitz losses.
  arXiv  Detail & Related papers  (2022-02-11T14:10:35Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning. The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
  arXiv  Detail & Related papers  (2021-10-09T21:13:48Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)

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.