Pith. sign in

REVIEW 4 minor 1 cited by

Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?

T0 review · 0 major / 4 minor · reviewed 2026-07-12 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper asks whether any non-adaptive 1-bit quantizers can match the adaptive order-optimal rate for nonparametric mean estimation under moment bounds.

desk verdict Clean COLT-style open problem that isolates the remaining non-adaptive gap for nonparametric 1-bit mean estimation; no new theorems, but well-posed and useful. read the letter →

arxiv 2607.02896 v1 pith:WH7THS2N submitted 2026-07-03 cs.IT cs.LGmath.ITmath.STstat.MLstat.TH

Ivan Lau , Jonathan Scarlett This is my paper · ORCID
classification cs.ITcs.LGmath.ITmath.STstat.MLstat.TH MSC 62G0568Q3294A29
keywords 1-bitmeanestimationcommunicationconstraintsadaptivitynon-interactiveprotocolsnonparametricfinite-momentclassesopenproblem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This open-problem paper asks whether interaction is truly required to achieve the best possible sample complexity for 1-bit mean estimation when the underlying distribution is known only through a bound on its k-th moment. Adaptive 1-bit protocols already match the unquantized minimax rate up to at most one unavoidable logarithmic factor, and the same rate is known to be achievable with only a single adaptive transition (two stages). Fully non-adaptive threshold and interval queries are known to be badly suboptimal, but the paper leaves open whether completely general non-adaptive 1-bit quantizers could still match the adaptive rate. A positive answer would give an optimal one-shot protocol that devices can run without feedback; a negative answer would prove that one adaptive transition is both necessary and sufficient. Either resolution would pin down the precise role of interaction in the nonparametric 1-bit setting.

What carries the argument

The adaptive rate r_k(λ,σ,ε,δ) itself, written explicitly as localization cost plus refinement cost; the open problem is whether this same expression remains attainable when every binary query set must be fixed before any bits are observed.

What would settle it

Either exhibit a fully non-adaptive family of measurable 1-bit queries whose sample complexity is at most a constant multiple of r_k for every λ≥σ and every sufficiently small ε, or prove a lower bound showing that every non-adaptive protocol requires asymptotically more samples than r_k on some sequence of instances in D(k,λ,σ).

Watch

Extended reading notes

Core claim

The paper formulates Open Problem 1: whether there exist constants depending only on the moment order k such that fully non-adaptive arbitrary 1-bit quantizers can achieve the known adaptive 1-bit minimax sample complexity r_k(λ,σ,ε,δ) for every distribution class D(k,λ,σ). That rate consists of a logarithmic localization term log(λ/σ) plus a refinement term that matches the classical unquantized rate (with an extra log(σ/ε) factor only when k=2).

Load-bearing premise

The entire problem rests on earlier claims that the stated adaptive rate is both achievable and minimax-optimal among all 1-bit protocols; if those rates are incomplete, the open question is ill-posed.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The manuscript poses a clean open problem in communication-constrained nonparametric statistics: whether fully non-adaptive arbitrary 1-bit quantizers can achieve the order-optimal adaptive 1-bit minimax rate for mean estimation over the finite-moment class D(k, λ, σ). It recalls that adaptive threshold queries attain the rate r_k(λ, σ, ε, δ) of equation (1), that the same rate is achievable with general 1-bit queries using only one adaptive transition (two stages), and that non-adaptive threshold and interval queries are known to be highly suboptimal. Open Problem 1 asks whether there exist constants c_k, C_k such that a fully non-adaptive protocol matches this rate for all λ ≥ σ > 0, sufficiently small ε, and δ ∈ (0, 1/2). The note carefully separates localization from refinement costs, surveys parametric positive results that do not extend, and discusses technical barriers (tail aliasing under moment assumptions, the insufficiency of locality-based packing arguments for general measurable quantizers).

Significance. If resolved either way, the problem would settle a genuine adaptivity gap for a fundamental primitive under the strictest communication constraint. A positive answer would yield an order-optimal one-shot protocol; a negative answer would certify that the known two-stage estimator is stage-optimal. The formulation is precise, the rate formula is stated explicitly, and the discussion of barriers (universal refinement without prior localization, simultaneous localization/refinement/tail control) is technically useful. As a COLT-style open-problem note it is well-scoped and does not overclaim; its value lies in isolating the zero-adaptivity, general-query regime that prior work leaves open.

minor comments (4)
  1. Section 3, Fourier-feature example: the O((σ/ε)^8 (log(λ/ε) + log(1/δ))) bound is useful for illustration, but a one-sentence remark on whether the exponent 8 is an artifact of the second-order bias analysis or inherent would help readers gauge how far the construction is from optimality.
  2. Equation (1) and Open Problem 1: the dependence of the constants c_k, C_k only on k is stated clearly; it would be slightly cleaner to note explicitly that they may also hide absolute numerical factors independent of all parameters.
  3. References: the concurrent works Lau & Scarlett (2026a,b) are cited as arXiv/AISTATS; once final versions or DOIs are available, updating the bibliography would improve long-term citability.
  4. Section 4, last paragraph: the phrase 'standard packing arguments are insufficient' is accurate; a brief pointer to why a mutual-information or Assouad-style argument would also need new ingredients (because a single query can touch many locations) would make the barrier discussion even sharper.

Circularity Check

1 steps flagged · score 1.0 of 10

