betaFeedback

WorksComputer Science

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

Abstract

We study binary search for a target drawn from a distribution on nn 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−1n-1 moments determine the distribution exactly, for every constant δ∈(0,1)δ\in(0,1), the first n1−δn^{1-δ} exact moments can be as uninformative for search as no information: the worst-case approximation ratio remains Ω(log⁡n)Ω(\log n). In contrast, for every constant ε∈(0,1)\varepsilon\in(0,1), O(nεlog⁡4n)O(n^\varepsilon\log^4 n) suitably chosen linear measurements suffice for an O(1/ε)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/ε)Ω(1/\varepsilon) on the approximation ratio for summaries of any form using at most 12nεlog⁡n\frac12 n^\varepsilon\log n bits, for every sufficiently small constant ε>0\varepsilon>0. Quantiles match this within constant factors. For Kolmogorov balls of radius n−εn^{-\varepsilon} the optimal approximation ratio is Θ(1/ε)Θ(1/\varepsilon).

Introduction

How much information about a distribution is needed to make good decisions under uncertainty? We study this question by considering a distributionally robust framework based on uncertainty sets, and apply it to the fundamental problem of searching on an ordered array. Specifically, we ask which information about the target distribution allows us to search nearly as efficiently as if the distribution were completely known.

Consider an unknown target tt drawn from a distribution p=(p0,…,pn−1)p = (p_0, \ldots, p_{n-1}) on [n]0:={0,…,n−1}[n]_0 := \{0, \ldots, n-1\}. A query at a vertex vv reveals whether t<vt < v, t=vt = v, or t>vt > v. We seek an adaptive search strategy minimizing the expected number of queries. Without information about pp, binary search finds every target in O(log⁡n)O(\log n) queries. When pp is known, an optimal strategy can be computed by dynamic programming [24]. Moreover, distribution-guided bisection achieves expected cost O(1+H(p))O(1+H(p)), within a constant factor of the optimum OPT⁡(p)\operatorname{OPT}(p), where H(p)H(p) is the entropy of pp [31]. Distributional knowledge can therefore reduce the expected search cost from logarithmic to constant.

We study how much of this advantage can be retained with limited knowledge of pp. In our distributionally robust model, the available information specifies an uncertainty set UU containing pp, and the search strategy must perform well for every distribution in UU. For example, if we observe a sketch of pp, such as its first kk moments, then UU is the set of all distributions with the same sketch. We compare the strategy’s expected cost under each p∈Up \in U with OPT⁡(p)\operatorname{OPT}(p): the benchmark knows the true distribution, whereas our strategy knows only UU; neither knows the realized target. A collection U\mathcal{U} of uncertainty sets describes a form of partial information. Our central question is:

How much and what kind of distributional information is needed to obtain a constant-factor approximation for search?

We first measure information in bits, allowing arbitrary encodings of the distribution. This gives a baseline for the amount of information needed, independently of how it is represented.

We then ask how the form of the information affects search. A natural class of summaries consists of linear measurements ∑tatpt\sum_t a_t p_t, with coefficients chosen independently of pp. Such measurements can be estimated from samples by averaging the corresponding coefficients. We ask how many measurements suffice and how their choice affects the achievable approximation. Here we count exact real-valued measurements, rather than the bits needed to represent them.

Moments are a particularly natural class of linear measurements. The first kk moments are μi(p)=∑tptti\mu_i(p) = \sum_t p_t t^i for i=1,…,ki = 1, \ldots, k. Low-order moments have familiar interpretations: they determine the mean, variance, skewness, and kurtosis. For empirical distributions, moments can be maintained through sums of powers, which are easily updated under insertions and deletions and combined across datasets. Moments therefore provide interpretable, efficiently maintainable summaries of increasing informativeness; on [n]0[n]_0, the first n−1n-1 moments determine pp uniquely.

Moment information is widely used to describe distributional uncertainty in robust optimization [36, 16] and mechanism design [10, 13, 5, 39], and its informativeness for optimal stopping has recently been studied [7].

