Working Paper

Statistical and computational thresholds for the planted k-densest sub-hypergraph problem

Recovery a planted signal perturbed by noise is a fundamental problem in machine learning. In this work, we consider the problem of recovery a planted k-densest sub-hypergraph on h-uniform hypergraphs over n nodes. This fundamental problem appears in different contexts, e.g., community detection, average case complexity, and neuroscience applications. We first observe that it can be viewed as a structural variant of tensor PCA in which the hypergraph parameters k and h determine the structure of the signal to be...

Continuous submodular function maximization

Continuous submodular functions are a category of generally non-convex/non-concave functions with a wide spectrum of applications. The celebrated property of this class of functions - continuous submodularity - enables both exact minimization and approximate maximization in poly. time. Continuous submodularity is obtained by generalizing the notion of submodularity from discrete domains to continuous domains. It intuitively captures a repulsive effect amongst different dimensions of the defined multivariate function. In this paper, we systematically study continuous submodularity and a class of...

Learning Counterfactual Representations for Estimating Individual Dose-Response Curves-2019

Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference