CS Paper Radar

Distributionally Robust Search: The Power of Information and the Limits of Moments

Nicole Megow, Cliff Stein, Jose Verschae

cs.DS cs.DM ·submitted 2026-11-03 09:24 UTC · v1
theory

Abstract

We study binary search for a target drawn from a distribution on $n$ ordered elements. The cost is the expected number of comparison queries. In our distributionally robust framework, the algorithm knows only an uncertainty set containing the distribution and minimizes its worst-case approximation ratio against an optimal strategy that knows the distribution. Collections of uncertainty sets capture different forms of information: quantiles, moments, general linear measurements, or approximate CDFs. This framework quantifies how much and what form of information is needed for near-optimal search. Our main result separates moments from general linear measurements. Although $n-1$ moments determine the distribution exactly, for every constant $δ\in(0,1)$, the first $n^{1-δ}$ exact moments can be as uninformative for search as no information: the worst-case approximation ratio remains $Ω(\log n)$. In contrast, for every constant $\varepsilon\in(0,1)$, $O(n^\varepsilon\log^4 n)$ suitably chosen linear measurements suffice for an $O(1/\varepsilon)$-approximation. The limitation lies in the measurements chosen, rather than linearity itself. Using LP duality and polynomial bounds of Rakhmanov and Bernstein, we construct distributions with identical moments and mass concentrated at different positions. For the upper bound, we combine dyadic sketches and Johnson--Lindenstrauss embeddings with a truncated median-search algorithm that converts uniform CDF approximation into search guarantees. Measuring information in bits, we prove a lower bound of $Ω(1/\varepsilon)$ on the approximation ratio for summaries of any form using at most $\frac12 n^\varepsilon\log n$ bits, for every sufficiently small constant $\varepsilon>0$. Quantiles match this within constant factors. For Kolmogorov balls of radius $n^{-\varepsilon}$ the optimal approximation ratio is $Θ(1/\varepsilon)$.

Comment
43 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Moment Ambiguity and the Limits of Robust Stochastic Optimization

cs.IT cs.DScs.GTmath.OC ·2026-09-25 ·Andrés Cristi, Matteo Russo, Jiechen Zhang
benchmark similarity 0.70
Abstract

We study fundamental information-theoretic limits of robust stochastic optimization when the distribution is known only through its exact moment sequence. We develop a unified framework that produces families of distinct distributions sharing all moments yet inducing radically different optimal decisions, thereby establishing strong impossibility results for a range of decision problems under moment ambiguity. Our binary and $N$-way moment-matching constructions separate quantiles, threshold regions, and online selection opportunities while preserving every moment. For the newsvendor problem, moment equivalence causes quantile ambiguity, inducing any fixed or randomized order quantity to fail arbitrarily badly. For revenue maximization, no deterministic or randomized posted pricing scheme can secure a nontrivial approximation relative to the full-information benchmark. For the secretary problem with cardinal observations, the optimal robust success probability under exact moment disclosure is the classical finite-horizon value $s_m$, even for i.i.d. observations. This value converges to $1/e$, compared with the full-information limit of approximately $0.5801$ due to Gilbert and Mosteller (J. Am. Stat. Assoc., 1966). We also recover and expand upon the recent impossibility result of Correa et al. (STOC, 2026) for prophet inequalities with moment knowledge. For every fixed $r\ge1$, exact moment knowledge can yield at best a $Θ(1/\log m)$ competitive ratio, even when competing against relaxed benchmarks based on expected $r$-th order statistics or when the algorithm is allowed to select $r$ items.

0.28

Quantum Query Lower Bounds from Classical Moment Matching

cs.DS quant-ph ·2026-11-03 ·Chandrima Kayal, Frédéric Magniez, Sayantan Sen, Dániel Szabó
theory similarity 0.61
Abstract · 45 pages

We prove a quantum analogue of the classical moment matching method, a popular framework used to prove lower bounds in property testing. For two random variables $X_0$ and $X_1$ whose moments match up to the first $r-1$ moments, the classical moment matching method says that no classical algorithm can reliably distinguish between input instances of length $N$ constructed from $X_0$ and $X_1$, respectively, unless it performs at least $Ω(N^{1-1/r})$ queries. While this method has been widely explored since its inception in the seminal work of Raskhodnikova, Ron, Shpilka, and Smith (STOC 2007) to prove lower bounds for symmetric properties, it has remained an open question whether a quantum analogue of it could be proved. We prove two variants of this quantum moment matching method, which are incomparable. Our first quantum query lower bound scales as $Ω(N^{1/2-1/(2r)})$, while our second moment matching theorem yields a sharper lower bound of $Ω(N^{1/2-1/(2(2^r-1))})$, albeit for smaller parameter ranges. Our results combine a new continuous hybrid argument with the polynomial method. The continuous hybrid argument compares two hard input distributions generated from i.i.d. samples by continuously varying both distributions, keeping them identically distributed at every intermediate stage. It reduces the comparison to the effect of changing the distribution of a single sample. The polynomial method then cancels the terms determined by the matched moments. We apply these moment matching theorems to prove new optimal lower bounds on $k$-distinctness, $k$-star-freeness, planarity and outerplanarity testing, as well as to improve prior lower bounds on image size testing and $K$-junta testing by logarithmic factors. A key advantage of our framework is its simplicity: it reduces quantum lower bound proofs to the construction of suitable moment-matching distributions.