For search, however, choosing a distribution consistent with the observed moments does not by itself justify using its optimal strategy: the strategy must perform well for every distribution with those moments. Thus, we ask how many moments are needed for constant-factor approximate search, and how their power compares with that of the same number of arbitrary linear measurements.

Our Contributions and Techniques

We introduce an uncertainty-collection framework for studying how the amount and form of distributional information affect search. We measure a collection U\mathcal{U} of uncertainty sets by its approximability factor α(U)\alpha(\mathcal{U}): the worst-case approximation ratio of the best strategy that knows only the uncertainty set UU, compared with an optimal strategy that knows the true distribution p∈Up \in U (§ 2.2). The framework accommodates finite encodings, quantiles, moments, linear measurements, and approximate cumulative distribution functions (CDFs).

We ask which uncertainty collections achieve α(U)=O(1/ε)\alpha(\mathcal{U}) = O(1/\varepsilon), for some positive constant ε\varepsilon, and how much information is required. Our upper bounds use a common sufficient condition: a nominal distribution whose CDF approximates that of every distribution in the uncertainty set uniformly within n−εn^{-\varepsilon}, or equivalently, whose Kolmogorov distance dKd_K to each such distribution is at most n−εn^{-\varepsilon}. We consider a natural algorithm, Coarse Greedy, that runs the classical median-search algorithm analyzed by Mehlhorn [31] on the nominal distribution, truncating it at a depth determined by the available accuracy guarantee before switching to ordinary binary search. This yields an O(1/ε)O(1/\varepsilon)-approximation (Theorem 5). Thus, uniform CDF approximation provides a common route from distributional summaries to search guarantees.

Information-Theoretic Limits. We first establish a lower bound that applies to every encoding of the distribution into a finite bit string, regardless of how the information is computed or represented.

Theorem 1 (Information-theoretic lower bound, informal; see Theorem 6). Let ε>0\varepsilon> 0 be a small constant. For nn large enough and for every sketch σ\sigma whose output uses at most 12nεlog⁡n\frac{1}{2}n^\varepsilon\log n bits, every algorithm that only has access to σ(p)\sigma(p) has approximation ratio Ω(1/ε)\Omega(1/\varepsilon).

This lower bound is tight up to constant factors: storing nεn^\varepsilon quantiles uses O(nεlog⁡n)O(n^\varepsilon\log n) bits and determines the CDF within Kolmogorov distance n−εn^{-\varepsilon}, giving an O(1/ε)O(1/\varepsilon)-approximation through Coarse Greedy.

The proof of the lower bound uses distributions that place equal mass on one independently and uniformly chosen position in each of nεn^\varepsilon consecutive blocks. If the distribution is known, searching its support takes O(εlog⁡n)O(\varepsilon\log n) queries. The key step is to show that a short encoding leaves enough conditional entropy in the support positions that every strategy using this encoding incurs expected cost Ω(log⁡n)\Omega(\log n) on some compatible distribution.

We extend this lower bound to arbitrary uncertainty collections, including collections with overlapping sets (Corollary 7). The key observation is that a small cover of the simplex by uncertainty sets induces a short encoding: record the index of a covering set containing the distribution. As an application, the quantile construction provides a cover by Kolmogorov balls. Together with Coarse Greedy, this yields an approximability factor of Θ(1/ε)\Theta(1/\varepsilon) for balls of radius n−εn^{-\varepsilon} (Theorem 9).

Search Under Moment Information. We now turn to the interpretable summaries defined by moments. The first kk moments define the linear sketch σk(p):=(∑t∈[n]0tipt)i=0k\sigma_k(p) := (\sum_{t \in[n]_0} t^i p_t)_{i=0}^k, whose uncertainty collection consists of infinitely many lower-dimensional polytopes {p:σk(p)=μˉ}\{p : \sigma_k(p) = \bar{\mu}\}. We include the constant zeroth moment μ0(p)=1\mu_0(p) = 1 for convenience. Since we count moments rather than the bits needed to represent their values, the finite-bit lower bound does not directly apply. Any linear sketch needs nΩ(ε)n^{\Omega(\varepsilon)} measurements for an O(1/ε)O(1/\varepsilon)-approximation (Theorem 20). This makes nεn^\varepsilon moments a natural benchmark, up to a constant in the exponent. Our main result shows a much stronger limitation: Ω(n/log⁡n)\Omega(n/\log n) moments are needed for a constant approximability factor (Theorem 16).

