Optimization plays a central role in modern statistics and machine learning in particular. Beyond direct applications of optimization algorithms, convex duality results and complexity theory underpin many recent developments in statistical learning (e.g. compressed sensing or matrix completion problems). Yet the link and clear empirical tradeoff between statistical performance and computational complexity has yet to be fully explained, which are crucial in most domains, in particular safety/health critical ones.