No derivation circularity; only ordinary self-citation of the adaptive rate that defines the open problem.

  1. self citation load bearing [Section 2, Order-optimal rate paragraph and Open Problem 1; also Abstract and Section 3]
    "This rate is attainable by adaptive 1-bit protocols and is minimax optimal among 1-bit protocols (Lau and Scarlett, 2026b). ... Open Problem 1 ... using at most n ≤ C_k r_k(λ, σ, ε, δ) samples?"

    The target rate r_k that makes the open problem well-posed is justified solely by citation to the authors' own concurrent papers; no independent derivation or external verification appears in the present text. This is ordinary for an open-problem note and does not force any claimed result inside the manuscript, but it is the only self-referential step present.

full rationale

This is a COLT-style open-problem note, not a theorem paper that claims to derive a rate or prediction from first principles. The sole load-bearing external fact is the adaptive 1-bit minimax rate r_k (Eq. 1) and its attainability by adaptive/two-stage protocols, both imported from the authors' concurrent works (Lau & Scarlett 2026a,b). That dependence is transparent, standard for open-problem statements, and does not create an internal reduction: the manuscript never fits a parameter, reinterprets a fit as a prediction, smuggles an ansatz, renames a known result, or invokes a uniqueness theorem to force a conclusion. Open Problem 1 simply asks whether fully non-adaptive general quantizers can match the already-cited adaptive rate. No equation or claim inside the note is equivalent to its inputs by construction. Score 1 reflects only the minor, non-load-bearing self-citation that defines the target; the note itself is free of circular reasoning.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The note inherits the nonparametric moment class, the 1-bit protocol model, and the adaptive minimax rate from prior literature (chiefly the authors' own concurrent works). No free parameters are fitted, no new physical or mathematical entities are postulated, and the only axioms are standard measure-theoretic and statistical assumptions plus the domain definition of D(k,λ,σ).

assumptions (3)
  • domain assumption The nonparametric class D(k,λ,σ) of distributions with mean in [-λ,λ] and k-th central moment ≤ σ^k is the relevant model for 1-bit mean estimation.
    Defined in Section 2 and used throughout; standard in the nonparametric mean-estimation literature.
  • domain assumption The adaptive 1-bit minimax sample complexity is given (up to k-dependent constants) by the expression r_k(λ,σ,ε,δ) in equation (1).
    Stated as known from Lau & Scarlett 2026b; the open problem is defined relative to this rate.
  • standard math 1-bit messages are of the form Y_t = 1{X_t ∈ A_t} for measurable A_t ⊆ ℝ, chosen either adaptively or non-adaptively.
    Standard model of 1-bit quantization; Section 2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?." pith.science (2026). https://pith.science/paper/WH7THS2N

@misc{pith2026260702896,
  author       = {Pith},
  title        = {Pith review of: Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WH7THS2N}},
  note         = {Machine review of arXiv:2607.02896}
}
read the original abstract

We ask whether interaction is necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes. Adaptive threshold-query protocols achieve the order-optimal 1-bit minimax rate, and the same rate is attainable with general 1-bit queries using only one adaptive transition (i.e., two stages of querying). In the non-adaptive setting, threshold and interval queries are known to be highly suboptimal, but the case of arbitrary non-adaptive quantizers remains unresolved. Can such quantizers match the adaptive rate, yielding an optimal one-shot protocol? Or is the known two-stage estimator stage-optimal, with a single adaptive transition being necessary and sufficient?

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation

    stat.ML 2026-08 conditional novelty 7.0 of 10

    A fully non-adaptive one-bit protocol — every query fixed before data arrives — matches the minimax-optimal adaptive sample complexity for mean estimation under finite k-th moments, answering the COLT 2026 open proble...

Reference graph

Works this paper leans on

185 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

    arXiv preprint arXiv:2604.07796 , year=

    Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes , author=. arXiv preprint arXiv:2604.07796 , year=

    arXiv

  2. [2]

    International Conference on Artificial Intelligence and Statistics (AISTATS) , pages =

    Solving Multi-Arm Bandit Using a Few Bits of Communication , author =. International Conference on Artificial Intelligence and Statistics (AISTATS) , pages =

  3. [3]

    arXiv:2012.02876 , year =

    One-bit feedback is sufficient for upper confidence bound policies , author =. arXiv:2012.02876 , year =

    arXiv 2012

  4. [4]

    2018 , publisher =

    Reinforcement learning: An introduction , author =. 2018 , publisher =

    2018

  5. [5]

    , author =

    Advancements in Dueling Bandits. , author =. IJCAI , pages =

  6. [6]

    International Conference on Machine Learning (ICML) , pages =

    Versatile dueling bandits: Best-of-both world analyses for learning from relative preferences , author =. International Conference on Machine Learning (ICML) , pages =

  7. [7]

    International Conference on Machine Learning (ICML) , pages =

    Reducing dueling bandits to cardinal bandits , author =. International Conference on Machine Learning (ICML) , pages =

  8. [8]

    Journal of Machine Learning Research , volume =

    Preference-based online learning with dueling bandits: A survey , author =. Journal of Machine Learning Research , volume =