0.28

Visible Tails: Characterizing Adaptation to Unknown Moments in Heavy-Tailed Bandits

cs.LG cs.AI ·2026-11-09 ·Tuan Ngoc Do, Hai Duc Nguyen
benchmarktheory similarity 0.59
Abstract

Heavy-tailed bandit learners must tell a poor arm from an arm whose favorable rewards have not yet appeared. We characterize this obstruction through a scale of one-sided visibility conditions on the optimal reward law: the mean hidden in a rare event is at most a constant multiple of a retained central moment. A quantile-trimmed UCB index that is given the visibility constants attains arm-specific moment rates at every exponent, with no lower bound on the exponent. Conversely, every strategy with a fixed exploration budget has polynomial regret on each law that violates the corresponding condition. For the variance benchmark we determine the order of both budget constants in the visibility level. The frontier depends on the largest exponent the benchmark promises, and the resulting classes are strictly nested. The same index has logarithmic expected regret when rewards are integrable, with a coefficient that can be exponential in the inverse gap.

0.16

Hypothesis Selection via Weighted Medians

cs.DS cs.LG ·2026-10-14 ·Liang-Yu Zou
similarity 0.58
Abstract · fix some typos

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.

0.33

Optimal Support Size Testing

cs.IT cs.DSmath.ST ·2026-10-13 ·Qisheng Wang
theory similarity 0.58
Abstract · 12 pages

We present an optimal tester for support size that determines whether an unknown probability distribution is supported on $n$ elements or $\varepsilon$-far away (in total variation distance) with sample complexity $Θ(\frac{n}{\varepsilon\log(n)})$, improving the prior best $O(\frac{n}{\varepsilon\log(n)} \log(\min\{\frac{1}{\varepsilon}, n\}))$ due to Ferreira Pinto Jr. and Harms (STOC 2025). As a generalization, we provide a pretty good lower bound on support size.

0.30

On Minimum Divergence for Distribution Reconstruction

cs.IT math.ST ·2026-10-15 ·Justin Bec, Thomas Le Corre, Aurélien Garivier
similarity 0.56
Abstract

We study the possibility of generalizing maximum-entropy reconstruction, which approximately recovers a probability distribution from finitely many (generalized) moments by minimizing the Kullback--Leibler (KL) divergence to a reference measure. The reconstruction lies in an exponential family and is also the best KL approximation of the unknown distribution within that family: moment matching and information projection coincide. Replacing KL by a smooth f-divergence, the reconstruction still exists in an associated family, but the best approximation property does not. Specifically, a family is called entropy-adapted if the projection of any distribution matches its moments. We show that, up to equivalence, KL is the only $C^2$ f-divergence that is entropy-adapted, whatever the choice of the generalized moments. We illustrate the consequences of this failure numerically.

0.22

Adaptive Robust Confidence Sets in High Dimensions

cs.DS math.STcs.LGstat.ME+1 ·2026-10-11 ·Ilias Diakonikolas, Chao Gao, Daniel M. Kane, Yuetian Luo
theory similarity 0.56
Abstract

We study adaptive confidence sets for mean vectors of multivariate Gaussians with identity covariance under Huber contamination when the contamination proportion is unknown. We show that an information-theoretically optimal adaptive confidence set can be constructed by simultaneously quantifying uncertainty across all one-dimensional projections. The resulting confidence set achieves the optimal diameter and reveals a substantial adaptation cost compared with the minimax estimation error. Although statistically optimal, this construction is computationally infeasible. We establish a Statistical Query (SQ) lower bound showing that achieving diameter $O(m^{-1/2})$ requires either exponentially many queries or query tolerance $d^{-Ω(m)}$. Thus, in contrast to robust mean estimation, adaptation to the unknown contamination proportion incurs both a statistical cost and a computational barrier within the SQ framework. Finally, we give a low-degree moment-matching algorithm that constructs an adaptive confidence set using $d^{O(m)}$ samples and time. Its diameter bound contains an additional $O(m^{-1/2})$ term beyond the information-theoretic rate, matching the dependence on $m$ in the SQ lower bound. Together, these results characterize the statistical limits of adaptive robust confidence sets under Huber contamination and quantify a computational barrier within the SQ framework.

0.36

Sorting from Counterexamples

cs.LG cs.CCcs.CGcs.DS+1 ·2026-08-21 ·Noga Alon, Shay Moran, Shlomo Moran
publishedtheory similarity 0.56
Abstract

Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to $k$ of the returned counterexamples may be untruthful, where $k$ is not known in advance. We determine the optimal query complexity up to constant factors: \[ Θ(n\log n + nk). \] Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$. The upper bound is based on a geometric representation of permutations and Grünbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in $\mathbb{R}^d$, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of $O(d^2\log n+dk)$ and a lower bound of $Ω(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.

0.37