Minimax rates for private density estimation with mixed anisotropy
Fix an integer $d \ge 2$, $R > 0$ with $R^2 > d$, $A > 0$, and vectors $\boldsymbol\beta, \boldsymbol\delta \in \mathbb{N}_{>0}^d$ such that $\beta_m/\delta_m$ does not depend on $m$, with $\delta_m < d$ for some $m$ and $\delta_k > d$ for some $k$. Let $\phi_1(t) = 1$, $\phi_{2j}(t) = \sqrt2 \cos(2\pi j t)$ and $\phi_{2j+1}(t) = \sqrt2 \sin(2\pi j t)$ for $j \ge 1$, let $\phi_{\mathbf j}(x) = \prod_{m} \phi_{j_m}(x_m)$ for $\mathbf j \in \mathbb{N}_{>0}^d$, and write $\theta_{\mathbf j}(h) = \int_{[0,1]^d} h \phi_{\mathbf j}$. For a vector $\mathbf s$ and $r > 0$ let $$W^{\mathbf s}(r) = \Bigl\{h \in L^2([0,1]^d) : \sum_{\mathbf j \in \mathbb{N}_{>0}^d} \Bigl(\sum_{m=1}^d j_m^{2 s_m}\Bigr) |\theta_{\mathbf j}(h)|^2 \le r^2\Bigr\},$$ let $\mathcal{F}_{\boldsymbol\beta,R}$ be the set of probability densities in $W^{\boldsymbol\beta}(R)$, and let $$d_{\boldsymbol\delta}(h, f) = \sup_{g \in W^{\boldsymbol\delta}(1)} \Bigl|\int_{[0,1]^d} (h - f) g\Bigr|.$$ Given independent observations $X_1, \dots, X_n$ with density $f$, a sequentially interactive $\alpha$-locally private mechanism releases each $Z_i$ through a channel $Q_i(\cdot \mid X_i, Z_1, \dots, Z_{i-1})$ with $$Q_i(B \mid x, z_{<i}) \le e^{\alpha} Q_i(B \mid x', z_{<i})$$ for every measurable $B$, all $x, x'$ and all histories $z_{<i}$; let $\mathcal{Q}_\alpha$ be the class of these mechanisms, and let $$\mathcal{R}_{n,\alpha}(\boldsymbol\beta, \boldsymbol\delta) = \inf_{Q \in \mathcal{Q}_\alpha} \inf_{\widehat f} \sup_{f \in \mathcal{F}_{\boldsymbol\beta,R}} \mathbb{E}_{f,Q}\, d_{\boldsymbol\delta}(\widehat f, f),$$ where $\widehat f$ ranges over measurable $L^2$-valued functions of the released data.
Let $\bar\beta$ and $\bar\delta$ be the harmonic means of the $\beta_m$ and of the $\delta_m$. Albert, Chevallier, Laurent and Sacko proved that, for a constant $c > 0$ depending only on $d$, $R$, $A$, $\boldsymbol\beta$ and $\boldsymbol\delta$, $$\mathcal{R}_{n,\alpha}(\boldsymbol\beta, \boldsymbol\delta) \ge c \max\bigl\{(n\alpha^2)^{-(\bar\beta + \bar\delta)/(2\bar\beta + 2d)},\ (n\alpha^2)^{-1/2}\bigr\}$$ for all $0 < \alpha \le A$ with $n\alpha^2 \ge 1$, for proportional integer smoothness vectors without the condition on the signs of $\delta_m - d$, and gave a non-interactive mechanism and projection estimator attaining this order when $\delta_m < d$ for every $m$ or $\delta_m > d$ for every $m$.
Problem. Determine $\mathcal{R}_{n,\alpha}(\boldsymbol\beta, \boldsymbol\delta)$, up to multiplicative constants independent of $n$ and $\alpha$, for $0 < \alpha \le A$ and $n\alpha^2 \ge 1$, with matching lower and upper bounds that include any necessary logarithmic factors. The parameters $d$, $R$, $\boldsymbol\beta$ and $\boldsymbol\delta$ are known and fixed.
Source: Albert, Chevallier, Laurent and Sacko (2026), §3, the remark after Theorem 11 on smoothness vectors δ whose coordinates lie on both sides of d; stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- ST — Statistics Theory
- Secondary
- PR
- Keywords
- AIM Open Applied Problems, density estimation, local differential privacy, minimax rates
References
@article{albert2026,
author = {Albert, M{\'e}lisande and Chevallier, Juliette and Laurent, B{\'e}atrice and Sacko, Ousmane},
title = {Minimax density estimation in the adversarial framework under local differential privacy},
journal = {J. Mach. Learn. Res.},
volume = {27},
number = {69},
year = {2026},
pages = {1--43},
url = {https://www.jmlr.org/papers/v27/24-0494.html},
eprint = {2403.18357},
archivePrefix = {arXiv},
}
@misc{aim-private-density-mixed-anisotropy,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Minimax rates for private density estimation with mixed anisotropy}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/506-private-density-mixed-anisotropy.md},
note = {Entry 506 at commit a153f46, 2026-10-13},
}
Resolution claims
We determine the minimax density-estimation rate under sequentially interactive local differential privacy and an anisotropic negative Sobolev loss, when the density and discriminator smoothness vectors are proportional. The result covers coordinates whose discriminator smoothness lies on opposite sides of the ambient dimension. The harmonic mean of discriminator smoothness determines the rate, with a single logarithmic factor at the critical value. …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-16 | Needs verification → Solution claimed | — | Recorded here: AIM @ a153f46, paper/mixed_private_density.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00766, "Minimax rates for private density estimation with mixed anisotropy", clopen.solutions.