Learning With $\ell _{1}$ -Regularizer Based on Markov Resampling

Tieliang Gong, Bin Zou, Zongben XuIEEE Trans. Cybernetics 2015 · DOI

Abstract

Learning with l1 -regularizer has brought about a great deal of research in learning theory community. Previous known results for the learning with l1 -regularizer are based on the assumption that samples are independent and identically distributed (i.i.d.), and the best obtained learning rate for the l1 -regularization type algorithms is O(1/√m) , where m is the samples size. This paper goes beyond the classic i.i.d. framework and investigates the generalization performance of least square regression with l1 -regularizer ( l1 -LSR) based on uniformly ergodic Markov chain (u.e.M.c) samples. On the theoretical side, we prove that the learning rate of l1 -LSR for u.e.M.c samples l1 -LSR(M) is with the order of O(1/m) , which is faster than O(1/√m) for the i.i.d. counterpart. On the practical side, we propose an algorithm based on resampling scheme to generate u.e.M.c samples. We show that the proposed l1 -LSR(M) improves on the l1 -LSR(i.i.d.) in generalization error at the low cost of u.e.M.c resampling.
BibTeX
@article{gong2015learning,
  author = {Tieliang Gong and Bin Zou and Zongben Xu},
  title = {{Learning With $\textbackslash\{\}ell \_\{1\}$ -Regularizer Based on Markov Resampling}},
  journal = {IEEE Transactions on Cybernetics},
  year = {2015},
  doi = {10.1109/tcyb.2015.2429312},
}

Loading related content...

Figure