Theorem 2 (Moment lower bound, informal). For large nn and k≤cn/log⁡nk \le cn/\log n, with c>0c > 0 sufficiently small, the first kk moments induce an uncertainty collection with approximability factor Ω(log⁡nklog⁡n)\Omega\left(\log\frac{n}{k\log n}\right).

In particular, for every constant δ∈(0,1)\delta\in(0,1), even k=n1−δk = n^{1-\delta} moments leave an approximability factor of Ω(log⁡n)\Omega(\log n), which is trivially obtained by ordinary binary search without any distributional information. Thus, a polynomially sublinear number of moments can be as uninformative for search as no information at all. In contrast, n−1n-1 moments determine the full distribution exactly and hence permit an optimal search strategy. Yet O(nlog⁡4n)O(n \log^{4} n) suitably chosen linear measurements already suffice for an O(1/ε)O(1/\varepsilon)-approximation (Corollary 21).

The key ingredient in the proof of Theorem 2 is Proposition 10: two distributions p,p′p,p' can share the same first kk moments but have peaks of mass at least 1−γ1-\gamma at different positions m,m0m,m_0, where γ=O(k∣m−m0∣/n)\gamma= O(k\lvert m-m_0\rvert/n); see Figure 1. In particular, their Kolmogorov distance is at least 1−2γ1-2\gamma, so matching moments alone need not determine the CDF accurately. Intuitively, a search strategy that only knows the kk moments cannot distinguish between pp and p′p', and hence does not know whether to search at mm or at m0m_0. To construct them, we start with point masses at mm and m0m_0 and seek a signed correction that compensates for the difference in their moments. A correction with small ℓ1\ell_1-norm lets us match the moments by adding little mass to either point mass and then normalizing, so both peaks remain large. The correction problem is an LP whose moment constraints have a Vandermonde coefficient matrix. Its dual therefore has a polynomial interpretation: the minimum correction norm equals the largest increment between mm and m0m_0 of a degree-kk polynomial bounded on the grid. The key is that such a polynomial cannot change too rapidly in the central part of the domain. Using Rakhmanov’s theorem [33] to control its magnitude between grid points, and Bernstein’s inequality to bound its derivative, we can bound the dual objective, yielding the small correction and hence the two distributions.

Figure 1. The construction in Proposition 10 for n=41n = 41, k=4k = 4, m=14m = 14, and m0=22m_0 = 22: the distributions pp and p′p' have the same first kk moments. Shading marks [n−14,3(n−1)4]\left[\frac{n-1}{4}, \frac{3(n-1)}{4}\right].

To obtain the search lower bound, we combine these corrections to construct R+1R+1 distributions with the same first kk moments, each concentrated at a different position (Proposition 15). Choosing R+1R+1 consecutive peak positions with R=Θ(n/(klog⁡n))R = \Theta(\sqrt{n/(k\log n)}) keeps the mass outside each peak at most 1/(4log⁡n)1/(4\log n). A strategy knowing the distribution queries its peak first and otherwise uses binary search, giving OPT=O(1)\mathrm{OPT} = O(1). A strategy observing only the common moments must accommodate all R+1R+1 possible peaks. A counting argument forces expected cost Ω(log⁡(R+1))\Omega(\log(R+1)) on one of these distributions, yielding the claimed Ω(log⁡(n/(klog⁡n)))\Omega(\log(n/(k\log n))) approximation lower bound.

Using the same LP-duality framework, we give proofs of approximate and exact CDF recovery from moments. Approximate recovery holds when one distribution consistent with the moments has bounded atoms, and exact recovery holds when one such distribution has small support.

