Hardness of Maximum Likelihood Learning of DPPs
- URL: http://arxiv.org/abs/2205.12377v2
- Date: Thu, 26 May 2022 02:12:36 GMT
- Title: Hardness of Maximum Likelihood Learning of DPPs
- Authors: Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
- Abstract summary: We prove Kulesza's conjecture that the problem of finding a maximum likelihood DPP model for a given data set is NP-complete.
In terms of techniques, we reduce approxing the maximum log-likelihood of DPPs on a data set to solving a gap of instance a "vector" problem on a hypergraph.
- Score: 25.06251462216571
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Determinantal Point Processes (DPPs) are a widely used probabilistic model
for negatively correlated sets. DPPs have been successfully employed in Machine
Learning applications to select a diverse, yet representative subset of data.
In seminal work on DPPs in Machine Learning, Kulesza conjectured in his PhD
Thesis (2011) that the problem of finding a maximum likelihood DPP model for a
given data set is NP-complete.
In this work we prove Kulesza's conjecture. In fact, we prove the following
stronger hardness of approximation result: even computing a
$\left(1-O(\frac{1}{\log^9{N}})\right)$-approximation to the maximum
log-likelihood of a DPP on a ground set of $N$ elements is NP-complete. At the
same time, we also obtain the first polynomial-time algorithm that achieves a
nontrivial worst-case approximation to the optimal log-likelihood: the
approximation factor is $\frac{1}{(1+o(1))\log{m}}$ unconditionally (for data
sets that consist of $m$ subsets), and can be improved to $1-\frac{1+o(1)}{\log
N}$ if all $N$ elements appear in a $O(1/N)$-fraction of the subsets.
In terms of techniques, we reduce approximating the maximum log-likelihood of
DPPs on a data set to solving a gap instance of a "vector coloring" problem on
a hypergraph. Such a hypergraph is built on a bounded-degree graph construction
of Bogdanov, Obata and Trevisan (FOCS 2002), and is further enhanced by the
strong expanders of Alon and Capalbo (FOCS 2007) to serve our purposes.
Related papers
- Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs [39.468324211376505]
We study the efficient learnability of low-degree threshold functions (PTFs) in the presence of a constant fraction of adversarial corruptions.
Our algorithm employs an iterative approach inspired by localization techniques previously used in the context of learning linear threshold functions.
arXiv Detail & Related papers (2024-03-31T02:03:35Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
We study differentially private approximation algorithms for hierarchical clustering.
We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset.
We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
arXiv Detail & Related papers (2023-01-31T19:14:30Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP)
We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
arXiv Detail & Related papers (2022-12-01T15:57:58Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model.
The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
arXiv Detail & Related papers (2022-08-11T04:12:50Z) - Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility
Amortizations in Repeated Rankings [9.066817876491053]
We consider the problem of computing a sequence of rankings that maximizes consumer-side utility while minimizing producer-side individual unfairness of exposure.
We introduce a geometrical object, a polytope that we call expohedron, whose points represent all achievable exposures of items for a Position Based Model.
Our approach compares favorably to linear or quadratic programming baselines in terms of algorithmic complexity and empirical runtime.
Our solution can be expressed as a distribution over only $n$ permutations, instead of the $(n-1)2 + 1$ achieved with BvN decompositions.
arXiv Detail & Related papers (2022-02-07T14:43:35Z) - Recurrently Predicting Hypergraphs [30.092688729343678]
A problem arises from the number of possible multi-way relationships, or hyperedges, scaling in $mathcalO(2n)$ for a set of $n$ elements.
We propose a recurrent hypergraph neural network that predicts the incidence matrix by iteratively refining an initial guess of the solution.
arXiv Detail & Related papers (2021-06-26T01:12:41Z) - Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment [59.87663954467815]
In graph-based binary learning, a subset of known labels $hatx_i$ are used to infer unknown labels.
When restricting labels $x_i$ to binary values, the problem is NP-hard.
We propose a fast projection-free method by solving a sequence of linear programs (LP) instead.
arXiv Detail & Related papers (2021-06-03T07:22:48Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
We study the reinforcement learning for finite-horizon episodic Markov decision processes with adversarial reward and full information feedback.
We show that it can achieve $tildeO(dHsqrtT)$ regret, where $H$ is the length of the episode.
We also prove a matching lower bound of $tildeOmega(dHsqrtT)$ up to logarithmic factors.
arXiv Detail & Related papers (2021-02-17T18:54:08Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
We study the Empirical Risk Minimization (ERM) problem in the noninteractive Local Differential Privacy (LDP) model.
Previous research indicates that the sample complexity, to achieve error $alpha, needs to be depending on dimensionality $p$ for general loss functions.
arXiv Detail & Related papers (2020-11-11T17:48:00Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
arXiv Detail & Related papers (2020-09-18T02:18:44Z)
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.