Instance-optimal estimation of L2-norm
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910071916593152 |
|---|---|
| author | Adar, Tomer |
| author_facet | Adar, Tomer |
| contents | 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\|μ\|_2) + t_μ/\varepsilon^2)$, for $t_μ= \|μ\|_3^3 / \|μ\|_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 $Ω(1/(\varepsilon \|μ\|_2) + t_μ/ \varepsilon^2)$ is indeed the per-instance lower bound for estimating the norm of a distribution $μ$ by sampling (even for non-unbiased estimators). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_21937 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Instance-optimal estimation of L2-norm Adar, Tomer Data Structures and Algorithms 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\|μ\|_2) + t_μ/\varepsilon^2)$, for $t_μ= \|μ\|_3^3 / \|μ\|_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 $Ω(1/(\varepsilon \|μ\|_2) + t_μ/ \varepsilon^2)$ is indeed the per-instance lower bound for estimating the norm of a distribution $μ$ by sampling (even for non-unbiased estimators). |
| title | Instance-optimal estimation of L2-norm |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.21937 |