History

Please fill in your query. A complete syntax description you will find on the General Help page.
Efficient and numerically stable sparse learning. (English)
Balcázar, José Luis (ed.) et al., Machine learning and knowledge discovery in databases. European conference, ECML PKDD 2010, Barcelona, Spain, September 20‒24, 2010. Proceedings, Part III. Berlin: Springer (ISBN 978-3-642-15938-1/pbk). Lecture Notes in Computer Science 6323. Lecture Notes in Artificial Intelligence, 483-498 (2010).
Summary: We consider the problem of numerical stability and model density growth when training a sparse linear model from massive data. We focus on scalable algorithms that optimize certain loss function using gradient descent, with either $\ell _{0}$ or $\ell _{1}$ regularization. We observed numerical stability problems in several existing methods, leading to divergence and low accuracy. In addition, these methods typically have weak controls over sparsity, such that model density grows faster than necessary. We propose a framework to address the above problems. First, the update rule is numerically stable with convergence guarantee and results in more reasonable models. Second, besides $\ell _{1}$ regularization, it exploits the sparsity of data distribution and achieves a higher degree of sparsity with a PAC generalization error bound. Lastly, it is parallelizable and suitable for training large margin classifiers on huge datasets. Experiments show that the proposed method converges consistently and outperforms other baselines using 10\% of features by as much as 6\% reduction in error rate on average. Datasets and software are available from the authors.