{"ID":2842304,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.10366","arxiv_id":"2511.10366","title":"Product distribution learning with imperfect advice","abstract":"Given i.i.d.~samples from an unknown distribution $P$, the goal of distribution learning is to recover the parameters of a distribution that is close to $P$. When $P$ belongs to the class of product distributions on the Boolean hypercube $\\{0,1\\}^d$, it is known that $Ω(d/\\varepsilon^2)$ samples are necessary to learn $P$ within total variation (TV) distance $\\varepsilon$. We revisit this problem when the learner is also given as advice the parameters of a product distribution $Q$. We show that there is an efficient algorithm to learn $P$ within TV distance $\\varepsilon$ that has sample complexity $\\tilde{O}(d^{1-η}/\\varepsilon^2)$, if $\\|\\mathbf{p} - \\mathbf{q}\\|_1 \u003c \\varepsilon d^{0.5 - Ω(η)}$. Here, $\\mathbf{p}$ and $\\mathbf{q}$ are the mean vectors of $P$ and $Q$ respectively, and no bound on $\\|\\mathbf{p} - \\mathbf{q}\\|_1$ is known to the algorithm a priori.","short_abstract":"Given i.i.d.~samples from an unknown distribution $P$, the goal of distribution learning is to recover the parameters of a distribution that is close to $P$. When $P$ belongs to the class of product distributions on the Boolean hypercube $\\{0,1\\}^d$, it is known that $Ω(d/\\varepsilon^2)$ samples are necessary to learn...","url_abs":"https://arxiv.org/abs/2511.10366","url_pdf":"https://arxiv.org/pdf/2511.10366v1","authors":"[\"Arnab Bhattacharyya\",\"Davin Choo\",\"Philips George John\",\"Themis Gouleakis\"]","published":"2025-11-13T14:44:46Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false}