Learning with ℓ₁-Regularizer Based on Markov Resampling

Learning with ℓ₁-regularizer has brought about a great deal of research in learning theory community. Previous known results for the learning with ℓ₁-regularizer are based on the assumption that samples are independent and identically distributed (i.i.d.), and the best obtained learning rate for the ℓ₁-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 ℓ₁-regularizer (ℓ₁-LSR) based on uniformly ergodic Markov chain (u.e.M.c) samples. On the theoretical side, we prove that the learning rate of ℓ₁-LSR for u.e.M.c samples ℓ₁-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 ℓ₁-LSR(M) improves on the ℓ₁-LSR(i.i.d.) in generalization error at the low cost of u.e.M.c resampling.