A central theme of large-scale convex optimization is the search for ``optimal methods.’’ These are the algorithms whose convergence guarantees match complexity theoretic lower bounds for a given problem class. Standard optimal methods are notoriously unintuitive. I will begin by describing a new transparent optimal method for minimizing smooth convex functions that is rooted in elementary cutting plane ideas. Despite the successes of convex techniques, recent years have seen a resurgence of interest in nonconvex and nonsmooth optimization. In such settings, it is essential to exploit problem structure to make progress. One typical example of favorable structure occurs when minimizing a composition of a finite convex function with a smooth map. In the second part of the talk, I will discuss various aspects of this problem class, focusing on both worst-case and average case guarantees. The phase retrieval problem will illustrate the algorithms and theory. This is joint work work with D. Davis (Cornell), M. Fazel (Washington), A.S. Lewis (Cornell), C. Paquette (Lehigh), and S. Roy (Washington).