Guaranteed and Efficient Learning Algorithms for Ranking and Matrix Factorization

In this dissertation, two central problems in computer science are considered:(1) ranking n items from pairwise comparisons focussing on - (1a) handling adversarial noise (1b) incorporating feature information(2) robust matrix factorization algorithms focussing on - (2a) space-efficient computation (2b) using feature informationMotivated by several open theoretical and practical questions, novel solutions to the above problems are explored in detail; to be specific, the contributions are summarized below:(1) Ranking:(Part-1a) In the presence of adversarial noise, many popular ranking algorithms, such as maximum likelihood and rank centrality, for estimating standard models, fail to work well. Robustifying many existing models such as the binary choice models, an algorithm is devised to provably recover an epsilon-accurate ranking with high probability while allowing as large as O(n) grossly corrupted comparison results per item.(Part-1b) Typically, items have associated features. Subsuming several models including the classic Bradley-Terry-Luce and Thurstone models, a feature-based low-rank model is proposed and characterized. In learning this model, the O(n log n) sorting barrier is provably improved upon due to the proposed sample-efficient polynomial time algorithm that systematically uses features and feature correlations. Via empirical benchmarking, it is shown that the proposed approach consistently outperforms the state-of-the-art algorithms that do not use feature information.(2) Matrix factorization:(Part-2a) While principal component analysis and its variants are very well-studied, existing algorithms are either space-efficient or noise-tolerant; in contrast, incorporating both these aspects in solving eigen-problems, a space-efficient noise-tolerant algorithm with finite sample guarantees is developed and analyzed in the framework of the perturbed spiked covariance model under weaker assumptions than previous works; a key differentiating aspect from previous works is that the algorithm is streaming. Moreover, the derived computational and statistical guarantees are near optimal (up to logarithmic factors).(Part-2b) While robust subspace identification methods, both convex and non-convex, are well-studied, they are often oblivious to utilizing feature information that is available in practice; in contrast to existing (feature-oblivious) convex and non-convex approaches, a simple iterative method with a fast (linear) convergence property is proposed and studied - a key aspect that differentiates this from previous works is how side information is incorporated in achieving better robust subspace recovery