2020/06/19 by Shalev Ben-David, Ben-David, Shalev, Mika Göös +6
Computer Science · #Adversarial Robustness in Machine Learning #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2006.10957
openalex publication_date 2020/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Suppose we have randomized decision trees for an outer function f and an\ninner function g. The natural approach for obtaining a randomized decision\ntree for the composed function (f\∘\ngn)(x1,\…,xn)=f(g(x1),\…,g(xn)) involves amplifying the success\nprobability of the decision tree for g, so that a union bound can be used to\nbound the error probability over all the coordinates. The amplification\nintroduces a logarithmic factor cost overhead. We study the question: When is\nthis log factor necessary? We show that when the outer function is parity or\nmajority, the log factor can be necessary, even for models that are more\npowerful than plain randomized decision trees. Our results are related to, but\nqualitatively strengthen in various ways, known results about decision trees\nwith noisy inputs.\n