Optimal Recalibration of an Online Predictor

• URL: http://arxiv.org/abs/2607.19689v1
• Date: Wed, 22 Jul 2026 02:36:03 GMT
• Title: Optimal Recalibration of an Online Predictor
• Abstract summary: We study the problem of recalibrating an online predictor [KE17, OKS24]: given an arbitrary "hint" sequence of forecasts, the learner must output new predictions that are calibrated while incurring small excess error relative to the original forecasts, under a proper loss.<n>We give an online algorithm that achieves $(varepsilon calibrated varepsilon2)$-recalibration for Lipschitz proper losses in $T approx varepsilon-3$ rounds.<n>We show that this tradeoff is optimal by proving a matching lower bound for recalibrating against the squared
• Score: 17.79426749489757
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of recalibrating an online predictor [KE17, OKS24]: given an arbitrary "hint" sequence of forecasts, the learner must output new predictions that are calibrated while incurring small excess error relative to the original forecasts, under a proper loss. We give an online algorithm that achieves $(\varepsilon, \varepsilon^2)$-recalibration for Lipschitz proper losses in $T \approx \varepsilon^{-3}$ rounds, using an imbalanced extension of the recent simultaneous Blackwell approachability reduction framework of [HTY26]. We show that this tradeoff is optimal by proving a matching lower bound for recalibrating against the squared loss. We also prove a companion $\mathcal{K}_2$-recalibration theorem that obtains the same tradeoffs up to a logarithmic factor. As our main application, we show how our recalibration algorithms can be combined with the online refinement method of [FH23] to obtain simultaneous $\varepsilon$-calibration and $\varepsilon^2$-calibeating for smooth proper losses at the same asymptotic rate, improving upon prior works that achieved these properties separately or with a worse $\varepsilon$ dependence. In particular, the $\mathcal{K}_2$ variant answers a question of [CHJL26] on simultaneously achieving near-optimal calibeating and calibration rates. We also derive extensions to settings with multiple hint sequences. Finally, we empirically evaluate our algorithms on a classification dataset undergoing distribution shift.

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)
• The Minimax Rate of Second-Order Calibration [8.791341107339637]
  We characterize the minimax rate of estimating the second-order calibration error for binary classification.<n>As a corollary, we give the first finite-sample guarantee for second-order Platt scaling.
  arXiv  Detail & Related papers  (2026-05-08T14:41:56Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Near-optimal Swap Regret Minimization for Convex Losses [21.006993033547708]
  We give a randomized online algorithm that guarantees near-optimal $widetilde O(sqrt T)$ expected swap regret against any sequence of $T$ adaptively chosen Lipschitz convex losses on the unit interval.
  arXiv  Detail & Related papers  (2026-02-09T16:26:34Z)
• A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions [75.69959433669244]
  We study the problem of online sparse linear regression (OSLR) where the algorithms are restricted to accessing only $k$ out of $d$ per instance for prediction.<n>We introduce a new extend-time algorithm, which significantly improves previous regret bounds.
  arXiv  Detail & Related papers  (2025-10-31T05:02:33Z)
• High dimensional online calibration in polynomial time [17.45683822446751]
  In online (sequential) calibration, a forecaster predicts probability distributions over a finite outcome space $[d]$ over a sequence of $T$ days.<n>Best known algorithms require $exp(d)$ days to achieve non-trivial calibration.<n>We present the firstally calibrated strategy that guarantees non-trivial algorithm calibration after a number of rounds.
  arXiv  Detail & Related papers  (2025-04-12T06:28:05Z)
• A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum Optimization [7.014966911550542]
  We consider the problem of training a deep neural network with nonsmooth regularization to retrieve a sparse sub-structure. We derive a new solver, called SR2, whose convergence and worst-case complexity are established without knowledge or approximation of the gradient's Lipschitz constant. Experiments on network instances trained on CIFAR-10 and CIFAR-100 show that SR2 consistently achieves higher sparsity and accuracy than related methods such as ProxGEN and ProxSGD.
  arXiv  Detail & Related papers  (2022-06-14T00:28:44Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• 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)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)

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.