Adaptive Bayesian Online Learning via Expert Aggregation

Bayesian and multiplicative-weights updates reweight experts, models, or actions from sequential feedback. We show that the regret of any such update obeys an exact information-accounting identity. On each round, the learner's excess loss to any chosen comparator is the sum of an immediate payment for the uncertainty exposed by the round and a reduction in the information distance from the learner's current weights to the comparator. The cumulative payment defines a pathwise uncertainty clock, the \emph{intrinsic time} of the realized sequence. Summing one-step balances yields two exact adaptive decompositions of cumulative regret, one for each natural way of composing the update across rounds. Because the decompositions are exact rather than upper bounds, favorable stochastic or low-noise regimes appear as self-bounding properties of the realized intrinsic time, not as slack in worst-case analyses. The same calculus covers Hedge, optimistic and side-information variants, continuous priors, boosting, online convex optimization, contextual bandits, and repeated games: the pathwise account is the same in every case.

This article considers an online version of conformal inference, called adaptive conformal inference [ACI] and introduced by Gibbs and Candès (2021): prediction sets are issued sequentially, after observing features and before the outcomes are revealed. These sets are evaluated both in terms of validity (the fraction of rounds where the outcome was lying in the prediction set) and efficiency (the average lengths of the prediction sets). The two criteria point to different directions (validity favors larger sets). We also target a wide range of scenarios, with exchangeable data and arbitrary data (lack of any stochastic guarantees) as two extremes. A series of existing strategies for ACI typically guarantee that empirical coverage converges to the desired level for arbitrary sequences, but they generally lack simultaneous efficiency guarantees. To provide a unified study, we first formulate ACI as a repeated two-player game with finite action sets and vector-valued payoffs encoding validity and efficiency. Building on this reformulation, we introduce a strategy based on Blackwell approachability and on its opportunistic extension by Bernstein et al. (2014) that ensures validity while adapting the efficiency of the prediction intervals to the underlying degree of stochasticity of the opponent player. The resulting guarantee is "best of many worlds": it recovers the relevant efficiency guarantees in exchangeable and adversarial settings, and provides guarantees in intermediate settings that arise in typical applications such as the forecasting of time series.

Adaptive conformal inference (ACI) of Gibbs and Cand{è}s and its variants are the standard approach to online conformal prediction under distribution shift, but they suffer from three fundamental limitations. First, their guarantees control only the \emph{signed} long-run coverage error: persistent miscoverage in one direction can be masked by compensating errors later, so a method can satisfy the theoretical guarantee while being badly wrong for extended periods. Second, existing guarantees say nothing about prediction-set size, so validity can be achieved trivially at the cost of unduly wide prediction sets. Third, the efficiency guarantees that do exist compare against a \emph{fixed} predictor chosen in hindsight, a benchmark that becomes increasingly less meaningful once the data-generating distribution shifts, since the very notion of an optimal threshold then changes over time. We consider a unified online learning framework that simultaneously controls absolute, non-cancelling coverage violation and prediction-set efficiency against a dynamically evolving benchmark for three important models. In the fully adversarial setting, exploiting the fact that the standard ACI update is exactly projected online gradient descent on the pinball loss, we derive simultaneous coverage and efficiency guarantees for arbitrary monotone Lipschitz efficiency objectives, with no distributional or {\it convexity} assumptions. In the stochastic setting with full-score feedback, we propose a sliding-window quantile tracker and establish a matching minimax lower bound showing our algorithm is rate-optimal. In the covariate-dependent stochastic setting, we develop a partitioned ACI algorithm that tracks a function-valued oracle threshold, and derive simultaneous coverage and efficiency guarantees.