TV Distance Computation

TV: Total Variation

Follow this topic Ask about this topic

Latest papers

8 papers3 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Hypothesis Selection via Weighted Medians
Oct 14, 2026Liang-Yu ZouTV Distance Computation Statistical Learning Theory
Aarhus University
Optimal Transport PAC-Bayes Bounds
Oct 12, 2026Armin Beck, Peter Ochs, Jalal FadiliTV Distance Computation PAC-Bayesian Generalization Bounds
Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany · Saarland University, Saarland Informatics Campus, Saarbrücken, Germany · ENSICAEN, CNRS GREYC, Caen, France
How Divergence Becomes Decision Flips in Compressed Language Models
Sep 30, 2026Beatriz Almeida FelicioLLM Evaluation LLM Compression
Instituto de Informática (INF) Universidade Federal de Goiás (UFG)
Divergence Timing and Cumulative Disagreement under KV-Cache Eviction
Sep 15, 2026Xinyue Luo, Fei YuKV Caching KV-Cache Eviction
Wealth AI Lab, Ant Group
Total Variation Distance Estimation in Autoregressive Models
Jul 21, 2026Eric Price, Kevin Tian, Zhiyang Xun +1LLM Evaluation LLM Inference
University of Texas at Austin
On Computing Total Variation Distance Between Mixtures of Product Distributions
May 5, 2026Weiming Feng, Yucheng Fu, Minji Yang +1Distribution Matching Approximation Algorithms
School of Computing and Data Science, The University of Hong Kong. · The Institute for Interdisciplinary Information Sciences, Tsinghua University.
Revisiting GAN with Bayes-Optimal Discrimination
Oct 29, 2025Mohammadreza Tavasoli Naeini, Ali Bereyhi, Morteza Noshad +2TV Distance Computation Generative Adversarial Networks
University of Toronto · Stanford University · University of Michigan
Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing
Mar 10, 2025Debabrota Basu, Debarshi ChandaTV Distance Computation Wasserstein Distance
Équipe Scool, Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189- CRIStAL F-59000 Lille, France · Indian Statistical Institute Kolkata, India

Oct 14, 2026J/K move · Enter open · S save

Hypothesis Selection via Weighted Medians

Liang-Yu Zou

Aarhus University

TV Distance Computation Statistical Learning Theory Distribution Matching

Open paper AskPDF arXiv

Given

n

distributions (hypotheses)

\mathcal H=\{H_1,\ldots,H_n\}

and samples from an unknown target distribution

P

, proper hypothesis selection seeks a distribution whose total variation distance to

P

is close to the best achievable within the known distributions. We give an algorithm that, using

O(\varepsilon^{-2}\log(n/δ))

target samples, running in

O(n\varepsilon^{-2}\log(n/δ))

time, with probability at least

1-δ

, returns

H_{\hat i}

satisfying

d_\mathrm{TV}(P,H_{\hat i})\leq 3\min_{i\in[n]}d_\mathrm{TV}(P,H_i)+\varepsilon.

The algorithm achieves the optimal approximation factor and sample complexity. The running time improves the dependence on the failure probability from polynomial to logarithmic in the state-of-the-art bound

\tilde{O}(n\varepsilon^{-2}δ^{-1})

of Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026), thereby answering their Question~2.