Towards Testing Monotonicity of Distributions Over General Posets
Pith reviewed 2026-05-25 01:24 UTC · model grok-4.3
The pith
Testing monotonicity of distributions over posets requires Ω(n/log n) samples in the worst case.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We establish a lower bound of Ω(n/log n) for testing bigness of distributions on domains of size n. We then build on these lower bounds to give Ω(n/log n) lower bounds for testing monotonicity over a matching poset of size n and significantly improved lower bounds over the hypercube poset. We give sublinear sample complexity bounds for testing bigness and for testing monotonicity over the matching poset. We then give a number of tools for analyzing upper bounds on the sample complexity of the monotonicity testing problem.
What carries the argument
The bigness property (minimum probability at least T) together with reductions that embed bigness instances into monotonicity instances over specific posets such as matchings.
If this is right
- Monotonicity testing over a matching poset of size n requires Ω(n/log n) samples.
- Bigness testing admits sublinear sample complexity upper bounds.
- Monotonicity testing over the hypercube receives improved lower bounds beyond prior work.
- General tools exist for deriving upper bounds on monotonicity testing over arbitrary posets.
Where Pith is reading between the lines
- The same reduction technique may apply to other poset families if they support similar embeddings of hard instances.
- For posets without such structure, monotonicity testing could require more samples than the matching case.
- The sublinear upper bounds suggest that constant-factor improvements over the lower bound remain possible for matchings.
Load-bearing premise
The poset structure preserves distances to monotonicity so that a hard bigness instance can be embedded without extra sample cost.
What would settle it
An algorithm that distinguishes T-big distributions from those ε-far from T-big using o(n/log n) samples on a domain of size n would falsify the lower bound.
read the original abstract
In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution $p$ over a poset is monotone if, for any pair of domain elements $x$ and $y$ such that $x \preceq y$, $p(x) \leq p(y)$. To understand the sample complexity of this problem, we introduce a new property called bigness over a finite domain, where the distribution is $T$-big if the minimum probability for any domain element is at least $T$. We establish a lower bound of $\Omega(n/\log n)$ for testing bigness of distributions on domains of size $n$. We then build on these lower bounds to give $\Omega(n/\log{n})$ lower bounds for testing monotonicity over a matching poset of size $n$ and significantly improved lower bounds over the hypercube poset. We give sublinear sample complexity bounds for testing bigness and for testing monotonicity over the matching poset. We then give a number of tools for analyzing upper bounds on the sample complexity of the monotonicity testing problem.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the bigness property (a distribution p on [n] is T-big if min_x p(x) >= T) and proves an Omega(n/log n) lower bound for testing it. It then reduces from bigness to obtain an Omega(n/log n) lower bound for monotonicity testing over the matching poset of size n, improved lower bounds over the hypercube, and sublinear upper bounds for both bigness and monotonicity over the matching poset, together with general tools for analyzing monotonicity upper bounds.
Significance. If the reductions hold, the work advances distribution testing over posets by linking monotonicity to a new auxiliary property and supplying the first sublinear bounds for the matching poset; the explicit sublinear upper bounds and the reduction framework are concrete strengths.
major comments (1)
- [Abstract] Abstract (paragraph on building lower bounds from bigness): the transfer of the Omega(n/log n) bigness lower bound to monotonicity over the matching poset requires that the embedding preserves total-variation distance to the target property exactly. The manuscript must exhibit an explicit argument that no redistribution of mass along matched pairs can turn a distribution Omega(1)-far from bigness into one o(1)-close to monotone; without this, the lower-bound claim does not go through.
Simulated Author's Rebuttal
We thank the referee for the careful reading of the manuscript and for identifying this important point regarding the reduction. We address the comment below and will revise the paper accordingly.
read point-by-point responses
-
Referee: [Abstract] Abstract (paragraph on building lower bounds from bigness): the transfer of the Omega(n/log n) bigness lower bound to monotonicity over the matching poset requires that the embedding preserves total-variation distance to the target property exactly. The manuscript must exhibit an explicit argument that no redistribution of mass along matched pairs can turn a distribution Omega(1)-far from bigness into one o(1)-close to monotone; without this, the lower-bound claim does not go through.
Authors: We agree that an explicit argument is required to establish that the reduction from bigness testing to monotonicity testing over the matching poset preserves the relevant distance. While the manuscript describes the embedding and states the resulting lower bound, it does not provide a sufficiently detailed proof that mass redistribution along matched pairs cannot reduce the distance to monotonicity below a constant. In the revised version we will add this argument (in the section presenting the reduction) by showing that any distribution that is Omega(1)-far from being T-big remains Omega(1)-far from monotone even after arbitrary redistribution within each matched pair, because the bigness violation forces a constant fraction of the mass to be concentrated on too few elements in a way that cannot be compensated by the matching structure. revision: yes
Circularity Check
No circularity: independent lower bound for new bigness property then reduced to monotonicity
full rationale
The paper defines bigness as a fresh property (minimum probability mass T), proves an Ω(n/log n) lower bound for testing it on [n], and then reduces that bound to monotonicity testing over the matching poset. No equation or claim equates a derived quantity to its own input by construction, no parameter is fitted and relabeled as a prediction, and no load-bearing step rests on a self-citation whose content is itself unverified. The reduction is a standard hardness transfer whose validity is an external mathematical claim, not a definitional identity. This is the normal, non-circular case.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Finite domain probability distributions satisfy the usual axioms of non-negative masses summing to one.
invented entities (1)
-
T-big distribution
no independent evidence
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.