Optimal sub-Gaussian variance proxy for 3-mass distributions

Soufiane Atouani, Olivier Marchal, Julyan ArbelarXiv 2025 · DOI · arXiv

TL;DR

This paper provides a rigorous mathematical framework for finding the "tightest" possible sub-Gaussian variance proxy for discrete distributions, specifically focusing on 3-mass and uniform discrete distributions. The authors uncover a fascinating phase transition in symmetric 3-mass distributions and provide an open-source Python tool to help researchers calculate these optimal bounds for their own models.

What Problem Does This Paper Address?

In probability theory and machine learning, we often deal with "sub-Gaussian" random variables—variables whose tails decay at least as fast as a Gaussian distribution. This property is vital for proving concentration inequalities, which tell us how likely a sample mean is to deviate from its true expectation.

The "variance proxy" ($\sigma^2$) is the parameter that governs this decay. While any large $\sigma^2$ works, researchers always want the optimal variance proxy ($\sigma^2_{opt}$): the smallest possible value that still satisfies the sub-Gaussian condition. While this is well-understood for continuous distributions (like the Beta distribution) and simple binary ones (Bernoulli), it remains surprisingly underexplored for discrete distributions with more than two points. This paper fills that gap by analyzing 3-mass distributions (three possible outcomes) and uniform discrete distributions.

Methods

The authors employ a general characterization method based on function variation analysis.

  1. The Gap Function: They define a "gap function" $g_Y(\lambda; \sigma^2)$ which represents the difference between the target Gaussian-like bound and the actual log-moment-generating function of the variable. For a variable to be $\sigma^2$-sub-Gaussian, this gap must be non-negative for all $\lambda$.
  2. Critical Point Identification: By analyzing the derivatives of this gap function, the authors identify "critical points" where the bound is tightest.
  3. Equation Solving: They reduce the search for the optimal proxy to solving a system of transcendental equations. For some cases, they derive closed-form solutions; for others, they provide robust numerical procedures.
  4. Software Implementation: They developed a Python package (sub-Gaussian-implementation) that uses a hybrid of analytical formulas and numerical root-finding (like Brent’s method) to compute these proxies.

Datasets

As a theoretical statistics paper, it does not use traditional empirical datasets. Instead, it evaluates and proves properties for specific classes of probability distributions:

  • Symmetric 3-mass distributions: Supported on $\{-a, 0, a\}$ with weights $(p, 1-2p, p)$.
  • Asymmetric 3-mass distributions: Supported on $\{-a, 0, a\}$ with weights $(p_1, p_3, p_2)$.
  • Uniform discrete distributions: $N$ equally spaced points with equal probability $1/N$.

Key Insights and Ideas

  • The 1/6 Phase Transition: For symmetric 3-mass distributions, the authors discovered a "phase transition." If the probability of the outer points $p \ge 1/6$, the distribution is strictly sub-Gaussian (meaning the optimal variance proxy is simply the variance). If $p < 1/6$, the distribution is no longer strictly sub-Gaussian, and the proxy must be larger than the variance.
  • Uniformity is "Strict": The paper proves that a discrete uniform distribution over $N$ equally spaced points is always strictly sub-Gaussian for any $N \ge 2$. This is a clean, useful result for researchers working with quantized data or simple combs.
  • Asymmetry Complexity: In asymmetric cases, the relationship between the central mass ($p_3$) and the edge masses ($p_1, p_2$) determines the regime. If the central mass is small ($p_3 \le 4\sqrt{p_1p_2}$), a relatively simple closed-form expression for the proxy exists. If the central mass is large, the behavior becomes "oscillatory," requiring more complex numerical solving.

Key Results

  • Theorem 3.1: Formally defines the two regimes for symmetric 3-mass distributions and provides the equations to solve for the proxy when $p < 1/6$.
  • Theorem 4.1: Establishes that for a uniform discrete distribution on $N$ points with spacing $a$, the optimal variance proxy is exactly the variance: $\sigma^2_{opt} = a^2 \frac{N^2 - 1}{12}$.
  • Numerical Tool: The provided Python package allows users to visualize these "gap functions" and find optimal proxies for a wide range of distributions, including truncated Gaussians and 3-mass variants.

Limitations and Future Work

  • Intractability of N-mass: The authors note that a general treatment for $N$-mass categorical distributions (where $N > 3$) remains "essentially intractable" in full generality due to the increasing complexity of the moment-generating functions.
  • Non-equidistant Support: The current study focuses on equally spaced atoms (e.g., $\{-1, 0, 1\}$). Analyzing distributions where the "gaps" between outcomes are unequal is a suggested direction for future research.
  • Bayesian Nonparametrics: The authors suggest applying these refined tail analyses to more complex discrete processes used in Bayesian statistics, such as the Dirichlet or Pitman–Yor processes.

Summary updated

Abstract

We investigate the problem of characterizing the optimal variance proxy for sub-Gaussian random variables,whose moment-generating function exhibits bounded growth at infinity. We apply a general characterization method to discrete random variables with equally spaced atoms. We thoroughly study 3-mass distributions, thereby generalizing the well-studied Bernoulli case. We also prove that the discrete uniform distribution over $N$ points is strictly sub-Gaussian. Finally, we provide an open-source Python package that combines analytical and numerical approaches to compute optimal sub-Gaussian variance proxies across a wide range of distributions.
BibTeX
@misc{atouani2025optimal,
  author = {Soufiane Atouani and Olivier Marchal and Julyan Arbel},
  title = {{Optimal sub-Gaussian variance proxy for 3-mass distributions}},
  year = {2025},
  eprint = {2510.06132},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.06132},
  howpublished = {arXiv},
}
Figure