pith. sign in

arxiv: 1907.05816 · v1 · pith:N3GOQMVWnew · submitted 2019-07-12 · 💻 cs.DS

Towards Optimal Moment Estimation in Streaming and Distributed Models

Rajesh Jayaram , David P. Woodruff This is my paper

Pith reviewed 2026-05-24 22:13 UTC · model grok-4.3

classification 💻 cs.DS
keywords moment estimationdata streamsp-normsstreaming algorithmsdistributed computationcommunication complexityrandomized roundingempirical entropy
0
0 comments X

The pith

For p in (0,1], the p-moment can be estimated to (1+ε) using Õ(ε^{-2} + log n) bits on any worst-case stream of positive updates.

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

The paper closes the space gap for p-moment estimation when all updates are non-negative. For p at most 1 it removes the random-order requirement and achieves Õ(ε^{-2} + log n) bits on adversarial streams, matching the known lower bound up to logarithmic factors. For p between 1 and 2 it supplies Õ(ε^{-2})-bit communication protocols in the coordinator and blackboard models via randomized rounding, plus a diameter-dependent bound for general networks. The same techniques yield new streaming bounds for empirical entropy.

Core claim

For p ∈ (0,1] we give a streaming algorithm that estimates ||X||_p^p to (1+ε) accuracy using Õ(ε^{-2} + log n) bits on worst-case streams of non-negative updates. In coordinator and blackboard topologies for p ∈ (1,2] a randomized-rounding protocol uses Õ(ε^{-2}) bits of max-communication; the bound generalizes to Õ(ε^{-2} log d) bits on any communication graph of diameter d. These protocols also solve heavy hitters and approximate matrix product.

What carries the argument

A worst-case streaming algorithm for small p that avoids the random-order assumption, together with a randomized rounding scheme that produces the communication bounds for larger p.

If this is right

  • New upper bounds hold for estimating empirical entropy in a stream.
  • The same protocols give communication-efficient solutions for heavy hitters and approximate matrix product.
  • Natural communication-complexity reductions cannot prove an Ω(ε^{-2} log n) streaming lower bound for p in (1,2]; any such lower bound must exploit large-diameter topologies.
  • The Õ(ε^{-2} log d) bound applies to arbitrary communication graphs of diameter d.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Techniques that succeed without random order for p ≤ 1 may extend to other streaming statistics previously analyzed only under random-order assumptions.
  • The separation between p ≤ 1 and p > 1 suggests that the ordering hardness is concentrated in the regime where moments behave more like norms.
  • Diameter dependence implies that network topology itself can be a resource for reducing communication in distributed moment estimation.

Load-bearing premise

All updates are non-negative and the algorithm is allowed to be randomized.

What would settle it

An explicit worst-case stream of positive updates on which every algorithm estimating ||X||_p^p for some p ≤ 1 either exceeds Õ(ε^{-2} + log n) bits or fails to return a (1+ε) approximation.

Figures

Figures reproduced from arXiv: 1907.05816 by David P. Woodruff, Rajesh Jayaram.

