Timezone: »
Given their pervasive use, social media, such as Twitter, have become a leading source of breaking news. A key task in the automated identification of such news is the detection of novel documents from a voluminous stream of text documents in a scalable manner. Motivated by this challenge, we introduce the problem of online L1-dictionary learning where unlike traditional dictionary learning, which uses squared loss, the L1-penalty is used for measuring the reconstruction error. We present an efficient online algorithm for this problem based on alternating directions method of multipliers, and establish a sublinear regret bound for this algorithm. Empirical results on news-stream and Twitter data, shows that this online L1-dictionary learning algorithm for novel document detection gives more than an order of magnitude speedup over the previously known batch algorithm, without any significant loss in quality of results. Our algorithm for online L1-dictionary learning could be of independent interest.
Author Information
Shiva Kasiviswanathan (Amazon)
Huahua Wang (University of Minnesota, Twin Cites)
Arindam Banerjee (Univ. of Minnesota)
Prem Melville (Millennium Management)
More from the Same Authors
-
2021 : Reconstructing Test Labels from Noisy Loss Scores (Extended Abstract) »
Abhinav Aggarwal · Shiva Kasiviswanathan · Zekun Xu · Oluwaseyi Feyisetan · Nathanael Teissier -
2022 : Diffusion Prior for Online Decision Making: A Case Study of Thompson Sampling »
Yu-Guan Hsieh · Shiva Kasiviswanathan · Branislav Kveton · Patrick Blöbaum -
2022 Poster: Uplifting Bandits »
Yu-Guan Hsieh · Shiva Kasiviswanathan · Branislav Kveton -
2021 Poster: Collaborative Causal Discovery with Atomic Interventions »
Raghavendra Addanki · Shiva Kasiviswanathan -
2014 Poster: Bregman Alternating Direction Method of Multipliers »
Huahua Wang · Arindam Banerjee -
2014 Poster: Parallel Direction Method of Multipliers »
Huahua Wang · Arindam Banerjee · Zhi-Quan Luo -
2013 Poster: Large Scale Distributed Sparse Precision Estimation »
Huahua Wang · Arindam Banerjee · Cho-Jui Hsieh · Pradeep Ravikumar · Inderjit Dhillon -
2012 Poster: A Divide-and-Conquer Method for Sparse Inverse Covariance Estimation »
Cho-Jui Hsieh · Inderjit Dhillon · Pradeep Ravikumar · Arindam Banerjee