Optimization Trade-offs: Variance Reduction and Statistical Dimension

This lecture covers the trade-offs between time and data in optimization, focusing on variance reduction techniques and the statistical dimension of convex cones. It discusses conditions for exact recovery in noiseless cases, statistical dimension properties, numerical results, and optimization algorithms like Gradient Descent and Stochastic Gradient Descent. The lecture also explores the impact of sample size on convergence rates and statistical errors, as well as techniques like Mini-batch SGD and SVRG for variance reduction. Convergence analysis and complexity considerations for different optimization methods are also presented.