UCLA

Methods that analyze large-scale data and make predictions based on data are increasingly prevalent in a variety of industries. These methods are often complex, rely on a variety of subroutines and are applied in settings for which they lack theoretical guarantees. Additionally, storage requirements and computational speed are crucial to the feasibility of methods at large-scales.Here, we derive theoretical guarantees for machine learning and data analytic subroutines such as matrix completion and optimization. We also extend the development of classification methods for binary, compressed data. More specifically, we consider the following. We analyze a regularized variant of the standard nuclear-norm minimization problem for low-rank matrix completion for settings in which smaller entries are more likely to be missing. We derive convergence guarantees for a gradient descent method for solving support vector machines and compare the derived convergence guarantees to those of existing strategies. We analyze adaptive sampling strategies for sketch-and-project methods for solving large-scale least- squares problems. We develop hierarchical and iterative extensions to the simple classification method for binary data introduced in [NSW17].