This work refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to $O( \log n / \epsilon^2)$ for $\ell_\infty$-recovery, matching the untruncated minimax rate.
Abstract
Learning the natural parameters $z \in \mathbb{R}^n$ of discrete distributions $\mu_z$ from independent samples constrained to a subset $S \subseteq \{0,1\}^n$ is a foundational challenge in high-dimensional statistics. Existing methods for efficiently estimating truncated Boolean product distributions, notably the work of [Fotakis et al'COLT'20, Algorithmica'22], require either strong local connectivity assumptions on $S$ -- a property denoted fatness -- or stringent anti-concentration assumptions and necessitate the total mass of the truncation set to be a constant with respect to $n$. Moreover, the results in [Fotakis et al'COLT'20, Algorithmica'22] suffer from sample complexities that scale as $\Omega(2^n)$ if the mass of $S$ is exponentially small in $n$. In this work, we circumvent these limitations by analyzing the geometry of $S$ under the measure $\mu_z$. We refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to $O( \log n / \epsilon^2)$ for $\ell_\infty$-recovery, matching the untruncated minimax rate. We further generalize fatness using the notion of influence utilized in the analysis of Boolean functions and provide sufficient conditions for efficient inference. Notably, unlike previous work, our method does not require sampling at arbitrary parameterizations of the model. Lastly, we establish a theoretical lower bound demonstrating the sample complexity exhibits an intrinsic exponential dependence on the width of the model and the minimum distance between elements in the set.
A uniformly random $m$-subset of $[n]=\{0,\ldots,n-1\}$ has entropy $\log_2\binom{n}{m}$. Standard without-replacement procedures often expose an additional ordering coordinate that is absent from the returned set. We show that Floyd's subset sampler admits an exact round-local factorization of this coordinate. In round $r$, let $S$ be an $(r-1)$-subset of $[j]$, let $T\sim\operatorname{Unif}([j+1])$, and let $S'$ be the result of Floyd's transition. If $D$ is the zero-based rank of the original draw $T$ in $S'$, then $(S,T)\leftrightarrow(S',D)$ is a bijection between $\binom{[j]}{r-1}\times[j+1]$ and $\binom{[j+1]}{r}\times[r]$. Consequently, $S'$ and $D$ are independent and uniform on their respective spaces. The digit $D$ can therefore be merged immediately into a residual uniform random state; an induction shows that the partial subset remains independent of that state after every round. For $k=\min(m,n-m)$, the sampling phase uses $O(k\log k)$ time and $O(k)$ auxiliary space with an order-statistic tree; explicitly materializing a complement incurs the unavoidable output cost. The combinatorial layer avoids binomial-coefficient arithmetic and recovers the complete $k!$ state-space factor exactly. We also give a finite counterexample showing that analogous immediate rank recycling in a partial Fisher-Yates array is invalid because the unselected suffix retains a correlated ordering. A 64-bit Rust implementation is checked by exhaustive state-space enumeration for all $n\leq 8$ and by an entropy-accounting trace for choosing $20{,}000$ of $30{,}000$ items. We make no claim of runtime superiority over existing subset samplers.
The theorem below establishes the order for arbitrary real factors under the factorization contract of Arkhipov and Kalinin, who prove the matching lower order for factors with entries in $\{0,1\}$ and state the arbitrary-factor extension as open.
Suppose we observe two sets of $n$ Gaussian vectors in $\mathbb{R}^d$, with the promise that, after applying a permutation of $[n]$ and a rotation of $\mathbb{R}^d$, the two sets are $\rho$-correlated. The Procrustes matching problem asks us to recover the unknown permutation of $[n]$ that aligns the two sets. The problem is well-studied in the low-dimensional regime $d=O(\log n)$, but the high-dimensional regime $d\gg \log n$ has remained largely uncharted: prior matching guarantees require nearly perfect correlation $\rho=1-o(1)$, even for information-theoretic recovery. Our main result is a polynomial-time algorithm for exact recovery at constant correlation. The algorithm works by computing and comparing weighted counts of a specially chosen family of ``wide''trees. So long as $d\ge \mathrm{polylog}(n)$, the algorithm succeeds with high probability for any $\rho^2>\sqrt{\alpha}$, where $\alpha\approx 0.338$ is Otter's tree-counting constant. We complement this algorithmic result with an improved information-theoretic guarantee, showing that exact recovery is possible when $\rho^2 \gtrsim \max\{\log n/d,\sqrt{\log n/n}\}$. We also carry out a low-degree advantage calculation, which suggests that the condition $\rho^2>\sqrt{\alpha}$ is necessary for any tree-counting algorithm.
We consider the problem of finding the root vertex of a random uniform attachment tree, when the union of the unlabeled tree and an Erd\H{o}s-R\'enyi random graph $\mathbb{G}(n,p)$ is observed. We prove that, as long as $p=o(\log n /n)$, for any $\varepsilon>0$, one can construct a confidence set of vertices of size $K(\varepsilon)$ that depends only on $\varepsilon$ and not on $n$, such that it contains the root with probability at least $1-\varepsilon$. This affirms a conjecture of Crane and Xu (2021). Our approach ranks vertices by their Jordan centrality in the largest component of the subgraph spanned by high-degree vertices. We show that the same approach works in other noise models as well.
Luc Devroye, Gábor Lugosi, Neeladri Maitra· 1 citation· ⚡1
Given $[0,1]$-valued random variables $X_1,\dots,X_n$ such that $\mathbb{E}[X_i | X_1,\dots,X_{i-1}]= \mu$ for all $i$, we propose a new nonasymptotic confidence interval for $\mu$ that is obtained by inverting terminal e-values generated by a novel betting strategy. When the data are iid, its limiting width matches that of the central limit theorem (``Gaussian-efficient''), finally surpassing the inefficient limits of previous betting intervals. Our main conceptual advance involves designing betting fractions that track the conditional rejection probability of the most powerful terminal test in a limiting Gaussian experiment. When one predictable variance estimator is shared across candidate means, the deterministic inversion is an interval for every data sequence and its two endpoints can be found easily. The width can be improved further with external randomization. In simulations, our method yields the tightest intervals to date; for every distribution tested and all sufficiently large $n$, our deterministic version beats STaR-Bets and is competitive with Gaffke, while the randomized improvement beats both. It thus combines finite-sample validity under martingale dependence, easy endpoint computation, Gaussian-efficient inference for iid data, and excellent empirical performance. We also extend the construction and its efficiency theory to sampling without replacement, where it again achieves state-of-the-art empirical performance.
Diego Martinez-Taboada, Aaditya Ramdas· 0 citations
This analysis reveals a scale-sensitive interaction between the statistical estimation of classification error and its amplification by robustness, sharply explaining the transition in the agnostic rate.
Elad Aigner-Horev, Daniel Rosenberg, Roi Weiss· 1 citation· ⚡1