Adaptive Bayes exactly tracks information over intrinsic time

• URL: http://arxiv.org/abs/2607.08789v1
• Date: Fri, 26 Jun 2026 23:59:28 GMT
• Title: Adaptive Bayes exactly tracks information over intrinsic time
• Abstract summary: We show that the regret of any such update obeys an exact information-accounting identity.<n>The same calculus covers Hedge, optimistic and side-information variants, continuous priors, boosting, online convex optimization, contextual bandits, and repeated games.
• Score: 0.42671348654734564
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• The concentration game: Bayesian updating, regret, and information [0.42671348654734564]
  We give a two-player zero-sum repeated game between a learner and nature.<n>The terminal payoff is the most a comparator can gain at fixed relative entropy from the prior.<n>With the learner's move otherwise unrestricted, Gibbs/Bayes weights emerge as its unique Bellman equalizer.
  arXiv  Detail & Related papers  (2026-08-18T17:52:26Z)
• Stabilizing Extrapolation in Looped Transformers via Learned Stochastic Stopping [56.14767235650558]
  Looped Transformers, which repeatedly apply a shared transformer block, are an architecturally natural fit for variable-length computation tasks.<n>We trace this variance to the spurious correlation in simple algorithmic tasks between sequence length and number of loops.<n>Our work suggests that "when to stop" should be treated as a training design choice, not merely an inference-time-allocation rule.
  arXiv  Detail & Related papers  (2026-06-29T08:58:09Z)
• Capacity-Constrained Online Convex Optimization with Delayed Feedback [58.59385794080679]
  We study delayed online convex optimization (OCO) under a hard capacity constraint.<n>We find that for first-order feedback, capacity $C = (log T)$ suffices to recover standard delayed OCO rates up to logarithmic factors.<n>For bandit feedback, the regret rates are modulated by powers of $(1 + _textmax/C)$, where $_textmax$ is the maximum number of pending observations at any time.
  arXiv  Detail & Related papers  (2026-06-10T06:37:06Z)
• Convergence, design and training of continuous-time dropout as a random batch method [0.0]
  We study dropout regularization in continuous-time models through the lens of random-batch methods.<n>We construct an unbiased, well-posed estimator that mimics dropout by sampling neuron batches over time intervals of length $h$.<n>We then specialize in a single-layer neural ODE and validate the theory on classification and flow matching.
  arXiv  Detail & Related papers  (2025-10-15T04:19:01Z)
• Non-stochastic Bandits With Evolving Observations [47.61533665679308]
  We introduce a novel online learning framework that unifies and generalizes pre-established models. We propose regret minimization algorithms for both the full-information and bandit settings. Our algorithms match the known regret bounds across many special cases, while also introducing previously unknown bounds.
  arXiv  Detail & Related papers  (2024-05-27T05:32:46Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Accelerated Rates between Stochastic and Adversarial Online Convex Optimization [6.1866042321432175]
  We establish novel regret bounds for online convex optimization in a setting that interpolates between i.i.d. and fully adversarial losses.<n>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)
• 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)
• Optimal Change-Point Detection with Training Sequences in the Large and Moderate Deviations Regimes [72.68201611113673]
  This paper investigates a novel offline change-point detection problem from an information-theoretic perspective. We assume that the knowledge of the underlying pre- and post-change distributions are not known and can only be learned from the training sequences which are available.
  arXiv  Detail & Related papers  (2020-03-13T23:39:40Z)

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.