Sparse Random Feature Algorithm as Coordinate Descent in Hilbert Space
Date Issued
2014
Date
2014
Author(s)
Lin, Ting-Wei
Abstract
In this paper, we propose a Sparse Random Feature Algorithm as Coordinate Descent in Hilbert Space, which learns a sparse non-linear predictor by minimizing an ℓ1-regularized objective function over the Hilbert Space induced from kernel function. By interpreting the algorithm as Randomized Coordinate Descent in the infinite-dimensional space, we show the proposed approach converges to a solution comparable within ϵ-precision to exact kernel method by drawing O(1/ϵ) number of random features, contrasted to the O(1/ϵ^2)-type convergence achieved by Monte-Carlo analysis in current Random Feature literature. In our experiments, the Sparse Random Feature algorithm obtains sparse solution that requires less memory and prediction time while maintains comparable performance on tasks of regression and classification. In the meantime, as an approximate solver for infinite-dimensional ℓ1-regularized problem, the randomized approach converges to better solution than Boosting approach when the greedy step of Boosting cannot be performed exactly.
Subjects
隨機特徵
核心逼近
支持向量機
隨機座標下降法
正規化
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-103-R01944011-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):d9b0e5f4796a9b9d87a84ee57a92b75c