Breaking the Finite-Sample Barrier in Entropy Coupling

• URL: http://arxiv.org/abs/2605.16229v1
• Date: Fri, 15 May 2026 17:39:57 GMT
• Title: Breaking the Finite-Sample Barrier in Entropy Coupling
• Abstract summary: Dependence among marginally constrained observations can break a finite-sample barrier.<n>We formalize this phenomenon by introducing the emphminimum list entropy coupling $H(P|Q_1,dots,Q_m)$.<n>We show that the same framework formalizes finite-sample limits in distribution-matching representation learning and randomness extraction.
• Score: 9.251944578856843
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dependence among marginally constrained observations can break a finite-sample barrier. To formalize this phenomenon, we introduce the \emph{minimum list entropy coupling} $H(P\|Q_1,\dots,Q_m)$, the minimum conditional entropy $H(X|Y_1,\dots,Y_m)$ over all joint distributions with prescribed discrete marginals $X\sim P$ and $Y_i\sim Q_i$. Unlike classical formulations based on independent observations, our model allows $Y_1,\dots,Y_m$ to be arbitrarily dependent while keeping each marginal fixed. This enlarged coupling space reveals a sharp dichotomy: independent observations reduce residual uncertainty exponentially, whereas dependent observations can eliminate it exactly after finitely many samples. We characterize this zero-entropy regime through necessary and sufficient conditions and give concrete structural criteria under which it occurs. In particular, under mild support assumptions, zero entropy is achieved with $O(\log(1/P_{\min}))$ observations, where $P_{\min}$ is the minimum nonzero mass of $P$. We also develop a greedy algorithm with monotone approximation guarantees for computing $H(P\|Q_1,\dots,Q_m)$. Finally, we show that the same framework formalizes finite-sample limits in distribution-matching representation learning and randomness extraction, where zero entropy corresponds to exact recovery and exact extraction.

Related papers

• Uniform Statistical Convergence of Empirical Sinkhorn Potentials with Exponential and Polynomial Dependence on the Regularization Parameter [3.6552781109515853]
  We study the empirical Sinkhorn estimator of the entropic optimal transport potentials under the uniform loss.<n>For a fixed regularization parameter $varepsilon>0$, we establish a non-asymptotic statistical rate of $n-1/2$.<n>Key requirement is a residual-stability estimate for the population Sinkhorn map.
  arXiv  Detail & Related papers  (2026-08-29T08:59:00Z)
• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• When Does the Best Sampling Temperature Rise with the Budget? Sufficient Conditions for Pass@k [0.0]
  The temperature that maximizes pass@$k$ is often low for a small sampling budget and higher for a large budget.<n>We show that the mechanism is a monotone-likelihood-ratio power tilt toward lower-success tasks.<n>The contribution is a conditional theory of an established empirical phenomenon, with assumptions that can be tested in future work.
  arXiv  Detail & Related papers  (2026-08-01T08:43:36Z)
• Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue [17.761018390014602]
  Learning the natural parameters $z in mathbbRn$ from independent samples constrained to a subset $S subseteq 0,1n$ is a foundational challenge in high-dimensional statistics.<n>We refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to $O( log n / 2)$ for $ell_infty$-recovery, matching the untruncated minimax rate.
  arXiv  Detail & Related papers  (2026-07-24T20:01:15Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations [49.702772230127465]
  We study finite-state Markov chains with $n$ states and transition matrix $P$.<n>We show that all non-decaying modes are captured by a real peripheral invariant subspace $mathcalK(P)$, and that the induced operator on the quotient space $mathbbRn/mathcalK(P) is strictly contractive, yielding a unique quotient solution.
  arXiv  Detail & Related papers  (2026-01-31T02:57:01Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Precise Asymptotics of Bagging Regularized M-estimators [20.077783679095443]
  We characterize the squared prediction risk of ensemble estimators obtained through subagging (subsample bootstrap aggregating) regularized M-estimators.<n>Key to our analysis is a new result on the joint behavior of correlations between the estimator and residual errors on overlapping subsamples.<n>Joint optimization of subsample size, ensemble size, and regularization can significantly outperform regularizer optimization alone on the full data.
  arXiv  Detail & Related papers  (2024-09-23T17:48:28Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Smooth min-entropy lower bounds for approximation chains [0.0]
  We prove a simple entropic triangle inequality, which allows us to bound the smooth min-entropy of a state in terms of the R'enyi entropy of an arbitrary auxiliary state. Using this triangle inequality, we create lower bounds for the smooth min-entropy of a state in terms of the entropies of its approximation chain in various scenarios.
  arXiv  Detail & Related papers  (2023-08-22T18:55:16Z)
• On counterfactual inference with unobserved confounding [36.18241676876348]
  Given an observational study with $n$ independent but heterogeneous units, our goal is to learn the counterfactual distribution for each unit. We introduce a convex objective that pools all $n$ samples to jointly learn all $n$ parameter vectors. We derive sufficient conditions for compactly supported distributions to satisfy the logarithmic Sobolev inequality.
  arXiv  Detail & Related papers  (2022-11-14T04:14:37Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)

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.