Statistical Spectral Algorithms for Learning From Discrete Data / Manh Duc Nguyen.

Format:

Book

Thesis/Dissertation

Author/Creator:

Nguyễn, Mạnh Đức, author.

Contributor:

University of Pennsylvania. Computer and Information Science, degree granting institution.

Language:

English

Subjects (All):

Computer science.

Statistics.

Information science.

Computer and Information Science--Penn dissertations.

Penn dissertations--Computer and Information Science.

Local Subjects:

Computer science.

Statistics.

Information science.

Computer and Information Science--Penn dissertations.

Penn dissertations--Computer and Information Science.

Physical Description:

1 online resource (227 pages)

Contained In:

Dissertations Abstracts International 85-12A.

Place of Publication:

[Philadelphia, Pennsylvania] : University of Pennsylvania, 2022.

Ann Arbor : ProQuest Dissertations & Theses, 2024

Language Note:

English

Summary:

In recent decades, the interaction between computer systems and human users has generated a substantial volume of data. A significant portion of this data takes on a discrete form. Notable examples include choice data where a user selects an item from a list, binary response data where users vote either yes or no on an item, and ranking data where users provide a complete ordering of items based on preference. The development of efficient, robust, and accurate algorithms tailored to handle discrete data has become a focal point of interest across various applications, including recommendation systems, the social sciences, and psychometrics, among others.The present thesis contributes to this dynamic and evolving field. We focus on a class of efficient and powerful statistical algorithms known as spectral algorithms. We introduce novel, efficient and provably accurate spectral algorithms, and analyse the theoretical performance guarantees of classical spectral algorithms when applied to discrete data.For binary and ordered response data, we design novel spectral algorithms that are not only provably accurate but, under reasonable assumptions, also achieve the optimal sample complexity. This is particularly significant for the Rasch model, a fundamental model in psychometrics. Beyond binary response data, we introduce a generalized spectral algorithm designed to yield precise estimates under the Partial Credits model, which extends the Rasch model to encompass discrete ordered responses and ratings data. Our proposed spectral algorithms outperform other popular algorithms in terms of both accuracy and efficiency.In the domain of ranking data, we present novel spectral algorithms that address two well known problems in computer science. Firstly, we tackle the challenge of inference under a mixture of Plackett-Luce models by introducing a novel two-step algorithm. We propose an initialization algorithm based on spectral clustering, which offers provable guarantees. Furthermore, by recognizing the connection between the M-step of the EM algorithm and Markov chain analysis, we introduce a novel EM algorithm that surpasses the accuracy and time efficiency of previously proposed algorithms in the literature. Secondly, we delve into the permutation synchronization problem, which holds a broad range of applications in computer vision. We address a subtle yet critical limitation of previously proposed spectral algorithms, thereby introducing an innovative spectral algorithm designed specifically for this problem. The resulting algorithm enjoys information-theoretic optimal guarantee and performs significantly better than the previous approaches.

Notes:

Source: Dissertations Abstracts International, Volume: 85-12, Section: A.

Advisors: Zhang, Anderson; Committee members: Chen, Yuxin; Gao, Chao; Hassani, Hamed; Khanna, Sanjeev.

Department: Computer and Information Science.

Ph.D. University of Pennsylvania 2024.

Local Notes:

School code: 0175

ISBN:

9798382830148

Access Restriction:

Restricted for use by site license.