Figure 1
Figure 1. Figure 1: For the communication problems above, the bounds a [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Recursive Randomized Rounding For each player i in layer 0, they take their input Xi , and compute hZ, Xii. They then round their values as ri = Γ(hZ, Xii), where the randomness used for the rounding function Γ is drawn independently for each call to Γ. Then player i sends ri to their parent in T. In general, consider any player i at depth j > 0 of T. At the end of the j-th round, player i will receive a r… view at source ↗
Figure 3
Figure 3. Figure 3: Multi-party Fp estimation protocol, p < 1 We now provide our algorithm for Fp estimation in the message passing model with p ≤ 1. Our protocol is similar to our algorithm for p ≥ 1. We fix a vertex C which is a center of the 21 [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Entropy Estimation algorithm of [CC13] The algorithm of [CC13] is given formally in [PITH_FULL_IMAGE:figures/full_fig_p027_4.png] view at source ↗
read the original abstract

One of the oldest problems in the data stream model is to approximate the $p$-th moment $\|\mathcal{X}\|_p^p = \sum_{i=1}^n |\mathcal{X}_i|^p$ of an underlying vector $\mathcal{X} \in \mathbb{R}^n$, which is presented as a sequence of poly$(n)$ updates to its coordinates. Of particular interest is when $p \in (0,2]$. Although a tight space bound of $\Theta(\epsilon^{-2} \log n)$ bits is known for this problem when both positive and negative updates are allowed, surprisingly there is still a gap in the space complexity when all updates are positive. Specifically, the upper bound is $O(\epsilon^{-2} \log n)$ bits, while the lower bound is only $\Omega(\epsilon^{-2} + \log n)$ bits. Recently, an upper bound of $\tilde{O}(\epsilon^{-2} + \log n)$ bits was obtained assuming that the updates arrive in a random order. We show that for $p \in (0, 1]$, the random order assumption is not needed. Namely, we give an upper bound for worst-case streams of $\tilde{O}(\epsilon^{-2} + \log n)$ bits for estimating $\|\mathcal{X}\|_p^p$. Our techniques also give new upper bounds for estimating the empirical entropy in a stream. On the other hand, we show that for $p \in (1,2]$, in the natural coordinator and blackboard communication topologies, there is an $\tilde{O}(\epsilon^{-2})$ bit max-communication upper bound based on a randomized rounding scheme. Our protocols also give rise to protocols for heavy hitters and approximate matrix product. We generalize our results to arbitrary communication topologies $G$, obtaining an $\tilde{O}(\epsilon^{2} \log d)$ max-communication upper bound, where $d$ is the diameter of $G$. Interestingly, our upper bound rules out natural communication complexity-based approaches for proving an $\Omega(\epsilon^{-2} \log n)$ bit lower bound for $p \in (1,2]$ for streaming algorithms. In particular, any such lower bound must come from a topology with large diameter.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript presents algorithmic results for approximating the p-th moment of a vector in streaming and distributed settings. For p ∈ (0,1], it claims an Õ(ε^{-2} + log n) bit space upper bound for worst-case positive streams, removing the need for random order. It also gives bounds for empirical entropy. For p ∈ (1,2], it provides Õ(ε^{-2}) max-communication upper bounds in coordinator and blackboard models using randomized rounding, generalizing to Õ(ε^{-2} log d) for graphs with diameter d, with applications to heavy hitters and matrix product approximation.

Significance. These results are significant because they nearly close the gap for the streaming moment estimation problem for small p and provide efficient distributed protocols. The explicit constructions and the implication ruling out certain lower bound techniques based on communication complexity are valuable contributions. The paper credits the randomized rounding technique explicitly.

major comments (1)
  1. [distributed models section] The randomized rounding scheme for p ∈ (1,2] in the coordinator/blackboard models is load-bearing for the Õ(ε^{-2}) max-communication claim; the error analysis must confirm that the rounding does not introduce n-dependent factors that would violate the bound (see abstract and the distributed-model section).
minor comments (2)
  1. [Introduction] The introduction could include a table comparing the new bounds to prior work for p ≤ 1 and p ∈ (1,2] to clarify the contribution.
  2. [Abstract and Section 1] Expand the definition of the tilde notation in the main text to explicitly list the hidden logarithmic factors in the space and communication bounds.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, positive assessment of the results, and recommendation for minor revision. We address the single major comment below.

read point-by-point responses

  1. Referee: [distributed models section] The randomized rounding scheme for p ∈ (1,2] in the coordinator/blackboard models is load-bearing for the Õ(ε^{-2}) max-communication claim; the error analysis must confirm that the rounding does not introduce n-dependent factors that would violate the bound (see abstract and the distributed-model section).

    Authors: We appreciate the referee drawing attention to this aspect of the analysis. The error analysis for the randomized rounding scheme (detailed in the proof of the main theorem in the distributed-model section) already confirms that no n-dependent factors are introduced into the Õ(ε^{-2}) max-communication bound. Each update is rounded independently with probability proportional to its contribution to the current p-moment estimate; the resulting bias and variance are bounded using the p-norm properties for p ∈ (1,2], yielding an additive error of O(ε ||X||_p^p) that holds with high probability and depends only on ε and the moment value itself. The total communication therefore remains Õ(ε^{-2}) bits in both the coordinator and blackboard models, as claimed in the abstract. The current write-up already contains the necessary bounds; we do not believe a change is required. revision: no

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper establishes upper bounds via explicit algorithmic constructions and protocols for p-moment estimation on worst-case streams (p in (0,1]) and distributed models. These rest on randomized rounding schemes, communication topologies, and new techniques rather than self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations. The abstract and claims describe independent results with no equations or steps that reduce by construction to the paper's own inputs or prior self-citations. This matches the default case of a self-contained theoretical construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard properties of p-norms and communication complexity but introduces no new free parameters, axioms beyond standard math, or invented entities.

axioms (1)
  • standard math Standard properties of the p-norm and the data-stream update model with non-negative updates
    Invoked throughout the abstract when stating the moment estimation problem and the positive-update restriction.

pith-pipeline@v0.9.0 · 5951 in / 1416 out tokens · 19266 ms · 2026-05-24T22:13:38.952667+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages · 7 internal anchors

  1. [1]

    Streaming Algorithms from Precision Sampling

    [AKO10] Alexandr Andoni, Robert Krauthgamer, and Krzyszto f Onak. Streaming algorithms from precision sampling. arXiv preprint arXiv:1011.1263 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  2. [2]

    BPTree: an $\ell_2$ heavy hitters algorithm using constant memory

    [BCI+16] Vladimir Braverman, Stephen R Chestnut, Nikita Ivkin, J elani Nelson, Zhengyu Wang, and David P Woodruff. Bptree: an l2 heavy hitters algorithm usi ng constant memory. arXiv preprint arXiv:1603.00759 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  3. [3]

    Continuous monitoring of $\ell_p$ norms in data streams

    [BDN17] Jaros/suppress law B/suppress lasiok, Jian Ding, and Jelani Nelson. Continuous monitoring of lp norms in data streams. arXiv preprint arXiv:1704.06710 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  4. [4]

    A tight bound for set disjointness in the message- passing model

    [BEO+13] Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pita ssi, and Vinod Vaikun- tanathan. A tight bound for set disjointness in the message- passing model. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science , pages 668–677. IEEE,

    work page 2013

  5. [5]

    An optimal algorithm for large frequency moments using o (nˆ(1 -2/k)) bits

    [BKSV14] Vladimir Braverman, Jonathan Katzman, Charles Se idell, and Gregory Vorsanger. An optimal algorithm for large frequency moments using o (nˆ(1 -2/k)) bits. In Approxi- mation, Randomization, and Combinatorial Optimization. Al gorithms and Techniques (APPROX/RANDOM 2014). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014 . [BLS+16] Maria Flori...

    work page 2014

  6. [6]

    Recursive Sketching For Frequency Moments

    [BO10] Vladimir Braverman and Rafail Ostrovsky. Recursive sketching for frequency moments. arXiv preprint arXiv:1011.2571 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  7. [7]

    Revisiting Frequency Moment Estimation in Random Order Streams

    [BVWY18] Vladimir Braverman, Emanuele Viola, David Woodru ff, and Lin F Yang. Revisiting fre- quency moment estimation in random order streams. arXiv preprint arXiv:1803.02270,

    work page internal anchor Pith review Pith/arXiv arXiv

  8. [8]

    Tau cs 0368.3239, leveraging big data l ecture notes, Fall

    [Coh13] Edith Cohen. Tau cs 0368.3239, leveraging big data l ecture notes, Fall

    work page arXiv

  9. [9]

    Topology matters in communication

    [CRR14] Arkadev Chattopadhyay, Jaikumar Radhakrishnan, a nd Atri Rudra. Topology matters in communication. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 631–640. IEEE,

    work page 2014

  10. [10]

    Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information

    [Gro09] Andre Gronemeier. Asymptotically optimal lower bo unds on the nih-multi-party in- formation. arXiv preprint arXiv:0902.1609 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  11. [11]

    Sketching and streaming en- tropy via approximation theory

    [HNO08a] Nicholas JA Harvey, Jelani Nelson, and Krzysztof O nak. Sketching and streaming en- tropy via approximation theory. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages 489–498. IEEE,

    work page 2008

  12. [12]

    Streaming algorithms for estimating entropy

    [HNO08b] Nicholas JA Harvey, Jelani Nelson, and Krzysztof O nak. Streaming algorithms for estimating entropy. In 2008 IEEE Information Theory Workshop , pages 227–231. IEEE,

    work page 2008

  13. [13]

    The data strea m space complexity of cascaded norms

    [JW09] Thathachar S Jayram and David P Woodruff. The data strea m space complexity of cascaded norms. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 765–774. IEEE,

    work page 2009

  14. [14]

    Perfect lp samplin g in a data stream

    32 [JW18] Rajesh Jayaram and David P Woodruff. Perfect lp samplin g in a data stream. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 544–555. IEEE,

    work page 2018

  15. [15]

    Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams

    [KNP+17] Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zheng yu Wang, David P Woodruff, and Mobin Yahyazadeh. Optimal lower bounds for universal re lation, and for samplers and finding duplicates in streams. arXiv preprint arXiv:1704.00633 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  16. [16]

    Distributed low ran k approximation of implicit functions of a matrix

    [WZ16] David P Woodruff and Peilin Zhong. Distributed low ran k approximation of implicit functions of a matrix. In 2016 IEEE 32nd International Conference on Data Engineer- ing (ICDE) , pages 847–858. IEEE,

    work page 2016