Theory Seminar, Wednesday May 27: Tomer Adar (Technion) - Instance-optimal estimation of L2-norm

[Arnold Filtser]

Hi all,

Next week (Wednesday May 27, at 12pm) we will meet for our theory seminar.

Location: Building 503 room 226.

Looking forward to seeing you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Tomer Adar (Technion)
Title: Instance-optimal estimation of L2-norm
Abstract: The $L_2$-norm, or collision norm, is a core entity in the analysis of distributions and probabilistic algorithms. Batu and Canonne (FOCS 2017) presented an extensive analysis of algorithmic aspects of the $L_2$-norm and its connection to uniformity testing. However, when it comes to estimating the $L_2$-norm itself, their algorithm is not always optimal compared to the instance-specific second-moment bounds, $O(1/(\varepsilon\|\mu\|_2) + t_\mu/\varepsilon^2)$, for $t_\mu = \|\mu\|_3^3 / \|\mu\|_2^4 - 1$, as stated by Batu (WoLA 2025, open problem session).

In this paper, we present an unbiased $L_2$-estimation algorithm whose sample complexity matches the instance-specific second-moment analysis. Additionally, we show that $\Omega(1/(\varepsilon\|\mu\|_2) + t_\mu / \varepsilon^2)$ is indeed the per-instance lower bound for estimating the norm of a distribution $\mu$ by sampling (even for non-unbiased estimators).

https://arxiv.org/pdf/2602.21937

[Arnold Filtser]

The talk will start in one hour!