Machine Learning Algorithms Workshop: Logarithmic Time Online Multiclass Prediction & Log-Concave Sampling with SGD

Logarithmic Time Online Multiclass prediction: We study the problem of multiclass classification with an extremely large number of classes (k), with the goal of obtaining train and test time complexity logarithmic in the number of classes. We develop top-down tree construction approaches for constructing logarithmic depth trees. On the theoretical front, we formulate a new objective function, which is optimized at each node of the tree and creates dynamic partitions of the data which are both pure (in terms of class labels) and balanced. We demonstrate that under favorable conditions, we can construct logarithmic depth trees that have leaves with low label entropy. However, the objective function at the nodes is challenging to optimize computationally. We address the empirical problem with a new online decision tree construction procedure. Experiments demonstrate that this online algorithm quickly achieves improvement in test error compared to more common logarithmic training time approaches, which makes it a plausible method in computationally constrained large-k applications.

And…

Log-concave Sampling with SGD: We extend the Langevin Monte Carlo (LMC) algorithm to compactly supported measures via a projection step, akin to projected Stochastic Gradient Descent (SGD). We show that (projected) LMC allows to sample in polynomial time from a log-concave distribution with smooth potential. This gives a new Markov chain to sample from a log-concave distribution.

Speaker Details

John Langford studied Physics and Computer Science at the California Institute of Technology, earning a double bachelor’s degree in 1997, and received his Ph.D. from Carnegie Mellon University in 2002. Since then, he has worked at Yahoo!, Toyota Technological Institute, and IBM’s Watson Research Center. He is also the primary author of the popular Machine Learning weblog, hunch.net and the principle developer of Vowpal Wabbit. Previous research projects include Isomap, Captcha, Learning Reductions, Cover Trees, and Contextual Bandit learning. For more information visit http://hunch.net/~jl.

Sebastien Bubeck is a researcher with the Theory Group at MSR Redmond. He was co-chair for COLT 2013, COLT 2014, and is currently on the program committee for NIPS 2012, NIPS 2014, COLT 2013, COLT 2014, COLT 2015, ICML 2015, ALT 2013, ALT 2014. He is also on the steering committee for COLT. Currently Sebastien is especially interested in (i) the interplay between convexity and randomness in optimization, and (ii) inference problems on random graphs. His research interests include machine learning, combinatorial statistics/analysis of networks, multi-armed bandits, online learning, stochastic optimization and convex optimization.

Date:
Speakers:
John Langford and Sebastien Bubeck
Affiliation:
MSR Redmond, Microsoft