Statistics meets Optimization: Computational guarantees for statistical learning algorithms

Fan Yang

Abstract

Modern technological advances have prompted massive scale data collection in manymodern fields such as artificial intelligence, and traditional sciences alike. This has led toan increasing need for scalable machine learning algorithms and statistical methods to drawconclusions about the world. In all data-driven procedures, the data scientist faces thefollowing fundamental questions: How should I design the learning algorithm and how longshould I run it? Which samples should I collect for training and how many are sufficient togeneralize conclusions to unseen data? These questions relate to statistical and computational properties of both the data and the algorithm. This thesis explores their role in the areas of non-convex optimization, non-parametric estimation, active learning and multiple testing.In the first part, we provide insights of different flavor concerning theinterplay between statistical and computational properties of first-order type methods oncommon estimation procedures. The expectation-maximization (EM) algorithm estimatesparameters of a latent variable model by running a first-order type method on a non-convexlandscape. We identify and characterize a general class of Hidden Markov Models for whichlinear convergence of EM to a statistically optimal point is provable for a large initializationradius. For non-parametric estimation problems, functional gradient descent type (alsocalled boosting) algorithms are used to estimate the best fit in infinite dimensional functionspaces. We develop a new proof technique showing that early stopping the algorithm insteadmay also yield an optimal estimator without explicit regularization. In fact, the samekey quantities (localized complexities) are underlying both traditional penalty-based andalgorithmic regularization.In the second part of the thesis, we explore how data collected adaptively with a constantlyupdated estimation can lead to signifcant reduction in sample complexity for multiplehypothesis testing problems. In particular, we show how adaptive strategies can be usedto simultaneously control the false discovery rate over multiple tests and return the bestalternative (among many) for each test with optimal sample complexity in an online manner.
BibTeX
@inproceedings{yang2018statistics,
  author = {Fan Yang},
  title = {{Statistics meets Optimization: Computational guarantees for statistical learning algorithms}},
  booktitle = {eScholarship},
  year = {2018},
}

Loading related content...

Figure