Provably efficient methods for large-scale learning

The scale of machine learning problems grows rapidly in recent years and calls for efficient methods. In this dissertation, we propose simple and efficient methods for various large-scale learning problems. We start with a standard supervised learning problem of solving quadratic regression. In Chapter 2, we show that by utilizing the quadratic structure and a novel gradient estimation algorithm, we can solve sparse quadratic regression with sub-quadratic time complexity and near-optimal sample complexity. We then move to online learning problems. In Chapter 3, we identify a weak assumption and theoretically prove that the standard UCB algorithm efficiently learns from inconsistent human preferences with nearly optimal regret; in Chapter 4 we propose an approximate maximum inner product search data structure for adaptive queries and present two efficient algorithms that achieve sublinear time complexity for linear bandits, which is especially desirable for extremely large and slowly changing action sets. In Chapter 5, we study how to efficiently use privileged features with deep learning models. We present an efficient learning algorithm to exploit privileged features that are not available during testing time. We conduct comprehensive empirical evaluations and present rigorous analysis for linear models to build theoretical insights. It provides a general algorithmic paradigm that can be integrated with many other machine learning methods.