clopen.solutions
OP-00766 Solution claimed

Minimax rates for private density estimation with mixed anisotropy

Submit a result

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

Kaiwen Jin

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. …

Full resolution · not verified · fidelity not established · posted on GitHub 12 Oct 2026

Status history

WhenChangeByReason
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.