Information from coincidences

• URL: http://arxiv.org/abs/2606.25042v1
• Date: Tue, 23 Jun 2026 18:01:05 GMT
• Title: Information from coincidences
• Abstract summary: We prove a single algebraic mixed coincidence identity derivation that unifies a broad swath of informationtheoretic variational results.<n>Identity yields a unified cornerstones of information theory: concentration of empirical distributions, hypothesis-testing error exponents, change-measure inequalities, and laws governing rare-pattern coincidences.
• Score: 0.42671348654734564
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove a single algebraic mixed coincidence identity that unifies a broad swath of information-theoretic variational results. For any family of priors $\{π_i\}$ and real exponents $\{ α_i \}$, the log of the mixed count $E_{x\simν}\!\left[\prod_{i=1}^W π_i^{α_i}(x)\right]$ is simultaneously a Boltzmann coincidence weight, an exponential-family normalizer, a maximum-entropy value, and a KL-barycenter optimum. The identity yields a unified derivation of classical cornerstones of information theory: concentration of empirical distributions (Sanov-type decompositions and Gibbs conditioning), hypothesis-testing error exponents (Chernoff information and its multi-way analogue), change-of-measure inequalities (Donsker-Varadhan and PAC-Bayes), and laws governing rare-pattern coincidences (Erdos-Renyi run-length, iterative guesswork, rate-distortion, and birthday thresholds). Each is recovered as a specialization of the same algebraic equality. It strictly generalizes the classical Renyi entropy and divergence variational formulas (one and two priors respectively) to a $W$-prior simplex, and holds for unnormalized and continuum-indexed priors. Among its consequences are an exact multi-prior PAC-Bayes penalty that subtracts an explicit "coincidence bonus" from the usual single-prior posterior penalty, and the asymptotic MAP error exponent for $W$-ary hypothesis testing as an edge-restricted simplex optimum. We demonstrate the calculus at scale on two large alphabets encoding richly modeled sequential languages: on language-model next-token predictives where we recover contrastive decoding, and on human genomic regulatory sequence where it separates correlated from diverse prior families along a sliding-window trace.

Related papers

• Statistical inverse learning and $\ell^1$-regularization [0.27998963147546135]
  We study the recovery of sparse functions from finite, noisy, and indirect observations in the framework of statistical inverse learning.<n>We establish almost-sure exponents and derive non-asymptotic high-probability convergence rates in both prediction and $ell1$ reconstruction norms.
  arXiv  Detail & Related papers  (2026-07-08T14:32:08Z)
• Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition [51.253617466579335]
  We study the Bayesian fixed-budget best-arm identification problem in which a learner can abstain from making a terminal recommendation.<n>We analyze the probability of undetected error--the risk of recommending a suboptimal arm without abstaining.
  arXiv  Detail & Related papers  (2026-06-28T05:07:27Z)
• All you need is log [0.42671348654734564]
  We show that the Rényi divergences of order $in[0,infty]$ are the unique family monotone under data processing and additive on independent products.<n>Many problems compare more than two distributions at once -- multi-population fairness, multi-prior PAC-Bayes bounds, multi-hypothesis testing.<n>The right multi-distribution generalization of the Rényi family has been an open question.
  arXiv  Detail & Related papers  (2026-06-25T17:54:49Z)
• Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
  Invariant learning can fail even when the structure is statistically identifiable.<n>We show a conditional computational barrier: under a black-box samplable supervised sparse recovery primitive, there exist emphamplable multi-dimensional environments.<n>Synthetic and real datasets illustrate the predicted gaps and transitions and motivate simple diversity diagnostics.
  arXiv  Detail & Related papers  (2026-06-11T05:49:43Z)
• Exponential families from a single KL identity [7.106986689736826]
  Exponential families encompass the distributions central to modern machine learning -- softmax, Gaussians, and Boltzmann distributions.<n>We isolate a simple identity for exponential families that expresses the KL difference $mathrmKL(q | p_|)$ in terms of the log-partition function $A()$ and the moment $_q$.<n>Remarkably, this identity together with the single fact that $mathrmKL geq 0$ suffices, by direct substitution and rearrangement, to derive a cluster of results that are classically obtained
  arXiv  Detail & Related papers  (2026-04-30T15:48:03Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback [50.89125374999765]
  We provide the first convergence guarantee for Optimistic Multiplicative Weights Update ($mathtOMWU$) in NLHF.<n>Our analysis identifies a novel marginal convergence behavior, where the probability of rarely played actions grows exponentially from exponentially small values.
  arXiv  Detail & Related papers  (2025-12-31T12:08:29Z)
• Correlated Mutations for Integer Programming [0.0]
  This study seeks to establish the groundwork for Evolution Strategies (IESs)<n>IESs already excel in treating IP in practice, but accomplish it via discretization and by applying sophisticated patches to their continuous operators.<n>We focus on mutation distributions for integer decision variables.<n>We explore their theoretical properties, including entropy functions, and propose a procedure to generate scalable correlated mutation distributions.
  arXiv  Detail & Related papers  (2025-06-27T08:24:15Z)
• Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements [19.524063429548278]
  Extragradient (SEG) and Gradient Descent Ascent (SGDA) are preeminent algorithms for min-max optimization and variational inequalities problems. Our work endeavors to quantify and quantify the intrinsic structures intrinsic to these algorithms. By recasting the constant step-size SEG/SGDA as time-homogeneous Markov Chains, we establish a first-of-its-kind Law of Large Numbers and a Central Limit Theorem.
  arXiv  Detail & Related papers  (2023-06-28T18:50:07Z)
• Sparse random matrices and Gaussian ensembles with varying randomness [0.0]
  We study a system of $N$ qubits with a random Hamiltonian obtained by drawing coupling constants from Gaussian distributions in various ways. We find some evidence that the behaviour changes in an abrupt manner when the number of non-zero independent terms in the Hamiltonian is exponentially large in $N$.
  arXiv  Detail & Related papers  (2023-05-12T14:19:27Z)
• Optimization Variance: Exploring Generalization Properties of DNNs [83.78477167211315]
  The test error of a deep neural network (DNN) often demonstrates double descent. We propose a novel metric, optimization variance (OV), to measure the diversity of model updates.
  arXiv  Detail & Related papers  (2021-06-03T09:34:17Z)
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
  This paper establishes a precise high-dimensional theory for boosting on separable data. Under a class of statistical models, we provide an exact analysis of the universality error of boosting. We also explicitly pin down the relation between the boosting test error and the optimal Bayes error.
  arXiv  Detail & Related papers  (2020-02-05T00:24:53Z)

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.