"Interior point algorithms and a dramatic growth in computing power have revolutionized optimization inthe last two decades. Highly nonlinear problems which were previously thought intractable are nowroutinely solved at reasonable scales. Semidefinite programs (i.e. linear programs on the cone of positivesemidefinite matrices) are a perfect example of this trend: reasonably large, highly nonlinear but convexeigenvalue optimization problems are now solved efficiently by reliable numerical packages. This in turnmeans that a wide array of new applications for semidefinite programming have been discovered,mimicking the early development of linear programming. To cite only a few examples, semidefiniteprograms have been used to solve collaborative filtering problems (e.g. make personalized movierecommendations), approximate the solution of combinatorial programs, optimize the mixing rate ofMarkov chains over networks, infer dependence patterns from multivariate time series or produce optimalkernels in classification problems.These new applications also come with radically different algorithmic requirements. While interior pointmethods solve relatively small problems with a high precision, most recent applications of semidefiniteprogramming in statistical learning for example form very large-scale problems with comparatively lowprecision targets, programs for which current algorithms cannot form even a single iteration. Thisproposal seeks to break this limit on problem size by deriving reliable first-order algorithms for solvinglarge-scale semidefinite programs with a significantly lower cost per iteration, using for examplesubsampling techniques to considerably reduce the cost of forming gradients.Beyond these algorithmic challenges, the proposed research will focus heavily on applications of convexprogramming to statistical learning and signal processing theory where optimization and duality resultsquantify the statistical performance of coding or variable selection algorithms for example. Finally,another central goal of this work will be to produce efficient, customized algorithms for some keyproblems arising in machine learning and statistics."