Information on trajectories: martingales and random times

• URL: http://arxiv.org/abs/2608.20337v1
• Date: Thu, 20 Aug 2026 17:59:57 GMT
• Title: Information on trajectories: martingales and random times
• Abstract summary: Accounting for information flow on trajectories of a nonnegative martingale yields exact variational identities for it, even at arbitrary random times.<n>The tail a bound controls is itself a relative entropy, resolved by the chain rule into per-step conditional divergences.
• Score: 0.42671348654734564
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Accounting for information flow on the path space of trajectories of a nonnegative martingale yields exact variational identities for it, even at arbitrary random times. This recovers the widely used classical concentration inequalities, from Ville to PAC-Bayes, and measures what each one discards. The tail a bound controls is itself a relative entropy, resolved by the chain rule into per-step conditional divergences. The discarded slack has an exact form in each of three geometries: a Gibbs tilt for the Azuma-Hoeffding and PAC-Bayes bounds, the crossing itself for Ville's and for pooled tests, and a dominating certificate for the $L^p$ maximal bound. That certificate's optional-stopping deficit resolves per step into Bregman divergences of the running maximum. On a path-time space, the same identity gains one factor that prices anticipation: an arbitrary random time carries an e-process ``peeking penalty.'' The partition function can be read as a coalescent--a prefix-sharing probability of independent copies--and geometric mixtures of test martingales gain a pooling benefit for multi-model safe testing.

Related papers

• Time-Uniform Self-Normalized Concentration for Discounted Least Squares: Limits and Corrections [1.599072005190786]
  Self-normalized concentration inequalities are standard tools in bandit and reinforcement-learning analyses.<n>A widely used weighted extension claims an analogous time-uniform guarantee for discounted least-squares estimators in non-stationary problems.<n>We show that the weighted inequality remains valid at each fixed deterministic time, give valid finite- and infinite-horizon corrections, and discuss consequences for downstream analyses.
  arXiv  Detail & Related papers  (2026-08-20T05:19:11Z)
• Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and a Tight Univariate Rate [47.36630149538994]
  In high-dimensional online prediction, the best predictor may depend on only a few features, so regret should scale with sparsity rather than the ambient dimension.<n>Warmuth and Amid asked at COLT 2023 whether any of three such rules admits a competitive online regret guarantee.<n>Our analysis identifies a common obstruction: cheap nuisance causes the refit to underweight the truly predictive coordinate.
  arXiv  Detail & Related papers  (2026-08-18T09:32:03Z)
• Value Functions as Supermartingale Certificates [48.922124609307566]
  We show that under an appropriate reward, the value function associated to a policy that almost surely satisfies an $$-regular property encodes a Streett supermartingale certificate for that specification.<n>Our results, validated experimentally on finite Markov decision processes, hold for finite, countably infinite, and continuous state spaces, suggesting a principled route to certificate synthesis via RL.
  arXiv  Detail & Related papers  (2026-05-29T16:39:02Z)
• Anytime PAC-Bayes for Constrained Density-Ratio Networks under Covariate Shift [0.0]
  PAC-Bayes is instantiated on the weighted risk in a fixed-time regime that yields Bernoulli-KL bounds.<n>A patch test against analytic ground truth with a real-data deployment validates the framework.<n>A single fixed-time coverage failure is recorded, with per-split coverage aligning one-to-one with the magnitude of the label shift.
  arXiv  Detail & Related papers  (2026-05-17T01:07:17Z)
• Entropic Riemannian Neural Optimal Transport [41.69130102668252]
  We propose a unified framework that combines intrinsic entropic OT and amortized out-of-sample evaluation.<n>Our method matches or improves over Euclidean, tangent-space, and log-Euclidean baselines on benchmarks over $mathbbS2$, $mathrmSO(3)$, $mathrmSPD(3)$, $mathrmSE(3)$, and $mathbbH2$.
  arXiv  Detail & Related papers  (2026-05-05T19:43:03Z)
• Score-Repellent Monte Carlo: Toward Efficient Non-Markovian Sampler with Constant Memory in General State Spaces [48.37754141688874]
  We propose a framework that summarizes history by a running average of score evaluations in $Rd$, where $d$ is the dimension of the score and state representation.<n>This history is converted into a surrogate target through an exponential score tilt, indexed with $$ that represents the strength of repellence in controlling the magnitude of the history-based repulsion.<n>Experiments on continuous targets and discrete energy-based models demonstrate improved estimator variance and mode coverage, while retaining $O(d)$ memory usage and modest per-it overhead.
  arXiv  Detail & Related papers  (2026-04-24T18:39:50Z)
• On the Probability of First Success in Differential Evolution: Hazard Identities and Tail Bounds [0.0]
  We study first-hitting times in Differential Evolution (DE) through a conditional hazard frame work.<n>For the L-SHADE algorithm with current-to-$p$best/1 mutation, we construct a checkable algorithmic witness event $mathcal L_t$ under which the conditional hazard admits an explicit lower bound.
  arXiv  Detail & Related papers  (2026-01-16T18:24:24Z)
• A unified recipe for deriving (time-uniform) PAC-Bayes bounds [31.921092049934654]
  We present a unified framework for deriving PAC-Bayesian generalization bounds. Our bounds are anytime-valid (i.e., time-uniform), meaning that they hold at all stopping times.
  arXiv  Detail & Related papers  (2023-02-07T12:11:59Z)
• Robust PAC$^m$: Training Ensemble Models Under Misspecification and Outliers [46.38465729190199]
  PAC-Bayes theory demonstrates that the free energy criterion minimized by Bayesian learning is a bound on the generalization error for Gibbs predictors. This work presents a novel robust free energy criterion that combines the generalized score function with PAC$m$ ensemble bounds.
  arXiv  Detail & Related papers  (2022-03-03T17:11:07Z)
• Nonparametric extensions of randomized response for private confidence sets [51.75485869914048]
  This work derives methods for performing nonparametric, nonasymptotic statistical inference for population means under the constraint of local differential privacy (LDP) We present confidence intervals (CI) and time-uniform confidence sequences (CS) for $mustar$ when only given access to the privatized data.
  arXiv  Detail & Related papers  (2022-02-17T16:04:49Z)
• Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound [18.92870267111897]
  We provide the first PAC-Bayes bound capable of providing rich information by bounding the Kullback-Leibler divergence.<n>Our bound is especially useful in cases where the severity of different mis-classifications may change over time.
  arXiv  Detail & Related papers  (2022-02-11T11:35: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.