This paper is concerned with the problem of top- K ranking from pairwise comparisons. Given a collection of K items and a few pairwise comparisons across them, one wishes to identify the set of K items that receive the highest ranks. To tackle this problem, we adopt the logistic parametric model---the Bradley-Terry-Luce model, where each item is assigned a latent preference score, and where the outcome of each pairwise comparison depends solely on the relative scores of the two items involved. Recent works have made significant progress towards characterizing the performance (eg the mean square error for estimating the scores) of several classical methods, including the spectral method and the maximum likelihood estimator (MLE). However, where they stand regarding top- K ranking remains unsettled.

We present a novel variation of the well-known infomax algorithm of blind source separation. Under natural gradient descent, the infomax algorithm converges to a stationary point of a limiting ordinary differential equation. However, due to the presence of saddle points or local minima of the corresponding likelihood function, the algorithm may be trapped around these bad stationary points for a long time, especially if the initial data are near them. To speed up convergence, we propose to add a sequence of random perturbations to the infomax algorithm to shake the iterating sequence so that it is captured by a path descending to a more stable stationary point. We analyze the convergence of the randomly perturbed algorithm, and illustrate its fast convergence through numerical examples on blind demixing of stochastic signals. The examples have analytical structures so that saddle points or local minima of the likelihood functions are explicit. The results may have implications for online learning algorithms in dissimilar problems.

Maximum likelihood ratio theory contributes tremendous success to parametric inferences, due to the fundamental theory of Wilks (1938). Yet, there is no general applicable approach for nonparametric inferences based on function estimation. Maximum likelihood ratio test statistics in general may not exist in nonparametric function estimation setting. Even if they exist, they are hard to nd and can not be optimal as shown in this paper. In this paper, we introduce the sieve likelihood statistics to overcome the drawbacks of nonparametric maximum likelihood ratio statistics. New Wilks' phenomenon is unveiled. We demonstrate that the sieve likelihood statistics are asymptotically distribution free and follow 2-distributions under null hypotheses for a number of useful hypotheses and a variety of useful models including Gaussian white noise models, nonparametric regression models, varying coefficient models and generalized varying coefficient models. We further demonstrate that sieve likelihood ratio statistics are asymptotically optimal in the sense that they achieve optimal rates of convergence given by Ingster (1993). They can even be adaptively optimal in the sense of Spokoiny (1996) by using a simple choice of adaptive smoothing parameter. Our work indicates that the sieve likelihood ratio statistics are indeed general and powerful for nonparametric inferences based on function estimation.

Measuring conditional dependence is an important topic in statistics with broad applications including graphical models. Under a factor model setting, a new conditional dependence measure based on projection is proposed. The corresponding conditional independence test is developed with the asymptotic null distribution unveiled where the number of factors could be high-dimensional. It is also shown that the new test has control over the asymptotic significance level and can be calculated efficiently. A generic method for building dependency graphs without Gaussian assumption using the new test is elaborated. Numerical results and real data analysis show the superiority of the new method.

In this note we include a correction for Equation (19) on page 840 which is a step in the proof of Theorem 4 of Fan et al.(2014). There is no change in the statement of Theorem 4, and the rest of the proof stays unchanged. Equation (19) on page 840 should be corrected to as follows: We apply the coordinatewise mean-value theorem with respect to each coordinate of (ie, j) to obtain that