Inference and Learning: Computational Difficulty and Efficiency / Tengyuan Liang.

Format:

Book

Thesis/Dissertation

Author/Creator:

Liang, Tengyuan, author.

Contributor:

Rakhlin, Alexander, degree supervisor.

Cai, Tony T., degree supervisor.

Mossel, E. (Elchanan), degree committee member.

Low, Mark G., degree committee member.

University of Pennsylvania. Statistics, degree granting institution.

Language:

English

Subjects (All):

Statistics--Penn dissertations.

Penn dissertations--Statistics.

Local Subjects:

Statistics--Penn dissertations.

Penn dissertations--Statistics.

Genre:

Academic theses.

Physical Description:

1 online resource (240 pages)

Contained In:

Dissertation Abstracts International 78-12B(E).

Place of Publication:

[Philadelphia, Pennsylvania]: University of Pennsylvania ; Ann Arbor : ProQuest Dissertations & Theses, 2017.

Language Note:

English

System Details:

Mode of access: World Wide Web.

text file

Summary:

In this thesis, we mainly investigate two collections of problems: statistical network inference and model selection in regression. The common feature shared by these two types of problems is that they typically exhibit an interesting phenomenon in terms of computational difficulty and efficiency. For statistical network inference, our goal is to infer the network structure based on a noisy observation of the network. Statistically, we model the network as generated from the structural information with the presence of noise, for example, planted submatrix model (for bipartite weighted graph), stochastic block model, and Watts-Strogatz model. As the relative amount of "signal-to-noise" varies, the problems exhibit different stages of computational difficulty. On the theoretical side, we investigate these stages through characterizing the transition thresholds on the "signal-to-noise" ratio, for the aforementioned models. On the methodological side, we provide new computationally efficient procedures to reconstruct the network structure for each model. For model selection in regression, our goal is to learn a "good" model based on a certain model class from the observed data sequences (feature and response pairs), when the model can be misspecified. More concretely, we study two model selection problems: to learn from general classes of functions based on i.i.d. data with minimal assumptions, and to select from the sparse linear model class based on possibly adversarially chosen data in a sequential fashion. We develop new theoretical and algorithmic tools beyond empirical risk minimization to study these problems from a learning theory point of view.

Notes:

Source: Dissertation Abstracts International, Volume: 78-12(E), Section: B.

Advisors: Tony T. Cai; Alexander Rakhlin; Committee members: Mark G. Low; Elchanan Mossel.

Department: Statistics.

Ph.D. University of Pennsylvania 2017.

Local Notes:

School code: 0175

ISBN:

9780355095784

Access Restriction:

Restricted for use by site license.