In this talk, we introduce an optimization-based framework called Generalized Low Rank Models designed to uncover structure in big messy data sets. These models generalize many well known techniques in data analysis, such as (standard or robust) PCA, nonnegative matrix factorization, matrix completion, and k-means. We examine their effectiveness at capturing the structure present in datasets drawn from social science and medical informatics applications. Strikingly, these models can perform more than 30% better than state of the art methods for imputing missing data in social science surveys. The resulting optimization problems are nonconvex, nonsmooth, and often have millions or even billions of parameters. We'll discuss efficient optimization techniques for these problems, and ways of exploiting parallelism to improve runtime, including a fast asynchronous parallel method with provable convergence and a linear speedup.