Spectral method and regularized MLE are both optimal for top-\(K\) ranking

DOI10.1214/18-AOS1745zbMath1425.62038arXiv1707.09971WikidataQ90617980 ScholiaQ90617980MaRDI QIDQ2313284

Yuxin Chen, Kaizheng Wang, Cong Ma, Jianqing Fan

Publication date: 18 July 2019

Published in: The Annals of Statistics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.09971

zbMATH Keywords

spectral methodpairwise comparisonsreversible Markov chainsentrywise perturbationleave-one-out analysisregularized MLEtop-\(K\) ranking

Mathematics Subject Classification ID

Inference from stochastic processes and spectral analysis (62M15) Statistical ranking and selection procedures (62F07) Statistical aspects of information-theoretic topics (62B10)

Related Items (26)

Iterative Collaborative Filtering for Sparse Matrix Estimation ⋮ Partial recovery for top-\(k\) ranking: optimality of MLE and suboptimality of the spectral method ⋮ Optimal full ranking from pairwise comparisons ⋮ Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods ⋮ Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices ⋮ Nonconvex Low-Rank Tensor Completion from Noisy Data ⋮ Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method ⋮ Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution ⋮ A low-rank spectral method for learning Markov models ⋮ Partition–Mallows Model and Its Inference for Rank Aggregation ⋮ Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs ⋮ Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval ⋮ Optimal permutation estimation in crowdsourcing problems ⋮ A General Pairwise Comparison Model for Extremely Sparse Networks ⋮ Entrywise eigenvector analysis of random matrices with low expected rank ⋮ PALM: patient-centered treatment ranking via large-scale multivariate network meta-analysis ⋮ A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization ⋮ Top-\(k\) list aggregation: mathematical formulations and polyhedral comparisons ⋮ Localization in 1D non-parametric latent space models from pairwise affinities ⋮ Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization ⋮ Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees ⋮ Spectral method and regularized MLE are both optimal for top-\(K\) ranking ⋮ Community detection on mixture multilayer networks via regularized tensor decomposition ⋮ Antithetic and Monte Carlo kernel estimators for partial rankings ⋮ An \({\ell_p}\) theory of PCA and spectral clustering ⋮ Time-homogeneous top-K ranking using tensor decompositions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotics and concentration bounds for bilinear forms of spectral projectors of sample covariance
• Statistical ranking and combinatorial Hodge theory
• Spectral clustering and the high-dimensional stochastic blockmodel
• On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators
• MM algorithms for generalized Bradley-Terry models.
• Debiasing the Lasso: optimal sample size for Gaussian designs
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Worst-case versus average-case design for estimation from partial pairwise comparisons
• Entrywise eigenvector analysis of random matrices with low expected rank
• The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square
• Active ranking from pairwise comparisons and when parametric assumptions do not help
• Spectral method and regularized MLE are both optimal for top-\(K\) ranking
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Perturbation of Linear Forms of Singular Vectors Under Gaussian Noise
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
• Solution of a Ranking Problem from Binary Comparisons
• Simple, Robust and Optimal Ranking from Pairwise Comparisons
• An $\ell_{\infty}$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation
• Competitive analysis of the top-K ranking problem
• The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
• Near-Optimal Bounds for Phase Synchronization
• Adversarial Top- $K$ Ranking
• An Introduction to Matrix Concentration Inequalities
• The Rotation of Eigenvectors by a Perturbation. III
• Rank Centrality: Ranking from Pairwise Comparisons

This page was built for publication: Spectral method and regularized MLE are both optimal for top-\(K\) ranking