- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies functionals for concave with and . The family contains statistical similarity 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 and an evaluation oracle for
Critical strengths
-
Multiplicative approximation of exponentially small overlaps. The FPTAS gives a deterministic -approximation of statistical similarity and of the Bayes error of naive-Bayes models with arbitrary marginals.
-
One short analysis for the whole family. Subhomogeneity and the bound on positive partial products give the guarantee for every admissible , including the square-root overlaps with infinite slope at zero, with explicit bit complexity and logarithmic dependence on .
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: , , , the marginals , the moment order , , "slice" and "partial-product ratio". In a single sentence, the alphabet size is called and then , while in the same sentence denotes a marginal of . Every cross-reference is labeled "Theorem", including references to Definition 2.1, Remark 2.9 and, 26 times, Lemma 2.7.
Questions for authors
-
Does the case , 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?
-
Can the authors implement the algorithm, for example in the log domain, and report its accuracy and running time as functions of and on naive-Bayes models with heterogeneous marginals, including at least one model fitted to real data?
-
Can anything be said about hardness for full-support Bayes nets, or under a promise that ?