Why ADAGRAD Fails for Online Topic Modeling

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 446–451 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Why ADAGRAD Fails for Online Topic Modeling You Lu Computer Science (CS) University of Colorado Boulder Boulder, CO you.lu@colorado.edu Jeffrey Lund Computer Science (CS) Brigham Young University Provo, UT jefflund@byu.edu Jordan Boyd-Graber CS, iSchool, LSC, and UMIACS University of Maryland College Park, MD jbg@umiacs.umd.edu Abstract Online topic modeling, i.e., topic modeling with stochastic variational inference, is a powerful and efficient technique for ana- lyzing large datasets, and ADAGRAD is a widely-used technique for tuning learning rates during online gradient optimization. However, these two techniques do not work well together. We show that this is because ADAGRAD uses accumulation of previous gradients as the learning rates’ denomina- tors. For online topic modeling, the mag- nitude of gradients is very large. It causes learning rates to shrink very quickly, so the parameters cannot fully converge until the training ends. Probabilistic topic models (Blei, 2012) are pop- ular algorithms for uncovering hidden thematic structure in text. They have been widely used to help people understand and navigate document collections (Blei et al., 2003), multilingual collec- tions (Hu et al., 2014), images (Chong et al., 2009), networks (Chang and Blei, 2009; Yang et al., 2016), etc. Probabilistic topic modeling usually requires computing a posterior distribution over thousands or millions of latent variables, which is often in- tractable. Variational inference (Blei et al., 2016, VI) approximates posterior distributions. Stochas- tic variational inference (Hoffman et al., 2013, SVI) is its natural online extension and enables the anal- ysis of large datasets. Online topic models (Hoffman et al., 2010; Bryant and Sudderth, 2012; Paisley et al., 2015) optimize the global parameters of interest using stochastic gradient ascent. At each iteration, they sample data points to estimate the gradient. In practice, the sample has only a small percentage of the vocabulary. The resulting sparse gradients hurt performance. ADAGRAD (Duchi et al., 2011) is designed for high dimensional online optimiza- tion problems and adjusts learning rates for each dimension, favoring rare features. This makes ADAGRAD well-suited for tasks with sparse gra- dients such as distributed deep networks (Dean et al., 2012), forward-backward splitting (Duchi and Singer, 2009), and regularized dual averaging methods (Xiao, 2010). Thus, it may seem reasonable to apply ADA- GRAD to optimize online topic models. However, ADAGRAD is not suitable for online topic models (Section 1). This is because to get a topic model, the training algorithm must break the symmetry be- tween parameters of words that are highly related to the topic and words that are not related to the topic. Before the algorithm converges, the magni- tude of gradients of the parameters are very large. Since ADAGRAD uses the accumulation of previous gradients as learning rates’ denominators, the learn- ing rates shrink very quickly. Thus, the algorithm cannot break the symmetry quickly. We provide solutions for this problem. Two alternative learning rate methods, i.e., ADADELTA (Zeiler, 2012) and ADAM (Kingma …

Content truncated to 500 words