acceptodds
Under review as a conference paper at ICLR 2027

Algorithms and Hardness for Concave Expectational Functionals

Abstract

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 for every non-negative concave with and . The family includes statistical similarity , which determines Bayes-optimal error, as well as log, harmonic, exponential, , , and square-root overlaps. For product distributions, given a rational lower bound on and a polynomial-time evaluation oracle for , 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 . 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 , deciding whether is -complete for every member of the family, ruling out polynomial-time multiplicative approximation unless . The algorithm uses subhomogeneity and a positive lower bound on partial likelihood-ratio products; no growth condition on at the origin is needed.

Primary area:
learning theory
Keywords:
total variation distance, statistical similarity, Bayes error, naive Bayes, FPTAS, product distributions, Bayes networks, computational complexity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.60 over 5 reviews, above 70% of the others.
Reviewer_SuUbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies functionals Ff(P,Q)=Ex∼Q[f(P(x)/Q(x))]F_f(P,Q)=\mathbb E_{x\sim Q}[f(P(x)/Q(x))] for concave f:[0,∞)→[0,∞)f:[0,\infty)\to[0,\infty) with f(0)=0f(0)=0 and f≢0f\not\equiv0. The family contains statistical similarity 1−dTV1-d_{\mathrm{TV}} and its capped versions, hence the Bayes error of binary classification, together with several smooth overlaps (log, harmonic, exponential, tanh, arctan, square-root). For product distributions, given a rational lower bound on f(1)f(1) and an evaluation oracle for ff

Critical strengths
  1. Multiplicative approximation of exponentially small overlaps. The FPTAS gives a deterministic (1+ε)(1+\varepsilon)-approximation of statistical similarity and of the Bayes error of naive-Bayes models with arbitrary marginals.

  2. One short analysis for the whole family. Subhomogeneity and the bound τn\tau^n on positive partial products give the guarantee for every admissible ff, including the square-root overlaps with infinite slope at zero, with explicit bit complexity and logarithmic dependence on 1/τ1/\tau.

Critical weaknesses

The paper is hard to read, and its practical motivation is not supported by any computation. The introduction is dense with formulas whose symbols are defined only later or not at all: nn, ℓ\ell, b0b_0, the marginals pi,qip_i,q_i, the moment order KK, Sol(ϕ)\mathrm{Sol}(\phi), "slice" and "partial-product ratio". In a single sentence, the alphabet size is called qq and then ℓ\ell, while qiq_i in the same sentence denotes a marginal of QQ. Every cross-reference is labeled "Theorem", including references to Definition 2.1, Remark 2.9 and, 26 times, Lemma 2.7.

Questions for authors
  1. Does the case f(r)=min⁡(r,c)f(r)=\min(r,c), and hence the naive-Bayes Bayes error, follow from the FPTAS of Li and Shi or from the counting-knapsack dynamic program after rounding the log-likelihood ratios to a grid?

  2. Can the authors implement the algorithm, for example in the log domain, and report its accuracy and running time as functions of nn and ε\varepsilon on naive-Bayes models with heterogeneous marginals, including at least one model fitted to real data?

  3. Can anything be said about hardness for full-support Bayes nets, or under a promise that Ff(P,Q)>0F_f(P,Q)>0?

Reviewer_goG3OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary
  • The authors study expectational functionals Ff(P,Q)=Ex∼Q[f(P(x)Q(x))],F_f(P,Q)=\mathbb{E}_{x\sim Q}\left[f\left(\frac{P(x)}{Q(x)}\right)\right], where, PP and QQ are product distributions and ff is nonnegative and concave, with f(0)=0f(0)=0 and f≢0f\not\equiv 0.

  • Exact computation of statistical similarity, corresponding to f(r)=min⁡(r,1)f(r)=\min(r,1), was already known to be #P-hard on product distributions. This paper extends exact hardness to several related piecewise-linear functionals.

  • Several standard divergences, including KL, Hellinger, and Rényi-type quantities, were already known to be efficiently computable on product distributions because they admit coordinate-wise formulas. The authors note that the functionals they considered generally do not decompose in this way.

  • Prior work gave FPTAS for TV distance dTV(P,Q)d_{\mathrm{TV}}(P,Q), but does not extend to 1−dTV(P,Q)1-d_{\mathrm{TV}}(P,Q) (which can be exponentially small even when dTVd_{\mathrm{TV}} is very close to 11).

  • The main contribution is a deterministic FPTAS giving a (1+ε)(1+\varepsilon) multiplicative approximation to Ff(P,Q)F_f(P,Q). The algorithm is DP-like over partial likelihood-ratio products, and uses geometric rounding after each coordinate to keep the number of states polynomial.

  • The main application is computing the Bayes-optimal error of a binary naive-Bayes classifier, i.e. the minimum classification error achievable given the class priors and class-conditional feature distributions. The authors also note applications in hypothesis testing, coupling, asymmetric classification loss, and information theory.

  • The main hardness result shows for Bayes nets of in-degree 22, deciding whether Ff(P,Q)>0F_f(P,Q)>0 is NP-complete, ie. the problem admits an FPTAS only with the independence assumptions.

Critical strengths

Their FPTAS gives a multiplicative guarantee in regimes where previously there was none and where the existing additive approximations are not meaningful, as in their example of 1−dTV(P,Q)1-d_{TV}(P,Q).

It's also useful that their FPTAS applies to a broad class of problems, rather than one specific quantity. The assumptions (ie. including concavity) of the function ff seem mild, and they require independence of the variables for each distribution.

Critical weaknesses

One possible weakness is that the result only applies to distributions with completely independent variables (although they do show that this requirement is necessary).

