Solving Marginal MAP Problems with NP Oracles and Parity Constraints
Arising from many applications at the intersection of decision-making and machine learning, Marginal Maximum A Posteriori (Marginal MAP) problems unify the two main classes of inference, namely maximization (optimization) and marginal inference (counting), and are believed to have higher complexity than both of them. We propose XOR_MMAP, a novel approach to solve the Marginal MAP problem, which represents the intractable counting subproblem with queries to NP oracles, subject to additional parity constraints. XOR_MMAP provides a constant factor approximation to the Marginal MAP problem, by encoding it as a single optimization in a polynomial size of the original problem. We evaluate our approach in several machine learning and decision-making applications, and show that our approach outperforms several state-of-the-art Marginal MAP solvers.
This paper aims at approximating marginal MAP (MMAP) problem instances using NP oracles. In the spirit of Ermon et. al.’s work (ICML 2013) for approximating #P-complete problems using pairwise independent hashing and optimization, the authors propose a randomized algorithm (XOR-MMAP) that transforms an MMAP query into a series of joint MAP (or MPE) queries, each begin defined as a nonlinear optimization problem over all variables, subject to randomly generated parity constraints.  From a theoretical viewpoint, approximation guarantees for XOR-MMAP are provided in both the unweighted (or binary) case and the weighted case. Comparative experiments, with respect to two state-of-the-art MMAP approximation methods are performed on various domains, including random SAT instances, an image completion task, and a network design application. 
There are pros and cons in this article. On the one hand, the idea of approximating complex MMAP queries using a series of random constrained optimization problems is conceptually simple and opens the door to many potential improvements. Furthermore, I really appreciated the diversity of experimental domains used to evaluate the method. On the other hand, I have several concerns about the approximation bounds and the optimization oracle.  * Approximation bounds  The approximation guarantees provided by Theorem 3.2. and Theorem 3.6 are very weak. For the unweighted case, we have a bound of $4^c$ and, to ensure that the denominator $\alpha(c)$  of the complexity parameter T is greater or equal than 1, $c$ must be greater or equal than 5, which roughly means an approximation constant about one thousand. For the weighted case, the constant is about three thousands. With such large constants, one may wonder whether the approximation guarantees of the algorithm are useful in practice.  The extension to the weighted case (Section 3.2) could be improved using a recent article by Chakraborty et al. (IJCAI 15) (From Weighted to Unweighted Model Counting). Indeed, since the weight function is encoded as a literal-weighted CNF (as specified by Lines 358-362 in the S.M.), it can be transformed into an equivalent unweighted (binary) CNF formula of polynomial size. By applying Theorem 2 of Chakraborty and Theorem 5.2, it seems that we can get a better bound for the weighted case of MMAP.    In Lines 178-180, the authors suggest to use binary search instead of linear search for the number of calls to the optimization oracle. This is clearly a preferable strategy, but I am wondering whether the approximation bounds are still preserved in this case. In fact, the proof of Theorem 3.2 (Lines 173-177) needs $n$ calls to the oracle in order to derive a probability of $1 - \delta$. By the way, XOR-MMAP+ provided in the S.M. looks more interesting for reducing the complexity parameter $T$, but the number of calls to the oracle is in $O(n log n)$. So, can you obtain similar approximation bounds when XOR-MMAP(+) calls XOR-K only $O(log n)$ times?  * Optimization oracle  The XOR-MMAP algorithm relies on an optimization oracle which is far from easy to solve. Namely, Eq. (2) of Algorithm 2 is a nonlinear constrained optimization task, where the constraint set is a list of $kT$ random XOR clauses (Lines 87-88), each of size $O(n)$. Based on the standard encoding suggested in the supplementary material, the objective function can be specified as a linear function. But the overall set of constraints for this linear optimization problem involves both XOR clauses (encoding the hash function), and CNF clauses (encoding the weight function). As we know, XOR clauses over $n$ variables cannot be translated into CNF clauses (this would give an exponential number of disjuncts). So, which algorithm do you use to solve this linear optimization problem involving both CNF and XOR clauses? Unless I missed something, there is no discussion in the paper about the practical implementation of this expensive optimization oracle.      In light of the above remark, I think that it is crucial to report the running times of all algorithms in the experimental study. Even if XOR-MMAP behaves well in practice for approximating MMAP instances, its optimization oracle is very expensive. So one might really wonder whether XOR-MMAP is scalable, in comparison with SAA and Mixed LBP.   * Minor comments  Line 182: From Theorem 3.2 -> From Theorem 3.1  The use of “NP oracles” in the title is not - strictly speaking - appropriate. The procedure used by XOR-MMAP is an FP^NP (i.e. constrained optimization) oracle.