Optimization methods in machine learning: theory and applications

We look at the integral role played by convex optimization in various machine learning problems. Over the last few years there has been a lot of machine learning problems which have a (non)smooth convex optimization at its core. These problems generally call for fast first order iterative methods as obtaining the exact minimum is often impossible and second order methods or higher become prohibitively expensive even on moderately sized datasets. We look at a few such optimization problems that arise in different contexts and show that a class of smoothing strategies due to Nesterov can be applied to these seemingly very different problems to obtain theoretically faster rates of convergence than existing methods. Our experimental results validate the speed and efficacy of our methods and scale significantly well over a broad range of datasets. This thesis also explores an often used but understudied optimization algorithm, namely the cyclic coordinate descent method, and provides a novel theoretical analysis of the first non-asymptotic convergence rates of cyclic coordinate descent under certain assumptions. This work also sheds light on some of the recent advances in online convex optimization to minimize regret in the presence of smooth unknown functions. We also look at online learning from the point of view of stability and provide a new integral framework which encompasses the regret analysis of all existing algorithms as specific cases of this framework. We investigate related methods of analysis and the central role played by optimization in all these seemingly different but connected domains of machine learning research.