Inapproximability of Minimizing a Pair of DNFs or Binary Decision Trees Defining a Partial Boolean Function

• URL: http://arxiv.org/abs/2102.04703v1
• Date: Tue, 9 Feb 2021 08:46:50 GMT
• Title: Inapproximability of Minimizing a Pair of DNFs or Binary Decision Trees Defining a Partial Boolean Function
• Authors: David Stein and Bjoern Andres
• Abstract summary: We consider partial Boolean functions defined by a pair of Boolean functions $f, g colon 0,1J to 0,1$ such that $f cdot g = 0$ and such that $f$ and $g$ are defined by disjunctive normal forms or binary decision trees.
• Score: 13.713089043895959
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The desire to apply machine learning techniques in safety-critical environments has renewed interest in the learning of partial functions for distinguishing between positive, negative and unclear observations. We contribute to the understanding of the hardness of this problem. Specifically, we consider partial Boolean functions defined by a pair of Boolean functions $f, g \colon \{0,1\}^J \to \{0,1\}$ such that $f \cdot g = 0$ and such that $f$ and $g$ are defined by disjunctive normal forms or binary decision trees. We show: Minimizing the sum of the lengths or depths of these forms while separating disjoint sets $A \cup B = S \subseteq \{0,1\}^J$ such that $f(A) = \{1\}$ and $g(B) = \{1\}$ is inapproximable to within $(1 - \epsilon) \ln (|S|-1)$ for any $\epsilon > 0$, unless P=NP.

Related papers

• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
  arXiv  Detail & Related papers  (2021-09-21T13:19:04Z)
• Approximate Maximum Halfspace Discrepancy [6.35821487778241]
  We consider the range space $(X, mathcalH_d)$ where $X subset mathbbRd$ and $mathcalH_d$ is the set of ranges defined by $d$ halfspaces. For each halfspace $h in mathcalH_d$ define a function $Phi(h)$ that measures the "difference" between the fraction of red and fraction of blue points which fall in the range $h$.
  arXiv  Detail & Related papers  (2021-06-25T19:14:45Z)
• Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints [18.03695167610009]
  We show that when sample size $n$ exceeds a minimum threshold $n*(s, d, b)$, we can achieve an $ell$ estimation error of $Oleft( fracsn2bright)$. For the interactive setting, we propose a novel tree-based estimation scheme and show that the minimum sample-size needed to achieve dimension-free convergence can be further reduced to $n*(s, d, b)$.
  arXiv  Detail & Related papers  (2021-06-16T07:52:14Z)
• Universal guarantees for decision tree induction via a higher-order splitting criterion [16.832966312395126]
  Our algorithm achieves provable guarantees for all target functions $f: -1,1n to -1,1$ with respect to the uniform distribution. The crux of our extension is a new splitting criterion that takes into account the correlations between $f$ and small subsets of its attributes. Our algorithm satisfies the following guarantee: for all target functions $f : -1,1n to -1,1$, sizes $sin mathbbN$, and error parameters $epsilon$, it constructs a decision
  arXiv  Detail & Related papers  (2020-10-16T21:20:45Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.