Theorem 3 (Recovery from moments, informal). Let pp and π\pi be distributions on [n]0[n]_0 with the same first kk moments.

(a) If πt≤L\pi_t \le L for every tt, then the Kolmogorov distance is dK(p,π)=O(Lnklog⁡n)d_K(p,\pi) = O(L\frac{n}{k}\log n).

(b) If π\pi has at most ℓ\ell support points and k≥2ℓk \ge2\ell, then p=πp = \pi.

The exact recovery statement in part (b) is known [42 Lemma 4(2)]. LP duality expresses the largest CDF value consistent with the moments as the minimum expectation of a polynomial of degree at most kk majorizing the corresponding threshold indicator on the grid. For part (a), we use Chebyshev polynomials to approximate this indicator from above with transition width O((n/k)log⁡n)O((n/k)\log n) and negligible additional loss (Lemma 17 and Theorem 18). For part (b), interpolation gives a dual certificate that agrees with the indicator on the support of π\pi, making the bound exact (Proposition 19).

Exact recovery in part (b) yields optimal search. When the bound in part (a) guarantees CDF error n−εn^{-\varepsilon} with k≤nk \le n, every compatible distribution has point probabilities O(n−ε)O(n^{-\varepsilon}), so ordinary binary search already achieves an O(1/ε)O(1/\varepsilon)-approximation (§ 4.3). If L=O(n−α)L = O(n^{-\alpha}) for constant α∈(0,1]\alpha\in(0,1], then k=O(n1−α+εlog⁡n)k = O(n^{1-\alpha+\varepsilon}\log n) moments suffice for CDF error n−εn^{-\varepsilon} for fixed ε∈(0,α)\varepsilon\in(0,\alpha). The separated-peak construction explains why the bound on point probabilities in Theorem 3(a) matters: without it, distributions with identical moments can have Kolmogorov distance close to one.

Effective Linear Sketches

It is natural to ask whether the limitations of moments extend to all linear measurements. We show that they do not (Theorem 20 and Corollary 21).

Theorem 4 (Linear sketches, informal).

(a) Every linear sketch with k≥2k \ge2 measurements induces an uncertainty collection with approximability factor Ω(log⁡n/log⁡k)\Omega(\log n / \log k).

(b) For every ε∈(0,1)\varepsilon\in(0,1), there exists a linear sketch with O(nεlog⁡4n)O(n^{\varepsilon}\log^{4} n) measurements whose uncertainty collection has approximability factor O(1/ε)O(1/\varepsilon).

Part (a) implies that nΩ(ε)n^{\Omega(\varepsilon)} measurements are necessary for an O(1/ε)O(1/\varepsilon)-approximation, while part (b) shows that this is tight up to a constant in the exponent and polylogarithmic factors. The upper bound adapts dyadic quantile sketches [GKMS02, CM05], using near-orthogonal vectors from the Johnson–Lindenstrauss lemma [21] to sketch interval masses at each level. Every prefix decomposes into O(log⁡n)O(\log n) dyadic intervals, giving a uniform CDF estimate with error n−ε/2n^{-\varepsilon/2}; Coarse Greedy then yields the search guarantee. Thus, suitably chosen linear measurements succeed where even n1−δn^{1-\delta} moments fail: the limitation lies in the Vandermonde structure of the moment matrix, rather than linearity itself.

Related Literature

Lin, Luo, and Woodruff [29] study learning-augmented binary search trees, built from predicted access frequencies. Dinitz et al. [14] study binary search with a predicted target distribution. Their algorithm achieves expected query complexity O(H(p)+log⁡η)O(H(p) + \log\eta), where H(p)H(p) is the true distribution’s entropy and η\eta is its earth mover’s distance from the prediction. Their algorithm interleaves median phases with endpoint searches, without knowing the prediction error beforehand. Our Coarse Greedy uses a known CDF-error bound to fix the truncation depth of median search.

