Book chapter
Sparse Learning for Large-Scale and High-Dimensional Data: A Randomized Convex-Concave Optimization Approach
Algorithmic Learning Theory, pp.83-97
Lecture Notes in Computer Science, Springer International Publishing
09/21/2016
DOI: 10.1007/978-3-319-46379-7_6
Abstract
In this paper, we develop a randomized algorithm and theory for learning a sparse model from large-scale and high-dimensional data, which is usually formulated as an empirical risk minimization problem with a sparsity-inducing regularizer. Under the assumption that there exists a (approximately) sparse solution with high classification accuracy, we argue that the dual solution is also sparse or approximately sparse. The fact that both primal and dual solutions are sparse motivates us to develop a randomized approach for a general convex-concave optimization problem. Specifically, the proposed approach combines the strength of random projection with that of sparse learning: it utilizes random projection to reduce the dimensionality, and introduces \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\ell _1$$\end{document}-norm regularization to alleviate the approximation error caused by random projection. Theoretical analysis shows that under favored conditions, the randomized algorithm can accurately recover the optimal solutions to the convex-concave optimization problem (i.e., recover both the primal and dual solutions).
Details
- Title: Subtitle
- Sparse Learning for Large-Scale and High-Dimensional Data: A Randomized Convex-Concave Optimization Approach
- Creators
- Lijun Zhang - Nanjing UniversityTianbao Yang - University of IowaRong Jin - Alibaba GroupZhi-Hua Zhou - Nanjing University
- Resource Type
- Book chapter
- Publication Details
- Algorithmic Learning Theory, pp.83-97
- Publisher
- Springer International Publishing; Cham
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-319-46379-7_6
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 09/21/2016
- Academic Unit
- Computer Science
- Record Identifier
- 9984259408202771
Metrics
50 Record Views