Show all 185 references
  1. [9]

    ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

    Noisy binary search and its applications , author =. ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

  2. [10]

    51st International Colloquium on Automata, Languages, and Programming (ICALP) , pages =

    Gretta, Lucas and Price, Eric , title =. 51st International Colloquium on Automata, Languages, and Programming (ICALP) , pages =. 2024 , volume =

    2024

  3. [11]

    Journal of Machine Learning Research , volume =

    Best arm identification for contaminated bandits , author =. Journal of Machine Learning Research , volume =

  4. [12]

    International Conference on Machine Learning (ICML) , pages =

    Quantile bandits for best arms identification , author =. International Conference on Machine Learning (ICML) , pages =

  5. [13]

    2022 , publisher =

    Howard, Steven R and Ramdas, Aaditya , journal =. 2022 , publisher =

    2022

  6. [14]

    Szorenyi, Balazs and Busa-Fekete, Robert and Weng, Paul and Hüllermeier, Eyke , booktitle =

  7. [15]

    IEEE Journal on Selected Areas in Information Theory , volume =

    Quantile multi-armed bandits: Optimal best-arm identification and a differentially private scheme , author =. IEEE Journal on Selected Areas in Information Theory , volume =. 2021 , publisher =

    2021

  8. [16]

    SIAM Journal on Control and Optimization , volume =

    Bisection search with noisy responses , author =. SIAM Journal on Control and Optimization , volume =. 2013 , publisher =

    2013

  9. [17]

    Yu, Jia Yuan and Nikolova, Evdokia , booktitle =

  10. [18]

    IEEE Journal on Selected Areas in Information Theory , volume =

    A unified approach to translate classical bandit algorithms to the structured bandit setting , author =. IEEE Journal on Selected Areas in Information Theory , volume =. 2020 , publisher =

    2020

  11. [19]

    Conference on Algorithmic Learning Theory (ALT) , year =

    Structured best arm identification with fixed confidence , author =. Conference on Algorithmic Learning Theory (ALT) , year =

  12. [20]

    Generalized

    Mukherjee, Subhojyoti and Tripathy, Ardhendu and Nowak, Robert , journal =. Generalized

  13. [21]

    Asilomar Conference on Signals, Systems, and Computers , year =

    Best Arm Identification under Additive Transfer Bandits , author =. Asilomar Conference on Signals, Systems, and Computers , year =

  14. [22]

    Tan, Vincent Y. F. and L.A., Prashanth and Jagannathan, Krishna , booktitle =. A Survey of Risk-Aware Multi-Armed Bandits , year =

  15. [23]

    Journal of Machine Learning Research , volume =

    The sample complexity of exploration in the multi-armed bandit problem , author =. Journal of Machine Learning Research , volume =

  16. [24]

    Robust Bandit Learning with Imperfect Context , author =

  17. [25]

    2020 , author =

    Bandit Algorithms , publisher =. 2020 , author =

    2020

  18. [26]

    INFORMS Journal on Computing , volume =

    Nonconvex robust optimization for problems with constraints , author =. INFORMS Journal on Computing , volume =

  19. [27]

    Robust submodular maximization: A non-uniform partitioning approach , booktitle =

    Bogunovic, Ilija and Mitrovi. Robust submodular maximization: A non-uniform partitioning approach , booktitle =

  20. [28]

    International Conference on Artificial Intelligence and Statistics (AISTATS) , year =

    The true sample complexity of identifying good arms , author =. International Conference on Artificial Intelligence and Statistics (AISTATS) , year =

  21. [29]

    Mathematical Programming , volume =

    Robust monotone submodular function maximization , author =. Mathematical Programming , volume =. 2018 , publisher =

    2018

  22. [30]

    , author =

    Robust Submodular Observation Selection. , author =. Journal of Machine Learning Research , volume =

  23. [31]

    2012 , pages =

    Gabillon and Victor and Ghavamzadeh and Mohammad and Lazaric, Alessandro , booktitle =. 2012 , pages =

    2012

  24. [32]

    International Conference on Machine Learning (ICML) , year =

    Multiple identifications in multi-armed bandits , author =. International Conference on Machine Learning (ICML) , year =

  25. [33]

    Categorized Bandits , year =

    Jedor, Matthieu and Perchet, Vianney and Louedec, Jonathan , booktitle =. Categorized Bandits , year =

  26. [34]

    Multi-armed bandits with dependent arms , author =

  27. [35]

    Local clustering in contextual multi-armed bandits , author =

  28. [36]

    Optimal exploitation of clustering and history information in multi-armed bandit , author =

  29. [37]

    2011 , booktitle =

    Deng, Kun and Pineau, Joelle and Murphy, Susan , title =. 2011 , booktitle =

    2011

  30. [38]

    Conference on Neural Information Processing Systems , title =

    Gabillon, Victor and Ghavamzadeh, Mohammad and Lazaric, Alessandro and Bubeck, S\'. Conference on Neural Information Processing Systems , title =

  31. [39]

    2012 , booktitle =

    Kalyanakrishnan, Shivaram and Tewari, Ambuj and Auer, Peter and Stone, Peter , title =. 2012 , booktitle =

    2012

  32. [40]

    Adversarially robust optimization with

    Bogunovic, Ilija and Scarlett, Jonathan and Jegelka, Stefanie and Cevher, Volkan , booktitle =. Adversarially robust optimization with

  33. [41]

    Robust optimization for non-convex objectives , author =

  34. [42]

    Journal of Machine Learning Research , volume =

    On the complexity of best-arm identification in multi-armed bandit models , author =. Journal of Machine Learning Research , volume =

  35. [43]

    Conference on Learning Theory (COLT) , year =

    Information Complexity in Bandit Subset Selection , author =. Conference on Learning Theory (COLT) , year =

  36. [44]

    IEEE International Symposium on Information Theory , year =

    Overlapping multi-bandit best arm identification , author =. IEEE International Symposium on Information Theory , year =

  37. [45]

    Kakade and Matthias W

    Niranjan Srinivas and Andreas Krause and Sham M. Kakade and Matthias W. Seeger , title =. CoRR , volume =. 2009 , note =

    2009

  38. [46]

    AAAI Conference on Artificial Intelligence , title =

    Wang, Zhenlin and Scarlett, Jonathan , year =. AAAI Conference on Artificial Intelligence , title =

  39. [47]

    2019 , volume =

    Foundations and Trends® in Machine Learning , title =. 2019 , volume =

    2019

  40. [48]

    Conference on Algorithmic Learning Theory , pages =

    Pure exploration in infinitely-armed bandit models with fixed-confidence , author =. Conference on Algorithmic Learning Theory , pages =

  41. [49]

    2022 , title =

    Kevin Jamieson , key =. 2022 , title =

    2022

  42. [50]

    Journal of the ACM (JACM) , volume =

    Bandits and experts in metric spaces , author =. Journal of the ACM (JACM) , volume =. 2019 , publisher =

    2019

  43. [51]

    ACM Symposium on Theory of Computing , year =

    Multi-armed bandits in metric spaces , author =. ACM Symposium on Theory of Computing , year =

  44. [52]

    Online optimization in

    Bubeck, S. Online optimization in. Conference on Neural Information Processing Systems , year =

  45. [53]

    , author =

    X-Armed Bandits. , author =. Journal of Machine Learning Research , volume =

  46. [54]

    Conference on Neural Information Processing Systems , volume =

    Grill, Jean-Bastien and Valko, Michal and Munos, Remi and Munos, Remi , title =. Conference on Neural Information Processing Systems , volume =

  47. [55]

    The Annals of Statistics , volume =

    Bandit problems with infinitely many arms , author =. The Annals of Statistics , volume =. 1997 , publisher =

    1997

  48. [56]

    Conference on Neural Information Processing Systems , year =

    Algorithms for infinitely many-armed bandits , author =. Conference on Neural Information Processing Systems , year =

  49. [57]

    2013 , booktitle =

    Thomas Bonald and Alexandre Proutière , title =. 2013 , booktitle =

    2013

  50. [58]

    European Conference on Machine Learning and Knowledge Discovery in Databases , year =

    Infinitely many-armed bandits with unknown value distribution , author =. European Conference on Machine Learning and Knowledge Discovery in Databases , year =

  51. [59]

    International Conference on Machine Learning (ICML) , year =

    Simple regret for infinitely many armed bandits , author =. International Conference on Machine Learning (ICML) , year =

  52. [60]

    arXiv preprint arXiv:2110.12118 , year =

    Bandits with Dynamic Arm-acquisition Costs , author =. arXiv preprint arXiv:2110.12118 , year =

    arXiv

  53. [61]

    ACM SIGMETRICS Performance Evaluation Review , year =

    Dynamic Learning in Large Matching Markets , author =. ACM SIGMETRICS Performance Evaluation Review , year =

  54. [62]

    , author =

    Quantile-Regret Minimisation in Infinitely Many-Armed Bandits. , author =. Conference on Uncertainty in Artificial Intelligence , year =

  55. [63]

    Conference on Neural Information Processing Systems , year =

    The power of adaptivity in identifying statistical alternatives , author =. Conference on Neural Information Processing Systems , year =

  56. [64]

    Conference on Artificial intelligence and statistics (AISTATS) , year =

    Exploring k out of Top Fraction of Arms in Stochastic Bandits , author =. Conference on Artificial intelligence and statistics (AISTATS) , year =

  57. [65]

    Chaudhuri, Arghya Roy and Kalyanakrishnan, Shivaram , booktitle =

  58. [66]

    AAAI Conference on Artificial Intelligence , year =

    Infinitely many-armed bandits with budget constraints , author =. AAAI Conference on Artificial Intelligence , year =

  59. [67]

    Mayekar, Prathamesh and Scarlett, Jonathan and Tan, Vincent YF , booktitle =

  60. [68]

    Learning for Dynamics and Control Conference (L4DC) , pages =

    Linear stochastic bandits over a bit-constrained channel , author =. Learning for Dynamics and Control Conference (L4DC) , pages =

  61. [69]

    McGill University Report , year =

    Distribution and quantile functions , author =. McGill University Report , year =

  62. [70]

    Biometrika , volume =

    On the likelihood that one unknown probability exceeds another in view of the evidence of two samples , author =. Biometrika , volume =. 1933 , publisher =

    1933

  63. [71]

    Bulletin of the American Mathematical Society , year =

    Some aspects of the sequential design of experiments , author =. Bulletin of the American Mathematical Society , year =

  64. [72]

    2002 , booktitle =

    Even-Dar, Eyal and Mannor, Shie and Mansour, Yishay , title =. 2002 , booktitle =

    2002

  65. [73]

    Asian Conference on Machine Learning , pages =

    Torossian, L. Asian Conference on Machine Learning , pages =

  66. [74]

    Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML-PKDD) , pages =

    Pure exploration for max-quantile bandits , author =. Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML-PKDD) , pages =. 2016 , organization =

    2016

  67. [75]

    International Conference on Machine Learning (ICML) , pages =

    Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost , author =. International Conference on Machine Learning (ICML) , pages =. 2023 , volume =

    2023

  68. [76]

    International Conference on Machine Learning (ICML) , pages =

    Distributed Linear Bandits under Communication Constraints , author =. International Conference on Machine Learning (ICML) , pages =

  69. [77]

    International Conference on Machine Learning , pages =

    Correlated quantization for distributed mean estimation and optimization , author =. International Conference on Machine Learning , pages =. 2022 , organization =

    2022

  70. [78]

    2013 , month =

    Boucheron, Stéphane and Lugosi, Gábor and Massart, Pascal , title =. 2013 , month =

    2013

  71. [79]

    G. Sub-. The Annals of Statistics , number =

  72. [80]

    Distance between mean and median , year =

    Arash (https://math.stackexchange.com/users/92185/arash) , note =. Distance between mean and median , year =

  73. [81]

    Optimal Sub-

    Lee, Jasper CH and Valiant, Paul , booktitle =. Optimal Sub-. 2022 , organization =

    2022

  74. [82]

    Conference on Learning Theory (COLT) , pages =

    Efficient median of means estimator , author =. Conference on Learning Theory (COLT) , pages =. 2023 , organization =

    2023

  75. [83]

    Conference on Learning Theory , pages =

    Optimal mean estimation without a variance , author =. Conference on Learning Theory , pages =. 2022 , organization =

    2022

  76. [84]

    U-statistics of growing order and sub-

    Minsker, Stanislav , journal =. U-statistics of growing order and sub-

  77. [85]

    Conference on Learning Theory (COLT) , pages =

    Beyond catoni: Sharper rates for heavy-tailed and robust mean estimation , author =. Conference on Learning Theory (COLT) , pages =. 2024 , organization =

    2024

  78. [86]

    Optimality in mean estimation: Beyond worst-case, beyond sub-

    Dang, Trung and Lee, Jasper and Song, Maoyuan'Raymond' and Valiant, Paul , booktitle =. Optimality in mean estimation: Beyond worst-case, beyond sub-

  79. [87]

    All-purpose mean estimation over R: Optimal sub-

    Lee, Jasper CH and McKelvie, Walter and Song, Maoyuan and Valiant, Paul , booktitle =. All-purpose mean estimation over R: Optimal sub-

  80. [88]

    International Conference on Machine Learning (ICML) , pages =

    Accelerating Federated Learning with Quick Distributed Mean Estimation , author =. International Conference on Machine Learning (ICML) , pages =. 2024 , volume =

    2024

  81. [89]

    International Conference on Machine Learning (ICML) , pages =

    Distributed mean estimation with limited communication , author =. International Conference on Machine Learning (ICML) , pages =. 2017 , organization =

    2017

  82. [90]

    communication , author =

    Randomized distributed mean estimation: Accuracy vs. communication , author =. Frontiers in Applied Mathematics and Statistics , volume =. 2018 , publisher =

    2018

  83. [91]

    Advances in Neural Information Processing Systems , volume =

    Drive: One-bit distributed mean estimation , author =. Advances in Neural Information Processing Systems , volume =

  84. [92]

    2022 , volume =

    Vargaftik, Shay and Basat, Ran Ben and Portnoy, Amit and Mendelson, Gal and Itzhak, Yaniv Ben and Mitzenmacher, Michael , booktitle =. 2022 , volume =

    2022

  85. [93]

    International Conference on Learning Representations, (ICLR) , year =

    Peter Davies and Vijaykrishna Gurunanthan and Niusha Moshrefi and Saleh Ashkboos and Dan Alistarh , title =. International Conference on Learning Representations, (ICLR) , year =

  86. [94]

    International Conference on Artificial Intelligence and Statistics (AISTATS) , pages =

    Unbiased Quantization of the L_1 Ball for Communication-Efficient Distributed Mean Estimation , author =. International Conference on Artificial Intelligence and Statistics (AISTATS) , pages =. 2025 , volume =

    2025

  87. [95]

    IEEE Transactions on Information Theory , volume =

    Interactive inference under information constraints , author =. IEEE Transactions on Information Theory , volume =. 2021 , publisher =

    2021

  88. [96]

    Nguyen , booktitle =

    Ankit Garg and Tengyu Ma and Huy L. Nguyen , booktitle =. On Communication Cost of Distributed Statistical Estimation and Dimensionality , year =

  89. [97]

    Nguyen and David P

    Mark Braverman and Ankit Garg and Tengyu Ma and Huy L. Nguyen and David P. Woodruff , booktitle =. Communication lower bounds for statistical estimation problems via a distributed data processing inequality , year =

  90. [98]

    Fundamental limits of online and distributed algorithms for statistical learning and estimation , year =

    Shamir, Ohad , booktitle =. Fundamental limits of online and distributed algorithms for statistical learning and estimation , year =

  91. [99]

    Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints , volume =

    Yanjun Han and Ayfer. Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints , volume =. Conference on Learning Theory (COLT) , pages =

  92. [100]

    Distributed Statistical Estimation of High-Dimensional and Non-parametric Distributions , year =

    Yanjun Han and Pritam Mukherjee and Ayfer. Distributed Statistical Estimation of High-Dimensional and Non-parametric Distributions , year =. IEEE International Symposium on Information Theory (ISIT) , pages =

  93. [101]

    Barnes and Yanjun Han and Ayfer

    Leighton P. Barnes and Yanjun Han and Ayfer. IEEE International Symposium on Information Theory (ISIT) , pages =

  94. [102]

    IEEE Journal on Selected Areas in Information Theory , number =

    Leighton Pate Barnes and Wei. IEEE Journal on Selected Areas in Information Theory , number =

  95. [103]

    On Learning Parametric Distributions from Quantized Samples , year =

    Septimia Sarbu and Abdellatif Zaidi , booktitle =. On Learning Parametric Distributions from Quantized Samples , year =

  96. [104]

    Inference under information constraints

    Acharya, Jayadev and Canonne, Cl\'. Inference under information constraints. IEEE Transactions on Information Theory , number =

  97. [105]

    Inference Under Information Constraints

    Jayadev Acharya and Cl. Inference Under Information Constraints. IEEE Transactions on Information Theory , volume =

  98. [106]

    Inference Under Information Constraints

    Jayadev Acharya and Cl. Inference Under Information Constraints. IEEE Journal on Selected Areas in Information Theory , number =

  99. [107]

    Advances in Neural Information Processing Systems , volume =

    Unified lower bounds for interactive high-dimensional estimation under information constraints , author =. Advances in Neural Information Processing Systems , volume =

  100. [108]

    Distributed Signal Detection under Communication Constraints , booktitle =

    Jayadev Acharya and Cl. Distributed Signal Detection under Communication Constraints , booktitle =

  101. [109]

    and Wainwright, Martin J

    Zhang, Yuchen and Duchi, John and Jordan, Michael I. and Wainwright, Martin J. , booktitle =. Information-theoretic lower bounds for distributed statistical estimation with communication constraints , year =

  102. [110]

    Xu, Aolin and Raginsky, Maxim , journal =

  103. [111]

    , journal =

    Wainwright, Martin J. , journal =. Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting , volume =. 2009 , doi =

    2009

  104. [112]

    2020 , url =

    Wu, Yihong , title =. 2020 , url =

    2020

  105. [113]

    Information Theory: From Coding to Learning , publisher =

    Polyanskiy, Yury and Wu, Yihong , year =. Information Theory: From Coding to Learning , publisher =

  106. [114]

    Lower bounds for learning distributions under communication constraints via

    Barnes, Leighton Pate and Han, Yanjun and \". Lower bounds for learning distributions under communication constraints via. Journal of Machine Learning Research , pages =. 2020 , issn =

    2020

  107. [115]

    Private Identity Testing for High-Dimensional Distributions , year =

    Cl. Private Identity Testing for High-Dimensional Distributions , year =. Advances in Neural Information Processing Systems 33 , note =

  108. [116]

    NeurIPS , year =

    Thomas Berrett and Cristina Butucea , title =. NeurIPS , year =

  109. [117]

    Kane and Sankeerth Rao , title =

    Ilias Diakonikolas and Themis Gouleakis and Daniel M. Kane and Sankeerth Rao , title =. Conference on Learning Theory (COLT) , volume =

  110. [118]

    Information-constrained optimization: can adaptive processing of gradients help? , journal =

    Jayadev Acharya and Cl. Information-constrained optimization: can adaptive processing of gradients help? , journal =

  111. [119]

    Bernoulli , fjournal =

    Butucea, Cristina and Dubois, Amandine and Kroll, Martin and Saumard, Adrien , title =. Bernoulli , fjournal =. 2020 , number =. doi:10.3150/19-BEJ1165 , url =

    2020 doi

  112. [120]

    Optimal Rates for Nonparametric Density Estimation under Communication Constraints , journal =

    Jayadev Acharya and Cl. Optimal Rates for Nonparametric Density Estimation under Communication Constraints , journal =

  113. [121]

    Local Differential Privacy Is Equivalent to Contraction of E_ -Divergence , journal =

    Shahab Asoodeh and Maryam Aliakbarpour and Fl. Local Differential Privacy Is Equivalent to Contraction of E_ -Divergence , journal =

  114. [122]

    Berger, Toby and Zhang, Zhen and Viswanathan, Harish , journal =. The. 1996 , publisher =

    1996

  115. [123]

    Advances in Statistical Signal Processing , volume =

    Decentralized detection , author =. Advances in Statistical Signal Processing , volume =. 1993 , pages =

    1993

  116. [124]

    2012 , publisher =

    Distributed detection and data fusion , author =. 2012 , publisher =

    2012

  117. [125]

    Advanced topics , author =

    Distributed detection with multiple sensors II. Advanced topics , author =. Proceedings of the IEEE , volume =. 2002 , publisher =

    2002

  118. [126]

    Fundamentals , author =

    Distributed detection with multiple sensors Part I. Fundamentals , author =. Proceedings of the IEEE , volume =. 2002 , publisher =

    2002

  119. [127]

    Information Fusion , volume =

    Distributed estimation over a low-cost sensor network: A review of state-of-the-art , author =. Information Fusion , volume =. 2020 , publisher =

    2020

  120. [128]

    IEEE Transactions on Signal Processing , volume =

    Universal decentralized detection in a bandwidth-constrained sensor network , author =. IEEE Transactions on Signal Processing , volume =. 2005 , publisher =

    2005

  121. [129]

    IEEE Transactions on Information Theory , volume =

    Universal decentralized estimation in a bandwidth constrained sensor network , author =. IEEE Transactions on Information Theory , volume =. 2005 , publisher =

    2005

  122. [130]

    , journal =

    Te Sun Han and Amari, S. , journal =. Statistical inference under multiterminal data compression , year =

  123. [131]

    IEEE Transactions on Aerospace and Electronic systems , volume =

    Detection with distributed sensors , author =. IEEE Transactions on Aerospace and Electronic systems , volume =. 1981 , publisher =

    1981

  124. [132]

    Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume =

    Distributed inference in wireless sensor networks , author =. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume =. 2012 , publisher =

    2012

  125. [133]

    IEEE signal processing magazine , volume =

    Distributed learning in wireless sensor networks , author =. IEEE signal processing magazine , volume =. 2006 , publisher =

    2006

  126. [134]

    International Conference on Artificial Intelligence and Statistics , pages =

    Discrete distribution estimation under user-level local differential privacy , author =. International Conference on Artificial Intelligence and Statistics , pages =. 2023 , organization =

    2023

  127. [135]

    2022 , school =

    Statistical Inference Under Information Constraints , author =. 2022 , school =

    2022

  128. [136]

    2025 , school =

    Distributed Hypothesis Testing under Privacy and Bandwidth Constraints , author =. 2025 , school =

    2025

  129. [137]

    2024 , school =

    Learning With Classical and Quantum Information Constraints , author =. 2024 , school =

    2024

  130. [138]

    IEEE Transactions on Information Forensics and Security , volume =

    Optimal private discrete distribution estimation with 1-bit communication , author =. IEEE Transactions on Information Forensics and Security , volume =. 2024 , publisher =

    2024

  131. [139]

    Advances in Neural Information Processing Systems , volume =

    Pointwise bounds for distribution estimation under communication constraints , author =. Advances in Neural Information Processing Systems , volume =

  132. [140]

    Advances in Neural Information Processing Systems , volume =

    Distributed estimation with multiple samples per user: Sharp rates and phase transition , author =. Advances in Neural Information Processing Systems , volume =

  133. [141]

    Algorithmic Learning Theory (ALT) , pages =

    Estimating sparse discrete distributions under privacy and communication constraints , author =. Algorithmic Learning Theory (ALT) , pages =. 2021 , organization =

    2021

  134. [142]

    IEEE Signal Processing Magazine , volume =

    Distributed compression-estimation using wireless sensor networks , author =. IEEE Signal Processing Magazine , volume =. 2006 , publisher =

    2006

  135. [143]

    Bandwidth-constrained distributed estimation for wireless sensor networks-part II:

    Ribeiro, Alejandro and Giannakis, Georgios B , journal =. Bandwidth-constrained distributed estimation for wireless sensor networks-part II:. 2006 , publisher =

    2006

  136. [144]

    Bandwidth-constrained distributed estimation for wireless sensor networks-part I:

    Ribeiro, Alejandro and Giannakis, Georgios B , journal =. Bandwidth-constrained distributed estimation for wireless sensor networks-part I:. 2006 , publisher =

    2006

  137. [145]

    Distributed

    Cai, T Tony and Wei, Hongji , journal =. Distributed

  138. [146]

    Transactions on Machine Learning Research , year=

    One-Bit Distributed Mean Estimation with Unknown Variance , author=. Transactions on Machine Learning Research , year=

  139. [147]

    IEEE Transactions on Information Theory , volume =

    Mean estimation from one-bit measurements , author =. IEEE Transactions on Information Theory , volume =. 2022 , publisher =

    2022

  140. [148]

    Distributed adaptive

    Cai, T Tony and Wei, Hongji , journal =. Distributed adaptive. 2022 , publisher =

    2022

  141. [149]

    International Conference on Machine Learning (ICML) , pages =

    Distributed nonparametric regression under communication constraints , author =. International Conference on Machine Learning (ICML) , pages =. 2018 , organization =

    2018

  142. [150]

    The Annals of Statistics , volume =

    Distributed nonparametric function estimation: Optimal rate of convergence and cost of adaptation , author =. The Annals of Statistics , volume =. 2022 , publisher =

    2022

  143. [151]

    The Annals of Statistics , year =

    Adaptive distributed methods under communication constraints , author =. The Annals of Statistics , year =

  144. [152]

    Mathematical Statistics and Learning , year =

    Distributed function estimation: Adaptation using minimal communication , author =. Mathematical Statistics and Learning , year =

  145. [153]

    The Annals of Statistics , number =

    Szab. The Annals of Statistics , number =. 2023 , doi =

    2023

  146. [154]

    IEEE Transactions on Information Theory , year =

    Simple binary hypothesis testing under local differential privacy and communication constraints , author =. IEEE Transactions on Information Theory , year =

  147. [155]

    IEEE Transactions on Information Theory , volume =

    Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities , author =. IEEE Transactions on Information Theory , volume =. 2023 , publisher =

    2023

  148. [156]

    Optimal distributed composite testing in high-dimensional

    Szab. Optimal distributed composite testing in high-dimensional. IEEE Transactions on Information Theory , volume =. 2022 , publisher =

    2022

  149. [157]

    arXiv preprint arXiv:2204.10373 , year =

    Distributed nonparametric estimation under communication constraints , author =. arXiv preprint arXiv:2204.10373 , year =

    arXiv

  150. [158]

    International Conference on Artificial Intelligence and Statistics (AISTATS) , pages =

    Wyner-Ziv estimators: Efficient distributed mean estimation with side-information , author =. International Conference on Artificial Intelligence and Statistics (AISTATS) , pages =. 2021 , organization =

    2021

  151. [159]

    Algorithmic Learning Theory , pages =

    Quantile Multi-Armed Bandits with 1-bit Feedback , author =. Algorithmic Learning Theory , pages =. 2025 , organization =

    2025

  152. [160]

    International Conference on Acoustics, Speech and Signal Processing (ICASSP) , year =

    Generalized Linear Models with 1-Bit Measurements: Asymptotics of the Maximum Likelihood Estimator , author =. International Conference on Acoustics, Speech and Signal Processing (ICASSP) , year =

  153. [161]

    High-Dimensional Probability: An Introduction with Applications in Data Science , publisher =

    Vershynin, Roman , year =. High-Dimensional Probability: An Introduction with Applications in Data Science , publisher =

  154. [162]

    arXiv preprint arXiv:1908.10761 , year =

    A short note on the median-of-means estimator , author =. arXiv preprint arXiv:1908.10761 , year =

    1908 arXiv

  155. [163]

    International Conference on Artificial Intelligence and Statistics (AISTATS) , year =

    Sequential 1-bit mean estimation with near-optimal sample complexity , author =. International Conference on Artificial Intelligence and Statistics (AISTATS) , year =

  156. [164]

    2013 , publisher =

    Probability and Statistics: Pearson New International Edition , author =. 2013 , publisher =

    2013

  157. [165]

    Oliveira , title =

    Luc Devroye and Matthieu Lerasle and Gabor Lugosi and Roberto I. Oliveira , title =. The Annals of Statistics , number =

  158. [166]

    arXiv preprint arXiv:2601.07074 , year =

    Robust Mean Estimation under Quantization , author =. arXiv preprint arXiv:2601.07074 , year =

  159. [167]

    2003 , organization=

    Kleinberg, Robert and Leighton, Tom , booktitle=. 2003 , organization=

    2003

  160. [168]

    ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Pricing query complexity of revenue maximization , author=. ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  161. [169]

    Foundations of Computational Mathematics , volume=

    Mean estimation and regression under heavy-tailed distributions: A survey , author=. Foundations of Computational Mathematics , volume=. 2019 , publisher=

    2019

  162. [170]

    IEEE Transactions on Information Theory , volume=

    Bandits with heavy tail , author=. IEEE Transactions on Information Theory , volume=. 2013 , publisher=

    2013

  163. [171]

    , Publisher =

    Tsybakov, Alexandre B. , Publisher =. Introduction to Nonparametric Estimation , Year =

  164. [172]

    The Annals of Statistics , volume=

    Time-uniform, nonparametric, nonasymptotic confidence sequences , author=. The Annals of Statistics , volume=

  165. [173]

    Conference on Learning Theory , pages=

    lil’ucb: An optimal exploration algorithm for multi-armed bandits , author=. Conference on Learning Theory , pages=. 2014 , organization=

    2014

  166. [174]

    Proceedings of the National Academy of Sciences , volume=

    Confidence sequences for mean, variance, and median , author=. Proceedings of the National Academy of Sciences , volume=

  167. [175]

    The Thirty Seventh Annual Conference on Learning Theory , pages=

    An information-theoretic lower bound in time-uniform estimation , author=. The Thirty Seventh Annual Conference on Learning Theory , pages=. 2024 , organization=

    2024

  168. [176]

    The Annals of Mathematical Statistics , pages=

    Inequalities for the r th absolute moment of a sum of random variables, 1 r 2 , author=. The Annals of Mathematical Statistics , pages=

  169. [177]

    Israel Journal of Mathematics , volume=

    On the subspaces of L^p (p > 2) spanned by sequences of independent random variables , author=. Israel Journal of Mathematics , volume=. 1970 , publisher=

    1970

  170. [178]

    Proceedings of Thirty Sixth Conference on Learning Theory , pages =

    Finite-Sample Symmetric Mean Estimation with Fisher Information Rate , author =. Proceedings of Thirty Sixth Conference on Learning Theory , pages =. 2023 , editor =

    2023

  171. [179]

    The Annals of Statistics , volume=

    Mean estimation with sub-Gaussian rates in polynomial time , author=. The Annals of Statistics , volume=. 2020 , publisher=

    2020

  172. [180]

    Conference on Learning Theory , pages=

    The role of interactivity in structured estimation , author=. Conference on Learning Theory , pages=. 2022 , organization=

    2022

  173. [181]

    Conference on Learning Theory , pages=

    Sample-optimal locally private hypothesis selection and the provable benefits of interactivity , author=. Conference on Learning Theory , pages=. 2024 , organization=

    2024

  174. [182]

    Conference on Learning Theory , pages=

    The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints , author=. Conference on Learning Theory , pages=. 2025 , organization=

    2025

  175. [183]

    ACM SIGACT Symposium on Theory of Computing , pages=

    Interaction is necessary for distributed learning with privacy or communication constraints , author=. ACM SIGACT Symposium on Theory of Computing , pages=

  176. [184]

    Conference on Learning Theory , pages=

    Locally private hypothesis selection , author=. Conference on Learning Theory , pages=. 2020 , organization=

    2020

  177. [185]

    Conference on Learning Theory , pages=

    Lower bounds for locally private estimation via communication complexity , author=. Conference on Learning Theory , pages=. 2019 , organization=

    2019

Pith tools

Reviewed July 12, 2026 · model on record in the stance chip above.