Algorithms and Hardness for Concave Expectational Functionals

Statistical similarity and several related overlaps lack simple coordinatewise formulas on product distributions, unlike familiar quantities such as Kullback–Leibler divergence and Hellinger affinity. This distinction matters for the Bayes-optimal error of a naive-Bayes classifier: the error can be exponentially small, making additive estimates and standard bounds from coordinatewise quantities uninformative. We study the expectational functionals $F(P,Q)={\mathbb{E}}_{x\sim Q}[f(P(x)/Q(x))]$ for every non-negative concave $f$ with $f(0)=0$ and $f\not\equiv 0$. The family includes statistical similarity $1-d_{\mathrm{TV}}(P,Q)$, which determines Bayes-optimal error, as well as log, harmonic, exponential, $\tanh$, $\arctan$, and square-root overlaps. For product distributions, given a rational lower bound on $f(1)$ and a polynomial-time evaluation oracle for $f$, we give a deterministic fully polynomial-time approximation scheme for the entire family. Its running time is polynomial in the logarithm of the reciprocal of the smallest nonzero marginal probability, and it approximates naive-Bayes error within a factor $1+\epsilon$. On a simple naive-Bayes family, the lower bound from the factorizing Bhattacharyya coefficient misses the true error by an exponential factor. For Bayes nets of in-degree $2$, deciding whether $F(P,Q)>0$ is $\mathsf{NP}$-complete for every member of the family, ruling out polynomial-time multiplicative approximation unless $\mathsf{P}=\mathsf{NP}$. The algorithm uses subhomogeneity and a positive lower bound on partial likelihood-ratio products; no growth condition on $f$ at the origin is needed.