Large-scale data sets are now ubiquitous throughout engineering and science, and present a number of interesting challenges at the interface between statistics and optimization. In this talk, we discuss the use of randomized dimensionality reduction techniques, also known as sketching, for obtaining fast but approximate solutions to large-scale convex programs. Using informationtheoretic techniques, we first reveal a surprising deficiency of the most widely used sketching technique. We then show how a simple iterative variant leads to a much faster algorithm, and one which adapts to the intrinsic dimension of the solution space. Moreover, we show how it generalizes naturally to a randomized version of the Newton algorithm with provable guarantees.