In the first part, I will consider the problem of minimizing a finite sum
of smooth functions. This is a ubiquitous computational problem in
statistics, as it frequently arises in various maximum likelihood and
regularized maximum likelihood frameworks. I will describe the stochastic
average gradient algorithm which, despite over 60 years of work on
stochastic gradient algorithms, is the first method to achieve the low
iteration cost of stochastic gradient methods while achieving a linear
convergence rate as in deterministic gradient methods that process the
entire dataset on every iteration.
In the second part, I will consider the even-more-specialized case where we
have a linearly-parameterized model (such as linear least squares or
logistic regression). I will talk about how coordinate descent methods,
though a terrible idea for minimizing general functions, are theoretically
and empirically well-suited to solving such problems. I will also discuss
how we can design clever coordinate selection rules, that are much more
efficient than the classic cyclic and randomized choices.
*Bio: * Mark Schmidt has been an assistant professor in the Department of
Computer Science at the University of British Columbia since 2014. His
research focuses on developing faster algorithms for large-scale machine
learning, with an emphasis on methods with provable convergence rates and
that can be applied to structured prediction problems. From 2011 through
2013 he worked at the École normale supérieure in Paris on inexact and
stochastic convex optimization methods. He finished his M.Sc. in 2005 at
the University of Alberta working as part of the Brain Tumor Analysis
Project, and his Ph.D. in 2010 at the University of British Columbia
working with Kevin Murphy on graphical model structure learning with
L1-regularization. He has also worked at Siemens Medical Solutions on heart
motion abnormality detection, with Michael Friedlander in the Scientific
Computing Laboratory at the University of British Columbia on
semi-stochastic optimization methods, and with Anoop Sarkar at Simon Fraser
University on large-scale training of natural language models.