Another possible weakness is that the practicality of the algorithm is questionable, (however, this paper mostly emphasizes the theory result.)

Questions for authors

How significant is the algorithmic contribution? Meaning, how does the FPTAS in this paper differ algorithmically to the one in prior work (Feng et al)?

Reviewer_ZnpQOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

Paper provides a deterministic approximation algorithm (FPTAS) for the problem of estimating similarity measures like statistical similarity between two product probability distributions, such as class conditionals in Naive Bayes. Their algorithm applies to a class of measures---expectations of certain concave functions ff of ratio of the two distributions (termed "admissible" functions). Notable points:

  • The emphasis is on multiplicative approximation; known multiplicative approximations for total variation distance don't imply the result here (additive would have). Also the similarity measures can be very small, e.g. exponentially small in number of variables in Naive Bayes, so additive approximations are not as strong as multiplicative.
  • The algo requires oracle access to the concave function ff, and a lower bound on the marginal probability for either distribution and all variables.
  • The FPTAS works by progressively bucketing the ratio of the two distributions (termed "J-sparsification") as the algo iterates over the sequence of variables over which the distributions are defined.
  • Concave functional means this bucketing with bucket boundaries growing geometrically guarantees the approximation of the functional will be multiplicative. The paper proves the FPTAS guarantees of this algorithm, and further proves that even deciding that similarity is >0> 0 for indegree-22 Bayes Nets, ruling out FPTAS for anything but product (indegree-11) distributions.
Critical strengths
  • The FPTAS and hardness results are correct, and proofs are rigorous. The paper does a good job of explaining the high level ideas behind the proofs, making it easy to follow.
  • The results covers a wide rage of concave functionals, notable statistical similarity. While approximation results are known under product distributions for common distance measures like KL divergence (which tend to be convex functionals), this may be the first significant result for approximating concave functionals.
Critical weaknesses
  • The paper does not do a good job explaining why multiplicative approximations of similarity measures are an interesting problem for machine learning. Where might it matter that we can approximate 1−dTV1- d_{TV} within 1±ϵ1 \pm \epsilon? Multiplicative errors for distance measures are easier to motivate and understand. Irrespective of the quality of the theoretical contributions, this is an important consideration for submissions to a ML conference like ICLR.

  • The theoretical result my be novel, but it is simply applying existing techniques like J−sparsificationJ-sparsification, and the algo and the FPTAS guarantee further require a lower bound on marginals (thereby avoiding the "slope at 00" problem they point out). So in this reviewer's opinion, the result is not contributing much in the way of new theoretical insights or analysis.

Questions for authors

I am willing to upgrade the rating if the motivation for studying multiplicative approximations of similarity measures for ML applications is better explained.

Reviewer_QKSsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This work studies the problem of computing f-divergences, for a nonnegative concave f with f(0) = 0 and f not identically zero, an f-expectational functional of two distribution P, Q is defined as E_{x \sim Q}[f(P(x) / Q(x))].

For product distributions they present a fully polynomial-time approximation scheme (FPTAS) for any such function f() (assuming access to f via a polynomial-time evaluation oracle and a positive rational lower bound on f(1)). For Bayes nets of in-degree at most 2 they show that even deciding whether the f-expectational functional of P, Q is > 0 (vs the two distributions having disjoint supports) is NP-hard.

Critical strengths
  1. I think the problem of approximating these functionals is well-motivated and interesting. The paper does a good job introducing the problem, related literature and the framework.
Critical weaknesses
  1. I think the structural scope of the main results is rather limited. The algorithmic result covers product distributions. The impossibility result shows that for special cases of non-product distributions the problem is NP-hard but I think the gap between the algorithmic result (product distributions) and the impossibility result is rather large. It would be interesting if simple dependent distributions were also studied algorithmically for multiplicative approximation to have a more complete picture of the computational landscape.

  2. The main algorithmic result for approximating these functionals seems to follows the techniques of the prior work [1]. It seems to me that there technical differences in error analysis and discretization but at a high level I think that the new algorithmic and technical content of this work is a bit limited.

  3. The impossibility result (NP-Hard to decide whether the f-expectational functional of P, Q is 0 or >0) seems similar to the corresponding hardness result in the prior work [2]. I think this result also seems to have rather limited novelty.

[1] https://arxiv.org/pdf/2309.14696

[2] https://ijcai.org/proceedings/2023/0387.pdf

Questions for authors

Please see weaknesses

Reviewer_UTVNOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies relative approximation of expectations of concave functions of a likelihood ratio. For product distributions, it gives a deterministic FPTAS using geometric sparsification. The result includes statistical similarity, which determines binary naive-Bayes error, and functions with infinite slope at zero. For Bayesian networks of indegree two, it proves that even deciding whether the functional is positive is NP-complete. The evidence consists of proofs and an analytic naive-Bayes example.

Critical strengths
  1. Looks like the theorem 4.1 gives a useful uniform relative-approximation guarantee when overlap is small. The positive-ratio invariant in Lemma A.2 eliminates the near-zero error and covers infinite-slope examples.
  2. The hardness results clarify the role of dependence and support. Theorem 5.1 applies uniformly across the family.
Critical weaknesses

I think the algorithmic contribution is incremental on the likelihood-ratio sparsification [1]. The earlier preprint [2] already gives a product-distribution FPTAS and indegree-two positivity hardness for statistical similarity.

References: [1] On Deterministically Approximating Total Variation Distance. [2] Algorithms and Hardness for Estimating Statistical Similarity.

Questions for authors
  1. Beyond generalizing the integrand, which technical step is essential relative to the statistical-similarity algorithm in [2]?
  2. What concrete application most benefits from a smooth or infinite-slope example beyond statistical similarity?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.