Our work connects to the classical moment problem [37, 26 KN77]: how do prescribed moments constrain a measure and event probabilities? See Landau [27] for its broader mathematical implications. We study this question for distributions supported on a fixed finite grid.

The duality between moments and polynomials goes back to Riesz [34] and Haviland [20]. Together with positivity results such as Putinar’s Positivstellensatz [32], it underlies moment-based approaches to polynomial optimization [Las01]. Bertsimas and Popescu [3] formulate tight probability bounds under moment constraints as optimization problems with polynomial dual certificates. On our finite domain, bounds on the CDF arise from finite LPs whose duals connect moment information to polynomial approximation.

Polynomial approximation and moment matching also underpin statistical lower bounds for nonsmooth functionals, entropy, and support size [9, 40, 41]. There, matching moments of auxiliary distributions makes observations difficult to distinguish. Here, the moments themselves are observed, making distributions with matching moments indistinguishable to the search algorithm.

Correa et al. [7] study moment information for prophet inequalities, where the goal is to select a large reward from sequential observations. Even knowing all moments yields only a Θ(1/log⁡m)\Theta(1/\log m) competitive guarantee, where mm counts the random variables. The two settings are hard for different reasons. Their moments cannot locate a rare atom of large value, which changes the expected maximum by polynomial factors. Search only sees mass, not values, so our lower bound places Ω(1)\Omega(1) mass at different but close positions that the first kk moments cannot separate.

Our bit-complexity formulation relates to advice complexity, which asks how many advice bits an online algorithm needs for a given guarantee [1]. The advice may encode arbitrary information, including input properties or a suitable (possibly optimal) solution. Our lower bound Theorem 6 applies to every encoding of the distribution, including encodings of search strategies. Beyond counting bits, our uncertainty-set framework compares specific forms of distributional information.

Compact quantile summaries with uniform additive rank-error guarantees are extensively studied in streaming [17, 22]; see [8] for relative-error variants. Their CDF approximations for the empirical distribution yield search guarantees through Coarse Greedy. Our bit lower bound concerns search performance directly and applies to arbitrary encodings, even with full access to the distribution and no requirement to approximate its CDF.

Organization. § 2 sets up the search model, the uncertainty model and the Coarse Greedy reduction. § 3 proves the bit-complexity and covering-number bounds and the tight characterization of Kolmogorov balls and quantiles. § 4 contains the moment results, negative and positive, while § 5 treats general linear sketches.

Model and Search from Approximate CDFs

Search Model

We consider search on the path with vertex set [n]0:={0,1,…,n−1}[n]_0 := \{0,1,\ldots,n-1\}, with n≥2n \ge2. An unknown target vertex t∈[n]0t \in[n]_0 is drawn from a distribution p=(p0,…,pn−1)p = (p_0,\ldots,p_{n-1}). A query at a vertex vv reveals whether t<vt < v, t=vt = v, or t>vt > v. Equivalently, the query either finds the target or identifies the component of the path after removing vv that contains it. Logarithms are base 2 unless noted.

A deterministic search strategy is an adaptive procedure that repeatedly queries vertices until the target is identified. Equivalently, a strategy is an ordered binary search tree. Each node corresponds to an interval of possible targets I={a,…,b}I = \{a,\ldots,b\} and is labeled by a vertex v∈Iv \in I. If a=ba=b, the target is identified without another query. Otherwise, the strategy queries vv, terminates on equality, and continues on the appropriate nonempty interval {a,…,v−1}\{a,\ldots,v-1\} or {v+1,…,b}\{v+1,\ldots,b\}.

