Paper

{
  "raw_xml": "<entry>\n    <id>http://arxiv.org/abs/2602.21937v1</id>\n    <title>Instance-optimal estimation of L2-norm</title>\n    <updated>2026-02-25T14:22:04Z</updated>\n    <link href='https://arxiv.org/abs/2602.21937v1' rel='alternate' type='text/html'/>\n    <link href='https://arxiv.org/pdf/2602.21937v1' rel='related' title='pdf' type='application/pdf'/>\n    <summary>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) + (\\|μ\\|_3^3 - \\|μ\\|_2^4) / (\\varepsilon^2 \\|μ\\|_2^4))$, as stated by Batu (WoLA 2025, open problem session).\n  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))$ is indeed a per-instance lower bound for estimating the norm of a distribution $μ$ by sampling (even for non-unbiased estimators).</summary>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.DS'/>\n    <published>2026-02-25T14:22:04Z</published>\n    <arxiv:primary_category term='cs.DS'/>\n    <author>\n      <name>Tomer Adar</name>\n    </author>\n  </entry>"
}