Conference proceeding
Theory of Dual-sparse Regularized Randomized Reduction
Proceedings of Machine Learning Research, Vol.37, pp.305-314
International Conference on Machine Learning, 32nd (Lille, France, 07/2015)
07/2015
Abstract
In this paper, we study randomized reduction methods, which reduce high-dimensional features into low-dimensional space by randomized methods (e.g., random projection, random hashing), for large-scale high-dimensional classification. Previous theoretical results on randomized reduction methods hinge on strong assumptions about the data, e.g., low rank of the data matrix or a large separable margin of classification, which hinder their in broad domains. To address these limitations, we propose dual-sparse regularized randomized reduction methods that introduce a sparse regularizer into the reduced dual problem. Under a mild condition that the original dual solution is a (nearly) sparse vector, we show that the resulting dual solution is close to the original dual solution and concentrates on its support set. In numerical experiments, we present an empirical study to support the analysis and we also present a novel application of the dual-sparse randomized reduction methods to reducing the communication cost of distributed learning from large-scale high-dimensional data.
Details
- Title: Subtitle
- Theory of Dual-sparse Regularized Randomized Reduction
- Creators
- Tianbao YangLijun ZhangRong JinShenghuo Zhu
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of Machine Learning Research, Vol.37, pp.305-314
- Conference
- International Conference on Machine Learning, 32nd (Lille, France, 07/2015)
- Language
- English
- Date published
- 07/2015
- Academic Unit
- Computer Science
- Record Identifier
- 9984259427602771
Metrics
9 Record Views