References

  1. [1]Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen. Online algorithms with advice: A survey. ACM Computing Surveys, 50(2):19:1–19:34, 2017. doi:10.1145/3056461.DOI
  2. [2]Jorge Bustamante, Reinaldo Martínez-Cruz, and José María Quesada. Quasi orthogonal Jacobi polynomials and best one-sided L₁ approximation to step functions. Journal of Approximation Theory, 198:10–23, 2015. doi:10.1016/j.jat.2015.05.001.
  3. [3]Dimitris Bertsimas and Ioana Popescu. Optimal inequalities in probability theory: A convex optimization approach. SIAM Journal on Optimization, 15(3):780–804, 2005. doi:10.1137/S1052623401399903.DOI
  4. [4]Dimitris Bertsimas and Jay Sethuraman. Moment Problems and Semidefinite Optimization. In Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe, editors, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, pages 469–509. Springer US, Boston, MA, 2000. doi:10.1007/978-1-4615-4381-7_16.DOI
  5. [5]Nir Bachrach and Inbal Talgam-Cohen. Distributional robustness: From pricing to auctions. In EC, page 150. ACM, 2022. doi:10.1145/3490486.3538273.DOI
  6. [6]Neal L. Carothers. A short course on approximation theory. Bowling Green State University, Available at https://math.bme.hu/~matolcsi/approximation_Carothers.pdf (Accessed: 2026-02-16), 1998.
  7. [7]José Correa, Andrés Cristi, Vasilis Livanos, Victor Verdugo, and Jiechen Zhang. On the informativeness of moments in optimal stopping. In Aditya Bhaskara and Artur Czumaj, editors, STOC, pages 777–787. ACM, 2026. doi:10.1145/3798129.3800792.DOI
  8. [8]Graham Cormode, Zohar Karnin, Edo Liberty, Justin Thaler, and Pavel Veselý. Relative error streaming quantiles. Journal of the ACM, 70(5):30:1–30:48, 2023. doi:10.1145/3617891.DOI
  9. [9]T. Tony Cai and Mark G. Low. Testing composite hypotheses, Hermite polynomials and optimal estimation of a nonsmooth functional. The Annals of Statistics, 39(2):1012–1041, 2011. doi:10.1214/10-AOS849.DOI
  10. [10]Vinicius Carrasco, Vitor Farinha Luz, Nenad Kos, Matthias Messner, Paulo Monteiro, and Humberto Moreira. Optimal selling mechanisms under moment conditions. J. Econ. Theory, 177:245–279, 2018. doi:10.1016/J.JET.2018.05.005.DOI
  11. [12]Thomas M. Cover and Joy A. Thomas. Elements of information theory. Wiley-Interscience, Hoboken, N.J., 2nd edition, 2006. doi:10.1002/047174882X.DOI
  12. [13]Yeon-Koo Che and Weijie Zhong. Robustly-optimal mechanism for selling multiple goods. In EC, pages 314–315. ACM, 2021. doi:10.1145/3465456.3467570.DOI
  13. [14]Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Aidin Niaparast, and Sergei Vassilvitskii. Binary search with distributional predictions. In NeurIPS, volume 37 of NIPS ’24, pages 90456–90472, Red Hook, NY, USA, 2024.arxiv.org/abs/2411.16030
  14. [15]Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, 27(3):642–669, 1956. doi:10.1214/aoms/1177728174.DOI
  15. [16]Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3):595–612, 2010. doi:10.1287/opre.1090.0741.DOI
  16. [17]Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile summaries. In Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, SIGMOD ’01, pages 58–66. ACM, 2001. doi:10.1145/375663.375670.DOI
  17. [19]Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou. Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness. In STOC, pages 395–406. ACM, 2025. doi:10.1145/3717823.3718227.DOI
  18. [20]E. K. Haviland. On the momentum problem for distribution functions in more than one dimension. American Journal of Mathematics, 57(3):562–568, 1935. doi:10.2307/2371187.DOI
  19. [21]William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in Modern Analysis and Probability, volume 26 of Contemporary Mathematics, pages 189–206. American Mathematical Society, 1984. doi:10.1090/conm/026/737400.DOI
  20. [22]Zohar Karnin, Kevin Lang, and Edo Liberty. Optimal quantile approximation in streams. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’16, pages 71–78. IEEE, 2016. doi:10.1109/FOCS.2016.17.DOI
  21. [24]D. E. Knuth. Optimum binary search trees. Acta Informatica, 1(1):14–25, March 1971. doi:10.1007/BF00264289.DOI
  22. [25]Michel Krawtchouk. Sur le problème de moments. In Verhandlungen des Internationalen Mathematiker-Kongresses Zürich 1932, volume 2, pages 127–128, 1932. URL: https://www.mathunion.org/fileadmin/ICM/Proceedings/ICM1932.2/ICM1932.2.ocr.pdf#page=147.
  23. [26]Samuel Karlin and William J. Studden. Tchebycheff Systems: With Applications in Analysis and Statistics. Pure and Applied Mathematics. Interscience Publishers (John Wiley & Sons), New York, 1966.
  24. [27]Henry J. Landau, editor. Moments in Mathematics, volume 37 of Proceedings of Symposia in Applied Mathematics. American Mathematical Society, Providence, RI, 1987. doi: 10.1090/psapm/037.DOI
  25. [29]Honghao Lin, Tian Luo, and David Woodruff. Learning Augmented Binary Search Trees. In Proceedings of the 39th International Conference on Machine Learning, pages 13431–13440. PMLR, 2022.arxiv.org/abs/2206.12110
  26. [30]Pascal Massart. The tight constant in the Dvoretzky–Kiefer–Wolfowitz inequality. The Annals of Probability, 18(3):1269–1283, 1990. doi:10.1214/aop/1176990746.DOI
  27. [31]Kurt Mehlhorn. Nearly optimal binary search trees. Acta Informatica, 5(4):287–295, December 1975. doi:10.1007/BF00264563.DOI
  28. [32]Mihai Putinar. Positive polynomials on compact semi-algebraic sets. Indiana University Mathematics Journal, 42:969–984, 1993. doi:10.1512/iumj.1993.42.42045.DOI
  29. [33]Evguenii A. Rakhmanov. Bounds for polynomials with a unit discrete norm. Annals of Mathematics, 165(1):55–88, 2007. doi:10.4007/annals.2007.165.55.DOI
  30. [34]Marcel Riesz. Sur le problème des moments. Troisième note. Arkiv för Matematik, Astronomi och Fysik, 17(16):1–52, 1923.
  31. [35]Theodore J. Rivlin. Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory. Wiley, New York, 2nd edition, 1990.
  32. [36]Herbert E. Scarf. A min-max solution of an inventory problem. In Kenneth J. Arrow, Samuel Karlin, and Herbert E. Scarf, editors, Studies in the Mathematical Theory of Inventory and Production, pages 201–209. Stanford University Press, Stanford, CA, 1958.
  33. [37]Konrad Schmüdgen. The Moment Problem, volume 277 of Graduate Texts in Mathematics. Springer International Publishing, Cham, 2017. doi:10.1007/978-3-319-64546-9.DOI
  34. [38]Lloyd N. Trefethen. Approximation Theory and Approximation Practice. Society for Industrial and Applied Mathematics, Philadelphia, PA, extended edition, 2019. doi: 10.1137/1.9781611975949.DOI
  35. [39]Shixin Wang, Shaoxuan Liu, and Jiawei Zhang. Minimax regret robust screening with moment information. Manuf. Serv. Oper. Manag., 26(3):992–1012, 2024. doi: 10.1287/MSOM.2023.0072.DOI
  36. [40]Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory, 62(6):3702–3720, 2016. doi:10.1109/TIT.2016.2548468.DOI
  37. [41]Yihong Wu and Pengkun Yang. Chebyshev polynomials, moment matching, and optimal estimation of the unseen. The Annals of Statistics, 47(2):857–883, 2019. doi:10.1214/17-AOS1665.DOI
  38. [42]Yihong Wu and Pengkun Yang. Optimal estimation of Gaussian mixtures via denoised method of moments. The Annals of Statistics, 48(4):1981–2007, 2020. doi:10.1214/19-AOS1873.DOI

Paper details

vlnc:W_scukacwt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 24

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Opus 5.5, Claude Fable 5.1 (bare), ChatGPT Astra

View statement
Looking for related papers…
Contents