We present an MCMC sampler for Dirichlet process mixture models that can be parallelized to achieve significant computational gains. We combine a nonergodic, restricted Gibbs iteration with split/merge proposals in a manner that produces an ergodic Markov chain. Each cluster is augmented with two subclusters to construct likely split moves. Unlike some previous parallel samplers, the proposed sampler enforces the correct stationary distribution of the Markov chain without the need for finite approximations. Empirical results illustrate that the new sampler exhibits better convergence properties than current methods.

We propose a parameter server system for distributed ML, which follows a Stale Synchronous Parallel (SSP) model of computation that maximizes the time computational workers spend doing useful work on ML algorithms, while still providing correctness guarantees. The parameter server provides an easy-to-use shared interface for read/write access to an ML model's values (parameters and variables), and the SSP model allows distributed workers to read older, stale versions of these values from a local cache, instead of waiting to get them from a central storage. This significantly increases the proportion of time workers spend computing, as opposed to waiting. Furthermore, the SSP model ensures ML algorithm correctness by limiting the maximum age of the stale values. We provide a proof of correctness under SSP, as well as empirical results demonstrating that the SSP model achieves faster algorithm convergence on several different ML problems, compared to fully-synchronous and asynchronous schemes.

Non-parametric approaches for analyzing network data base d on exchangeable graph models (ExGM) have recently gained interest. The key o bject that defines an ExGM is often referred to as a graphon . This non-parametric perspective on network modeling poses challenging questions on how to make inference on the graphon underlying observed network data. In this paper, we propose a computationally efficient procedure to estimate a graphon from a set of observed networks generated from it. This procedure is based on a stochastic bl ockmodel approximation (SBA) of the graphon. W e show that, by approximating t he graphon with a stochastic block model, the graphon can be consistently es timated, that is, the estimation error vanishes as the size of the graph approache s infinity.

Fitting high-dimensional statistical models often requires the use of non-linear parameter estimation procedures. As a consequence, it is generally impossible to obtain an exact characterization of the probability distribution of the parameter estimates. This in turn implies that it is extremely challenging to quantify the uncertainty associated with a certain parameter estimate. Concretely, no commonly accepted procedure exists for computing classical measures of uncertainty and statistical significance as confidence intervals or p-values. We consider here a broad class of regression problems, and propose an efficient algorithm for constructing confidence intervals and p-values.

Numerous datasets ranging from group memberships within social networks to purchase histories on e-commerce sites are represented by binary matrices. While this data is often either proprietary or sensitive, aggregated data, notably row and column marginals, is often viewed as much less sensitive, and may be furnished for analysis. Here, we investigate how these data can be exploited to make inferences about the underlying matrix H. Instead of assuming a generative model for H, we view the input marginals as constraints on the dataspace of possible realizations of H and compute the probability density function of particular entries H(i, j) of interest. We do this for all the cells of H simultaneously, without generating realizations, but rather via implicitly sampling the datasets that satisfy the input marginals. The end result is an efficient algorithm with asymptotic running time the same as that required by standard sampling techniques to generate a single dataset from the same dataspace. Our experimental evaluation demonstrates the efficiency and the efficacy of our framework in multiple settings.

This paper proposes a new model for link prediction in knowledge bases. By learning a non-linear scoring function based on tensor and matrix operators for representing relations and word embeddings for representing entities, this approach can outperform previous work on data from two knowledge bases: Wordnet and Freebase. Clarity: The paper is very clear and nicely written. I would only reduce the use of the term "reasoning", which is not obviously justified in this context and can be misleading. It seems that link prediction is more performed using (well-trained) similarity measures than by relying on (formal) reasoning. Originality: While building on previous work (cited), the model architecture is original and the use of word embeddings (learned on text corpora) is also brand new.

Learning the joint dependence of discrete variables is a fundamental problem in machine learning, with many applications including prediction, clustering and dimensionality reduction. More recently, the framework of copula modeling has gained popularity due to its modular parameterization of joint distributions. Among other properties, copulas provide a recipe for combining flexible models for univariate marginal distributions with parametric families suitable for potentially high dimensional dependence structures. More radically, the extended rank likelihood approach of Hoff (2007) bypasses learning marginal models completely when such information is ancillary to the learning task at hand as in, e.g., standard dimensionality reduction problems or copula parameter estimation. The main idea is to represent data by their observable rank statistics, ignoring any other information from the marginals. Inference is typically done in a Bayesian framework with Gaussian copulas, and it is complicated by the fact this implies sampling within a space where the number of constraints increases quadratically with the number of data points. The result is slow mixing when using off-the-shelf Gibbs sampling. We present an efficient algorithm based on recent advances on constrained Hamiltonian Markov chain Monte Carlo that is simple to implement and does not require paying for a quadratic cost in sample size.

The paper provides a simplified perspective on EDML and illustrated the benefits of such a simplified view. First, existing results about EDML are much easier to proce. Second, and most important, this new formulation provides a systematic procedure for deriving new instances of EDML for other models. This is illustrated for Markov networks. The derived EDML is shown to be competitive to existing learning approaches.

We are grateful to the reviewers for their careful reading of our manuscript and their suggestions. KCSD is a complex object to study and an important aspect of our contribution is to estimate its properties with good asymptotic result under mild conditions. We introduce an unbiased estimate and a statistical test using fast algorithms which are easily applicable to many datasets. Our results cannot be found elsewhere and further work can build on our mathematical treatment to assess statistical properties of kernel methods for stationary data. Most importantly, this contribution aims at bringing results from kernel methods to communities that are in important need for general time series analysis techniques with good statistical properties. Measures describing the dependency structure of the data without model assumptions, such as the linear cross-spectrum, became standard in applications such as Neurophysiology.

Many applications require the analysis of complex interactions between time series. These interactions can be non-linear and involve vector valued as well as complex data structures such as graphs or strings. Here we provide a general framework for the statistical analysis of these dependencies when random variables are sampled from stationary time-series of arbitrary objects. To achieve this goal, we study the properties of the Kernel Cross-Spectral Density (KCSD) operator induced by positive definite kernels on arbitrary input domains. This framework enables us to develop an independence test between time series, as well as a similarity measure to compare different types of coupling. The performance of our test is compared to the HSIC test using i.i.d.